Algorithms#

Asymptotic notation, sorting and searching, selection in linear time, and computational geometry.

About this chapter

The chapter starts with the language for running times: \(O\), \(\Theta\) and \(\Omega\) as upper, tight and lower bounds, and the recurrence theorem for divide-and-conquer. A few short sections on recursion, dynamic programming (the knapsack table) and flow problems follow.

Most of the chapter is sorting and searching. Comparison sorts need \(\Omega(n \log n)\) comparisons; the note lists the usual ones with their trade-offs, then the non-comparison sorts that beat that bound on special data. Searching works out exact comparison counts for finding the min, the min and max together, and the median in linear time. The last section is computational geometry: range queries, point-in-polygon tests, convex hulls (with a proof that they can’t beat sorting), and Voronoi diagrams.

Chapter outline: 9 sections
  1. AsymptoticsAll three notations ignore constants and small n: f \in O(g) means f(n) \le c \cdot g(n) for some c once n is large enough.
  2. RecursionA few recursion exercises: counting grid paths with a binomial coefficient, generating permutations, and n-queens.
  3. Dynamic programming1 interactiveDynamic programming fills a table of answers to subproblems in an order where every entry only reads entries already computed.
  4. Min-cut / max-cut
  5. Hungarian
  6. Max-flow
  7. Sorting1 interactiveAny comparison sort can be drawn as a binary decision tree with n! leaves, one per ordering, so its height is \Omega(n \log n).
  8. SearchingThis section counts comparisons exactly instead of asymptotically.
  9. Computational geometryEach problem here trades preprocessing time and space for fast queries.

Asymptotics#

All three notations ignore constants and small \(n\): \(f \in O(g)\) means \(f(n) \le c \cdot g(n)\) for some \(c\) once \(n\) is large enough. So \(57n + 3\) is \(\Theta(n)\), and also \(O(n^2)\) and \(\Omega(n^{0.5})\).

  • Big-O

    • big-oh: O(g): functions that grow no faster than g - upper bound, runs in time less than g

      • \(f(n) \leq c\cdot g(n)\) for some c, large n

      • set of functions s.t. there exists c,k>0, 0 ≤ f(n) ≤ c*g(n), for all n > k

    • big-theta: \(\Theta (g)\): functions that grow at the same rate as g

      • big-oh(g) and big-omega(g) - asymptotic tight bound

    • big-omega: \(\Omega(g)\): functions that grow at least as fast as g

      • f(n) \(\geq\) c*g(n) for some c, large n

    • Example: f = 57n+3

      • \(O(n^2)\) - or anything bigger

      • \(\Theta(n)\)

      • \(\Omega(n^{.5})\) - or anything smaller

      • input must be positive

      • We always analyze the worst case run-time

    • little-omega: omega(g) - functions that grow faster than g

    • little-o: o(g) - functions that grow slower than g

      • we write f(n) ∈ O(g(n)), not f(n) = O(g(n))

    • They are all reflexive and transitive, but only Θ is symmetric.

      • Θ defines an equivalence relation.

  • add 2 functions, growth rate will be \(O(\max(g_1(n), g_2(n)))\) (same for sequential code)

  • recurrence thm: \(f(n) = O(n^c) \Rightarrow T(n) = O(n^c)\)

    • \(T(n) = a*T(n/b) + f(n)\)

    • \(c = \log_b(a)\)

  • over bounded number of elements, almost everything is constant time

Recursion#

A few recursion exercises: counting grid paths with a binomial coefficient, generating permutations, and n-queens. The advice that runs through them is to settle the base case before writing the recursive step.

  • moving down/right on an NxN grid - each path has length (N-1)+(N-1)

    • we must move right N-1 times

    • ans = (N-1+N-1 choose N-1)

    • for recursion, if a list is declared outside static recursive method, it shouldn’t be static

  • generate permutations - recursive, add char at each spot

  • think hard about the base case before starting

    • look for lengths that you know

    • look for symmetry

  • n-queens - one array of length n, go row by row

Dynamic programming#

Dynamic programming fills a table of answers to subproblems in an order where every entry only reads entries already computed. In the 0/1 knapsack, \(K[i][w]\) is the best value using the first \(i\) items with capacity \(w\): either skip item \(i\) and keep \(K[i-1][w]\), or take it and add its value to \(K[i-1][w - wt]\).

Interactive 1. The table \(K[i][w]\) from the code below, for four items. Step through it and watch each cell read two cells in the row above, the one straight up (skip item \(i\)) and the one \(wt[i-1]\) columns to its left (take item \(i\)). When the table is full, the traceback shows which items were taken; with \(W = 7\) the best pick is items 2 and 3, not the most valuable item.
//returns max value for knapsack of capacity W, weights wt, vals val
int knapSack(int W, int wt[], int val[])
int n = wt.length;
int K[n+1][W+1];
//build table K[][] in bottom up manner
for (int i = 0; i <= n; i++)
   for (int w = 0; w <= W; w++)
    if (i==0 || w==0) // base case
     K[i][w] = 0;
    else if (wt[i-1] <= w) //max of including weight, not including
     K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
    else //weight too large
     K[i][w] = K[i-1][w];
return K[n][W];

Min-cut / max-cut#

Hungarian#

  • assign N things to N targets, each with an associated cost

Max-flow#

  • A list of pipes is given, with different flow-capacities. These pipes are connected at their endpoints. What is the maximum amount of water that you can route from a given starting point to a given ending point?

Sorting#

Any comparison sort can be drawn as a binary decision tree with \(n!\) leaves, one per ordering, so its height is \(\Omega(n \log n)\). Beyond the bound, sorts differ in stability, memory, adaptivity to nearly sorted input, and how well they parallelize.

  • you can assume w.l.o.g all input numbers are unique

  • sorting requires Ω(nlog n) (proof w/ tree)

    • considerations: worst case, average, in practice, input distribution, stability (order coming in is preserved for things with same keys), in-situ (in-place), stack depth, having to read/write to disk (disk is much slower), parallelizable, online (more data coming in)

  • adaptive - changes its behavior based on input (ex. bubble sort will stop)

Comparison-based#

The comparison sorts, from the simple \(O(n^2)\) ones (bubble, selection, insertion) to the \(O(n \log n)\) ones (heap, merge, quick). Insertion sort and smooth sort are adaptive: they run faster when the input is already close to sorted.

Interactive 2. Scrub through a sort one comparison at a time. Insertion sort on nearly sorted input finishes in close to \(n\) comparisons, the \(O(nk)\) case; switch the input to random and the count grows like \(n^2\). Quicksort with the last element as pivot is fast on random input but degrades on sorted or reversed input, \(n(n-1)/2\) comparisons, because every pivot is an extreme value. Merge sort stays near \(n \log_2 n\) whatever the input.
  • bubble sort

    • keep swapping adjacent pairs

      for i=1:n-1
       if a[i+1]<a[i]
        swap(a,i,i+1)
      
    • have a flag that tells if you did no swaps - done

    • number of passes ~ how far elements are from their final positions

    • O(n^2)

  • odd-even sort

    • swap even pairs

    • then swap odd pairs

    • parallelizable

  • selection sort

    • move largest to current position for i=1:n-1 for j=1:n x = max(x,a[j]) jmax = j swap(a,i,j)

    • O(n^2)

  • insertion sort

    • insert each item into lists for i=2:n insert a[i] into a[1..(i-1)] shift

    • O(n^2), O(nk) where k is max dist from final position

    • best when almost sorted

  • heap sort

    • insert everything into heap

    • keep removing max

    • can do in place by storing everything in array

    • can use any height-balanced tree instead of heap

      • traverse tree to get order

      • ex. B-tree: multi-rotations occur infrequently, average O(log n) height

    • O(n log n)

  • smooth sort

    • adaptive heapsort

    • collection of heaps (each one is a factor larger than the one before)

    • can add and remove in essentially constant time if data is in order

  • merge sort

    • split into smaller arrays, sort, merge

    • T(n) = 2T(n/2) + n = O(n log n)

    • stable, parallelizable (if parallel, not in place)

  • quicksort

    • split on pivot, put smaller elements on left, larger on right

    • O(n log n) average, O(n^2) worst

    • O(log n) space

  • shell sort

    • generalize insertion sort

    • insertion-sort all items i apart where i starts big and then becomes small

      • sorted after last pass (i=1)

    • O(n^2), O(n^(3/2)), … unsure what complexity is

      • no matter what must be more than n log n

    • not used much in practice

Not comparison-based#

These sorts never compare two elements; they use the values themselves as array indices. That is how they get under \(n \log n\), at the cost of needing small or evenly spread values.

  • counting sort

    • use values as array indices in new sort

    • keep count of number of times at each index

    • for specialized data only, need small values

    • O(n) time, O(k) space

  • bucket sort

    • spread data into buckets based on value

    • sort the buckets

    • O(n+k) time

    • buckets could be trees

  • radix sort

    • sort each digit in turn

    • stable sort on each digit

      • like bucket sort d times

    • O(d*n) time, O(k+n) space

  • meta sort

    • like quicksort, but O(n log n) worst case

    • run quicksort, mergesort in parallel

      • stop when one stops

    • there is an overhead but doesn’t affect big-oh analysis

    • ave, worst-cast = O(n log n)

Sorting overview#

The default answer is quicksort, mergesort or heapsort, but nearly sorted input favors insertion sort and small integer keys favor radix sort.

  • in exceptional cases insertion-sort or radix-sort are much better than the generic QuickSort / MergeSort / HeapSort answers.

  • merge a and b sorted - start from the back

Searching#

This section counts comparisons exactly instead of asymptotically. The proofs track what each comparison can teach you: every element except the min has to be seen larger than something at least once, which gives \(n - 1\) for the min and \(3n/2 - 2\) for the min and max together.

  • binary search can’t do better than linear if there are duplicates

  • if data is too large, we need to do external sort (sort parts of it and write them back to file)

  • write binary search recursively

    • use low<= val and high >=val so you get correct bounds

    • binary search with empty strings - make sure that there is an element at the end of it

  • “a”.compareTo(“b”) is -1

  • we always round up for these

  • finding minimum is Ω(n)

    • pf: assume an element was ignored, that element could have been minimum

    • simple algorithm - keep track of best so far

    • thm: n/2 comparisons are necessary because each comparison involves 2 elements

    • thm: n-1 comparisons are necessary - need to keep track of knowledge gained

      • every non-min element must win at least once (move from unknown to known)

  • find min and max

    • naive solution has 2n-2 comparison

    • pairwise compare all elements, array of maxes, array of mins = n/2 comparisons

      • check min array, max array = 2* (n/2-1)

    • 3n/2-2 comparisons are sufficient (and necessary)

      • pf: 4 categories (not tested, only won, only lost, both)

      • not tested-> w or l =n/2 comparisons

      • w or l -> both = n/2-1

      • therefore 3n/2-2 comparisons necessary

  • find max and next-to-max

    • thm: n-2 + log(n) comparisons are sufficient

    • consider elimination tournament, pairwise compare elements repeatedly

      • 2nd best must have played best at some point - look for it in log(n)

  • selection - find ith largest integer

    • repeatedly finding median finds ith largest

    • finding median linear yields ith largest linear

      • T(n) = T(n/2) + M(n) where M(n) is time to find median

    • quickselect - partition around pivot and recur

      • average time linear, worst case O(n^2)

  • median in linear time - quickly eliminate a constant fraction and repeat

    • partition into n/5 groups of 5

      • sort each group high to low

      • find median of each group

      • compute median of medians recursively

      • move groups with larger medians to right

        • move groups with smaller medians to left

      • now we know 3/10 of elements larger than median of medians

        • 3/10 of elements smaller than median of medians

      • partition all elements around median of medians

        • recur like quickselect

        • guarantees each partition contains at most 7n/10 elements

      • T(n) = T(n/5) + T(7n/10) + O(n) -> f(x+y)≥f(x)+f(y)

      • T(n) ≤ T(9n/10) + O(n) -> this had to be less than T(n)

Computational geometry#

Each problem here trades preprocessing time and space for fast queries. The convex hull part includes a reduction from sorting (lift the \(x_i\) onto a parabola), which shows no hull algorithm can beat \(\Omega(n \log n)\) comparisons.

  • range queries

    • input = n points (vectors) with preprocessing

    • output - number of points within any query rectangle

    • 1D

      • range query is a pair of binary searches

      • O(log n) time per query

      • O(n) space, O(n log n) preprocessing time

    • 2D

      • subtract out rectangles you don’t want

      • add back things you double subtracted

      • we want rectangles anchored at origin

    • nD

      • make regions by making a grid that includes all points

      • precompute southwest counts for all regions - different ways to do this - tradeoffs between space and time

      • O(log n) time per query (after precomputing) - binary search x,y

  • polygon-point intersection

    • polygon - a closed sequence of segments

    • simple polygon - has no intersections

    • thm (Jordan) - a simple polygon partitions the plane into 3 regions: interior, exterior, boundary

    • convex polygon - intersection of half-planes

    • polytope - higher-dimensional polygon

    • raycasting

      • intersections = odd - interior, even - exterior

      • check for tangent lines, intersecting corners

      • O(n) time per query, O(1) space and time

    • convex case

      • preprocessing

        • find an interior point p (pick a vertex or average the vertices)

        • partition into wedges (slicing through vertices) w.r.t. p

        • sort wedges by polar angle

      • query

        • find containing wedge (look up by angle)

        • test interior / exterior

          • check triangle - cast ray from p to point, see if it crosses edge

      • O(log n) time per query (we binary search the wedges)

      • O(n) space and O(n log n) preprocessing time

    • non-convex case

      • preprocessing

        • sort vertices by x

        • find vertical slices

        • partition into trapezoids (triangle is trapezoid)

        • sort slice trapezoids by y

      • query

        • find containing slice

        • find trapezoid in slice

        • report interior/ exterior

      • O(log n) time per query (two binary searches)

      • O(n^2) space and O(n^2) preprocessing time

  • convex hull

    • input: set of n points

    • output: smallest containing convex polygon

    • simple solution 1 - Jarvis’s march

    • simple solution 2 - Graham’s scan

    • mergehull

      • partition into two sets - compute MergeHull of each set

      • merge the two resulting CHS

        • pick point p with least x

        • form angle-monotone chains w.r.t p

        • merge chains into angle-sorted list

        • run Graham’s scan to form CH

      • T(n) = 2T(n/2) + n = O(n log n)

      • generalizes to higher dimensions

      • parallelizes

    • quickhull (like quicksort)

      • find right and left-most points

        • partition points along this line

        • find points farthest from line - make quadrilateral

          • eliminate all internal points

        • recurse on 4 remaining regions

        • concatenate resulting CHs

      • O(n log n) expected time

      • O(n^2) worst-case time - ex. circle

      • generalizes to higher dim, parallelizes

    • lower bound - CH requires Ω(n log n) comparisons

      • pf - reduce sorting to convex hull

      • consider arbitrary set of x_i to be sorted

      • raise the x_i to the parabola (x_i,x_i^2) - could be any concave function

      • compute convex hull of the parabola - all connected and line on top

      • from convex hull we can get sorted x_i => convex hull did sorting so at least n log n comparisons

      • corollary - Graham’s scan is optimal

    • Chan’s convex hull algorithm

      • assume we know CH size m=h

      • partitoin points into n/m sets of m each

  • convex polygon diameter

  • Voronoi diagrams - input n points - takes O(nlogn) time to compute

    • problems that are solved

      • Voronoi cell - the set of points closer to any given point than all others form a convex polygon

      • generalizes to other metrics (not just Euclidean distance)

      • a Voronoi cell is unbounded if and only if it’s point is on the convex hull

        • corollary - convex hull can be computed in linear time

      • Voronoi diagram has at most 2n-5 vertices and 3n-6 edges

      • every nearest neighbor of a point defines an edge of the Voronoi diagram

        • corollary - all nearest neighbors can be computed from the Voronoi diagram in linear time

        • corollary - nearest neighbor search in O(log n) time using planar subdivision search (binary search in 2D)

      • connection points of neighboring Voronoi diagram cells form a triangulation (Delaunay triangulation)

      • a Delaunay triangulation maximizes the minimum angle over all triangulations - no long slivery triangles

        • Euclidean minimum spanning tree is a subset of the Delaunay triangulation (can be computed easily)

    • calculating Voronoi diagram

      • discrete case / bitmap - expand breadth-first waves from all points

        • time is O(bitmap size)

        • time is independent of #points

      • intersecting half planes

        • Voronoi cell of a point is intersection of all half-planes induced by the perpendicular bisectors w.r.t all other points

        • use intersection of convex polygons to intersect half-planes (nlogn time per cell)

      • can be computed in nlogn total time

        1. idea divide and conquer

        • merging is complex

        1. sweep line using parabolas

Key ideas

  • \(O\), \(\Theta\) and \(\Omega\) are upper, tight and lower bounds that ignore constants and small \(n\).

  • Any comparison sort needs \(\Omega(n \log n)\) comparisons, and counting, bucket and radix sort get around this only by using the values as indices.

  • Sorts also differ in stability, extra space, adaptivity to nearly sorted input and parallelism, which often decides the choice in practice.

  • Exact comparison counts come from tracking what each comparison teaches, which gives \(n-1\) for the min and \(3n/2 - 2\) for the min and max together.

  • The median of medians guarantees each partition has at most \(7n/10\) elements, so selection runs in linear time in the worst case.

  • A convex hull algorithm can sort numbers lifted onto a parabola, so convex hulls also need \(\Omega(n \log n)\) comparisons.