 # 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