COMPSCI 531 Introduction to Algorithms

Lectures - Teaching Assistants -Resources

Lecture Schedule and Notes

Date

Topics and Lecture Notes

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

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

Tues, Aug 30

Lecture 1 by Prof John Reif

(Assignment of HM1)

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

(DF) Intro [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 31

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

Thurs, Sept 1

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] 

Tues, Sept 6

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]

Wends, Sept 7

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

Thurs, Sept 8

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 13

Lecture 5 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]

Wends, Sept 14

lecture by TA

Computational Geometry

(PI) Closest Pair in 2D 

(PI) Computational Geometry - Segment Intersection 

Optional Notes

(JR) Convex Hull [PPT] [PDF]

Thurs, Sept 15

 Lecture 6 by Prof John Reif

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 20

Lecture 7 by Prof John Reif

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 21

Proctored by TA

Quiz on Divide & Conquer and Randomized Sorting Algorithms

Thurs, Sept 22

Lecture 8 by Prof John Reif

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

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]

Wends, Sept 28

Lecture 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

Thurs, Sept 29

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 4

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]

Wends, Oct 5

Proctored by TA

(HM3 due)

(Assignment of HM4)

Exam on Hashing & Amortized Analysis

Thurs, Oct 6

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]

Oct 7 - 11

Duke Fall Break – no lectures

Wends, Oct 12

Review by TA

(GY) A Whirlwind Tour of Group Theory and Number Theory [PDF]

Thurs, Oct 13

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]

Tues, Oct 18

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

Wends, Oct 19

Review by TA

(HM4 due)

(Assignment of HM5)

(GY) Some Useful Graph Theory [PDF]

Thurs, Oct 20

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 25

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]

Wends, Oct 26

Review by TA

(GY) Random Graphs & Epidemics [PDF]

Thurs, Oct 27

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, Nov 1

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]

Wends, Nov 2

Proctored by TA

Exam (Computational Geometry, Amortized Analysis, FFT, Cryptography, Pattern Matching)

Thurs, Nov 3

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 8

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]

Wends, Nov 9

Review by TA

(HM5 due)

(Assignment of HM6)

Thurs, Nov 10

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 15

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]

Wends, Nov 16

Proctored by TA

Exam (Graph and Network Algorithms)

Thurs,  Nov 17

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 22

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]

Nov 23 - 25

Duke Thanksgivings Break – no lectures

Tues, Nov 29

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] 

Wends, Nov 30

Proctored by TA

(HM6 due)

NP Completeness

(GY) Introduction to NP Completeness and Complexity Theory [PDF]

Thurs,  Dec 1

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]

Monday, Dec 19

2:00 PM –5:00 PM

FINAL EXAM (see schedule of final exams for TTH, Period 2)