CPS 130 Algorithms Lectures 
 Homework  Handouts
 Teaching Assistants  Resources

Lecture Schedule and Notes 
Current homework is available from the homework
page.
Date 
Topics and
Lecture Notes (Required
Readings and Lectures in Bold) 
Required
Readings in Bold (from [CLRS] unless
otherwise noted) 
Tues, Aug 31 
Overview of the course: Introduction
to Algorithms: Optional Notes: (SS) analyzing algorithms [PS] (JR) Models
of Computation [PDF]
[PS] 
[CLRS 1 & 2]
Optional: 
Thurs, Sept 2 
Asymptotic Analysis:
Optional Notes on Asymptotic Analysis: (LA) Growth
of functions, summations [PS]

[CLRS 3] [GKP 2.5] 
Tues, Sept 7 
Recurrence Equations: Optional Notes on Recurrence
Equations: (SS) recurrence
relations [PS] 
[CLRS 4.34.6] 
Thurs, Sept 9 
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 [PS] 
[CLRS 4.14.2] 
Tues, Sep 14 
Sorting Algorithms: (DL) Linear
time sorting Lower bounds on comparisonbased
sort, decisiontree model, comparison sort, radix sort
Optional Notes on Linear Sorting: (SS) Linear Sorting [PS]
Optional Notes on Lower Bounds on Sorting: (LA) Lower
bound in decision tree model, bucket and radix sort [PS]
(SS) Heapsort
[PS]

[CLRS 8] 
Thurs, Sep 16 
Search Trees: Optional Notes on Search Trees: (DL) Binary
search trees  Expected Height Randomly Build Binary search trees
(LA) Search
trees, redblack trees [PS]

[CLRS 12 & 13] 
Tues, Sep 21 
Randomized Algorithms and
Quicksort: (PI) Randomized Algorithms and QuickSort Randomized algorithms: MonteCarlo vs. LasVegas; matrix product checker; quick sort: deterministic, randomized; indicator variables, expected running time
Optional Notes on Quicksort: (LA) Quicksort
[PS]
Optional Notes on Randomized and AverageCase Analysis: Optional Notes on Hidden Markov
Models: (PI) Hidden
Markov Models I Markov Chains, Hidden Markov Models, Dishonest Casino
Example, Evaluating path emissions likelihood, Maxlikelihood 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 baumwelch 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
genomewide conservation. 
[CLRS 7] 
Thurs, Sep 23 
Selection Algorithms:
Optional Notes on Selection: (LA) Linear
time selection, median lower bound [PS]

[CLRS 9] 
Tues, Sep 28 
Hashing: (DL) Hashing
I Simple uniform hashing, open addressing, hash
functions in practice Universal Hashing:
(to be presented by TA in Recitation): (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 [PS] (JR) Hashing
Polynomials [PS] 
[CLRS 11] 
Thurs, Sep 30 
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 

*Tues, Oct 5 
Quiz on Asymptotic Notation and Recurrences 

Thurs, Oct 7 
Amortized Analysis: (EU) Amortized
Analysis [PS] Further Notes on Amortized Analysis (to be presented in Recitation): (PI) Amortized
Analysis II Findunion
data structure  amortized analysis Optional Notes on Amortized
Analysis: (DL) Competitive
Analysis SelfOrganizing Lists 
[CLRS 17] 
Tues, Oct 12 
No Class:
Fall Break 

Thurs, Oct 14 
Fast Fourier Transform and Polynomial Algorithms Optional Notes on Fast Fourier Transform and Polynomial Algorithms: (PI) Fast
Fourier Transform Fast Fourier Transform  Polynomial
multiplication 
[CLRS 30] 
Tues, Oct 19 
Number Theory and Cryptography Algorithms:
Optional Notes on Cryptography: 
[CLRS 31] 
Thurs, Oct 21 
Pattern Matching: (PI)Randomized
Pattern Matching Pattern matching  average case
analysis  KarpRabin algorithm – fingerprinting Optional Notes
on Pattern Matching: (JR) Randomized
Pattern Matching [PS] 
[CLRS 32] 
Tues, Oct 26 
Computational Geometry: (PI) Computational Geometry I Closest Pair Further Computational Geometry
(to be presented in Recitation): (PI) Computational
Geometry II Segment Intersection 
[CLRS 33] 
Thurs, Oct 28 
Introduction to Graph algorithms (Depth First Search): (SS) Data
structures for graphs Optional Notes on Graph Definitions: (EU) Formal
Graph Definitions [PS]
Optional Notes on Depth First Search (LA) Model,
basic algorithms, DFS, BFS, topological sort, strongly connected components
[PS]

[CLRS 22] 
Tues, Nov 2 
(DL) Greedy Algorithms (and Graphs) Graphs, representation, 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: (LA) Minimum
spanning trees, UnionFind [PS]

[CLRS 16.016.3 & 23] 
Thurs, Nov 4 
Graph algorithms (Single Source Shortest Paths): Further Shortest
Paths Algorithms (to be presented in Recitation): (DL) Shortest
Paths II Negative weights and lack of
greedychoice property; BellmanFord. Optional Notes on Shortest Paths: (LA) Shortest
paths [PS]

[CLRS 24] 
Tues, Nov 9 
Graph
algorithms (Multiple Source Shortest Paths): (DL) All
Pair Shortest Paths Allpairs shortest paths
and dynamic programming, matrix multiplication, FloydWarshall; Johnson's
algorithm, graph reweighing and difference constraints. Optional Notes on Multiple Source Shortest Paths: 
[CLRS 25] 
Thurs, Nov 11 
Augmenting Paths (Matching): 
[CLRS 22.122.2] 
Tues, Nov 16 
Augmenting Paths (Network
Flow): (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  FordFulkerson algorithm 
EdmondsKarp Algorithm Optional Notes on Network Flows:
(JR) Flow
Algorithms [PDF]
[PS] 
[CLRS 26.126.2] 
Thurs, Nov 18 
Exam on Randomized Analysis, Amortized Analysis,
Sorting, Searching, Hashing, FFT, Number Theory Algorithms, Pattern
Matching, & Computational
Geometry 

Tues, Nov 23 
(DL) Dynamic
Programming Dynamic Programming Hallmarks;
DP vs. Greedy; Fibonacci, Overlapping subproblems, Reuse of computation,
BottomUp; Longest Common Subsequence, recursive formulation, proof of
optimal substructure, c[i,j] parameterization, traceback, duality of paths
and alignments Optional Notes: (LA) Dynamic
Programming, Matrix chain multiplication [PS]

[CLRS 15] 
Thurs, Nov 25 
No Class: Thanksgiving Break 

Tues, Nov 30 
External Memory Algorithms:

[CLRS 18 & 19] 
Thurs, Dec 2 
NP Search Problems and Approximation Algorithms: Optional Notes on NP Search Problems: (PI) NP I Polynomial vs exponential running time  class NP  reductions (PI) NP II NPcompleteness  SAT  Clique  Independent set  Vertex cover Optional Notes on Approximation Algorithms: (PI) Approximation algorithms Approximation algorithms  TSP  set cover (LA) Approximation
Algorithms [PS]

[CLRS 34 & 35] 
Tues, Dec 7 
Review of Course Material and Key Algorithms and
Analysis Methods 

Thurs, Dec 9 
Exam on Graph & Network Algorithms, Dynamic
Programming 

TBD 
FINAL EXAM:
TBD Times PLEASE DOUBLECHECK THE EXAM DATE AND TIME WITH REGISTRAR

Final Exam 