2015 CSA FRQ Question 3
Completing each FRQ so it runs, and blogging about relation to final project
Question 3
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) 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.
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 SparseArray {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray(int numRows, int numCols) {//create a sparse array with a certain number of rows and columns
entries = new ArrayList<SparseArrayEntry>();
this.numRows = numRows;
this.numCols = numCols;
}
public void addSparseValue(int r, int c, int v) {//adds a value to the sparse array
SparseArrayEntry entry = new SparseArrayEntry(r, c, v);
entries.add(entry);
}
public int getNumRows() {//gets the number of rows
return numRows;
}
public int getNumCols() {//gets number of columns
return numCols;
}
// Part a-getValueAt
public int getValueAt(int row, int col) {//get the value at a specific row and column
for (SparseArrayEntry ent : entries) {
if (ent.getCol()==col && ent.getRow()==row) {//if the row and column number match up to the ones the user wanted, return the value at that position
return ent.getValue();
}
}
return 0;
}
// Part b-removeColumn
// public void removeColumn(int col) {
// }
}
public class Test3 {
public static void main(String[] args) {
SparseArray sparse = new SparseArray(6, 5);
sparse.addSparseValue(1,4,4);
sparse.addSparseValue(2,0,1);
sparse.addSparseValue(3,1,-9);
sparse.addSparseValue(1,1,5);
System.out.println("Value at (3,1): " + sparse.getValueAt(3,1));
System.out.println("Value at (2,0): " + sparse.getValueAt(2,0));
System.out.println("Value at (3,0): " + sparse.getValueAt(3,0));
}
}
Test3.main(null);
Value at (3,1): -9
Value at (2,0): 1
Value at (3,0): 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.
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 SparseArray {
private int numRows;
private int numCols;
private List<SparseArrayEntry> entries;
public SparseArray(int numRows, int numCols) {
entries = new ArrayList<SparseArrayEntry>();
this.numRows = numRows;
this.numCols = numCols;
}
public void addSparseValue(int r, int c, int v) {
SparseArrayEntry entry = new SparseArrayEntry(r, c, v);
entries.add(entry);
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
// Part a-getValueAt
public int getValueAt(int row, int col) {
for (SparseArrayEntry ent : entries) {
if (ent.getCol()==col && ent.getRow()==row) {
return ent.getValue();
}
}
return 0;
}
// Part b-removeColumn
public void removeColumn(int col) {
List<SparseArrayEntry> temp = new ArrayList<SparseArrayEntry>();
for (int i=0; i<entries.size(); i++) {//iterates through the entries
if (entries.get(i).getCol()==col) {//if the entries are at the column requested by the user, it is not added the temporary list
continue;
}
else {
temp.add(entries.get(i));//otherwise it is added to the temporary list
}
}
entries=temp;//entries is set to the temporary list
numCols-=1;//number of columns is decreased
}
}
public class Test3 {
public static void main(String[] args) {
SparseArray sparse = new SparseArray(6, 5);
sparse.addSparseValue(1,4,4);
sparse.addSparseValue(2,0,1);
sparse.addSparseValue(3,1,-9);
sparse.addSparseValue(1,1,5);
System.out.println("Value at (3,1): " + sparse.getValueAt(3,1));
System.out.println("# of columns: " + sparse.getNumCols());
System.out.println("# of rows: " + sparse.getNumRows());
sparse.removeColumn(1);
System.out.println("Value at (3,1): " + sparse.getValueAt(3,1));
System.out.println("# of columns: " + sparse.getNumCols());
System.out.println("# of rows: " + sparse.getNumRows());
}
}
Test3.main(null);
Value at (3,1): -9
# of columns: 5
# of rows: 6
Value at (3,1): 0
# of columns: 4
# of rows: 6
- FRQ Type: 2D Arrays
- How main algorithm shows FRQ type:
This FRQ revolves around 2D Arrays. Specifically, it deals with a type of 2D Array called a sparse array. This is a special type of 2d array where a large number of the values are 0. In the FRQ, we must do things like get the value of a specific value in the list and delete an entire column of data. Manipulating the values in a 2d array is an important part of this course and the real world beyond it.