Home Bookmarks Papers Blog

Class notes for graduate algorithms class

Sariel Har-Peled
Class notes in one file: here.

(Contains also the chapters missing below.
Slides for the course are here (Fall 2014).

Class notes in separate file per chapter


    I NP Completeness
      1 NP Completeness I
        1.1 Introduction
            Can we solve all problems in polynomial time?
        1.2 Complexity classes
          1.2.1 Reductions
        1.3 More NP-Complete problems
          1.3.1 3SAT
        1.4 Bibliographical Notes

      2 NP Completeness II

        2.1 Max-Clique How to prove that a problem X is NP-Hard
        2.2 Independent Set
        2.3 Vertex Cover
        2.4 Graph Coloring

      3 NP Completeness III

        3.1 Hamiltonian Cycle
        3.2 Traveling Salesman Problem
        3.3 Subset Sum
        3.4 3 dimensional Matching (3DM)
        3.6 Some other problems

      4 Exercises - NP Completeness

        4.1 Equivalence of optimization and decision problems
        4.2 Showing problems are NP-Complete
        4.3 Solving special subcases of NP-Complete problems in polynomial time

    II Dynamic programming

      5 Dynamic programming

        5.1 Basic Idea - Partition Number
          5.1.1 A Short sermon on memoization
        5.2 Example -- Fibonacci numbers 5.2.1 Why, where, and when?
        5.2.2 Computing Fibonacci numbers 5.3 Edit Distance 5.3.1 Shortest path in a DAG and dynamic programming

      6 Dynamic programming II - The Recursion Strikes Back

        6.1 Optimal search trees
        6.2 Optimal Triangulations
        6.3 Matrix Multiplication
        6.4 Longest Ascending Subsequence
        6.5 Pattern Matching

    III Approximation algorithms

      7 Approximation algorithms

        7.1 Greedy algorithms and approximation algorithms
          7.1.1 Alternative algorithm -- two for the price of one
        7.2 Fixed parameter tractability, approximation, and fast exponential time algorithms (to say nothing of the dog)
          7.2.1 A silly brute force algorithm for vertex cover
          7.2.2 A fixed parameter tractable algorithm
            7.2.2.1 Remarks
        7.3 Traveling Salesman Person
          7.3.1 TSP with the triangle inequality
            7.3.1.1 A 2-approximation
            7.3.1.2 A 3/2-approximation to TSP
        7.4 Biographical Notes

      8 Approximation algorithms II

        8.1 Max Exact 3SAT
        8.2 Approximation Algorithms for Set Cover
          8.2.1 Guarding an Art Gallery
          8.2.2 Set Cover
          8.2.3 Lower bound
          8.2.4 Just for fun -- weighted set cover
          8.2.4.1 Analysis
        8.3 Biographical Notes

      9 Approximation algorithms III

        9.1 Clustering
          9.1.1 The approximation algorithm for $k$-center clustering
        9.2 Subset Sum
          9.2.1 On the complexity of eps-approximation algorithms
          9.2.2 Approximating subset-sum
            9.2.2.1 Bounding the running time of ApproxSubsetSum 9.2.2.2 The result
        9.3 Approximate Bin Packing
        9.4 Bibliographical notes

      10 Exercises - Approximation Algorithms

        10.1 Greedy algorithms as approximation algorithms
        10.2 Approxiamtion for hard problems

    IV Randomized algorithms

      11 Randomized Algorithms

        11.2 Sorting Nuts and Bolts
          11.2.1 Running time analysis
            11.2.1.1 Alternative incorrect solution
          11.2.2 What are randomized algorithms?
        11.3 Analyzing QuickSort
        11.4 QuickSelect -- median selection in linear time

      12 Randomized Algorithms II

        12.1 QuickSort and Treaps with High Probability
          12.1.1 Proving that an element participates in small number of rounds
          12.1.2 An alternative proof of the high probability of QuickSort
        12.2 Chernoff inequality
          12.2.1 Preliminaries
          12.2.2 Chernoff inequality
            12.2.2.1 The Chernoff Bound --- General Case
        12.3 Treaps
          12.3.1 Construction
          12.3.2 Operations
            12.3.2.1 Insertion
            12.3.2.2 Deletion
            12.3.2.3 Split
            12.3.2.4 Meld
          12.3.3 Summery
        12.4 Bibliographical Notes

      13 Min Cut

        13.1 Min Cut 13.1.1 Problem Definition
        13.1.2 Some Definitions 13.2 The Algorithm
          13.2.1 The resulting algorithm
            13.2.1.1 On the art of randomly picking an edge
          13.2.2 Analysis
            13.2.2.1 The probability of success
            13.2.2.2 Running time analysis.
        13.3 A faster algorithm
          13.3.1 On coloring trees and min-cut
        13.4 Bibliographical Notes

      14 Randomized Algorithms - exercises


    V Network flow

      15 Network Flow

        15.1 Network Flow
        15.2 Some properties of flows and residual networks
        15.3 The Ford-Fulkerson method
        15.4 On maximum flows

      16 Network Flow II - The Vengeance

        16.1 Accountability
        16.2 The Ford-Fulkerson Method
        16.3 The Edmonds-Karp algorithm
        16.4 Applications and extensions for Network Flow
          16.4.1 Maximum Bipartite Matching
          16.4.2 Extension: Multiple Sources and Sinks

      17 Network Flow III - Applications

        17.1 Edge disjoint paths
          17.1.1 Edge-disjoint paths in a directed graphs
          17.1.2 Edge-disjoint paths in undirected graphs
        17.2 Circulations with demands
          17.2.1 Circulations with demands 17.2.1.1 The algorithm for computing a circulation
        17.3 Circulations with demands and lower bounds
        17.4 Applications
          17.4.1 Survey design

      18 Network Flow IV - Applications II

        18.1 Airline Scheduling
          18.1.1 Modeling the problem
          18.1.2 Solution
        18.2 Image Segmentation
        18.3 Project Selection
          18.3.1 The reduction
        18.4 Baseball elimination
          18.4.1 Problem definition
          18.4.2 Solution

      19 Network Flow V - Min-cost flow

        19.1 Minimum Average Cost Cycle
        19.2 Potentials
        19.3 Minimum cost flow
        19.4 A Strongly Polynomial Time Algorithm for Min-Cost Flow
        19.5 Analysis of the Algorithm
          19.5.1 Reduced cost induced by a circulation
          19.5.2 Bounding the number of iterations
        19.6 ZZZ Bibliographical Notes

      20 Network Flow VI - Min-Cost Flow Applications

        20.1 Efficient Flow
        20.2 Efficient Flow with Lower Bounds
        20.3 Shortest Edge-Disjoint Paths
        20.4 Covering by Cycles
        20.5 Minimum weight bipartite matching
        20.6 The transportation problem

      21 Exercises - Network Flow

        21.1 Network Flow
        21.2 Min Cost Flow

    VI Linear Programming

      22 Linear Programming

        22.1 Introduction and Motivation
          22.1.1 History
          22.1.2 Network flow via linear programming
        22.2 The Simplex Algorithm
          22.2.1 Linear program where all the variables are positive
          22.2.2 Standard form
          22.2.3 Slack Form
          22.2.4 The Simplex algorithm by example
            22.2.4.1 Starting somewhere

      23 Linear Programming II

        23.1 The Simplex Algorithm in Detail
        23.2 The SimplexInner Algorithm
          23.2.1 Degeneracies
          23.2.2 Correctness of linear programming
          23.2.3 On the ellipsoid method and interior point methods
        23.3 Duality and Linear Programming
          23.3.1 Duality by Example
          23.3.2 The Dual Problem
          23.3.3 The Weak Duality Theorem
        23.4 The strong duality theorem
        23.5 Some duality examples
          23.5.1 Shortest path
          23.5.2 Set Cover and Packing
          23.5.3 Network flow
        23.6 Solving LPs without ever getting into a loop - symbolic perturbations
          23.6.1 The problem and the basic idea
          23.6.2 Pivoting as a Gauss elimination step
            23.6.2.1 Back to the perturbation scheme
            23.6.2.2 The overall algorithm

      24 Approximation Algorithms using Linear Programming

        24.1 Weighted vertex cover
        24.2 Revisiting Set Cover
        24.3 Minimizing congestion

      25 Exercises - Linear Programming

        25.1 Miscellaneous
        25.2 Tedious

    VII Miscellaneous topics

      26 Fast Fourier Transform

        26.1 Introduction
        26.2 Computing a polynomial quickly on $n$ values
          26.2.1 Generating Collapsible Sets
        26.3 Recovering the polynomial
        26.4 The Convolution Theorem
          26.4.1 Complex numbers -- a quick reminder

      27 Sorting Networks

        27.1 Model of Computation
        27.2 Sorting with a circuit -- a naive solution
          27.2.1 Definitions
          27.2.2 Sorting network based on insertion sort
        27.3 The Zero-One Principle
        27.4 A bitonic sorting network
          27.4.1 Merging sequence
        27.5 Sorting Network
        27.6 Faster sorting networks

      28 Union Find

        28.1 Union-Find
          28.1.1 Requirements from the data-structure
          28.1.2 Amortized analysis
          28.1.3 The data-structure
        28.2 Analyzing the Union-Find Data-Structure

      29 Approximate Max Cut

        29.1 Problem Statement
          29.1.1 Analysis
        29.2 Semi-definite programming
        29.3 Bibliographical Notes

      30 The Perceptron Algorithm

        30.1 The perceptron algorithm
        30.2 Learning A Circle
        30.3 A Little Bit On VC Dimension
          30.3.1 Examples

    VIII Compression, entropy, and randomness

      31 Huffman Coding

        31.1 Huffman coding
          31.1.1 The algorithm to build Hoffman's code
          31.1.2 Analysis
          31.1.3 What do we get
          31.1.4 A formula for the average size of a code word

      32 Entropy, Randomness, and Information

        32.1 Entropy
          32.1.1 Extracting randomness

      33 Even more on Entropy, Randomness, and Information

        33.1 Extracting randomness
          33.1.1 Enumerating binary strings with $j$ ones
          33.1.2 Extracting randomness
        33.2 Bibliographical Notes

      34 Shannon's theorem

        34.1 Coding: Shannon's Theorem
        34.2 Proof of Shannon's theorem
          34.2.1 How to encode and decode efficiently
            34.2.1.1 The scheme
            34.2.1.2 The proof
          34.2.2 Lower bound on the message size
        34.3 Bibliographical Notes

      35 Exercises - Entropy


    IX Miscellaneous topics II

      36 Matchings

        36.1 Definitions
        36.2 Unweighted matching in a bipartite graph
        36.3 Matchings and Alternating Paths
        36.4 Maximum Weight Matchings in A Bipartite Graph
          36.4.1 Faster Algorithm
        36.5 The Bellman-Ford Algorithm - A Quick Reminder

      37 Matchings II

        37.1 Maximum Size Matching in a Non-Bipartite Graph
          37.1.1 Finding an augmenting path
          37.1.2 The algorithm
            37.1.2.1 Running time analysis
        37.2 Maximum Weight Matching in A Non-Bipartite Graph

      38 Lower Bounds

        38.1 Sorting
          38.1.1 Decision trees 38.1.2 An easier direct argument
        38.2 Uniqueness
        38.3 Other lower bounds
          38.3.1 Algebraic tree model
          38.3.2 3Sum-Hard

      39 Backwards analysis

        39.1 How many times can the minimum change?
        39.2 Yet another analysis of QuickSort 39.3 Closest pair: Backward analysis in action
          39.3.1 Definitions
          39.3.2 Back to the problem
          39.3.3 Slow algorithm
          39.3.4 Linear time algorithm
        39.4 Computing a good ordering of the vertices of a graph
          39.4.1 The algorithm
          39.4.2 Analysis
        39.5 Computing nets
          39.5.1 Basic definitions
            39.5.1.1 Metric spaces{subsubsection.39.5.1.1 39.5.1.2 Nets{subsubsection.39.5.1.2
          39.5.2 Computing nets quickly for a point set in Rd
          39.5.3 Computing an $r$-net in a sparse graph
            39.5.3.1 The algorithm
            39.5.3.2 Analysis
        39.6 Bibliographical notes

    X Exercises

      40 Exercises - Prerequisites

        40.1 Graph Problems 40.2 Recurrences
        40.3 Counting
        40.5 Probability
        40.6 Basic data-structures and algorithms
        40.7 General proof thingies
        40.8 Miscellaneous

      41 Exercises - Miscellaneous

        41.1 Data structures
        41.2 Divide and Conqueror
        41.3 Fast Fourier Transform
        41.4 Union-Find
        41.5 Lower bounds
        41.6 Number theory
        41.7 Sorting networks
        41.8 Max Cut

      42 Exercises - Computational Geometry


    XI Homeworks/midterm/final

      43 Fall 2014

        43.1 Homeworks
          43.1.1 Homework 0
          43.1.2 Homework 1
          43.1.3 Homework 2
          43.1.4 Homework 3
          43.1.5 Homework 4
          43.1.6 Homework 5
        43.2 Midterm
        43.3 Final

Last modified: Tue Dec 30 20:07:25 CST 2014