Topics for the final

Dec 15th, Thursday, 7:30am-9:30am, 107 EPB

Below I have listed 5 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 final, one problem on each of the 5 topics mentioned below. Each problem will be worth 40 points for a total of 200 points. The exam is worth 20% of your overall grade.

  1. Linked lists: How would a singly/doubly/circular linked list object be defined in Java? How would basic operations such as insert, delete, search, etc be implemented on these linked lists? What is the running time of these operations?

    Read all of Chapter 5.

  2. The heap data structure: What is a binary heap? What operations does a binary heap usually support and how are these implemented? What is the running time of these operations? What is the heapSort algorithm and what is the argument that heapSort runs in O(nlog(n)) time?

    Read all of Chapter 12.

  3. Dijkstra's shortest path algorithm: What is Dijkstra's shortest path (DSP) algorithm? How does it differ from breadth-first traversal? Under what circumstances does DSP work and when does it not work? What is the running time of DSP as a function of n (number of vertices) and m (number of edges) when we use the heap data structure to store vertices and their distance estimates? What is the running time if we just use an unsorted array? Make sure that you know the actual running time analysis of DSP in these two situations.

    Read the description of DSP from the textbook, pages 687-707. Also read the description from Project 3 handout. Running time analysis was done in class.

  4. Binary search trees: What is a binary search tree? What operations does it support? How is a binary search tree implemented in Java? What is the running time of the typical binary search tree operations? What are worst case examples for the running time of these operations?

    Read all of Chapter 8.

  5. Red-black trees: What is a red-black tree? Given a binary search tree with nodes colored red/black, you should be able to determine if the tree is a red-black tree or not. Given a binary search tree, you should be able to turn it into a red-black tree, if possible. Why is the height of a red-black tree O(log n)? How does the insert operation on a red-black tree work? You will not be asked to write code, but you should be able to show how insert works on examples. Specifically, you should know what the three cases for insert are and what happens when you perform left/right rotation.

    Read all of Chapter 9.