CPS 130 Algorithms Lectures

# Lecture Schedule and Notes

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 31 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 2 Asymptotic Analysis: (DL) Asymptotic analysis - Worst case/average case - Insertion sort - Merge Sort   Optional Notes on Asymptotic Analysis: (SS) asymptotic notation [PS] [CLRS 3] Optional: [CLRS App. A] [GKP 2.5] Tues, Sept 7 Recurrence Equations:   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 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: [CLRS 4.1-4.2] Tues, Sep 14 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 16 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) Randomly Build Binary search trees [CLRS 12 & 13] Optional: [CLRS 13, 14] [deBerg, 10.1] Tues, Sep 21 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 23 Selection Algorithms: (DL) Order Statistics, Median Select Finding ith smallest element, probabilistic order statistic finder, deterministic linear-time select   Optional Notes on Selection: [CLRS 9] Optional: [Baase, 3.4] 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:   Optional Notes on Universal Hashing and Extensions: (JR) [PS] [CLRS 11] Optional: [Kozen, 12] 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: *Tues, Oct 5 Quiz on Asymptotic Notation and Recurrences Thurs, Oct 7 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 12 No Class: Fall Break Thurs, Oct 14 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 19 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 21 Pattern Matching: (PI)Randomized Pattern Matching Pattern matching - average case analysis - Karp-Rabin algorithm – fingerprinting Optional Notes on Pattern Matching: [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): Optional Notes on Graph Definitions: (JR) Graph Algorithms using Depth First Search [PDF] [PS] Optional Notes on Depth First Search [CLRS 22] Optional: [CLRS Appendix B.4-B.5] 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: [CLRS 16.0-16.3 & 23] Thurs, Nov 4 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: [CLRS 24] Tues, Nov 9 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] Thurs, Nov 11 Augmenting Paths (Matching): (JR) Breadth-First Search of Graphs and Matching [PDF] [PS] Optional Notes: (EU) Matching [PS] [CLRS 22.1-22.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 - Ford-Fulkerson algorithm - Edmonds-Karp Algorithm Optional Notes on Network Flows: (JR) Flow Algorithms [PDF] [PS] [CLRS 26.1-26.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, 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: [CLRS 15] Thurs, Nov 25 No Class: Thanksgiving Break Tues, Nov 30 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 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 NP-completeness - SAT - Clique - Independent set - Vertex cover Optional Notes on Approximation Algorithms: (PI) Approximation algorithms Approximation algorithms - TSP - set cover [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 DOUBLE-CHECK THE EXAM DATE AND TIME WITH REGISTRAR Final Exam

## Course textbook:

• [CLRS] Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, McGraw Hill, third edition, 2009. Be sure to get the third edition!