Lecture 1: Course overview. Complete enumeration and the Traveling Salesman Problem. Introduction to Dynamic Programming.
Lecture 2: More Dynamic Programming: Matrix Multiplication and the Longest Common Subsequence Problem.
Lecture 3: Algorithms for Minimum Weight Spanning Trees and introduction
to the theory of the
Greedy Algorithm.
Lecture 4: The Greedy Algorithm for Weighted Matroids and proof of its correctness.
Lecture 5: Revision of BFS and DFS on a digraph. Determining Shortest Paths using BFS.
Lecture 6: DFS and some applications. Topological Sorting and finding strongly connected components in digraphs.
Lecture 7: Proof of correctness of the algorithm for strongly connected components in digraphs. (Here are some lecture notes on the topic.)
Lecture 8: Graph searching: Dijkstra's algorithm and the Bellman-Ford algorithm for single-source shortest paths.
Lecture 9: All pairs shortest paths: Johnson's algorithm and the Floyd-Warshall algorithm.
Lecture 10: Introduction to Flows on networks and the Max. Flow-Min. Cut Theorem.
Lecture 11: The Ford-Fulkerson algorithm for max. flows in networks.
Lecture 12: Applications: matchings in bipartite graphs and disjoint paths in connected graphs. ( Here are some lecture notes on the Maximum Matching-Minimum Cover Theorem for bipartite graphs.)
Lecture 13: Introduction to Linear Programming. Definitions and a few examples. We gave the three forms a linear program can have and ways to transform an LP in general form either to canonical form or to standard form.
Lecture 14: Duality in Linear Programming. Proof of the Weak duality theorem and statement of the Strong duality Theorem. Proof of the complementary slackness conditions. The dual of the max-flow problem.
Lecture 15: Certificates for feasibility, infeasibility and uboundedness of a linear program.
Lecture 16: Turing Machines and complexity classes.
Lecture 17: Non-deterministic Turing Machines and the class NP. Examples.
Lecture 18: The notion of (polunomially many-one or Karp) reduction. Completeness. Statement of Cook's Theorem.
Lecture 19: Proof of Cook's Theorem.
Lecture 20: We completed the proof of Cook's Theorem and we proved the NP-completeness of 3-SAT.
Lecture 21: 2-SAT is in P. Variantions of 2-SAT that are NP-complete.
Lecture 22: Some more comments on 2-SAT. The problemMAX-2-SAT.
Lecture 23: The NP-completeness of some graph-theoretic problems: independent
set, vertex cover and the clique problem.
Lecture 24: The Not-All-Equal-SAT problem and the 3-colourability problem.
Lecture 25: Proof the NP-completeness of the 3-colourability problem.