Learning Goals

  • Understand the difference between an ADT and a data structure.

    Many students find it easier to understand these concepts by exploring a working codebase, and in this assignment, we have one with multiple ADTs and data structures.

  • Practice debugging code using tests.

    Learning how to write and use tests to identify and fix flaws in a program will save us a lot of time in the future. Following the debugging cycle allows us to do so effectively and systematically.

    1. Develop a hypothesis based on what we know about the problem.
    2. Reproduce the issue in a minimal working example.
    3. Make productive changes based on the root cause discovered.
    4. If there are more issues, return to step 1.

  • Apply your understanding of invariants towards testing programs.

    Data structures can be difficult to test, since simply calling the methods provided by their ADTs may not always reveal issues hidden in the remainder of the data structure’s internal state. Instead of relying only on values returned by the ADT‘s methods, it can sometimes be easier to check the validity of this state directly by determining whether it violates the data structure’s invariants.

Reminder

This and all future projects allow you to work in groups of 2. See the introductory page of this assignment for more details on partner logistics.

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. Intro - Acquire and prepare for the assignment.
  2. Programming - Complete the programming portion of the assignment.
  3. Experiments - Run some experiments and complete a brief write-up.