COMPSCI 531D Introduction to Algorithms

Lectures - Teaching Assistants -Resources

 

 

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]
(JR) 
Example of Efficient Algorithm Development: Computing Fibonacci Numbers [PDF]

 

Optional Notes:

 (SS) analyzing algorithms

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

Required Reading:

[E 0, 3.2]

[CLRS 1 & 2]

 

Optional reading:

[DPV 0]
[GKP 1.1-1.2]

 

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:

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

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) 
Asymptotic analysis - Worst case/average case - Insertion sort - Merge Sort

(DL) Solving recurrences - substitution method - recursion tree - master method

 

Optional Notes on Asymptotic Analysis:
(JR) Asymptotics and Recurrence Equations [PDF]

(SS) asymptotic notation

(LA) Growth of functions, summations

Optional Notes on Recurrence Equations:

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

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:
(EU) 
Probabilistic Algorithms
(JR) 
Probability Theory [PDF]

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) 
Examples of Sorting Lower Bounds

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

(SS) Heapsort
(SS) 
Example heap problems

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
(SS) 
Introduction to Quicksort
(SS) 
Applications of Sorting
(ML) Sorting
(ML) Analysis of Quicksort
(JR) 
Randomized Algorithms for Selection and Sorting [PDF]
(SS) 
Selection Sort
(SS) 
Examples of Quicksort Analysis

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:
(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]

Required Reading:

[CLRS 12&13]

Optional reading:
[deBerg, 10.1]

 

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

Required Reading:

[E 1.8]

[CLRS 9]

Optional Reading:
[Baase, 3.4]

 

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:
[Kozen, 12]

 

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) Universal Hash Functions

(JR) Hashing Polynomials

 

Required Reading:

[CLRS 11]

Optional Reading:
[Kozen, 12]

 

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
(DS) 
Amortized Analysis 
(LA) 
Aggregate analysis, potential method, binary counter, dynamic table

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

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: 
(LY) Introduction to Cryptography

(EU) Public Key Cryptography and Number Theory Algorithms 

 

Optional Notes on Cryptography:

 (BF) Bit-Coin and Cryptographic Hashing
(JR) 
Number Theory and Cryptography Algorithms [PDF]

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:

(JR) Randomized 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: 

(KM) Data Compression and Entropy

 

 

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 
(SS) 
DFS and BFS 
 

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 

Required Reading:

[E 5]

[CLRS 20]

Optional Reading:

[DPV 3]
[CLRS Appendix B.4-B.5]

 

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 
(SS) 
DFS and BFS 

 Required Reading:

[E 6]

[CLRS 20]

Optional Reading:

[DPV 3]
[CLRS Appendix B.4-B.5]

 

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
(EU) 
Data Structures for Disjoint Sets
(SS) 
Minimum Spanning Trees

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 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.

(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 
(SS) 
Shortest path algorithms
(EU) 
Shortest Paths Problems
(EU) 
Bellman-Ford Algorithm

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:

(EU) All-pairs 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):
(JR) 
Breadth-First Search of Graphs and Matching  [PDF]

Optional Notes on Graph Matching:
(EU) 
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:
(SS) 
Introduction to Dynamic Programming 
(SS) 
Dynamic Programming applications
(EU) 
Dynamic Programming
(SS) 
Example dynamic programming problem

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

(LA) Approximation Algorithms

Optional Notes on NP Completeness:

(PI) NP - Reductions   

(Pearsaul) NP and NP Completeness

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

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

 

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:

(BF) Intro to Spectral Techniques: Graphs and Eigenvalues

(BF) Spectral Clustering in Graphs

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)

 

Credits for lecture notes:

Course textbooks:

Other auxiliary reading: