Sample questions can be found here.

Your are responsible for everything that was on the first Prelim. We aren't looking to test that material, but it is understood that you know all the technical Java concepts that we have covered. That material should be part of your programming repetoire by now. Below, with each section, we list what you are responsible for and give some sample questions.

Questions on correctness of programs. Know what an assertion is, what a Hoare triple is, the definition of the assignment in terms of finding the precondition from the postcondition, what it takes to prove a conditional statement correct, and the checklist for understanding a loop. Given a precondition, postcondition, invariant, and bound function, you should be able to develop the loop. If we say, "linear search", "binary searech", "selection sort", "insertion sort", "partition", or "compute "x^y", you should be able to say what the problem is and write a loop with initialization for it (with invariant, of course).

Questions on searching and sorting. You should know the following algorithms (some of them written as recursion procedures): linear search, binary search, partition, selection sort, insertion sort, merge sort, quick sort. You should know what their worst-case and best-case execution times are.

Questions on algorithmic analysis. Basically, know Weiss chapter 5. See the handout on algorithm analysis for a detailed list of what you have to know (it tells you what you are NOT responsible for). In addition, you should be able to prove that a given function is O(f(n)) (for some f(n)), and you should be able to analyze an algorithm and figure out its order of execution time.

Questions on data structures. 1. Linked lists. We have used the terms linked list, linked list with header, doubly linked list, and doubly linked list with head and tail with technical meanings. You have to know what those terms mean. You should be able to write algorithms that travers these kinds of lists, do something to each element. You have to be able to remove and element from and add an element to these kinds of linked lists (don't memorize code; instead, be able to draw the situation and develop the code from the drawing). Know the advantages and disadvantages of using these kinds of linked lists. Be able to say what the order of execution time is for these operations on the different kinds of linked list: find a value, delete the minimum value, delete a node whose name is known, insert a value after a given node, insert a value before a given node.  All of these are straightforward and obvious if you understand the details of the different kinds of list.

2. Hash tables. Know how to implement a set in a hash table (as discussed in a recitation handout). You do not have to know a hash function, bubt you have to know what its purpose is. Know about linear probing, quadratic probing, how an element is added, how an element is deleted. Know what the load factor is and how many probes can be expected when the load factor is 1/2.

3. Binary trees. Weiss, sections 18.1.1 (not 18.12 and 18.13), 18.2, 18.3). Know the definition of a binary tree and how a binary tree is implemented. Be able to write methods that perform preorder, inorder, and postorder traversals of trees. (Don't read Weiss, section 18.4, to find out about preorder, inorder, and postorder traversal, because he doesn't do them recursively.) Know how to implement an expression in a binary tree.

4. Binary search trees. Weiss, section 19.1) Know the definition of a binary search tree. Know how to lok for a value in a binary search tree, to find the minimum value of a binary search tree, and to add a value to a binary search tree.