CS 201: Topics for exam 3

This is intended to give you a sense of what I think is important from the course so far, and what I will be thinking of when creating the exam.

I hate disclaimers, but here are some anyway. This is not a contract. I may have inadvertently left something off this list that ends up in 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.

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

Here are the specifics: Students should be able to...

ADTs:

• Be able to describe, use, and determine appropriate uses priority queues and graphs.

Implementation approaches:

• Be able to explain what heaps, AVL 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 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, 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.