Topics for the final
December 15th, 9:45-11:45, 107 EPB
Below I have listed 5 topics that you will be tested on.
I have also listed what you should read for each topic.
There will be 5 problems on the final exam, one problem for each topic, each problem worth 50 points for
a total of 250 points.
The exam is worth 25% of your overall grade.
Each problem will have 3 or 4 parts and I expect you to spend about 20 minutes on each problem.
Each topic listed below corresponds to an important data structure that we have studied.
For each data structure you need to know:
- What operations are typically supported by the data structure
- Algorithms for implementing these operations
- Running times of these algorithms
- Some details of Bailey's implementations of these data structures
- One or two major applications of these data structures (for example, application of queues to BFS)
I expect that all your answers will be fairly short.
Any java code fragment or function you write will be no longer than 10 lines
of code.
Some possibilities for a typical question on the exam are: (i) add a small new function to Bailey's implementation
of a data structure or (ii) how might you implement a small variant of one of the data
structures listed below or (iii) analyze the running time of one of Bailey's implementations.
- Linked lists
- Chapter 8, class notes, discussion section notes, Quizzes 5 and 6, and Project 2
- Singly linked lists, doubly linked lists, circularly linked lists
- Bailey's implementation of these data structures (SinglyLinkedList, DoublyLinkedList, CircularList)
- The running time of various operations on these data structures
- Adjacency list representation of graphs as an application of linked lists
- Queues
- Section 9.2, class notes, discussion section notes, Quiz 7, and Project 2
- Bailey's implementation of Queues using arrays, Vectors, and lists (QueueArray, QueueVector, and QueueList)
- The running time of various operations on the queue data structure
- Using queues to implement BFS on graphs
- Stacks
- Section 9.1, class notes, discussion section notes and Quizzes 7 and 8
- Bailey's implementation of stacks using arrays, Vectors and linked lists (StackArray, StackVector, StackList)
- The running time of various operations on the stack data structure
- Using stacks to implement DFS on graphs
- A recursive implementation of DFS that does not explicitly use stacks
- Using stacks to simulate recursion
- Binary heaps
- Section 12.4, class notes, discussion section notes, Quiz 9, and Project 3
- Bailey's implementation of binary heaps (VectorHeap)
- The running time of various operations on the heap data structure
- Heapsort
- Implementation of Dijkstra's shortest path algorithm using binary heaps
- Binary trees and binary search trees
- Sections 11.4, 11.6, 13.1, and 13.7, class notes, discussion section notes, and Quiz 10
- Bailey's implementation of binary trees (BinaryTree) and binary search trees (BinarySearchTree)
- The running time of various operations on the binary tree and binary search tree data structures
- Red-black trees, the 5 red-black tree properties, and what these properties imply about the height of a red-black tree.