COS 216: Algorithms
Spring 2024
Exam 1 information
1. Logistics
- Notes and textbooks are not allowed on exams.
- Electronic devices (calculator, laptop, smart phone) are not allowed on exams.
- Since this class is scheduled within the 70-minute C4 block, you may use the entire 70 minutes.
2. Exam content
The exam covers everything we have done, up to and including Chapter 3. (Chapter 4 will be on the next exam.) Here are some topics we emphasized:- stable matching problem: deferred acceptance algorithm, details of the algorithm, proof that the algorithm works
- algorithm analysis: worst-case running time, big Oh notation
- the running time of any algorithm should be given in $O(.)$ notation; moreover:
- while a $O(n^2)$ algorithm is also $O(n^5)$, write the first one as it is smaller
- $O(n^2)$ and $O(23n^2+216n+55112)$ are the same, so write the first one as it is simpler
- data structures: abstract data types (ADTs) and common implementations, big Oh bounds of common operations
- list ADT: implemented via array, linked list
- stack ADT
- queue ADT
- priority queue ADT: implemented via heap
- graph ADT: implemented via adjacency matrix, adjacency lists
- graphs:
- big Oh bounds based on $n$ (number of vertices) only
- big Oh bounds based on both $n$ and $m$ (number of edges)
- traversal: BFS, DFS
- bipartite testing
- directed graphs
- (strongly) connected components
As usual, please note that this document is not a contract. I may have inadvertently left something off that ends up on an exam question. Moreover, I will not be able to test all of this material given the time limitations of the exam. I will have to pick and choose some subset of it.