Info

See an introductory video for this assignment and logistics here.

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.

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.