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.
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:
Lec 2

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

Lec 3

Optional Notes on Recurrence Equations:
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:

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:

Optional Notes on Lower Bounds on Sorting:
Lec 6
Search Trees:
(SS) Binary Search trees [PS]
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
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:

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:
Order Statistics, Median Select Finding ith smallest element, probabilistic order statistic finder, deterministic linear-time select

Optional Notes on Selection:
Lec 9
(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:
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:

Quiz on Asymptotic Notation and Recurrences

Lec 11
Amortized Analysis:
Amortized Analysis I Dynamic Tables, Accounting and Potential Analysis Methods
Further Notes on Amortized Analysis (to be presented in Recitation):
(PI) Amortized Analysis II  Find-union data structure - amortized analysis
(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:
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):
Optional Notes on Graph Definitions:
(JR) Graph Algorithms using Depth First Search [PDF] [PS]
Optional Notes on Depth First Search
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:
Lec 18
Graph algorithms (Single Source Shortest Paths):
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:
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:

No Class: Thanksgiving Break

Lec 23
 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

No comments: