## Topics for the Midterm

### October 14th, 10:30-11:20, 107 EPB

Below I have listed 7 topics that you will be tested on, with details on what you should focus on for each topic. I have also included references to portions of the textbook you should read for each of the topics. In addition to material from the textbook, make sure to read all lecture notes, all discussion section notes, and any other material posted on the course webpage such as sample code, homework solutions, etc.

There will be 5 problems on the midterm, each problem covering a different topic. Each problem will be worth 30 points for a total of 150 points. The exam is worth 15% of your overall grade. Each problem may have a couple of parts and I expect you to spend about 10 minutes on each problem.

1. Running time analysis: Asymptotic ("Big Oh") notation. Analyzing small fragments of code and functions containing nested loops and recursive function calls. Why is the running time of binary search O(log n)? Why is the running time of merge sort O(nlog n)? Why is the worst case running time of quick sort not O(nlog n)? Why is the running time of the simple recursive function that computed the nth Fibonacci number, exponential in n?

Read pages 291-294 (efficiency of merge sort) and pages 355-357 (efficiency of quick sort).

2. Recursion: The standard examples of recursive functions such as Fibonacci number computation, binary search, generating permutations, generating subsets, merge sort, and quick sort. Reasoning about the correctness and running time of simple recursive functions.

Read Chapter 6 (on recursion) and pages 325-357 (on quick sort).

3. Sorting: The slow sorting algorithms such as bubble sort, selection sort, and insertion sort. Why is the running time of these functions n^2? The fast sorting algorithms: merge sort and quick sort. How does the merge function work? Why does it take linear time to complete? How does the partition function work? We studied one version of the partition function in class and one version in Homework 2. How do the attempts to improve the running time of quick sort work? We studied the median-of-three rule, picking a random pivot.

Read Chapter 3 (on simple sorts), pages 277-294 (merge sort), and pages 325-357 (on quick sort).

4. 1-dimensional and multi-dimensional arrays: How to define and use them in Java. How to make dynamic versions of arrays by resizing them. Why resizing by doubling is much better than resizing by adding one extra slot. What methods does the Vector class from the Java collections framework provide? How to use Vector objects instead of arrays.

Read pages 33-44 on arrays and the documentation on the Vector class at java.sun.com.

5. Graphs: Adjacency matrix representation of graphs. Primitive operations on graphs such as adding a vertex or an edge, deleting a vertex or an edge, getting all the neighbors of a vertex. The myGraph class that we studied in class.

Read pages 615-623 (on graphs and graph representation).

6. Graph traversal: Why is graph traversal useful? How does depth first traversal work? How to implement it using the Stack data structure. How to implement it using recursion. What is a depth first traversal tree? How is it represented? How is it constructed using depth first traversal. How can depth first traversal be used to answer questions about connectivity, paths, etc.

Read pages 623-636 (on depth first traversal).

7. The Stack data structure: Simple array based implementation. Using the Stack data structure from the Java collections framework.

Read pages 115-132 (on stacks and their uses).