CPS 130 Algorithms >Lectures

| Homework - Handouts - Teaching Assistants - Resources

 

Lecture Schedule and Notes

uke Computer Science>

Current homework is available from the homework page.

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 [CLRS] unless otherwise noted)

Tues, Aug 30

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

Optional Notes:

 (SS) analyzing algorithms [PS]

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

[CLRS 1 & 2]

 

Optional:
[GKP 1.1-1.2]

Thurs, Sept 1

Asymptotic Analysis:
(DL) Asymptotic analysis - Worst case/average case - Insertion sort - Merge Sort

 

Optional Notes on Asymptotic Analysis:
(SS) asymptotic notation [PS]

(LA) Growth of functions, summations [PS]
(JR) Asymptotics and Recurrence Equations [PDF] [PS]

 

[CLRS 3]

Optional:
[CLRS App. A]

[GKP 2.5]

Tues, Sept 6

Recurrence Equations:
(DL) Solving recurrences - substitution method - recursion tree - master method

 

Optional Notes on Recurrence Equations:

(SS) recurrence relations [PS]
(SS) Example Problems [PS]
(SS) More Example Problems [PS]

[CLRS 4.3-4.6]

Optional:
[CLRS 28.1-28.2]

Thurs, Sept 8

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.1-4.2]

Tues, Sep 13

Sorting Algorithms:

(DL) Linear time sorting Lower bounds on comparison-based sort, decision-tree 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) Examples of Sorting Lower Bounds [PS]

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

(SS) Heapsort [PS]
(SS) Example heap problems [PS]

[CLRS 8]

Optional:
[Baase, 3.4]

Thurs, Sep 15

Search Trees:
(SS) Binary Search trees [PS]
(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 [PS]
(SS) Red-Black tree Rotation, Insertion, Deletion [PS]

 (LA) Search trees, red-black trees [PS]
(SS) Example Red-Black tree problem [PS]
(SS) Example Data Structure Problem [PS]
(LA) Augmented search trees, interval trees [PS]
(JR) Search Algorithms [PDF] [PS]

[CLRS 12 & 13]

Optional:
[CLRS 13, 14]
[deBerg, 10.1]

 

*Tues, Sep 20

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 [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, Sep 22

Quiz on Asymptotic Notation and Recurrences

 

Tues, Sep 27

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 [PS]
(JR) Deterministic Selection and Sorting [PDF] [PS]
(EU) Median and Order Statistics [PS]

[CLRS 9]
Optional:
[Baase, 3.4]

Thurs, Sep 29

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

Tues, Oct 4

 

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

 

Thurs, Oct 6

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

(EU) Amortized Analysis [PS]

Further Notes on Amortized Analysis (to be presented in Recitation):

(PI) Amortized Analysis II  Find-union data structure - amortized analysis

Optional Notes on Amortized Analysis:
(DS) Amortized Analysis
(LA) Aggregate analysis, potential method, binary counter, dynamic table [PS]

(DL) Competitive Analysis Self-Organizing Lists

[CLRS 17]

*Tues, Oct 11

 No Class: Fall Break

 

Thurs, Oct 13

Fast Fourier Transform and Polynomial Algorithms
(EU) Polynomials and the Fast Fourier Transform [PS]

Optional Notes on Fast Fourier Transform and Polynomial Algorithms:

(PI) Fast Fourier Transform Fast Fourier Transform - Polynomial multiplication
(JR) FFT and Multiplication [PDF] [PS]
(JR) Polynomial Computation [PDF] [PS]

[CLRS 30]

Tues, Oct 18

Number Theory and Cryptography Algorithms:
(EU) Intro to Public Key Cryptography and Number Theory Algorithms [PS]

 

Optional Notes on Cryptography:
(JR) Number Theory and Cryptography Algorithms [PDF] [PS]

[CLRS 31]

Thurs, Oct 20

Pattern Matching:

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

Optional Notes on Pattern Matching:

(JR) Randomized Pattern Matching [PS]

[CLRS 32]

Tues, Oct 25

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

 

 

*Thurs, Oct 27

Computational Geometry:

(PI) Computational Geometry I Closest Pair

Further Computational Geometry (to be presented in Recitation):

(PI) Computational Geometry II Segment Intersection

[CLRS 33]

Tues, Nov 1

Introduction to Graph algorithms (Depth First Search):

(SS) Data structures for graphs
(SS) DFS and BFS
 

Optional Notes on Graph Definitions:
(JR) Graph Algorithms using Depth First Search [PDF] [PS]

(EU) Formal Graph Definitions [PS]
 

Optional Notes on Depth First Search

(LA) Model, basic algorithms, DFS, BFS, topological sort, strongly connected components [PS]
(SS) DFS and BFS [PS]

[CLRS 22]

Optional:
[CLRS Appendix B.4-B.5]

Thurs, Nov 3

 (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, Union-Find [PS]
(EU) Minimum Weights Spanning Tree [PS]
(EU) Data Structures for Disjoint Sets [PS]
(SS) Minimum Spanning Trees [PS]

 [CLRS 16.0-16.3 & 23]

Tues, Nov 8

 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.

Further Shortest Paths Algorithms (to be presented in Recitation):

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

Optional Notes on Shortest Paths:

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

[CLRS 24]

Thurs, Nov 10

Graph algorithms (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 Multiple Source Shortest Paths:
(EU) All-pairs Shortest Paths [PS]

[CLRS 25]

Tues, Nov 15

Augmenting Paths (Graph Matching):
(JR) Breadth-First Search of Graphs and Matching [PDF] [PS]
Optional Notes:
(EU) Matching [PS]

[CLRS 22.1-22.2]

Thurs, Nov 17

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 - Ford-Fulkerson algorithm - Edmonds-Karp Algorithm

Optional Notes on Network Flows: (JR) Flow Algorithms [PDF] [PS]

[CLRS 26.1-26.2]

Tues, Nov 22

(DL) Dynamic Programming  Dynamic Programming Hallmarks; DP vs. Greedy; Fibonacci, Overlapping subproblems, Re-use of computation, Bottom-Up; 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]
(SS) Introduction to Dynamic Programming [PS]
(SS) Dynamic Programming applications [PS]
(EU) Dynamic Programming [PS]
(SS) Example dynamic programming problem [PS]

[CLRS 15]

 

*Thurs, Nov 24

No Class: Thanksgiving Break

 

 

Tues, Nov 29

External Memory Algorithms:


(LA) Model, basic upper and lower bounds, sorting, B-tree [PS]

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 [PS]
(LA) Lower bound on external sorting
(LA) External-Memory Algorithms

[CLRS 18 & 19]

Thurs, Dec 1

Approximation Algorithms & NP Search Problems, Part I:

(PI) Approximation algorithms Approximation algorithms - TSP - set cover

(LA) Approximation Algorithms [PS]
(EU) Approximately Correct Algorithms [PS]
(SS) Approximation Algorithms and Cook's Theorem [PS]

 

[CLRS 34 & 35]

*Tues, Dec 6

Approximation Algorithms & NP Search Problems, Part II:
(PI) 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 NP-completeness - SAT - Clique - Independent set - Vertex cover

 [CLRS 34 & 35]

*Thurs, Dec 8

Exam on Graph Algorithms, FFT, Number Theory Algorithms, Pattern Matching, Computational Geometry

 

TBD

FINAL EXAM:         Time & Place TBA

PLEASE DOUBLE-CHECK THE EXAM DATE AND TIME WITH REGISTRAR

Final Exam

 

Credits for lecture notes:

Course textbook:

Other references made available: