The CS222 Optional Summer Enrichment Exercises

In my earlier post, as part of my reflection on the Spring 2021 CS222 experience, I mentioned an optional summer enrichment program that I assembled for the students. The full document is in the course GitHub organization, and it contains some fluff explaining the context and goals. I decided to also copy over the exercises here, in case they are of general interest. The version on GitHub will eventually be discarded along with the students' repositories, probably the next time I teach the course and need to repurpose that organization.

Without further ado, then, here are the exercises that I designed to help students build their knowledge of data structures in Java while also strengthening the skills they learned in CS222. 

1. Watch my video about developing a linked list with TDD. In the video, I mention several areas in which the sample problem is underspecified, such as not handling exceptional cases and not supporting remove-by-value. Make a list of those, then work through a complete linked list example using TDD. This will strengthen your knowledge of Java, data structures, and Clean Code.
2. Using what you learned in that previous video, write your own implementation of array list. Note that the task list will be almost identical. The special cases to add will be where the internal array needs to be resized. For example, you should set it up so that your ArrayList constructor takes an argument which is the original size of the backing array. Then, make sure you test a case where you add more elements than fit into that array, in which case your implementation should be allocating a larger array behind the scenes.
3. To get practice with recursion, try the exercises above with recursive rather than iterative solutions. My video shows an iterative approach, but anything you can do iteratively you can do recursively.
4. Write your own library of ADT wrappers. For example, make an interface Queue that defines the behavior of a queue, then use TDD to write a LinkedQueue implementation that uses Java's LinkedList as a backing data structure, or ArrayQueue that uses Java's ArrayList as a backing data structure. Try it with Stack as well.

Consider it CC BY-SA 4.0, which is how I've been licensing all my public educational resources lately. I think it was on the SIGCSE mailing list that I saw someone exhort the community to be explicit about their licenses, and being a fan of Free Culture, I think it's a great idea.