Maps

Learning Goals¶

• Build a data structure by delegating to other data structures.

  In practice, software developers rarely write their own basic data structures with general functionality: we can usually find implementations for these written in pre-existing libraries. Instead, the data structure we need to implement ourselves are often tailored to specific purposes and built off of other existing data structures.

  Similarly, this assignment will have you first implement a basic data structure that fulfills the map ADT, then build a more-complex map using that basic implementation.

• Review the iterator design pattern.

  Iterators are a common sight in Java code, and for good reason: they allow us to access elements of data structures in sequential order—a task often inefficient or impossible otherwise. For example, the iterators you will implement in this assignment will provide access to all entries of a map, which would not be possible via any combination of the other methods that you will implement.

• Practice choosing invariants to ease implementation.

  The previous assignment gave you some experience with writing code to maintain invariants; now, it’s time to choose your own. Designing strong invariants will reduce the complexity of your code by restricting the number of possible cases your code needs to handle—by spending some time planning these out, you can save time spent writing needless special cases, especially for more-complex data structures.

Getting the Assignment¶

Follow the instructions from the Deques assignment to add your partner into your group and pull the assignment from the public skeleton.

Like previous projects, if IntelliJ doesn’t react to the new folder for whatever reason, refresh Gradle manually through the Gradle tool window (on the right by default):

Feedback Survey¶

After completing both the programming and experiment portions of the assignment, complete the mandatory 1-point individual feedback survey on Canvas. Each partner needs to submit their own individual response. Responses will be graded on completion, but we’d appreciate if you took a few minutes to really reflect on your experience so that we can improve the assignment for future quarters.

Subpages

1. Programming - Complete the programming portion of the assignment.
2. Experiments - Run some experiments and complete a brief write-up.