CSA 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.
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.
The following table shows an example of a two-dimensional sparse array. Empty cells in the table indicate zero values.
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.
(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.
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0;
}
(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.
public void removeColumn(int col) {
List<SparseArrayEntry> updatedEntries = new ArrayList<>(); //create a new list to store updated entries
for (SparseArrayEntry entry : entries) {//iterate through the entries to update and remove the specified column
if (entry.getCol() == col) {
continue; // Skip the entry if it belongs to the specified column
}
else if (entry.getCol() > col) {
updatedEntries.add(new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue())); //decrement the column index for entries with columns greater than col
}
else {
updatedEntries.add(entry); //keep entries with columns less than col unchanged
}
}
//update the entries list with the new list
entries = updatedEntries;
//adjust the number of columns in the sparse array
numCols--;
}
test.contains(1): true
test.contains(10): false
Runtime:
import java.util.ArrayList;
import java.util.List;
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int r, int c, int v) {
row = r; //constructor
col = c;
value = v;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
public class SparseArray {
private int numRows; //instance variables
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray() {
numRows = 4;
numCols = 5;
entries = new ArrayList<>();
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0;
}
public void removeColumn(int col) {
List<SparseArrayEntry> updatedEntries = new ArrayList<>();
for (SparseArrayEntry entry : entries) {
if (entry.getCol() == col) {
continue;
} else if (entry.getCol() > col) {
updatedEntries.add(new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue()));
} else {
updatedEntries.add(entry);
}
}
entries = updatedEntries;
numCols--;
}
public static void main(String[] args) {
SparseArray sparse = new SparseArray();
sparse.entries.add(new SparseArrayEntry(1, 4, 4));
sparse.entries.add(new SparseArrayEntry(2, 0, 1));
sparse.entries.add(new SparseArrayEntry(3, 1, -9));
sparse.entries.add(new SparseArrayEntry(1, 1, 5));
//displaying initial state
System.out.println("Initial Sparse Array:");
for (int i = 0; i < sparse.getNumRows(); i++) {
for (int j = 0; j < sparse.getNumCols(); j++) {
System.out.print(sparse.getValueAt(i, j) + "\t");
}
System.out.println();
}
//removing column 1
sparse.removeColumn(1);
//displaying the updated state
System.out.println("\nSparse Array after removing column 1:");
for (int i = 0; i < sparse.getNumRows(); i++) {
for (int j = 0; j < sparse.getNumCols(); j++) {
System.out.print(sparse.getValueAt(i, j) + "\t");
}
System.out.println();
}
}
}
SparseArray.main(null);
Initial Sparse Array:
0 0 0 0 0
0 5 0 0 4
1 0 0 0 0
0 -9 0 0 0
Sparse Array after removing column 1:
0 0 0 0
0 0 0 4
1 0 0 0
0 0 0 0
Explanation and Reflection:
This was probably the hardest problem for me as I don’t have a strong understanding of what sparse arrays are. However, after digging around online and asking chatgpt for some understanding help, I understood that in simple terms, a sparse array in this context is like a grid where most of the grid cells have a value of zero. It only keeps track of the cells that have non-zero values along with their positions (row and column).
In the quesiton above, there are two classes involved: SparseArrayEntry for each non-zero value, and SparseArray to represent the whole grid with its dimensions and non-zero entries. The code includes methods to get the value at a specific position and to remove a column efficiently. This way, we can work with large grids more efficiently because we only focus on the parts that have actual values.
class SparseArrayEntry {
private int row;
private int col;
private int value;
}
The SparseArrayEntry class represents a non-zero element in a sparse array. Each instance of this class holds information about a specific element, including its row index (row), column index (col), and the actual value of the element (value). This class is designed to make it easy to create and retrieve information about individual non-zero entries within a sparse array.
public class SparseArray {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0;
}
public void removeColumn(int col) {
List<SparseArrayEntry> updatedEntries = new ArrayList<>();
for (SparseArrayEntry entry : entries) {
if (entry.getCol() == col) {
continue;
} else if (entry.getCol() > col) {
updatedEntries.add(new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue()));
} else {
updatedEntries.add(entry);
}
}
entries = updatedEntries;
numCols--;
}
}
The SparseArray class serves as a container for a sparse array. It keeps track of the number of rows (numRows) and columns (numCols) in the array, along with a list of SparseArrayEntry objects (entries) representing the non-zero elements. This class provides methods to retrieve the dimensions of the array and efficiently access values at specific positions using the getValueAt method. The removeColumn method allows for the removal of a specified column, adjusting the entries and column indexes accordingly.