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.