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.22 and 1.23 of the text 
L2 (2016/08/29) 
Pseudocode: illustrated on insertion sort. The RAM model and runningtime analysis. Divide and conquer; setting up recurrences. Merge sort as an example. 
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 eggdrop problem 
Read Chapter 3.1 of the text Do questions 3.11, 3.13, 3.14, 31, and 32 
L4 (2016/09/07) 
Setting up and solving recurrences: the Master Method Camels and bananas 
Read Ch 4, pages 6567. Read Section 4.5 Do questions 4.51 and 4.54. 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.33, 4.36, 4.38, and 4.39 Do exercises 4.43, 4.45, 4.49 
L7 (2016/09/19) 
Probability and algorithms: averagecase 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.22 and 5.25 
L8 (2016/09/21) 
Randomized algorithms and Expected Value The Randomized version of the Hiring Problem Randomly permuting an array Sorting  running time and inplace 
Read Section 5.3 (pages 122124 and 126).
Read Sections 7.17.2 
L9 (2016/09/26) 
Characterizing sorting algorithms  running time, inplace, stability Quicksort and randomized quicksort Averagecase/ worstcase expected analysis of quicksort and randomized quicksort 
Read Sections 7.37.4 
L10 (2016/09/28)  Inclass test  
L11 (2016/10/3) 
Exam review Order Statistics. Selection in expected linear time. Selection in worstcase linear time 
Read Sections 9.29.3 Do Exercises 9.31, 9.33, 9.38 
L12 (2016/10/5) 
(Guest lecture by Kecheng Yang) Lower bound for comparisonbased sort Lineartime sorts: counting sort and radix sort Sorting in averagecase linear time: bucket sort 
Read Chapter 8 of the text (skip the derivation of bucketsort's averagecase running time) 
L13 (2016/10/10) 
Dynamic programming illustrated: the eggdrop 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: rodcutting and 0/1 integer knapsack 
Read Sections 151 and 153 Do Exercises 15.13, 15.35 
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 414416 and 423425 Do Exercise 16.11 
L16 (2016/10/19) 
The greedy strategy: activity selection Huffman encoding 
Chapter 16: read Sections 16.1  16.3 Do Exercise 16.13, 16.15, 16.23, 16.33 
L17 (2016/10/24) 
Introduction to intractability Tractable = running time is polynomial in size of input 
Read Chapter 34.1 Do Exercise 34.14 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.15 
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.53. Read Chapter 34.5.5 for a description of the Subset Sum Problem, and do Exercise 34.54 Do Exercise 34.55 by reducing the Subset Sum Problem to the Partition Problem (for this question, pretend that you do not already know that Partition is NPComplete) 
L20 (2016/11/2) 
Designing 2input Verification algorithms. Designing polynomialtime recognition algorithms The complexity classes P, NP, and coNP 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 342 
L21 (2016/11/7)  Inclass test  
L22 (2016/11/9)  A first NPcomplete problem: circuit satisfiability  Read pages 10701077 of the text. 
L23 (2016/11/14) 
Wrapping up NPcompleteness. Review of the Circuit Satisfiability hardness proof. Some additional reduction examples Overview of other complexity classes and the polynomialtime hierarchy 
Read Theorems 34.9 and 34.10 (and their proofs). Do problems 342 and 344 
L24 (2016/11/16) 
Introduction to graphs (a review): Concepts, terminology, notation, and representation Topological sort 
Read Chapter 22.1 of the text Do Exercises 22.13, 22.15, and 22.16, and Exercise 22.45 
L25 (2016/11/21)  Shortestpath problems  definition, concepts, and terminology. Allpairs shortest paths via Dynamic Programming: Theta(V^4) and Theta(V^3 log V) algorithms  Read Chapter 24, pages 641647, and Chapter 25, pages 684691 
L26 (2016/11/28) 
APSP: The FloydWarshall Algorithm Singlesource shortest paths  preleminaries 
Read Chapter 25.2. Read Chapter 24, pages 647649 Do Exercises 25.24 and 25.26 
L27 (2016/11/30)  Inclass test  
L28 (2016/12/5)  Singlesource shortest paths: The BellmanFord and Dijkstra algorithms 
Read Chapters 24.1 and 24.3 of the text. Do Exercises 24.11, 24.13, 24.31, 24.32, and 24.34 
L29 (2016/12/7)  Course review 