This term we will be using Ed Stem for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TA, and instructors. Rather than emailing questions to the teaching staff, we encourage you to post your questions on Ed
Find our class signup link at Brightspace under the syllabus: https://edstem.org/us/join/kZnuVH
| Topics |
Class presentations on transparencies/slides posted on this page may be useful |
| 1. Background, sorting, searching |
a. Big O- and Big-Omega [slides] |
| b. Heap sort
[transparencies] |
|
| c. Quick sort [transparencies] |
|
| d. Selection [transparencies] |
|
| e. Search trees [transparencies] |
|
| 2. Dynamic Programming |
a. Dynamic programming principles [slides] b. Dynamic programming example [transparencies] c. More dynamic programming examples [transparencies] |
| 3. Greedy Algorithms |
a. Greedy strategy in scheduling [transparencies] b. More problems solved with greedy strategy [ slides ] |
| 4. Amortization |
a. Amortization principle [transparecies] b. Fibinacci Heap I [transparencies] c. Fibonacci Heap II [transparencies] d. Union-Find [transparencies] |
| 5. Graph search |
a. Depth first search (DFS) [transparencies] b. Breadth first search (BFS) [transparencies] c. Topological sort [transparencies] |
| 6. Graph algorithms |
a. Minimum spanning tree [transparencies] b. Single source shortest path [transparencies] c. All-pairs shortest path [transparencies] d. Network flow [transparencies] e. Max-flow, min-cut [transparencies] f. Edmond-Karp algorithm [transparencies] |
| 7. Linear programming |
a. Framework [transparencies] b. Simplex algorithm [transparencies] c. Duality [transparencies] d. LP rounding and vertex cover [transparencies] |
| 8. Approximation Algorithms |
a. Vertex-cover and TSP [transparencies] b. TSP with 1.5-approximation [transparencies] c. Set-cover [transparencies] d. Subset-sum [transparencies] |
| 9. Randomization |
a. Randomized LP rounding [transparencies] b. Randomized global mincut [slides] c. Randomized max 3-SAT [transparencies] |
| 9. NP-completeness |
a. Intractability [slides] b.NP-completeness [slides] c. Reductions [slides] |
| Homework |
25% |
| Midterm |
35% |
| Final |
40% |