Question 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.
Part 3
(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.
import java.util.HashMap;
import java.util.Map;
// Class to represent an entry in the sparse array
class SparseArrayEntry {
private final int row;
private final int col;
private final int value;
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
// Class to represent the sparse array
class SparseArray {
private final Map<Integer, SparseArrayEntry> entries;
private final int numRows;
private final int numCols;
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
entries = new HashMap<>();
}
public void addEntry(int row, int col, int value) {
if (isValidIndex(row, col)) {
entries.put(generateKey(row, col), new SparseArrayEntry(row, col, value));
} else {
throw new IllegalArgumentException("Invalid index");
}
}
public int getValueAt(int row, int col) {
SparseArrayEntry entry = entries.get(generateKey(row, col));
return entry != null ? entry.getValue() : 0;
}
public int getNumRows() {
return numRows;
}
public int getNumCols() {
return numCols;
}
private boolean isValidIndex(int row, int col) {
return row >= 0 && row < numRows && col >= 0 && col < numCols;
}
private int generateKey(int row, int col) {
return row * numCols + col;
}
}
// Example usage
public class MainTesting {
public static void main(String[] args) {
SparseArray sparseArray = new SparseArray(5, 5); // 5x5 sparse array
sparseArray.addEntry(1, 2, 3); // Add an entry at row 1, column 2 with value 3
sparseArray.addEntry(3, 4, 5); // Add another entry at row 3, column 4 with value 5
System.out.println("Original Array");
for (int row = 1; row <= sparseArray.getNumRows(); row++) {
for (int col = 1; col <= sparseArray.getNumCols(); col++) {
System.out.println("Value at (" + row + ", " + col + "): " + sparseArray.getValueAt(row, col));
}
}
System.out.println();
}
}
MainTesting.main(null);
Original Array
Value at (1, 1): 0
Value at (1, 2): 3
Value at (1, 3): 0
Value at (1, 4): 0
Value at (1, 5): 0
Value at (2, 1): 0
Value at (2, 2): 0
Value at (2, 3): 0
Value at (2, 4): 0
Value at (2, 5): 0
Value at (3, 1): 0
Value at (3, 2): 0
Value at (3, 3): 0
Value at (3, 4): 5
Value at (3, 5): 0
Value at (4, 1): 0
Value at (4, 2): 0
Value at (4, 3): 0
Value at (4, 4): 0
Value at (4, 5): 0
Value at (5, 1): 0
Value at (5, 2): 0
Value at (5, 3): 0
Value at (5, 4): 0
Value at (5, 5): 0
Explanation
This code implements sparse arrays using a SparseArray class and an SparseArrayEntry class. The SparseArrayEntry class represents an individual entry with its row, column, and value. The SparseArray class represents the sparse array itself, utilizing a HashMap to store entries efficiently. It provides methods to add entries, get the value at a specific position, and retrieve the number of rows and columns in the array. Entries are stored based on a generated key calculated from the row and column indices. The MainTesting class demonstrates the usage of these classes by creating a sparse array, adding entries, and printing the values at specified positions within the array.
Part B
(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.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
// Class representing an entry in the sparse array
class SparseArrayEntry {
private int row;
private int col;
private int value;
public SparseArrayEntry(int row, int col, int value) {
this.row = row;
this.col = col;
this.value = value;
}
public int getRow() {
return row;
}
public int getCol() {
return col;
}
public int getValue() {
return value;
}
}
// Class representing a sparse array
class SparseArray {
private List<SparseArrayEntry> entries; // List to store sparse array entries
private int numRows; // Number of rows in the sparse array
private int numCols; // Number of columns in the sparse array
public SparseArray(int numRows, int numCols) {
this.numRows = numRows;
this.numCols = numCols;
entries = new ArrayList<>();
}
// Method to add an entry to the sparse array
public void addEntry(int row, int col, int value) {
entries.add(new SparseArrayEntry(row, col, value));
}
// Method to get the value at a specific position in the sparse array
public int getValueAt(int row, int col) {
for (SparseArrayEntry entry : entries) {
if (entry.getRow() == row && entry.getCol() == col) {
return entry.getValue();
}
}
return 0; // Return 0 if no value is found at the specified position
}
// Method to remove a column from the sparse array
public void removeColumn(int col) {
numCols--; // Decrease the number of columns
List<SparseArrayEntry> updatedEntries = new ArrayList<>(); // Temporary list to hold modified entries
// Iterate over the entries
for (SparseArrayEntry entry : entries) {
// If the entry doesn't belong to the specified column, add it to the updated list
if (entry.getCol() != col) {
// If the column of the entry is greater than the removed column,
// decrease the column index of the entry by 1
if (entry.getCol() > col) {
updatedEntries.add(new SparseArrayEntry(entry.getRow(), entry.getCol() - 1, entry.getValue()));
} else {
updatedEntries.add(entry);
}
}
}
// Update the original list with the modified entries
entries = updatedEntries;
}
// Method to get the number of rows in the sparse array
public int getNumRows() {
return numRows;
}
// Method to get the number of columns in the sparse array
public int getNumCols() {
return numCols;
}
}
// Class containing the main method for testing the SparseArray class
public class MainTesting {
public static void main(String[] args) {
// Creating a sparse array and adding entries
SparseArray sparseArray = new SparseArray(5, 5);
sparseArray.addEntry(1, 2, 3);
sparseArray.addEntry(3, 4, 5);
sparseArray.addEntry(2, 3, 7);
// Printing original array
System.out.println("Original Array");
System.out.println("Number of Rows: " + sparseArray.getNumRows());
System.out.println("Number of Columns: " + sparseArray.getNumCols());
// iterating through 2D array to print array out
for (int i = 0; i < sparseArray.getNumRows(); i++) {
for (int j = 0; j < sparseArray.getNumCols(); j++) {
int value = sparseArray.getValueAt(i, j);
System.out.print(value + " ");
}
System.out.println();
}
sparseArray.removeColumn(3);
System.out.println("Number of Rows: " + sparseArray.getNumRows());
System.out.println("Number of Columns: " + sparseArray.getNumCols());
for (int i = 0; i < sparseArray.getNumRows(); i++) {
for (int j = 0; j < sparseArray.getNumCols(); j++) {
int value = sparseArray.getValueAt(i, j);
System.out.print(value + " ");
}
System.out.println();
}
}
}
MainTesting.main(null);
Original Array
Number of Rows: 5
Number of Columns: 5
0 0 0 0 0
0 0 3 0 0
0 0 0 7 0
0 0 0 0 5
0 0 0 0 0
Number of Rows: 5
Number of Columns: 4
0 0 0 0
0 0 3 0
0 0 0 0
0 0 0 5
0 0 0 0
Explanation
This code defines classes to handle sparse arrays, where most elements are zero. The SparseArrayEntry class represents an entry with its row, column, and value. The SparseArray class represents the sparse array itself, storing entries in a list. It provides methods to add entries, get the value at a specific position, and remove a column, adjusting the column indices accordingly. The MainTesting class demonstrates the usage of these classes by creating a sparse array, adding entries, printing the original array, removing a column, and printing the modified array.
Reflection
This FRQ was the hardest one for me. I had to ask my friend Adi for help to understand it. I felt really stressed because there was a lot to deal with. I had to keep going back and forth between tabs because the question was in an image. The answers were also longer compared to the other FRQs. Now I understand it better, but I realize I need to study 2d arrays more than I expected.