CS 201: Exam 3 Info

You are permitted one 8.5 x 11 handwritten notes sheet (both sides) for use as a reference during the exam.

Lots of research has shown that reading over material isn't a very good way to prepare for exams. The best thing to do is to practice. Reading how to swing a baseball bat or how to cross-country ski might give you some good ideas on how to get better the next time you try it, but it's not even close to just getting out there and swinging a bat or skiing in the Arb.

How can you practice? The textbook has a fantastic set of self-test exercises, that appear throughout the readings. The answers to the self-test exercises are at the end of the chapter. Practice these under test conditions and see how you do.

Additionally, at the end of every chapter is a set of exercises. Even though the solutions to those are not available, just trying to do them can be incredibly useful. The ones that involve programming you can put into the computer to see if they work. Otherwise, you can work with other students to see if you think you've got the right answers. Even if you don't know for sure if you've got the right answer, just practicing with these exercises can be helpful.

Finally, make sure to do all of your practicing on paper, not at a keyboard, so as to simulate the exam conditions.

Listed below is the material that I have in mind that you should know for the exam. It's what's in my head when creating it. That said, this isn't a contract. I may have inadvertently left something off this list that ends up on an exam question. I make no guarantees that the exam will be 100% limited to items listed below. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.

Students should be able to…

ADTs:

• Be able to describe, use, and determine appropriate uses for sets, maps (dictionaries), priority queues and graphs.

Implementation approaches:

• Be able to explain what hash tables, binary search trees, heaps, AVL trees, 2-3 trees, adjacency lists, and adjacency matrices are used for. Be able to illustrate how standard operations (insert, delete, etc.) work. Be able to quantify performance (big-O) of standard operations. Show understanding of the ideas behind operations and big-O performance by being able to answer questions about novel variations on standard techniques.

Specifics regarding particular implementation approaches:

• Be able to distinguish between open addressing and chaining for hash tables. Know how they are implemented, and be able to consider tradeoffs between them. Be able to assess complexity (time and memory) of both approaches.
• Be able to distinguish between binary search trees, complete trees, balanced trees, and heaps. Know how and why they are implemented via pointer structures or arrays as appropriate.
• Be able to insert a series of data into a heap, AVL tree, 2-3 tree, adjacency matrix, or set of adjacency lists and be able to show the intermediate results along the way.
• Be able to describe trade-offs between adjacency lists, adjacency matrices, and other variations on the theme, and why one chooses one vs. the other.

Algorithms:

• Be able to demonstrate detailed examples of the following sorting algorithms: selection sort, insertion sort, heapsort, merge sort, quicksort, radix sort. Be able to describe big-O performance for each, and be able to justify it. Be able to analyze a novel sorting algorithm that uses similar ideas.
• Be able to demonstrate detailed examples of graph traversal algorithms such as depth-first and breadth-first traversal.

Java implementations:

• Be able to construct Java code to implement any reasonably-sized portion of the above implementation approaches or algorithms.
• Be able to construct Java code to implement sets or maps via binary search trees or hashing (open addressing or chaining).