CS473: Fundamental Algorithms (Spring 2013)

Schedule and Lecture Notes


All lecture notes in one big file.
Date Topics Reading
Tuesday,
January 15
1: Administrivia, overview, motivation, graph basics, DFS
(notes and handout versions)
Chapter 0, section 1.1 and 1.2 from textbook, Jeff Erickson's notes on induction/proofs
Thursday,
January 17
2: DFS in Directed Graphs, Strong Connected Components, DAGs
(notes and handout versions)
Slides annotated during lecture
Chapter 3 of book
Discussion 1
Tuesday,
January 22
3: BFS, Single-source Shortest Paths
(notes and handout versions)
Slides annotated during lecture
Chapter 3 of book
Thursday,
January 24
4: Shortest Paths with Negative Edge Lengths
(notes and handout versions)
Chapter 3 of Dasgupta etal book, Jeff Erickson's notes
Discussion 2
Tuesday,
January 29
5: Reductions, Recursion, Divide and Conquer
(notes and handout versions)
Chapter 5, Jeff Erickson's notes on recurrences
Thursday,
January 31
6: Recurrences, Closest Pair, Quick Sort and Quick Selection
(notes and handout versions)
Jeff Erickson's notes on recurrences
Discussion 3
Tuesday,
February 5
Catch up lecture
 
Thursday,
February 7
7: Exponentiation, Binary Search, Intro to Dynamic Programming
(notes and handout versions)
 
Discussion 4
Tuesday,
February 12
8: Dynamic Programming: Longest Increasing Subsequence, Weighted Interval Scheduling
(notes and handout versions)
 
Thursday,
February 14
9: Dynamic Programming: Independent Sets in Trees, Edit Distance
(notes and handout versions)
 
Discussion 5
Tuesday,
February 19
Review session: Lecture
(notes and handout versions)
---- Midterm 1:
7:00 PM to 9:00 PM 1EVRT 151
7:00 PM to 9:00 PM 1LMS 151
Topics
Thursday,
February 21
10: Dynamic Programming: Shortest Paths, Knapsack
(notes and handout versions)
 
Discussion 6
Tuesday,
February 26
11: Greedy Algorithms: Examples and Proof Techniques
(notes and handout versions)
 
Thursday,
February 28
12: Greedy Algorithms for Minimum Spanning Tree
(notes and handout versions)
 
Discussion 7
Tuesday,
March 5
13: Introduction to Randomized Algorithms
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Thursday,
March 7
14: Randomized Quick Sort and Selection
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Friday, March 8 Drop Deadline  
Discussion 8
Tuesday,
March 12
15: Hash Tables
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Thursday,
March 14
16: Introduction to Network Flows
(notes and handout versions)
 
Discussion 9
March 16 - March 24 Spring break
UnThanksgiving Vacation
Tuesday,
March 26
17: Ford-Fulkerson Algorithm for Maximum Flow and Minimum Cut
(notes and handout versions).
 
Thursday,
March 28
18: Applications of Network Flow: Disjoint Paths and Bipartite Matchings
(notes and handout versions)
 
Discussion 10
Tuesday,
April 2
Midterm 2:
7:00 PM to 9:00 PM 1NOYES 217
7:00 PM to 9:00 PM 1MH 103
Review session slides
Topics
Thursday,
April 4
19: More Applications of Network Flow
(notes and handout versions)
Even more notes
 
Discussion 11
Tuesday,
April 9
20: Polynomial time Reductions
(notes and handout versions)
 
Thursday,
April 11
21: SAT and Definition of NP
(notes and handout versions)
 
Discussion 12
Tuesday,
April 16
22: NP-Completeness, Circuit Sat and Cook-Levin Theorem
(notes and handout versions)
 
Thursday,
April 18
23: More NP-Complete Problems
(notes and handout versions)
 
Discussion 13
Tuesday,
April 23
24: P, NP, co-NP, Self Reductions
(notes and handout versions)
 
Thursday,
April 25
Catch up lecture  
Discussion 14
25: Linear programming
(notes and handout versions)
Chapter 9
Discussion 15
Final exam Topics: final topics
May 3, 7pm-10pm 1DKH 114
David Kinley Hall, Room 114.
Proof
Conflict to final exam - you need permission from instructors to take it!
May 6, 7pm-10pm 1EB 160
English Building, Room 160.
Proof

Additional notes - for no extra charge!

Date Topics Reading
26: Heuristics, Closing thoughts
(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 Apr 30 15:26:37 CDT 2013