Homework 2: Sparse IndexedList

In this homework, building on our classwork, you will be programming a different implementation of the IndexedList interface.

Objectives

• Implement a sparse data structure using object-oriented programming principles
• Practice working with linked lists and nested classes
• Improve code efficiency and optimization skills
• Gain experience in writing comprehensive unit tests
• Analyze and compare different data structure implementations
• Continue to adhere to coding standards and style guidelines

Important Dates

Homework Description

In this homework, you will implement a sparse list data structure called SparseIndexedList. The SparseIndexedList is a list that efficiently stores elements that differ from a default value. The default value is the value that most elements in the list share. The SparseIndexedList should only store elements that differ from the default value.

Additionally, you will write unit tests for the SparseIndexedList and other implementations of the IndexedList interface. You will also answer a discussion question related to the Roster class.

Note, you are not allowed to use (1) Java Collections (built-in data structures), (2) data structures that are not covered in the course yet.

Starter Code

Download the starter code from the following link: hw2.zip

The starter code is a zip file named hw2-starter.zip. You must unzip this file. After unzipping, you will get a folder called hw2-starter. Open this folder as an IntelliJ project.

Tasks

This assignment consists of three main tasks: writing unit tests, implementing a sparse list, and answering a discussion question.

Testing

You must write unit tests in the provided IndexedListTest.java (a few examples are provided). Write your tests based on the specification of the interface IndexedList. You can use the same suite of tests to test multiple implementations of IndexedList (that is ArrayIndexedList, LinkedIndexedList, and SparseIndexedList). Carefully study the starter code and make a note of how the same suite of tests (i.e., IndexedListTest) is employed to test multiple implementations by leveraging inheritance.

Feel free to use the unit tests we've provided in the lecture notes.

Make note that the IndexedList interface extends Iterable; therefore, it inherently includes the Iterable.iterator() method, and so you must write tests for it too.

Implementation

Implement a SparseIndexedList class that embodies a sparse list as described below while adhering to the IndexedList interface.

A sparse list is a data structure designed to efficiently handle lists where most elements have the same value, called the default value. Instead of storing every element, a sparse list only keeps track of elements that differ from this default.

Key Concepts:

1. Default Value: A value that most elements in the list share.

2. Efficient Storage: Only non-default values are explicitly stored.

3. Implicit Values: Elements not explicitly stored are assumed to have the default value.

Benefits:

• Space Efficiency: Saves memory when most elements are the default value.

• Time Efficiency: Operations can be faster when there are few non-default elements.

Implementation Hints:

• If all the elements in the list are the default value, do you need to store any elements explicitly?

• If only a few elements are non-default, could you use a linked list to store only those elements?

• If you used a linked list for non-default values, what information would you need to store in each node? How would you know the "position" of each node in the broader list?

Example Scenario:

Imagine a SparseIndexedList of length 10 with default value 0. At the start, you can internally represent this as an empty list.

head -> null

If you set position 3 to 5, you would add a node to the list with position 3 and value 5. If you then set position 7 to 2, you would add another node with position 7 and value 2.

head -> (3, 5) -> (7, 2)

If you then set position 3 back to 0, you would remove the node that was added for position 3. So, the internal list would look like this:

head -> (7, 2)

Remember, the goal is to create a list that behaves like a regular list from the outside, but internally optimizes for the sparse nature of the data.

Iterator

Make note that the IndexedList interface extends Iterable; therefore, your implementation of the SparseIndexedList must include an iterator for it. The iterator needs to present all the values for indices 0 through length()-1 in order, exhibiting the same behavior as the iterators of the ArrayIndexedList and the LinkedIndexedList.

Once you have a correct implementation, think about the efficiency of your iterator. In particular, consider the case where clients of SparseIndexedList use the iterator far more frequently than using put and get operators.

We have not yet formalized a notion of "efficiency." For this task, you can consider the iterators of the ArrayIndexedList and the LinkedIndexedList as examples of efficient implementations. Those implementations take a few operations to get the "next" element (the operations involve looking up/updating an index or a reference variable). The same can be said about the hasNext operation and the constructor.

You may need to refactor your implementation of SparseIndexedList to make its iterator efficient. Make sure first to make a backup of your solution. In case you end up breaking your solution to make it more efficient, you can always revert to the earlier version.

Discussion

This question is based on the content of chapters 1, 2, and 3, where we introduced and worked with the Roster class.

We want to implement a Roster where the find method performs a binary search. Furthermore, we want to use an IndexedList as the internal data structure in the Roster class (to hold a list of students).

public class Roster {
  
  private IndexedList<Student> students;

  // Other attributes and methods not shown.

  // Assume students' emails are unique.
  public Student find(String email) {
    // Implements binary search
  }
}

Which implementation of the IndexedList should be used here? (It could be one or more of ArrayIndexedList, LinkedIndexList, SparseIndexedList). And, why?

Write down your answer in the README.md file. Please keep it brief and to the point. (We reserve the right to reduce points if the answer is too long or contains irrelevant information.)

The README.md file is located at src/main/java/hw2/.

The information provided above is all that there is to be known. We don't know, e.g., the roster's size, how often add/remove is performed v.s. how often find is invoked. However, we know binary search needs a sorted collection, so add/remove must keep the students IndexedList sorted.

Submission

In preparation, you must (1) run checkstyle to ensure your code is checkstyle compliant (if not, fix the styling issues). (2) Create a zip file containing the src folder (and all therein). (3) Submit the zip file to Gradescope.

You can submit as many times as you like until deadline. We will only grade the last submission.

Rubric

Teaching assistants will evaluate your submission using the following criteria:

Please note, we reserve the right to change this rubric without advance notice, even after the submission deadline. However, the chances of doing so are slim, and at any rate, should not be a significant change.

• Spec 1: Unit tests are focused, targeted, and appropriately named. [1 point]

• Spec 2: IndexedListTest contains unit tests for basic behavior of core IndexedList operations, including constructor and exception cases. [3 points]

• Spec 3: IndexedListTest includes comprehensive tests for the iterator, using both for-each loops and direct iterator object usage. [1 points]

• Spec 4: Unit tests cover non-trivial, complex, and edge cases for most operations. [1 point]

• Spec 5: SparseIndexedList constructor is implemented correctly. The implementation is efficient, avoiding unnecessary work or space usage. [1.5 points]

• Spec 6: SparseIndexedList.length returns the correct list length and remains consistent during modifications. [1 point]

• Spec 7: SparseIndexedList.get is implemented correctly. The implementation is efficient, avoiding unnecessary work or space usage. [2 points]

• Spec 8: SparseIndexedList.put is implemented correctly. The implementation is efficient, avoiding unnecessary work or space usage. [4 points]

• Spec 9: The SparseIndexedList iterator is correctly implemented. [1.5 points]

• Spec 10: The SparseIndexedListIterator operations are efficient. [1.5 points]

• Spec 11: The code exhibits good programming style, including modular organization, appropriate method lengths, and proper encapsulation. Moreover, the code is checkstyle compliant, exhibiting good practices for readability, including consistent naming conventions, indentation, and useful comments. [1 point]

• Spec 12: The README.md file contains concise and accurate answers to the discussion questions. [1.5 point]

The total score for this homework is 20 points.