Date and Meeting Purpose

Topics and Notes

(Required Readings and Lectures in Bold)
(See below for parenthesis for credits for lecture notes)

Required Readings in Bold (from [CLRS] unless otherwise noted)

Assignments Released or Due

Tues., Aug. 28

Lecture 1

Overview of the course: Introduction to Algorithms:
(JR) Computing Fibonacci Numbers [PDF]

Optional Notes:

(SS) analyzing algorithms

(JR) Models of Computation [PDF]
(LA) Introduction to Algorithms
(SS) Algorithm Design

[CLRS 1 & 2], [DPV 0]

Optional:
[GKP 1.1-1.2]

Thurs., Aug. 30

Lecture 2

Asymptotic Analysis:
(DL) Asymptotic analysis - Worst case/average case - Insertion sort - Merge Sort

(JR) Asymptotics and Recurrence Equations [PDF]

Optional Notes on Asymptotic Analysis:
(SS) asymptotic notation

(LA) Growth of functions, summations

[CLRS 3], [DPV 0]

Optional:
[CLRS App. A]

[GKP 2.5]

Mon., Sept. 3

Lab 1

Intro to Lab:

(BF) Intro to Lab (lab1.zip)

Math review, LaTeX, Average Case Analysis Insertion Sort and Mergesort

Review [CLRS 3], [DPV 0]

Tues., Sept. 4

Lecture 3

Recurrence Equations:
(DL) Solving recurrences - substitution method - recursion tree - master method

(JR) Asymptotics and Recurrence Equations [PDF]

 Optional Notes on Recurrence Equations:

(SS) recurrence relations
(SS) Example Problems
(SS) More Example Problems

[CLRS 4.3-4.6], [DPV 2.2]

Optional:
[CLRS 28.1-28.2]

Theory HW 1 (Asymptotic Analysis, Recurrence Relations, Divide and Conquer) Released

Thurs., Sept. 6

Lecture 4

Divide and Conquer:

(DL) Divide and Conquer 

Merge sort, binary search, powering a number, polynomial multiplication, matrix multiplication, Fibonacci

Optional Notes on Divide and Conquer:

(LA) Strassen's algorithm, Master method for recurrence

[CLRS 4.1-4.2], [DPV 2]

Mon., Sep. 10

Lab 2

Divide and Conquer:

(BF) Matrix Multiplication

A Case Study in Strassen’s Matrix Multiplication Algorithm

[CLRS 4.1-4.2], [DPV 2] (review Strassen’s algorithm)

Lab HW 1 (Sorting and Compression) Released

Tues., Sept. 11

Lecture 5

Sorting Algorithms:

(DL) Linear time sorting

Lower bounds on comparison-based sort, decision-tree model, comparison sort, radix sort

Optional Notes on Linear Sorting:

(SS) Linear Sorting

Optional Notes on Lower Bounds on Sorting:

(LA) Lower bound in decision tree model, bucket and radix sort [PS] 
(SS) Examples of Sorting Lower Bounds

Optional Notes on Priority Queues:
(LA) Heaps and heapsort

(SS) Heapsort
(SS) Example heap problems

[CLRS 8]

Optional:
[Baase, 3.4]

Thurs., Sept. 13

Lecture 6 

CLASS CANCELLED FOR HURRICANE FLORENCE.

Mon., Sept. 17

Lab 3

CLASS CANCELED DUE TO TORNADOS / FLOODS

Tues., Sept. 18

Lecture 7

(SS) Binary Search trees
(DL) Binary search trees and Red-Black Trees

Binary search trees - Balanced BSTs - Red-Black trees

Optional Notes on Search Trees:

(DL) Binary search trees - Expected Height Randomly Build Binary search trees
(SS) Red-Black trees
(SS) Red-Black tree Rotation, Insertion, Deletion

 (LA) Search trees, red-black trees
(SS) Example Red-Black tree problem
(SS) Example Data Structure Problem
(LA) Augmented search trees, interval trees
(JR) Search Algorithms [PDF]

Optional: Skip Lists:

 (DL) Skip Lists Randomized Insertion & Analysis

Further Dynamic Data Structures (to be presented by TA in Recitation):

 (DL) Augmenting Data Structures Dynamic Order Statistics, Interval Trees

 Optional Notes on Skip Lists:

(LA) Hashing, Skip Lists

[CLRS 12 & 13]

Optional:
[CLRS 13, 14]
[deBerg, 10.1]

Theory HW 1 (Asymptotic Analysis, Recurrence Relations, Divide and Conquer, Search Trees) Due

Thurs., Sept. 20

Lecture 8

Randomized Algorithms and Quicksort:

(PI) Randomized Algorithms and QuickSort

Randomized algorithms: Monte-Carlo vs. Las-Vegas; matrix product checker; quick sort: deterministic, randomized; indicator variables, expected running time.  

Optional Notes on Quicksort:

(LA) Quicksort [PS]
(SS) Introduction to Quicksort [PS]
(SS) Applications of Sorting [PS]
(ML) Sorting [PS]
(ML) Analysis of Quicksort [PS]
(JR) Randomized Algorithms for Selection and Sorting [PDF] [PS]
(SS) Selection Sort [PS]
(SS) Examples of Quicksort Analysis [PS]

Optional Notes on Randomized and Average-Case Analysis:
(EU) Probabilistic Algorithms [PS] 
(JR) Probability Theory [PDF] [PS]

Optional Notes on Hidden Markov Models:

(PI) Hidden Markov Models I Markov Chains, Hidden Markov Models, Dishonest Casino Example, Evaluating path emissions likelihood, Max-likelihood path and Viterbi algorithm, total emissions probability and forward algorithm.

(PI) Hidden Markov Models II Algorithms for HMMs: review of evaluation, Viterbi, forward; posterior decoding; supervised learning; unsupervised learning: viterbi training and baum-welch training.

(PI) Computational Biology: Regulatory Motif Discovery  Bio intro: DNA and the dynamic cell, Regulatory motif definitions, Combinatorial formulation: median string finding, Probabilistic formulation: expectation maximization and Gibbs sampling, comparative genomics and discovery by genome-wide conservation.

Optional Notes on Selection Algorithms:
(DL) Order Statistics, Median Select 

Finding ith smallest element, probabilistic order statistic finder, deterministic linear-time select

(LA) Linear time selection, median lower bound
(JR) Deterministic Selection and Sorting [PDF] 
(EU) Median and Order Statistics

Optional Notes on Markov Chain Monte Carlo

(AM) Slides on Markov Chains and MCMC

(TR&GV) Lecture notes on MCMC

[CLRS 7]

Optional: [Baase, 3.4] [CLRS 9]

Theory HW 2 (Randomized Algorithms for Quicksort, Selection, Hashing, and Streaming) Released

Mon., Sept. 24

Lab 4

Lossless Compression: Huffman Encoding

(BF) Huffman Encoding

Optional Notes on Lossless Encoding:

(KM) Data Compression and Entropy

[CLRS 16.3], [DPV 5.2]

Tues., Sept. 25

Quiz Exam 1

Quiz on Asymptotic Notation and Recurrences

Thurs., Sept. 27

Lecture 9

Introduction to Hashing:

(DL) Hashing I Simple uniform hashing, open addressing

Universal Hashing: (DL) Hashing II Universal hashing, perfect hashing

Optional Notes Introducing Hashing:

(SS) Introduction to Hash Tables

Optional Notes on Universal Hashing and Extensions:

(EU) Universal Hashing

(SS) elementary data structures

(JR) Universal Hash Functions

(JR) Hashing Polynomials

[CLRS 11]

Optional: [Kozen, 12]

Mon., Oct. 1

Lab 5

Consistent Hashing: A Problem on the Web

(BF) Consistent Hashing

Optional References on Consistent Hashing:

(TR&GV) Consistent Hashing

(David Karger, et al.) Akamai Consistent Hashing Paper

Tues., Oct. 2

Lecture 10

Algorithms for Big Data:

(AM) Streaming

(JR) Probabilistic Inequalities

Streaming Algorithms: Bloom Filters and Counting Distinct Elements

Section 4.3 and 4.4 of Mining Data Streams

Thurs., Oct. 4

Lecture 11

External Memory Algorithms:

(LA) Model, basic upper and lower bounds, sorting, B-tree

Optional Notes on External Memory Algorithms:
(JV) The Input/Output Complexity of Sorting and Related Problems 
(JV) External Memory Algorithms and Data Structures: Dealing with MASSIVE Data 
(LA) Lower bound on external sorting 
(LA) External-Memory Algorithms

[CLRS 18]

Theory HW 2 (Randomized Algorithms for Quicksort, Selection, Hashing, and Streaming) Due

Mon., Oct. 8

No Meeting

No Class - Duke Fall Break

Tues., Oct. 9

No Meeting

No Class - Duke Fall Break

Thurs., Oct. 11

Lecture 12

Amortized Analysis:

(EU) Amortized Analysis  Potential Analysis for Stacks, Binary Counting and Tables

(DL) Amortized Analysis I Dynamic Tables, Accounting and Potential Methods

Optional Notes on Amortized Analysis:

(PI) Amortized Analysis II  Find-union data structure - amortized analysis
(DS) Amortized Analysis 
(LA) Aggregate analysis, potential method, binary counter, dynamic table [PS]

(DL) Competitive Analysis Self-Organizing Lists

 [CLRS 17]

Mon., Oct. 15

Lab 6

Count Min-Sketch: The Heavy Hitters Problem

(BF) Count Min-Sketch

Optional Notes on Count-Min Sketch

(TR&GV) Count-Min Sketch

(G. Cormode and S. Muthukrishnan) Count-Min Sketch Research Paper

Lab HW 1 (Sorting and Compression) Due

Lab HW 2 (Hashing and Count-Min Sketch) Released

Tues., Oct. 16

Midterm Exam 1

Midterm Exam (Covers lectures from Aug. 28 to Oct. 11, potentially including Divide and Conquer, Sorting, Searching, Hashing, Streaming, Amortized Analysis)

Thurs., Oct. 18

Lecture 13

Fast Fourier Transform and Polynomial Algorithms
(EU) Polynomials and the Fast Fourier Transform

Optional Notes on Fast Fourier Transform and Polynomial Algorithms:

(PI) Fast Fourier Transform Fast Fourier Transform - Polynomial multiplication
(JR) FFT and Multiplication [PDF]
(JR) Polynomial Computation [PDF]

[CLRS 30], [DPV 2.5,2.6]

Mon., Oct. 22

Lab 7

Bit Coin Puzzles and Cryptographic Hash Functions

(BF) Bitcoin

Optional Reference on Bit Coin

(Arvind Narayanan, et al.) Bitcoin and Cryptocurrence Technologies

Tues., Oct. 23

Lecture 14

Number Theory and Cryptography Algorithms: 
(EU) Intro to Public Key Cryptography and Number Theory Algorithms 

Optional Notes on Cryptography:
(JR) Number Theory and Cryptography Algorithms [PDF]

 [CLRS 31]

Theory HW 3 (Polynomial Multiplication, Cryptography and Number Theory, Pattern Matching, Computational Geometry) Released

Thurs., Oct. 25

Lecture 15

Pattern Matching:

(PI)Randomized Pattern Matching Pattern matching - average case analysis - Karp-Rabin algorithm – fingerprinting

Optional Notes on Pattern Matching:

(JR) Randomized Pattern Matching 

[CLRS 32]

Mon., Oct. 29

Lab 8

Computational Geometry: Approximate Nearest Neighbor in High Dimension

(BF) Locality Sensitive Hashing

Optional Reading for Locality Sensitive Hashing:

(Alexander Andoni and PI) Survey Article from Communications of The ACM

(KM) Locality Sensitive Hashing

(TR&GV) Dimensionality Reduction

Lab HW 2 (Hashing and Count-Min Sketch) Due

Lab HW 3 (Nearest Neighbor Classification) Released

Tues., Oct. 30

Lecture 16

Computational Geometry:

(PI) Computational Geometry I Closest Pair

(PI) Computational Geometry II Segment Intersection

[CLRS 33]

Thurs., Nov. 1

Lecture 17

Introduction to Graph algorithms (Depth First Search), Part I:

(SS) Data structures for graphs 
(SS) DFS and BFS 

[CLRS 22], [DPV 3]

Optional:
[CLRS Appendix B.4-B.5]

Mon., Nov. 5

Lab 9

A Case Study in the PageRank Algorithm

(BF) PageRank

Optional Notes:

(KM) Random Walks and Graph Centrality

Tues., Nov. 6

Lecture 18

Introduction to Graph algorithms (Depth First Search), Part II:

(JR) Graph Algorithms using Depth First Search [PDF]
 

Optional Notes on Graph Definitions:

(EU) Formal Graph Definitions 

Optional Notes on Graph Definitions:

(EU) Formal Graph Definitions 
 

Optional Notes on Depth First Search

(LA) Model, basic algorithms, DFS, BFS, topological sort, strongly connected components 
(SS) DFS and BFS 

[CLRS 22], [DPV 3]

Optional:
[CLRS Appendix B.4-B.5]

Theory HW 3 (Polynomial Multiplication, Cryptography and Number Theory, Pattern Matching, Computational Geometry) Due

Thurs., Nov. 8

Lecture 19

(DL) Greedy Algorithms (and Graphs)

(LA) Minimum spanning trees, Union-Find 
Minimum spanning tree (MST), greedy algorithms, hallmarks of Greedy vs. Dynamic Programming, Proof of optimal substructure and greedy property, Prim's algorithm, Kruskal's algorithm.

Optional Notes:

 (EU) Minimum Weights Spanning Tree
(EU) Data Structures for Disjoint Sets

[CLRS 16.0-16.3 & 23], [DPV 5]

Theory HW 4 (Graph Theory and Greedy Algorithms) Released

Mon., Nov. 12

Lab 10

Matrices and Graphs: Spectral Techniques

(BF) Introducing the Graph Laplacian

Optional Notes and Readings

(TR&GV) Spectral Graph Theory

(KM) Graph Laplacians and Cheeger’s Inequality

Tues., Nov. 13

Lecture 20

Graph algorithms (Single Source Shortest Paths):
(DL) Shortest Paths I Properties of shortest paths, optimal substructure, greedy choice property for non-negative edge weights, Dijkstra's algorithm, proof and analysis, Breadth-First Search (BFS) for unit-weight unweighted graphs.

Shortest Paths Algorithms for Graphs with Negative Weights:

(DL) Shortest Paths II  Negative weights and lack of greedy-choice property; Bellman-Ford.

Optional Notes on Shortest Paths:

 (LA) Shortest paths 
(SS) Shortest path algorthms
(EU) Shortest Paths Problems
(EU) Bellman-Ford Algorithm

Optional Notes on Multiple Source Shortest Paths:

(DL) All Pair Shortest Paths  All-pairs shortest paths and dynamic programming, matrix multiplication, Floyd-Warshall; Johnson's algorithm, graph reweighing and difference constraints.

(EU) All-pairs Shortest Paths

[CLRS 24], [DPV 4]

Thurs., Nov. 15

Lecture 21

Augmenting Paths (Graph Matching):
(JR) Breadth-First Search of Graphs and Matching  [PDF]

Optional Notes on Graph Matching:
(EU) Matching

Optional Notes on Network flow: (further application of augmenting paths)

(PI) Network Flows I Network flows - max flow - cut - residual graph - augmenting paths

Further Flow Algorithms (to be presented in Recitation):

(PI) Network Flows II Network flows - Ford-Fulkerson algorithm - Edmonds-Karp Algorithm

Further Optional Notes on Network Flows: (JR) Flow Algorithms [PDF]

[CLRS 22.1-22.2], [DPV 7.3]

Optional reading:

[CLRS 26.1-26.2], [DPV 7.2]

Mon., Nov. 19

Lab 11

Spectral Techniques for Clustering Graphs

(BF) Spectral Clustering

Optional Notes and Readings

(TR&GV) Spectral Graph Theory

(KM) Graph Laplacians and Cheeger’s Inequality

Lab HW 3 (Nearest Neighbor Classification) Due

Lab HW 4 (Spectral Methods for Analyzing Communities in Social Networks) Released

Tues., Nov. 20

Lecture 22

(DL) Dynamic Programming: Dynamic Programming Hallmarks; Overlapping subproblems, Re-use of computation, Bottom-Up; Longest Common Subsequence, recursive formulation, proof of optimal substructure, traceback

(LA) Dynamic Programming, Matrix chain multiplication 

Optional Notes:
(SS) Introduction to Dynamic Programming 
(SS) Dynamic Programming applications
(EU) Dynamic Programming
(SS) Example dynamic programming problem

[CLRS15], [DPV 6]

Thurs., Nov. 22

Thanksgiving Break – No Class

Mon., Nov. 26

Lab 12

Exam Review and Course Evaluations

(BF) Exam Review

Tues., Nov. 27

Lecture 23

Approximation Algorithms & NP Search Problems, Part I:

(LA) Approximation Algorithms

(PI) NP Search Problems and Approximation Algorithms

Search Problems, Part II:

(PI) NP - reductions   

(Pearsaul) NP and NP Completeness

Optional Notes on Approximation Algorithms
(EU) Approximately Correct Algorithms
(SS) Approximation Algorithms and Cook's Theorem 

 [CLRS 34 & 35], [DPV 8]

Theory HW 4 (Graph Theory and Greedy Algorithms) Due

Thurs., Nov. 29

Late-term Exam

Exam (Covers lectures from Oct. 18 to Nov. 20, potentially including FFT, Cryptography, Computational Geometry, Graph Algorithms, Greedy Algorithms, and Dynamic Programming)

Mon., Dec. 3

No Class (Graduate Classes Over)

Lab HW 4 (Spectral Methods for Analyzing Communities in Social Networks) Due

Thurs., Dec. 13

Final Exam

9:00 AM - Noon

COMPREHENSIVE FINAL EXAM (see schedule of final exams)