Lectures
The table below outlines the topics covered so far in lectures and shows what's coming up next lecture.
| Date | Topics | Textbook sections | Additional material |
|---|---|---|---|
| Sept 8. |
Introduction - Basic Notions - gcd Algorithms (Euclid's and sequential checking) |
Sec. 1.1 | Course Syllabus |
| Sept 10. |
Introduction - Algorithmic Problem Solving - Types of Problems |
Secs. 1.2 and 1.3 | Handout 1. on the stable marriage problem (Sec. 1.1 of supplementary reference [KT]) |
| Sept 12. |
Algorithm Analysis - Analysis Framework - Asymptotic Analysis - Analysis of Non Recursive Algorithms |
Secs. 2.1, 2.2, and 2.3 | |
| Sept 15. |
Algorithm Analysis - Analysis of Recursive Algorithms - Examples (Factorials, Tower of Hanoi, Fibonacci Numbers) |
Secs. 2.4, 2.5 | |
| Sept 17. |
Algorithm Analysis - Fibonacci Algorithms - Empirical Analysis of Algorithms Data Structures Review - Lists, Stacks, Queues |
Secs. 2.5, 2.6 and 1.4 | |
| Sept 19. |
Data Structures Review - Graphs - Trees |
Sec. 1.4 | |
| Sept 22. |
Data Structures Review - Heaps - Priority Queues - Sets, Dictionaries Brute Force - Significance - Examples (exponentiation, sorting) |
Sec. 1.4 and 3.1. | Priority Queues - Sec. 2.5 of supplementary reference [KT]. |
| Sept 24. |
Brute Force - Examples (string matching, closest-pair) - Exhaustive Search (theoretical value, traveling salesman problem, knapsack problem) |
Sec. 3.2, 3.3 and 3.4 |
Optional reading: article on the knapsack problem. Below is a link to the abstract. Full article is electronically accessible through the library catalogue. Where Are the Hard Knapsack Problems? David Pisinger. Computers and Operations Research. Volume 32, Issue 9. Sept 2005. Pages: 2271-2284. |
| Sept 26. |
Brute Force - Exhaustive Search (assignment problem) Divide-&-Conquer - Technique and master theorem. - Examples: Mergesort. |
Secs. 3.4. and Ch4, 4.1 | |
| Sept 29. |
Divide-&-Conquer - Examples: Quicksort, Large Integer Multiplication and Strassen's Matrix Multiplication |
Secs. 4.2 and 4.5 |
Proof for O(n log n) average-case run time of quicksort: Average-Case Analysis of Quicksort |
| Oct 3rd. |
Divide-&-Conquer - Examples: Closest-Pair Problem |
Sec. 4.6. | Closest-Pair Algorithm - Sec. 5.4 of supplementary reference [KT]. |
| Oct 6. |
Dynamic Programming - Technique - Examples: Binomial Coefficient, Transitive Closure of a digraph. |
Secs. 8.1 and 8.2 | Growth Rate of the Binomial Coefficient |
| Oct 8. |
Dynamic Programming - All-Pairs Shortest Paths Problem - Optimal Binary Search Trees |
Secs. 8.2 and 8.3 | |
| Oct 10. |
Dynamic Programming - Optimal Binary Search Trees (Con't) - Knapsack Problem |
Secs. 8.3 and 8.4 | |
| Oct 15. |
Dynamic Programming - Knapsack Problem (Con't) - Memory Functions |
Sec. 8.4 | |
| Oct 17. |
Midterm Exam - no lecture |
||
| Oct 20. |
Greedy Technique - The minimum spanning tree problem (Prim's algorithm) |
Sec. 9.1 | |
| Oct 22. |
Greedy Technique - The single-source shortest-paths problem (Dijkstra's algorithm) |
Sec. 9.3 | |
| Oct 24. |
Greedy Technique - Huffman Trees |
Sec. 9.4 | |
| Oct 27. |
Iterative Improvement - Technique - The Maximum-Flow Problem (Ford-Fulkerson/Augmenting-Path Method) |
Sec. 10.2 | |
| Oct 29. |
Iterative Improvement - The Maximum-Flow Problem: Shortest-Augmenting Path Algorithm |
Sec. 10.2 | |
| Oct 31. |
Iterative Improvement - Max-Flow/Min-Cut Proof of Optimality (for the Ford-Fulkerson/Augmenting-Path Method): - The Maximum Bipartite Matching Problem |
Sec. 10.2. | Lecture Notes |
| Nov 3rd. |
Limitations and NP-Completeness - Overview - Lower-Bound Arguments (Trivial Lower Bounds) |
Sec. 11.1 | |
| Nov 5. |
Limitations and NP-Completeness - Lower-Bound Arguments (Trivial - con't, Information-Theoretic, Adversary) |
Sec. 11.1 | |
| Nov 7. |
Limitations and NP-Completeness - Decision Trees |
Sec. 11.2 | |
| Nov 10. |
Limitations and NP-Completeness - Intractability, Class P, and Problem Reduction |
Sec. 11.3 and problem reduction in Sec 11.1. | |
| Nov 12. |
Limitations and NP-Completeness - Class NP and NP-Completeness |
Sec. 11.3. | Handout on Independent Set and Vertex Cover |
| Nov 14. |
Limitations and NP-Completeness - Undecidability - Example of Polynomial Reducibility (Hamiltonian circuit and traveling Salesman Problem). Dealing with Hard Problem - Backtracking |
Secs. 11.3 and 12.1. | |
| Nov 17. |
Dealing with Hard Problem - Comments on P and NPC problems - Backtracking (Hamiltonian Circuit Problem) |
Sec. 12.1. |
Optional reading: The breakthrough discovery of a deterministic polynomial-time algorithm for primality testing (a problem that was not known to be in P or NPC until recently, however the problem of factoring composite numbers is not known to be in P or NPC). PRIMES is in P. Manindra Agrawal, Neeraj Kayal and Nitin Saxena. Annals of Mathematics, Volume 160, Number 2 (2004), pages 781-793. |
| Nov 19. |
Dealing with Hard Problem - Backtracking (Subset Sum Problem) - Branch-and-Bound |
Secs. 12.1. and 12.2 | |
| Nov 21. |
Dealing with Hard Problem - Branch-and-Bound (TSP) - Discussion of Diverse Subset problem |
Sec 12.2 | |
| Nov 24. |
Dealing with Hard Problem - Discussion of Efficient Recruiting problem - Branch-and-Bound (Knapsack) - Approximation Algorithms for NP-hard Problems (Definitions) |
Secs 12.2 and 12.3 | |
| Nov 26. |
Dealing with Hard Problem - Approximation Algorithms for NP-hard Problems: - Inequivalence of NP-hard problems - Theorem 1 for TSP, Nearest Neighbor heuristic algorithm for TSP, Euclidean TSP |
Sec 12.3 | |
| Nov 28. |
Dealing with Hard Problem - Approximation Algorithms for NP-hard Problems: - Twice-around-the-tree algorithm for TSP, Theorem 2 for Euclidean TSP. - Local Search Algorithms: Local search 2-opt heuristic algorithm for TSP - Approximation Algorithms for Knapsack: Greedy, Enhanced 2-approx Greedy, and Fractional Knapsack |
Sec 12.3 | Bounded Approximation Algorithm for Knapsack |
| Dec 1. |
Review Lecture - Review of course topics - A job scheduling problem |
Weighted Job Scheduling problem |