COS 216: Algorithms
Spring 2022
Exam 2 information
1. Allowed materials
During the exam:- You are strongly discouraged to use the textbook, your notes, homework, and PDFs I've given you.
- You are not allowed to use other resources (Internet search, friends, etc.).
- You may only use electronic devices (computer, smart phone) to the extent of following exam logistics (below).
2. Exam content
The exam covers everything we have done, up to and including Day 18 (master theorem). While the exam is cumulative, we will focus on what was not already tested. Here are some topics we emphasized since the last exam:- greedy algorithms (chapter 4)
- techniques: greedy stays ahead, exchange argument
- application: interval scheduling, deadline scheduling, shortest paths, minimum spanning trees
- famous named algorithms: Dijkstra, Prim, Kruskal
- divide and conquer (chapter 5)
- recurrence relations
- techniques: recursion tree method (unrolling), substition method (induction), master method (master theorem)
- application: mergesort
- (the rest of chapter 5 will be on the next exam)
- data structures: abstract data types (ADTs) and common implementations, big Oh bounds of common operations
- disjoint sets ADT: implemented via union-find data structure
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.
3. Logistics
Logistics will be identical to Exam 1; review it if you don't remember the procedure.