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.

[CLRS 7]

Thurs, Oct 19

(HM2 due before class)

Selection Algorithms:
(DL) Order Statistics, Median Select

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

Optional Notes on Selection:

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

[CLRS 9]
Optional:
[Baase, 3.4]

*Tues, Sept 24

Introduction to Hashing:

(DL) Hashing I Simple uniform hashing, open addressing

Universal Hashing:

(DL) Hashing II Universal hashing, perfect hashing

Optional Notes Introducing Hashing:

(BF) Consistent 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]

Thurs, Sept 26

Quiz on Asymptotic Notation and Recurrences

Tues, Oct 1

Amortized Analysis:

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

(EU) Amortized Analysis

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]

Thurs, Oct 3

Computational Geometry:

(PI) Computational Geometry I Closest Pair

(PI) Computational Geometry II Segment Intersection

Further Computational Geometry:

(BF) Approximate Nearest Neighbor

[CLRS 33]

*Tues, Oct 8

No Class - Duke Fall Break

*Thurs, Oct 10

(Assignment of HM3)

Midterm Exam (Sorting, Searching, Hashing, Randomized and Amortized Analysis)

Tues, Oct 15

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

(PI) Fast Fourier Transform Fast Fourier Transform - Polynomial multiplication

Optional Notes on Fast Fourier Transform and Polynomial Algorithms:\
(JR) FFT and Multiplication [PDF]
(JR) Polynomial Computation [PDF]

[CLRS 30], [DPV 2.5,2.6]

Thurs, Oct 17

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]

Tues, Oct 22

(HM3 due before class)

Pattern Matching:

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

Optional Notes on Pattern Matching:

(JR) Randomized Pattern Matching

Optional Notes on Data Compression:

(BF) Huffman Codes

[CLRS 32]

Thurs, Oct 24

(Assignment of HM4)

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]

Tues, Oct 29

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]

Thurs, Oct 31

(Assignment of HM5)

(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
(SS) Minimum Spanning Trees

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

Tues, Nov 5

(HM4 due before class)

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.

Multiple Source Shortest Paths:

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

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

Optional Notes on Shortest Paths:

Further Shortest Paths Algorithms:

(EU) All-pairs Shortest Paths

Shortest Paths Algorithms for Graphs with Negative Weights:

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

[CLRS 24], [CLRS 25] , [DPV 4]

Thurs, Nov 7

(Assignment of HM5)

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]

Tues, Nov 12

(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 14

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]

Tues, Nov 19

(HM5 due before class)

Algorithms Applied to WWW

(BF) Streaming Algorithms- CountMin-Sketch

(BF) Measuring Graph Centrality - The PageRank Algorithm

Option Notes on Algorithms Applied to WWW

Spectral Graph Algorithms:

(BF) Intro to Spectral Techniques: Graphs and Eigenvalues

(BF) Spectral Clustering in Graphs

Thurs, Nov 21

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]

*Tues, Nov 26

Exam (FFT, Cryptography, Computational Geometry, Graph Algorithms)

Optional Notes on Final Exam Review (read before you take the final exam):

(BF) Final Exam Review

*Monday, Dec 16

7:00 PM - 10:00 PM

FINAL EXAM (see schedule of final exams)

Credits for lecture notes:

(BF) Brandon Fain - lecture notes.
(PI) Piotr Indyk - lecture notes based on CLRS Textbook.
(DL) Erik Demaine and Charles Leiserson undergraduate level lecture notes by CLRS Textbook author.
(ML) Michael Littman – low level undergraduate lecture notes.
(HE) Herbert Edelsbrunner - graduate level notes with detailed technical explanations.
(JR) John H Reif – detailed lecture notes covering many algorithm techniques.
(SS) Steven Skiena - lecture notes with lots of graphics.
(DS) Dan Sleator - brief lecture notes.
(EU) Eli Upfal - lecture notes with terse proofs.
(JV) Jeff Vitter – survey papers on external memory model.

Course textbooks:

[CLRS] Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, McGraw Hill, third edition, 2009. Be sure to get the third edition!
[DPV] Dasgupta, Papadimitriou, and Vazirani. Algorithms, McGraw-Hill, first edition, 2006. (ISBN: 0073523402)

Other references made available:

[Baase] Sara Baase. Computer Algorithms, Introduction to Design and Analysis.
[GKP] Ron Graham, Donald Knuth, and Oren Patashnik. Concrete Mathematics.
[GT] Michael. T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java.
[Kozen] Dexter C. Kozen. The Design and Analysis of Algorithms.
[MR] Rajeev Motwani Prabhakar Raghavan. Randomized Algorithms.