FRQ 3

Directions: SHOW ALL YOUR WORK. REMEMBER THAT PROGRAM SEGMENTS ARE TO BE WRITTEN IN JAVA.

Notes:

Assume that the classes listed in the Java Quick Reference have been imported where appropriate.

Unless otherwise noted in the question, assume that parameters in method calls are not null and that methods are called only when their preconditions are satisfied.

In writing solutions for each question, you may use any of the accessible methods that are listed in classes defined in that question. Writing significant amounts of code that can be replaced by a call to one of these methods will not receive full credit.

A two-dimensional array of integers in which most elements are zero is called a sparse array. Because most elements have a value of zero, memory can be saved by storing only the non-zero values along with their row and column indexes. The following complete SparseArrayEntry class is used to represent non-zero elements in a sparse array. A SparseArrayEntry object cannot be modified after it has been constructed.

A 31-line code segment reads as follows. Line 1: public class Sparse Array Entry. Line 2: open brace. Line 3: forward slash, asterisk, asterisk, The row index and column index for this entry in the sparse array, asterisk, forward slash. Line 4, highlighted: private int row, semicolon. Line 5, highlighted: private int col, semicolon. Line 6: blank. Line 7: forward slash, asterisk, asterisk, The value of this entry in the sparse array, asterisk, forward slash. Line 8, highlighted: private int value, semicolon. Line 9: blank. Line 10: forward slash, asterisk, asterisk, Constructs a Sparse Array Entry object that represents a sparse array element. Line 11: asterisk, with row index r and column index c comma containing value v. Line 12: asterisk, forward slash. Line 13, highlighted: public Sparse Array Entry, open parenthesis, int r comma int c comma int v, close parenthesis. Line 14: open brace. Line 15: row equals r, semicolon. Line 16: col equals c, semicolon. Line 17: value equals v, semicolon. Line 18: close brace. Line 19: blank. Line 20: forward slash, asterisk, asterisk, Returns the row index of this sparse array element, dot, asterisk, forward slash. Line 21, highlighted: public int get Row, open parenthesis, close parenthesis. Line 22: open brace, return row, semicolon, close brace. Line 23: blank. Line 24: forward slash, asterisk, asterisk, Returns the column index of this sparse array element, dot, asterisk, forward slash. Line 25, highlighted: public int get Col, open parenthesis, close parenthesis. Line 26: open brace, return col, semicolon, close brace. Line 27: blank. Line 28: forward slash, asterisk, asterisk, Returns the value of this sparse array element, dot, asterisk, forward slash. Line 29, highlighted: public int get Value, open parenthesis, close parenthesis. Line 30: open brace, return value, semicolon, close brace. Line 31: close brace.

The SparseArray class represents a sparse array. It contains a list of SparseArrayEntry objects, each of which represents one of the non-zero elements in the array. The entries representing the non-zero elements are stored in the list in no particular order. Each non-zero element is represented by exactly one entry in the list.

A 38-line code segment reads as follows. Line 1: public class Sparse Array. Line 2: open brace. Line 3: forward slash, asterisk, asterisk, The number of rows and columns in the sparse array, dot, asterisk, forward slash. Line 4, highlighted: private int num Rows, semicolon. Line 5, highlighted: private int num Cols, semicolon. Line 6: blank. Line 7: forward slash, asterisk, asterisk, The list of entries representing the non-zero elements of the sparse array, dot, Entries are stored in the. Line 8: asterisk, list in no particular order, dot, Each non-zero element is represented by exactly one entry in the list. Line 9: asterisk, forward slash. Line 10, highlighted: private List, open angular bracket, Sparse Array Entry, close angular bracket, entries semicolon. Line 11: blank. Line 12: forward slash, asterisk, asterisk, Constructs an empty Sparse Array, dot, asterisk, forward slash. Line 13, highlighted: public Sparse Array, open parenthesis, close parenthesis. Line 14: open brace, entries equals new Array List, open angular bracket, Sparse Array Entry, close angular bracket, open parenthesis, open parenthesis, semicolon, close brace. Line 15: blank. Line 16: forward slash, asterisk, asterisk, Returns the number of rows in the sparse array, dot, asterisk, forward slash. Line 17, highlighted: public int get Num Rows, open parenthesis, close parenthesis. Line 18: open brace, return num Rows, semicolon, close brace. Line 19: blank. Line 20: forward slash, asterisk, asterisk, Returns the number of columns in the sparse array, dot, asterisk, forward slash. Line 21, highlighted: public int get Num Cols, open parenthesis, close parenthesis. Line 22: open brace, return num Cols, semicolon, close brace. Line 23: blank. Line 24: forward slash, asterisk, asterisk, Returns the value of the element at row index row and column index col in the sparse array. Line 25: asterisk, Precondition, colon, 0, less than or equal to row less than get Num Rows, open parenthesis, close parenthesis. Line 26: asterisk, 0 less than or equal to col less than get Num Cols, open parenthesis, close parenthesis. Line 27: asterisk, forward slash. Line 28, highlighted: public int get Value At, open parenthesis, int row comma int col, close parenthesis. Line 29: open brace forward slash, asterisk, to be implemented in part, open parenthesis, a close parenthesis, asterisk, forward slash, close brace. Line 30: blank. Line 31: forward slash, asterisk, asterisk, Removes the column col from the sparse array. Line 32: asterisk, Precondition, colon, 0 less than or equal to col less than get Num Cols, open parenthesis, close parenthesis. Line 33: asterisk, forward slash. Line 34, highlighted: public void remove Column, open parenthesis, int col, close parenthesis. Line 35: open brace, forward slash, asterisk, to be implemented in part, open parenthesis, b close parenthesis, asterisk, forward slash, close brace. Line 36: blank. Line 37: forward slash, forward slash, There may be instance variables comma constructors comma and methods that are not shown. Line 38: close brace.

The following table shows an example of a two-dimensional sparse array. Empty cells in the table indicate zero values.

A table is shown with five columns and six rows. From the upper left the columns are labeled 0 through 4 and the rows 0 through 5. Using these labels, the number 5 is in row 1 column 1, the number 1 is in row 2 column 0, the number negative 9 is in row 3 column 1, and the number 4 is in row 1 column 4. The rest of the entries are blank. The sample array can be represented by a SparseArray object, sparse, with the following instance variable values. The items in entries are in no particular order; one possible ordering is shown below.

An array labeled entries is shown that is a horizontal row with four boxes. In the first box it reads row 1, column 4, value 4. In the second box it reads row 2, column 0, value 1. In the third box it reads row 3, column 1, value negative 9. In the fourth box it reads row 1, column 1, value 5.

(a) Write the SparseArray method getValueAt. The method returns the value of the sparse array element at a given row and column in the sparse array. If the list entries contains an entry with the specified row and column, the value associated with the entry is returned. If there is no entry in entries corresponding to the specified row and column, 0 is returned. In the example above, the call sparse.getValueAt(3, 1) would return -9, and sparse.getValueAt(3, 3) would return 0.

Complete method getValueAt below.

A 5-line code segment reads as follows. Line 1: forward slash, asterisk, asterisk, Returns the value of the element at row index row and column index col in the sparse array. Line 2: asterisk, Precondition, colon, 0 less than or equal to row less than get Num Rows, open parenthesis, close parenthesis. Line 3: asterisk, 0 less than or equal to col less than get Num Cols, open parenthesis, close parenthesis. Line 4: asterisk, forward slash. Line 5: public int get Value At, open parenthesis, int row comma int col, close parenthesis.

(b) Write the SparseArray method removeColumn. After removing a specified column from a sparsearray:

All entries in the list entries with column indexes matching col are removed from the list.

All entries in the list entries with column indexes greater than col are replaced by entries with column indexes that are decremented by one (moved one column to the left).

The number of columns in the sparse array is adjusted to reflect the column removed.

The sample object sparse from the beginning of the question is repeated for your convenience.

The shaded entries in entries, below, correspond to the shaded column above.

When sparse has the state shown above, the call sparse.removeColumn(1) could result insparse having the following values in its instance variables (since entries is in no particular order, itwould be equally valid to reverse the order of its two items). The shaded areas below show the changes.

An array labeled entries is shown that is a horizontal row with two boxes. In the first box it reads row 1, column 3, value 4. In the second box it reads row 2, column 0, value 1. The first box is shaded grey. A box with text at the top that reads, Class information repeated from the beginning of the question. A 17-line code segment reads as follows. Line 1: public class Sparse Array Entry (underlined). Line 2: blank. Line 3: public Sparse Array Entry, open parenthesis, int r comma int c comma int v, close parenthesis. Line 4: public int get Row, open parenthesis, close parenthesis. Line 5: public int get Col, open parenthesis, close parenthesis. Line 6: public int get Value, open parenthesis, close parenthesis. Line 7: blank. Line 8: public class Sparse Array (underlined). Line 9: blank. Line 10: private int num Rows. Line 11: private int num Cols. Line 12: private List, open angular bracket, Sparse Array Entry, close angular bracket, entries. Line 13: public int get Num Rows, open parenthesis, close parenthesis. Line 14: public int get Num Cols, open parenthesis, close parenthesis. Line 15: public int get Value At, open parenthesis, int row comma int col, close parenthesis. Line 16: public void remove Column, open parenthesis, int col, close parenthesis.

Text at the top reads, Complete method remove Column below. A 4-line code segment reads as follows. Line 1: forward slash, asterisk, asterisk Removes the column col from the sparse array. Line 2: asterisk, Precondition, colon, 0 less than or equal to col less than get Num Cols, open parenthesis, close parenthesis. Line 3: asterisk, forward slash. Line 4: public void remove Column, open parenthesis, int col, close parenthesis. BoldItalicUnderlineBullet listNumbered listImage (12 image limit)Code InlineCode Editor Edit imageView imageDelete image

Here’s the corrected and revised section for FRQ 3:

FRQ Type: 2D Arrays

Key Algorithm:

The key algorithms in the SparseArray1 class involve accessing values at specific indices, removing columns from the sparse array, and displaying the sparse array. Let’s analyze how these algorithms match the FRQ type of 2D Arrays:

Class Structure: Similar to the SparseArray class, the SparseArray1 class encapsulates functionality related to sparse arrays. It contains instance variables to store the number of rows, number of columns, and a list of SparseArrayEntry objects representing non-zero elements.
Instance Variables: The class maintains instance variables numRows, numCols, and entries, similar to the SparseArray class.
Method Implementation:
- getValueAt(int row, int col): This method retrieves the value at the specified row and column in the sparse array. It iterates through the list of entries and returns the value associated with the matching entry. If no entry is found, it returns 0.
- removeColumn(int col): This method removes the specified column from the sparse array. It iterates through the list of entries, removes entries with column indexes matching the given column, and decrements the column indexes of entries with column indexes greater than the specified column.
- display(): This method displays the sparse array by iterating over each row and column and printing the corresponding values. It utilizes the getValueAt method to retrieve values at specific indices.
Instance Methods: All three methods (getValueAt, removeColumn, display) are instance methods that operate on specific instances of the SparseArray1 class. They utilize the instance variables of the class to access and manipulate the sparse array.

// For part b)
public class SparseArrayEntry {
    private int row;
    private int col;
    private int value;

    public SparseArrayEntry(int r, int c, int v) {
        row = r;
        col = c;
        value = v;
    }

    public int getRow() {
        return row;
    }

    public int getCol() {
        return col;
    }

    public int getValue() {
        return value;
    }
}

public class SparseArray1 {
    private int numRows;
    private int numCols;
    private List<SparseArrayEntry> entries;

    public SparseArray1() {
        entries = new ArrayList<SparseArrayEntry>();
        entries.add(new SparseArrayEntry(1, 4, 4));
        entries.add(new SparseArrayEntry(2, 0, 1));
        entries.add(new SparseArrayEntry(3, 1, -9));
        entries.add(new SparseArrayEntry(1, 1, 5));
        numRows = 6;
        numCols = 5;
    }

    public int getNumRows() {
        return numRows;
    }

    public int getNumCols() {
        return numCols;
    }

    public int getValueAt(int row, int col) {
        for (SparseArrayEntry entry : entries) { // iterates over each object in the list
            if (entry.getRow() == row && entry.getCol() == col) //makes sure the entry's row and column match
                return entry.getValue();
        }
        return 0;
    }

    public void removeColumn(int col) {
        for (int i = entries.size() - 1; i >= 0; i--) { // iterates over the list
            SparseArrayEntry entry = entries.get(i); // current object is retrieved
            if (entry.getCol() == col) {
                entries.remove(i);
            } else if (entry.getCol() > col) {
                entries.set(i, new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue())); // removed from the list if column matches
            }
        }
        numCols--;
    }

    public void display() {
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numCols; j++) { 
                System.out.print(getValueAt(i, j) + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SparseArray1 sparse = new SparseArray1();
        System.out.println("Original SparseArray:");
        sparse.display();

        sparse.removeColumn(1);
        System.out.println("SparseArray after removing column 1:");
        sparse.display();
    }
}

SparseArray1.main(null);

Original SparseArray:
0 0 0 0 
5 0 0 4 
0 0 0 0 
-9 0 0 0 
0 0 0 0 
0 0 0 0 
SparseArray after removing column 1:
0 0 0 
0 0 4 
0 0 0 
0 0 0 
0 0 0 
0 0 0 

FRQ 3 • 42 min read

Description