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.
- 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.
- 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.
- 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.
- 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.
- 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.