| Lecture (date) | Summary | Assignments and Handouts |
|---|---|---|
| L1 (2016/08/24) |
Introduction to the course - administrative and topical. |
Read all of Chapter 1 of the text Do Qns 1.2-2 and 1.2-3 of the text |
| L2 (2016/08/29) |
Pseudo-code: illustrated on insertion sort. The RAM model and running-time analysis. Divide and conquer; setting up recurrences. Merge sort as an example. Slides used in class |
Read Chapter 2.1 - 2.3 of the text HW1 is available here - due back on September 7th |
| L3 (2016/08/31) |
Review of divide and conquer: Karatsuba Multiplication Asymptotic notation: definition and properties The egg-drop problem Slides used in class |
Read Chapter 3.1 of the text Do questions 3.1-1, 3.1-3, 3.1-4, 3-1, and 3-2 |
| L4 (2016/09/07) |
Setting up and solving recurrences: the Master Method Camels and bananas |
Read Ch 4, pages 65-67. Read Section 4.5 Do questions 4.5-1 and 4.5-4. Do question 4.2 a. HW2 is available here - due back on September 21st (Here are the solutions. See our class piazza page for corrections) |
| L5 (2016/09/12) |
Some Master Method examples Some Divide and Conquer examples: integer exponentiation; counting inversions The Substitution method of solving recurrences: guessing a solution using unrolling |
|
| L6 (2016/09/14) |
The Substitution method of solving recurrences: recursion trees and proof by induction Further examples of Divide and Conquer |
Read Sections 4.3 and 4.4 of the text Do exercises 4.3-3, 4.3-6, 4.3-8, and 4.3-9 Do exercises 4.4-3, 4.4-5, 4.4-9 |
| L7 (2016/09/19) |
Probability and algorithms: average-case analysis and randomized algorithms A brief introduction to probability Linearity of expectation - The hiring problem. The coupon collector problem |
Read Sections 5.1 and 5.2 of the text Do exercises 5.2-2 and 5.2-5 |
| L8 (2016/09/21) |
Randomized algorithms and Expected Value The Randomized version of the Hiring Problem Randomly permuting an array Sorting - running time and in-place |
Read Section 5.3 (pages 122-124 and 126).
Read Sections 7.1-7.2 |
| L9 (2016/09/26) |
Characterizing sorting algorithms -- running time, in-place, stability Quicksort and randomized quicksort Average-case/ worst-case expected analysis of quicksort and randomized quicksort |
Read Sections 7.3-7.4 |
| L10 (2016/09/28) | In-class test | |
| L11 (2016/10/3) |
Exam review Order Statistics. Selection in expected linear time. Selection in worst-case linear time |
Read Sections 9.2-9.3 Do Exercises 9.3-1, 9.3-3, 9.3-8 |
| L12 (2016/10/5) |
(Guest lecture by Kecheng Yang) Lower bound for comparison-based sort Linear-time sorts: counting sort and radix sort Sorting in average-case linear time: bucket sort |
Read Chapter 8 of the text (skip the derivation of bucket-sort's average-case running time) |
| L13 (2016/10/10) |
Dynamic programming illustrated: the egg-drop problem Principles of dynamic programming |
HW3 is available here - due back on October 19th. (Here are the solutions.) |
| L14 (2016/10/12) | Further DP examples: rod-cutting and 0/1 integer knapsack |
Read Sections 15-1 and 15-3 Do Exercises 15.1-3, 15.3-5 |
| L15 (2016/10/17) |
Further examples of DP: making change and activity selection Greedy algorithm example: making change in certain currencies |
Chapter 16: read pages 414-416 and 423-425 Do Exercise 16.1-1 |
| L16 (2016/10/19) |
The greedy strategy: activity selection Huffman encoding |
Chapter 16: read Sections 16.1 - 16.3 Do Exercise 16.1-3, 16.1-5, 16.2-3, 16.3-3 |
| L17 (2016/10/24) |
Introduction to intractability Tractable = running time is polynomial in size of input |
Read Chapter 34.1 Do Exercise 34.1-4 HW4 is available here - due back on November 2nd |
| L18 (2016/10/26) |
Review: efficiency and polynomial running time Reducibility amongst problems Decision versions of optimization problems - illustrated on 0/1 Knapsack Reduction illustrated: Partition to 0/1 Knapsack |
Do Exercise 34.1-5 |
| L19 (2016/10/31) |
Representing Decision Problems as Languages Reduction illustrated: Partition to Parallel Machine Scheduling Verification algorithms and the class NP |
Read Chapter 34.2 (up to and including the definition of NP on page 1064). Read Chapter 34.3 up to page 1069 Do Exercise 34.5-3. Read Chapter 34.5.5 for a description of the Subset Sum Problem, and do Exercise 34.5-4 Do Exercise 34.5-5 by reducing the Subset Sum Problem to the Partition Problem (for this question, pretend that you do not already know that Partition is NP-Complete) |
| L20 (2016/11/2) |
Designing 2-input Verification algorithms. Designing polynomial-time recognition algorithms The complexity classes P, NP, and co-NP of languages Showing languages to be in NP (and in P) Another reduction example: Partition to Bonnie and Clyde |
Read rest of Chapter 34.2. Read Lemma 34.8 of Chapter 34.4 Do Problem 34-2 |
| L21 (2016/11/7) | In-class test | |
| L22 (2016/11/9) |
A first NP-complete problem: circuit satisfiability
Slides used in class |
Read pages 1070-1077 of the text. |
| L23 (2016/11/14) |
Wrapping up NP-completeness. Review of the Circuit Satisfiability hardness proof. Some additional reduction examples Overview of other complexity classes and the polynomial-time hierarchy |
Read Theorems 34.9 and 34.10 (and their proofs). Do problems 34-2 and 34-4 |
| L24 (2016/11/16) |
Introduction to graphs (a review): Concepts, terminology, notation, and representation Topological sort Slides used in class |
Read Chapter 22.1 of the text Do Exercises 22.1-3, 22.1-5, and 22.1-6, and Exercise 22.4-5 |
| L25 (2016/11/21) | Shortest-path problems -- definition, concepts, and terminology. All-pairs shortest paths via Dynamic Programming: Theta(V^4) and Theta(V^3 log V) algorithms | Read Chapter 24, pages 641-647, and Chapter 25, pages 684-691 |
| L26 (2016/11/28) |
APSP: The Floyd-Warshall Algorithm Single-source shortest paths - preleminaries |
Read Chapter 25.2. Read Chapter 24, pages 647-649 Do Exercises 25.2-4 and 25.2-6 |
| L27 (2016/11/30) | In-class test | |
| L28 (2016/12/5) | Single-source shortest paths: The Bellman-Ford and Dijkstra algorithms |
Read Chapters 24.1 and 24.3 of the text. Do Exercises 24.1-1, 24.1-3, 24.3-1, 24.3-2, and 24.3-4 |
| L29 (2016/12/7) |
Course review
The slide used in class |
