CS 201: Topics for exam 1

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 for stacks, queues, sets and maps.

Implementation approaches: Be able to explain what binary search trees and hash tables 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 trees and binary search trees.
• Be able to insert a series of data into a binary search tree or hash table, and be able to show the intermediate results along the way.
• Be able to describe and/or work through examples of hashing via open addressing and via chaining. Demonstrate how collision strategies work, such as linear probing, quadratic probing, and double hashing. Distinguish between primary and secondary clustering. Be able to describe trade-offs between open addressing and chaining. Be able to construct an appropriate hash function for a particular situation.
• Be able to describe trade-offs between trees and hashing, and why one chooses one vs. the other
• Be able to demonstrate detailed examples of preorder, inorder, and postorder tree traversal.

Java implementations:

• Stacks: Be able to construct Java code to implement a stack using an array, ArrayList, or LinkedList.
• Queues: Be able to construct Java code to implement a stack using an array, ArrayList, or LinkedList. Be able to appropriately handle problems that occur with a queue in an array.
• Be able to construct Java code to implement sets or maps via binary search trees or hashing (open addressing or chaining).

Recursion: Be able to code a recursive method in Java subject to specifications. Be able to explain quantitatively (with big-O notation) tradeoffs in recursive vs. iterative solutions to a particular problem.