OLD CS473: Fundamental Algorithms

Schedule and Lecture Notes


All lecture notes in one big file.
Date Topics Additional reading
Tuesday,
January 20
1: Administrivia, overview, motivation, graph basics, DFS
(notes and handout versions)
Jeff Erickson's notes on induction/proofs
Thursday,
January 22
2: DFS in Directed Graphs and DAGs
(notes and handout versions)
Discussion 1
Tuesday,
January 27
3: Strong connected components
(notes and handout versions)
Thursday,
January 29
4: BFS, Single-source Shortest Paths
(notes and handout versions)
Jeff Erickson's notes
Discussion 2
Tuesday,
February 3
5: Shortest Paths with Negative Edge Lengths
(notes and handout versions)
Jeff Erickson's notes on recurrences
Thursday,
February 5
6: Reductions, Recursion, Divide and Conquer
(notes and handout versions)
Jeff Erickson's notes on recurrences
Discussion 3
Tuesday,
February 10
7: Recurrences, Closest Pair, Quick Sort and Quick Selection
(notes and handout versions)
 
Thursday,
February 12
8: Exponentiation, Binary Search, Intro to Dynamic Programming
(notes and handout versions)
 
Discussion 4
Tuesday,
February 17
9: Dynamic Programming: Longest Increasing Subsequence, Weighted Interval Scheduling
(notes and handout versions)
 
Thursday,
February 19
10: Dynamic Programming: Independent Sets in Trees, Edit Distance
(notes and handout versions)
 
Discussion 5
Tuesday,
February 24
Review session: Lecture
(notes and handout versions)
---- Midterm 1:
7:00 PM to 9:00 PM ARMRY 101
Topics
Thursday,
February 26
11: Dynamic Programming: Shortest Paths, Knapsack
(notes and handout versions)
 
Discussion 6
Tuesday,
March 3
12: Greedy Algorithms: Examples and Proof Techniques
(notes and handout versions)
 
Thursday,
March 5
13: Greedy Algorithms for Minimum Spanning Tree
(notes and handout versions)
 
Discussion 7
Tuesday,
March 10
14: Introduction to Randomized Algorithms
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Thursday,
March 12
15: Randomized Quick Sort and Selection
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Friday, March 13 Drop Deadline  
Discussion 8
Tuesday,
March 17
16: Hash Tables
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Thursday,
March 19
17: Introduction to Network Flows
(notes and handout versions)
 
Discussion 9
March 21 - 29 Spring break
UnThanksgiving Vacation
Tuesday,
March 31
18: Ford-Fulkerson Algorithm for Maximum Flow and Minimum Cut
(notes and handout versions).
 
Thursday,
April 2
19: Applications of Network Flow: Disjoint Paths and Bipartite Matchings
(notes and handout versions)
 
Discussion 10
Tuesday,
April 7
Midterm 2:
7:00 PM to 9:00 PM Armory 101
Review session slides
Topics
Thursday,
April 9
20: More Applications of Network Flow
(notes and handout versions)
Even more notes
 
Discussion 11
Tuesday,
April 14
21: Polynomial time Reductions
(notes and handout versions)
 
Thursday,
April 16
22: SAT and Definition of NP
(notes and handout versions)
 
Discussion 12
Tuesday,
April 21
23: NP-Completeness, Circuit Sat and Cook-Levin Theorem
(notes and handout versions)
 
Thursday,
April 23
24: More NP-Complete Problems
(notes and handout versions)
 
Discussion 13
Tuesday,
April 28
25: Introduction to Linear Programming
(notes and handout versions)
 
Thursday,
April 30
26: Approximation algorithms using Linear Programming
(notes and handout versions)
 
Discussion 14
Tuesday,
May 5
27: Review for the final
(notes and handout versions)
Discussion 15
Final exam Topics: final topics
Thursday, May 14th. May 14, 7pm-10pm Roger Adams Laboratory, 116
Proof.
directions.
Conflict to final exam - you need permission from instructors to take it!
May ???, 7pm-10pm TBD


Additional notes - for no extra charge!

  1. 28: Heuristics, Closing thoughts (notes and handout versions)
  2. 29: coNP and self-reductions (notes and handout versions)

Acknowledgments:
Lecture notes are based on notes of Jeff Erickson, Sariel Har-Peled, Chandra Chekuri and the slides of Mahesh Viswanathan and the books by Kleinberg and Tardos, and by Dasgupta, Papadimitrioiu and Vazirani. The slides and notes are typeset using LaTeX and the beamer package.
Last modified: Tue May 5 12:08:06 CDT 2015