Melvin's digital garden

combinatorial algorithms

The Design of Approximation Algorithms

Algorithms by Jeff Erickson

  • covers historical context

Algorithms for Competitive Programming

Network Flow

single source shortest path

Shortest Common Supersequence

Perfect graphs

Level Set Tree

Interval Packing

Hoffman-Knuth Puzzle

Graph algorithms

Dynamic Programming

Complexity of integer division

Big Oh

dominating set

Algorithm Analysis

Distribute cards into 13 piles. They can always be arranged with distinct ranks as the first card.

discrete resource allocation

Combinatorial problems in genomics and computational biology

combinatorial games

Gene Team Tree

earth mover’s distance in 2D grid

Exact TSP solver

smallest automata to separate two words

Optimal Algorithm Configuration

scheduling elevators

online graph exploration

  • used by robot vacuum cleaner to clean every location
  • start from s visit all nodes and return to s, minimize the total cost
  • DFS has competitive ratio 2 for unweighted undirected graph and that is optimal

finding code clones with mismatches

Techniques/tricks

  • Tournament
  • Naming technique
    • A Combinatorial Approach to Automatic Discovery of Cluster-Patterns, WABI 2003
  • Decreasing the level of granularity
    • start with large step length, half in each step, eg. n/2,…,8,4,2,1
    • Jump Flooding Algorithm
    • compute approximate vornoroi diagram quickly on GPU
  • Lazy
    • avoid doing work unless absolutely necessary
  • Relax the condition
    • Weaker structural property allows structures to be maintained more easily
    • Eg. Melding of leftist heaps, AVL property and balance

Data structures

Order statistics

  • selection can be solved in linear time
  • majority can be found in linear time
  • mode can be found in O(nlgn) time with a total ordering or O(n^2) time using only equality comparisons

Links to this note