| Lecture (date) | Summary | Handouts/ Assignments |
|---|---|---|
| L1 (2018/01/16) |
Introduction to the course - administrative and topical. |
Read all of Chapter 1 of the text A brief outline of the lecture |
| L2 (2018/01/18) |
Pseudocode; the RAM machine model; Algorithm efficiency & Asymptotic analysis Proving programs correct: loop invariants Algorithm design technique: Divide and conquer. Run-time analysis via recurrences. Examples: merge-sort, egg-drop |
Read all of Chapter 2 of the text A brief outline of the lecture Look through homework assignment 1 before the next lecture; we will discuss it then |
| L3 (2018/01/23) | Divide and conquer: further examples. Review of Asymptotic (Big-Oh) notation |
Read Chapter 3, Section 3.1 of the text
A brief outline of the lecture. |
| L4 (2018/01/25) |
Asymptotic notation: o and lower-case omega D&C Examples: maximum subsequence array sum, counting inversions The substitution method of solving recurrences |
Read the introductory material in Chapter 4, as well as Sections 4.1 and 4.3
A brief outline of the lecture. |
| L5 (2018/01/30) |
D&C example: Quick-sort Recursion-tree method for guessing solutions to recurrences D&C example: Deterministic Selection in linear time |
Read Sections 7.1 and 7.2 (quick-sort), Section 4.4 (Recursion trees), and Section 9.3 (selection) |
| L6 (2018/02/01) |
Deterministic selection in linear time The Master Method: statement and (outline of) proof Introducing Dynamic Programming: computing Fibonacci numbers; rod-cutting Memoization and bottom-up implementations of DP |
Read Section 2.4.5 and 4.6.1 of the text (the Master Method)
Look through homework assignment 2 before the next lecture; we will discuss it then |
| L7 (2018/02/06) | DP examples: Rod-cutting and egg-drop |
Read Section 15.1 of the text Announcement: the due-date for HW2 will be postponed (and some question[s] added to it) |
| L8 (2018/02/08) |
DP examples: Longest Increasing Sequence and 0-1 Knapsack
Principles of Dynamic Programming |
Read Section 15.3 of the text (The 0-1 knapsack problem is described in page 425 of your text) The updated version of homework assignment 2 may be found here; it's due on Sunday Feb 18th |
| L9 (2018/02/13) |
Principles of DP: continued. These principles applied to Activity Selection Greedy algorithms: a greedy algorithm for activity selection The coin change problem |
Read Sections 15.4 and 16.1 of the text |
| L10 (2018/02/15) |
The Greedy strategy: Principles Application to Activity Selection and coin-change Introduction to Huffman condes |
Read Section 16.2 of the text Look through homework assignment 3 before the next lecture; we will discuss it then Here's a revised version (a typo - Theorem 15.1 incorrectly referred to as Theorem 15.5 - has been fixed) |
| L11 (2018/02/20) |
The greedy strategy: Huffman encoding Introducing shortest-path problems on graphs |
Huffman codes: Read Section 16.3 of the text Representation of Graphs: Read Section 22.1 of the text Announcement: the first in-class exam will be held on March 6th |
| L12 (2018/02/22) |
Shortest paths: Optimal substructure property A DP algorithm for single-source SP: The Bellman Ford algorithm No negative edges: greedy choice property and Greedy algorithm: The Dijkstra algorithm |
Read Chapter 24 - the introductory material, 24.1 (Bellman-Ford) and 24.3 (Dijkstra)
Here's a practice test |
| L13 (2018/02/27) |
All-pairs shortest paths: Matrix multiply and Floyd-Warshall Introduction to probabilistic analysis |
All-pairs Shortest Paths: Read Chapters 25.1-25.2 The Hiring Problem is described in Chapter 5.1; Appendix C.2 discusses probability |
| L14 (2018/03/1) | Probabilistic analysis of the hiring problem and quick-sort. Randomized quicksort |
Chapter 5.2 discusses analysis of the hiring problem Randomized quick-sort, and its analysis, are discussed in Chapters 7.3 and 7.4 |
| L15 (2018/03/6) | In-class exam (on lectures 1 - 11) | Here are some sample solutions (hopefully, without any bugs!) |
| L16 (2018/03/8) | No class |
Look through homework assignment 4 before the next lecture; we will discuss it then |
| L17 (2018/03/20) |
Probabilistic analysis: review. Application to the hiring problem and randomized quick-sort Conditional probabilities. Randomly permuting an array (Randomize-in-place) |
The pseudocode and analysis of Randomize-in-place are in pages 126-128 of the text |
| L18 (2018/03/22) |
Independent RVs. Analysis of Randomized Selection Introducing intractability |
The randomized selection algorithm, and its analysis, are covered in Section9.2 of the text. |
| L19 (2018/03/27) | No class | |
| L20 (2018/03/29) | In-class exam on lectures 11 - 18 (excluding Huffman encoding) | Sample solutions |
| L21 (2018/04/3) |
Intractability and Lower Bounds Reductions for lower bounds: Reducing sorting to Priority Queue implementations Decision versus optimization problems. A formal-language representation of decision problems Polynomially-related encodings of abstract problems |
Read the introductory material (pages 1048-1053) of Chapter 34 The sorting lower bound is discussed in Chapter 8.1 |
| L22 (2018/04/5) |
The Hamilton cycle problem and TSP. Reducing the Hamilton cycle problem to TSP Polynomial time. Example algorithms that are and are not polynomial-time algorithms |
The Hamilton cycle problem is described on pages 1061-1062. The TSP, and the reduction, are in Section 34.5.4 (pages 1096-1097)
Review some of algorithms we have previously discussed in class (such as rod-cutting, activity selection, etc), and determine whether these algorithms have polynomial running time of not |
| L23 (2018/04/10) |
The classes P, NP, co-NP, and NPC Introducing CIRCUIT-SAT: a first NPC problem |
Read Sections 34.1 - 34.3 of the text Practice problems: 34.1-3, 34.1-4, 34.1-5, 34.3-1, 34.3-2 |
| L24 (2018/04/12) |
Showing CIRCUIT-SAT to be NP-complete Showing SAT, 3CNF-SAT, and CLIQUE to be NP-complete |
CIRCUIT-SAT, SAT and 3CNF-SAT are discussed in Section 34.4 of the text; CLIQUE is discussed in Section 35.5.1
Read up on the VERTEX-COVER problem (Sec 35.5.2) on your own. Look through homework assignment 5 before the next lecture; we will discuss it then |
| L25 (2018/04/17) | Some more NP-completeness proofs: SUBSET-SUM, PARTITION, MULTIPROCESSOR SCHEDULING, REAL-TIME SCHEDULING | SUBSET-SUM is discussed in Section 34.5.5; PARTITION is Exercise 34.5-5 |
| L26 (2018/04/19) | Example of Intractability analysis, and of dealing with intractability: the Restricted Shortest Paths problem. Proof of intractability. Dynamic Programming algorithm. | |
| L27 (2018/04/24) | ||
| L28 (2018/04/26) | In-class exam (comprehensive) |