The CS 112 midterm will be in class on Thursday November 10 for B section
and Friday November 11 for the A section.  

The best things to study are lecture notes (the schedule is on the main page), the code we give you, and the homework solutions.  The exercises in the book can also help you study.

Questions will be mostly of the following types:

-- short answer on basic concepts (such as big-O, recursion, data structures, etc.)
-- writing small pieces of code
-- figuring out what a piece of code does and/or modifying it

Here are two example questions.

1. Show the recursion tree for QuickSort running on the array 6 8 3 2 7 1 9.
At each node in the tree show the array that is being sorted.  Assume the
first element is always chosen as pivot.

2. The following code is supposed to QuickSort a linked list by rearranging
nodes in the list (allocating new nodes using the "new" operator is not allowed).
Fill in the missing pieces.

public class ListWithQuickSort {

	public static class ListNode {
		int value;
		ListNode next;
	}
	
	/**
	 * Give a linked list, returns a pointer to the sorted version of the list
	 * Destroys the original linked list
	 * @param inputList
	 * @return inputList with nodes rearranged in sorted order
	 */
	public static ListNode QuickSortList (ListNode inputList) {
		if (inputList == null)
			return null;
		
		ListNode pivot = inputList;
		ListNode smallerList = null, biggerList = null;
		
		// start with the node after the pivot,
		// add every node with value smaller than pivot's value to smallerList,
		// and all the other nodes to biggerList
		// rearrange nodes without allocating new nodes
		ListNode p = inputList.next;
		while (p!=null) {			

		 // FILL IN HERE

		}
			
		// Recursively sort the two lists
		smallerList = QuickSortList (smallerList);
		biggerList = QuickSortList (biggerList);

		// Put smallerList, followed by pivot, followed by biggerList

		// FILL IN HERE
	}
}