|
Schedule of Lectures &
Recitations (Times: 3:05PM-4:20PM, Room: LSRC A247) |
Downloadable PPT and PDF Lectures in Bold Red |
Required
Readings in Bold Red (from [E] or [CLRS] unless otherwise
noted) |
|
Tues, Aug 27 Lecture 1 by Prof John Reif (Assignment
of HM1) |
Introduction
to Algorithms: (DF) Intro to Course [PDF] Optional Notes: (SS) analyzing algorithms (JR) Models of Computation [PDF] |
Required
Reading: [E 0,
3.2] [CLRS
1 & 2] Optional reading: [DPV 0] |
|
Wends, Aug 28 Lecture 2 by Prof John Reif |
Divide and Conquer: (DL) Divide and
Conquer Merge
sort, binary search, powering a number, polynomial multiplication, matrix
multiplication, Fibonacci (BF) Matrix Multiplication via Divide and
Conquer Optional Notes on Divide and Conquer: |
Required
Reading: [E
1.4-1.6] [CLRS
4.1-4.2] Optional reading: [DPV 2] |
|
Thurs, Aug 29 Recitation by TA |
Asymptotic
Analysis: (JR) Asymptotics & Recurrence Equations [PDF] (DL) Solving
recurrences - substitution method - recursion tree - master method Optional Notes on Asymptotic Analysis: (SS) asymptotic notation (LA) Growth of functions,
summations Optional
Notes on Recurrence Equations: (SS) recurrence relations |
Required
Reading: [E
1.4-1.6] [CLRS
3 & 4.3-4.6]
Optional reading: [DPV 2.2] [GKP 2.5] |
|
Tues, Sept 3 Recitation by TA (HM1
due) (Assignment
of HM2) |
Randomized
Analysis (JR) Probability Theory Overview [PDF] Optional Notes on Randomized and
Average-Case Analysis: 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. |
Required
Reading: [E Appendix
C] |
|
Wends, Sept 4 Lecture 3 by Prof John Reif |
Sorting
Algorithms: Lower
bounds on comparison-based sort, decision-tree model, comparison sort, radix
sort (DL) Linear time sorting 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 (SS) Heapsort |
Required
Reading: [CLRS
8] Optional reading: [Baase, 3.4] |
|
Thurs, Sept 5 Lecture 4 by Prof John Reif |
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 |
Required
Reading: [CLRS
7] |
|
Tues, Sept 10 Lecture 5 by Prof John Reif |
Computational Geometry (PI) Closest Pair in 2D (PI) Computational Geometry - Segment
Intersection Optional Notes (JR) Convex Hull [PPT] [PDF] |
|
|
Wends, Sept 11 Lecture 6 by Prof John Reif |
Search 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 (LA) Search trees, red-black
trees |
Required
Reading: [CLRS
12&13] |
|
Thurs, Sept 12 Recitation by TA |
Randomized Dynamic Data Structures: Skip Lists: (DL) Skip Lists Randomized Insertion &
Analysis Optional Notes on Dynamic Data Structures (DL) Augmenting Data Structures Dynamic Order Statistics, Interval Trees Optional Notes on Skip Lists: (LA) Hashing, Skip Lists |
|
|
Tues, Sept 17 Lecture 7 by TA |
Selection Algorithms: Finding ith smallest element, probabilistic order statistic finder, deterministic linear-time select Optional Notes on Selection: (LA) Linear time selection,
median lower bound |
Required
Reading: [E
1.8] [CLRS
9] Optional Reading: |
|
Wends, Sept 18 |
Quiz
on Divide & Conquer and Randomized Sorting Algorithms |
|
|
Thurs, Sept 19 Lecture 8 by TA (HM2
due) (Assignment
of HM3) |
Introduction
to Hashing: (DL) Hashing I Simple uniform hashing, open addressing (BF) Consistent Hashing Optional Notes Introducing Hashing: (SS) Introduction to Hash
Tables Optional
References on Consistent Hashing: (TR&GV) Consistent
Hashing (David
Karger, et al.) Akamai
Consistent Hashing Paper |
Required
Reading: [CLRS 11] Optional Reading: |
|
Tues, Sept 24 Recitation by TA |
Locality Sensitive Hashing: (BF) Locality
Sensitive Hashing: Approximate Nearest Neighbor in
High Dimension (Alexander Andoni and PI) Survey Article from Communications of the ACM (KM) Locality Sensitive Hashing (GY) Sheppard's Formula [PDF] Optional Notes (TR&GV) Dimensionality
Reduction |
|
|
Wends, Sept 25 Lecture 9 by Prof John Reif |
Universal
Hashing: (DL) Hashing II Universal hashing, perfect
hashing
Optional Notes on Universal Hashing and Extensions: (EU) Universal Hashing (SS) elementary data structures (JR) Hashing Polynomials |
Required
Reading: [CLRS 11] Optional Reading: |
|
Thurs, Sept 26 Lecture 10 by Prof John Reif |
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 (DL) Competitive Analysis Self-Organizing Lists |
Required
Reading: [CLRS
16 & 27] |
|
Tues, Oct 1 Proctored by TA (HM3
due) (Assignment
of HM4) |
Exam on Hashing & Amortized Analysis |
|
|
Wends, Oct 2 Lecture 11 by Prof John Reif |
Fast
Fourier Transform and Polynomial Algorithms (PI) Fast Fourier Transform Fast Fourier
Transform - Polynomial multiplication Optional Notes on Fast Fourier
Transform and Polynomial Algorithms:\ |
Required
Reading: [CLRS 30] Optional Reading: [DPV
2.5,2.6] |
|
Thurs, Oct 3 Lecture 12 by Prof John Reif |
Number
Theory and Cryptography Algorithms: (EU) Public Key Cryptography and
Number Theory Algorithms Optional Notes on Cryptography: (BF) Bit-Coin
and Cryptographic Hashing |
Required
Reading: [CLRS
31] |
|
Tues, Oct 8 Recitation by TA |
(GY) A Whirlwind Tour of Group Theory and Number Theory [PDF] |
|
|
Wends, Oct 9 Lecture 13 by Prof John Reif |
Randomized
Pattern Matching: (PI)Randomized Pattern Matching Pattern matching - average
case analysis - Karp-Rabin algorithm – fingerprinting Optional Notes on Pattern Matching: |
Required
Reading: [CLRS 32] |
|
Thurs, Oct 10 Lecture 14 by Prof John Reif |
Lossless
Compression: Huffman Encoding (BF) Huffman Encoding (GB) Lempel-Ziv Compression [PDF] Optional Notes on Lossless
Encoding: |
|
|
Oct 12-15 |
Duke Fall Break – no lectures |
|
|
Wends, Oct 16 Review by Prof John Reif (HM4
due) (Assignment
of HM5) |
(GY) Some Useful Graph Theory [PDF] |
|
|
Thurs, Oct 17 Lecture 14 by Prof John Reif |
Introduction
to Graphs and Their Data Structures: (SS) Data structures for graphs Optional Notes on Graph Definitions: Optional Notes on Depth First Search (LA) Model, basic algorithms, DFS, BFS,
topological sort, strongly connected components |
Required
Reading: [E 5] [CLRS 20] [DPV 3] |
|
Tues, Oct 22 Recitation by TA |
(GY) Random Graphs & Epidemics [PDF] |
|
|
Wends, Oct 23 Lecture 15 by Prof John Reif |
Introduction
to Graph Algorithms (Depth First Search): (JR) Graph Algorithms using Depth
First Search [PDF] Optional Notes on Depth First Search (LA) Model, basic algorithms,
DFS, BFS, topological sort, strongly connected components |
Required Reading: [E 6] [CLRS 20] [DPV 3] |
|
Thurs, Oct 24 Lecture 16 by Prof John Reif |
Greedy Algorithms for Minimum
spanning trees (DL) Greedy
Algorithms (and Graphs) (LA) Minimum spanning trees, Union-Find Optional Notes: (EU) Minimum Weights Spanning
Tree |
Required
Reading: [E
5-6] [CLRS 15 & 21] Optional
Reading: [DPV 5] |
|
Tues, Oct 29 Proctored by TA |
Exam
(Computational Geometry, Amortized Analysis, FFT,
Cryptography, Pattern Matching) |
|
|
Wends, Oct 30 Lecture 17 by Prof John Reif |
Graph
algorithms (Single Source Shortest Paths): (DL) Shortest Paths II Negative weights and lack of greedy-choice property; Bellman-Ford. Shortest Paths Algorithms for Graphs with Negative Weights: (LA) Shortest paths |
Required
Reading: [E 8] [CLRS
22] Optional Reading: [DPV 4] |
|
Thurs, Oct 31 Lecture 18 by Prof John Reif |
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. Optional Notes on Shortest Paths: |
Required Reading: [E 9] [CLRS
23] |
|
Tues, Nov 5 Recitation by TA (HM5
due) (Assignment
of HM6) |
|
|
|
Wends, Nov 6 Lecture 19 by Prof John Reif |
Augmenting Paths (Graph Matching): Optional Notes on Graph Matching: |
Required
Reading: [E
11.3] [CLRS
22.2 & 25] Optional Reading: [CLRS 24] [DPV 7.2-7.3] |
|
Thurs, Nov 7 Lecture 20 by Prof John Reif |
Augmenting Paths, Continued (Network Flow): (PI) Network Flows I Network flows - max flow - cut - residual graph - augmenting paths (PI) Network Flows II Network flows - Fulkerson algorithm - Edmonds-Karp Algorithm Optional Notes on Network
Flows: (JR) Flow Algorithms [PDF] |
Required
Reading: [E
10] [CLRS
22.2 & 25] Optional Reading: [CLRS 24] [DPV 7.2-7.3] |
|
Tues, Nov 12 Proctored by TA |
Exam
(Graph and Network Algorithms) |
|
|
Wends, Nov 13 Lecture 21 by Prof John Reif |
(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: |
Required
Reading: [CLRS
14] Optional Reading: [DPV 6] |
|
Thurs,
Nov 14 Lecture 23 by Prof John Reif |
Combinatorial
Search Problems:
Approximation
Algorithms for NP Search Problems: (PI) NP Search Problems and
Approximation Algorithms Optional Notes on NP Completeness: (PI) NP - Reductions (Pearsaul) NP and NP Completeness Optional Notes on Approximation
Algorithms |
Required
Reading: [CLRS 34 & 35] Optional Reading: [E 12] [DPV 8] |
Tues,
Nov 19 Recitation by TA (HM6
due) |
NP
Completeness (GY) Introduction to NP Completeness and Complexity Theory [PDF] |
|
|
|
Wends, Nov 20 Lecture 23 by Prof John Reif |
Algorithms
for Big Data, I: External Memory Algorithms: (LA) Model, basic upper and lower
bounds, sorting, B-tree Optional Notes on External Memory Algorithms: |
Optional Reading: [DPV
5.2] |
|
Thurs, Nov 21 Lecture 24 by Prof John Reif |
Algorithms
for Big Data, II: Streaming
Algorithms: Bloom Filters and Counting Distinct Elements (MG) Intro to Streaming Algorithms [PPT] [PDF] (BF) Streaming
Algorithms: CountMin-Sketch Optional Lectures on Streaming
Algorithms (RJ) Streaming Algorithms
Overview [PPT] [PDF] |
|
|
Tues, Nov 25 Lecture 25 by Prof John Reif |
Algorithms Applied to WWW, I:
PageRank (BF) Measuring Web
Graph Centrality: The PageRank Algorithm Optional Lectures on Algorithms
Applied to WWW: Spectral Graph
Algorithms: |
Required
Reading: [CLRS
18] |
|
Nov 26 – Dec 1 |
Duke
Thanksgivings Break – grad course lectures end - no more lectures |
|
|
Sunday,
Dec 15 2:00
PM –5:00 PM |
FINAL EXAM (see schedule of final exams for
TTH, Period 5) |
|