Design and Analysis of Algorithms

Course Description:

This course is an introductory undergraduate course on the design and analysis of algorithms. The course builds on the study of the analysis and implementation of data structures and algorithms from CPS100. The goal is to introduce a number of important algorithm design techniques as well as basic algorithms that are interesting both from a theoretical and also practical point of view. We will cover basic algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy techniques for optimization. We will cover techniques for proof of the correctness of algorithms and also asymptotic analysis of algorithm time bounds by the solution of recurrence equations. We will apply these design and analysis techniques to derived algorithms for a variety of tasks such as sorting, searching, and graph problems. Some specific algorithm topics include: deterministic and randomized sorting and searching algorithms, depth and breadth first search graph algorithms for finding paths and matchings, and algebraic algorithms for fast multiplication and linear system solving.

Lec	Topics and Lecture Notes (Required Readings and Lectures in Bold) (See below for parenthesis for credits for lecture notes)
Lec 1	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]
Lec 2	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]
Lec 3	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]
Lec 4	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]
Lec 5	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]
Lec 6	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]
Lec7	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.
Lec 8	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]
Lec 9	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]
Lec 10	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
	Quiz on Asymptotic Notation and Recurrences
Lec 11	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
	No Class: Fall Break
Lec 12	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]
Lec 13	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]
Lec 14	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]
Lec 15	Computational Geometry: (PI) Computational Geometry I Closest Pair Further Computational Geometry (to be presented in Recitation): (PI) Computational Geometry II Segment Intersection
Lec 16	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]
Lec 17	(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]
Lec 18	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]
Lec 19	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]
Lec 20	Augmenting Paths (Matching): (JR) Breadth-First Search of Graphs and Matching [PDF] [PS] Optional Notes: (EU) Matching [PS]
Lec 21	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]
	Exam on Randomized Analysis, Amortized Analysis, Sorting, Searching, Hashing, FFT, Number Theory Algorithms, Pattern Matching,  & Computational Geometry
Lec 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]
	No Class: Thanksgiving Break
Lec 23	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
Lec 24	NP Search Problems and Approximation Algorithms: (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 Optional Notes on Approximation Algorithms: (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]