Perfectly Awesome

Algorithm Design Manual - Booknotes

Growth Rates

  • Constant: f(n) = 1
  • Logarithmic: f(n) = log(n)
  • Linear: f(n) = n
  • Superlinear: f(n) = n * log(n)
  • Quadratic: f(n) = n^2
  • Cubic: f(n) = n^3
  • Exponential: f(n) = c^n
  • Factorial: f(n) = n!

    • Graph Traversal

    Graph "Flavors"
    Data Structures
    Graph Traversal
    Breadth-First Search
    Depth-First Search
    Depth-First on Directed Graphs

    Weighted Graphs

    Minimum Spanning Trees
    Shortest Paths
    Network Flows - Bipartite Matching
    Design Graphs, not Algorithms

    Combinatorial Search

    Backtracking
    Search Pruning
    Soduku
    Heuristic Search Methods
    Other Methods
    Parallel Algorithms

    Dynamic Programming

    Caching vs Computation
    Approximate String Matches
    Longest Increasing Sequence
    Partition Problem
    Context-Free Grammar Parsing
    Traveling Salesman Problem (TSP)

    Approximation Algorithms

    Introduction

    Reductions
    Elementary Hardness Reductions
    Satisfiability
    Creative Reductions
    Proving Hardness
    P vs NP
    Dealing with NP-complete Problems


    Data Structures

    Dictionaries

    Priority Queues

    Suffix Trees/Arrays

    Graphs

    Sets

    KD Trees



    Numerical Problems

    Linear Equations

    Bandwidth Reduction

    Matrix Multiplication

    Determinants, Permanents

    Optimization

    Linear Programming

    Random Number Generation

    Factoring & Primality

    Arbitrary-Precision Math

    Knapsack Problems

    Discrete Fourier Transforms



    Combinational Problems

    Sorting

    Searching

    Median & Selection

    Permutations

    Subsets

    Partitions

    Graphs

    Calendar Math

    Job Schedules

    Satisfiability



    Polynomial-Time Graphs

    Connected Components

    Topological Sorting

    Minimum Spanning Trees

    Shortest Paths

    Transitive Closure/Reduction

    Matching

    Chinese Postman

    Edge/Verex Connectivity

    Network Flow

    Drawing Graphs

    Drawing Trees

    Planarity Detection



    Hard Graphs

    Cliques

    Independent Sets

    Vertex Covers

    Traveling Salesman

    Hamiltonian Cycle

    Graph Partition

    Vertex Coloring

    Edge Coloring

    Graph Isomorphism

    Steiner Trees

    Feedback Edge/Vortex Set



    Computational Geometry

    Geometric Primitives

    Convex Hull

    Triangulation

    Voronoi Diagrams

    Nearest Neighbors

    Range Search

    Point Location

    Intersection Detection

    Bin Packing

    Medial-Axis Transforms

    Polygon Partitioning

    Polygon Simplification

    Shape Similarity

    Motion Planning

    Line Arrangements

    Minkowski Sums



    Sets & Strings

    Set Covers

    Set Packing

    String Matching

    String Matching (approx)

    Text Compression

    Cryptography

    Finite State Machine Minimization

    Longest Common Substrings

    Shortest Common Superstrings



    Resources

    Software
    Data Sources
    Bibliographies