| Lecture (date) | Summary | Assignments and Handouts |
|---|---|---|
| L1 (2016/01/11) |
Introduction to the course - administrative and topical. Insertion sort pesudocode Slides used in class |
Read all of Chapter 1 of the text Do Qns 1.2-2 and 1.2-3 of the text Read Chapter 2.1 of the text Do Qn 2.1-3 of the text |
| L2 (2016/01/13) |
Loop invariants The RAM model and running-time analysis Divide and conquer; setting up recurrences Merge sort and integer multiplication Slides used in class |
Read Chapter 2.2 and 2.3 Review (make sure you somewhat familiar with) Chapter 3.2, and the following parts of Appendix A: A.1 up to formula (A.7); A.2 - the first section (titled Mathematical induction) HW1 is available here |
| L3 (2016/01/20) |
Asymptotic notation - Big-Oh, Omega, Theta, little-oh, and little-omega. Definitions and use Divide and conquer: setting up recurrences Slides used in class |
Read Chapter 3.1 of the text. Do Questions 3.1-2, 3-2 Chapter 4: Read pages 65-67 of the text |
| L4 (2016/01/25) | No class - Adverse weather alert (Condition 2) | |
| L5 (2016/01/27) |
Solving recurrences: the Master Theorem and the Substitution Method. |
Readings from Chapter 4: intro (pages 65-67). Chapter 4.5: The Master method. Chapter 4.3: The Substitution method. HW2 is available here |
| L6 (2016/02/1) |
Solving recurrences: a review of Proof by Induction. The substitution method. Guessing a solution: the iteration method. The recursion tree method. Slides used in class |
Read Chapter 4.4 Review Proof by Induction |
| L7 (2016/02/3) |
Further examples of the recursion tree method. Brief review of sorting: running time and memory requirements ("in place" sorting) Intro to probability. The Hiring Problem: worst-case and average-case analyses Some notes outlining topics on probability discussed in class |
Read Chapter 5.1 and 5.2 Do Questions 5.2-1, 5.2-5 |
| L8 (2016/02/8) |
The Hiring Problem: expected-case analysis. Randomizing an array Quicksort and Randomized quicksort, description and analysis Slides used in class |
Read Chapter 5.3 (you may skip the proofs of correctness for the array-permuting algorithms)
Read Chapter 7 |
| L9 (2016/02/10) |
Linear-time randomized selection Lower bound on comparison-based sorting Linear-time sorting: counting sort and radix sort. |
Read Chapter 9.2 (you may skip the derivation of the expected running time) Read Chapter 8.1 - 8.3 Do questions 8.3-1 and 8.3-3 HW3 is available here |
| L10 (2016/02/15) | No class - Adverse weather alert (Condition 2) | |
| L11 (2016/02/17) |
Sorting in average linear time -- bucket sort. Order statistics: maximum and minimum. Linear-time deterministic selection Introduction to graphs Slides used in class |
Read Chapter 8.4 (you may skip the analysis) Read Chapter 9.1 and 9.3 Do questions 8.4-2, 9.3-1, and 9.3-5 Read Chapter 22.1 |
| L12 (2016/02/22) |
Shortest paths in graphs: concepts. Review for mid-term |
Chapter 24: Read pages 642-650 of the text |
| L13 (2016/02/24) | First in-class exam | |
| L14 (2016/02/29) | Dynamic Programming. Introduction via rod-cutting and Floyd-Warshall APSP |
Read Chapter 15.1 (you can skip the "subproblem graphs" portion) Read Chapter 25.2 Practice problems: 15.1-2, 15.1-3 |
| L15 (2016/03/02) |
Dynamic programming examples: knapsack (integer and 0-1). Shortest path via matrix multiplication |
Read Chapter 25.1 The 0-1 knapsack problem is defined on page 425. Practice problems: 16.2-2 and 16.2-3 HW4 is available here (due back: March 24th - after Spring Break) |
| L16 (2016/03/07) |
Dynamic programming example: making change. (Introducing [Integer] Linear Programs. Introducing Greedy Algorithms)
Shortest Paths vis Matrix multiplication: the O(V^4) and the O(V^3 log V) solutions Review of some questions from the mid-term |
Practice problems: 25.1-1 and 25.1-2 |
| L17 (2016/03/09) |
Dynamic programming examples, including Optimal Binary Search Trees (Guest lecture by Zhishan Guo) |
|
| L18 (2016/03/21) | The Greedy strategy: introduction. The Activity Selection Problem. |
Read Chapter 16.1
Practice problems: 16.1-1, 16.1-3, 16.1-5 |
| L19 (2016/03/23) |
Elements of the Greedy Strategy DP on 0/1 Knapsack. A greedy algorithm for knapsack (that does not work). A 2-approximation algorithm for knapsack Data compression: Huffman codes |
Read Chapter 16.2
Practice problem: 16.2-5, |
| L20 (2016/03/28) |
Huffman encoding - algorithm and proof of correctness BFS on graphs |
Read Chapter 16.3. Read Chapter 22.2
Practice problems 16.3-2, 16.3-3, 22.2-2, 22.2-4 |
| L21 (2016/03/30) |
BFS: running time Single-source shortest path problems - definition and notation Dijkstra's SSSP algorithm Slides used in class |
Read Chapter 24.3
Practice problems: 24.3-1, 24.3-4 |
| L22 (2016/04/04) | Second in-class exam | |
| L23 (2016/04/06) |
Minimum Spanning Trees Introducing NP-Completeness |
Read Chapter 23.1 and Kruskal's algorithm from Chapter 23.2
Practice problems. 23.1-7, 23.1-8 |
| L24 (2016/04/11) | NP-Completeness: the class of problems P. Showing problems to (probably) not be in P | Read the subsection Overview of showing problems to be NP-complete (pages 1050-1052) in the text |
| L25 (2016/04/13) |
Polynomial-time algorithms - running times in terms of input size Showing problems to be hard: Decision Problems and Reductions Illustration: the knapsack problem (<- Partition) Defining the class NP of (decision) problems Another example reduction: Partition -> bin-packing Slides used in class |
|
| L26 (2016/04/18) |
Some more examples polynomial-time reductions: Partition to non-preemptive real-time scheduling; Hamiltonian circuit to TSP Two-input verification algorithms The class NP; NP-Complete problems |
Read Chapters 34.3 (up to, but not including, circuit satisfiability).
Chapter 34.5.4 describes the HAM-CYCLE to TSP reduction
HW5 is available here (due back on April 27) |
| L27 (2016/04/20) |
Showing problems to be in NP Showing problems to be NP-Complete The first NP-C problem: circuit satisfiablity |
Read Chapters 34.4 |
| L28 (2016/04/25) |
The class c--NP Showing circuit satisfiability to be in NP, and NP-hard Some other NP-complete problems - SAT, 3CNF-SAT, clique, vertex cover Slides used in class |
Read the proofs of Lemmas 34.5 and 34.6 |
| L29 (2016/04/27) |
Summarizing the course
Slides used in class |