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
Quick-sort. Worst-case and best-case running times. Intuition on average-case running time

Read Section 5.3 (pages 122-124 and 126).

Read Sections 7.1-7.2
Do Exercises 7.1-2, 7.2-2, 7.2-5

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

Final exam on Saturday, Dec 10th at 8:00 am