Ducky notes for CS 500 Midterm

From lecture notes:

• closest pair problem -- Shamos and Hoey early 70s Michael Rabin 1976
  • sort theta(n lg n)
  • sweep through sorted list considering only adjacent pairs, updating closest pair if needed theta(n)
  • in 2d, divide into cells, only need to examine
  • note about how it gets messy in higher-order: Bentley/Shamos 1976
  • other approches:
    • sweepline approach -- sweep maintaining invariant of past closest pairs; variable-thickness strip; basically converts this to dynamic 1d algorithm
    • Voronoi diagram approach -- every point "owns" a region (can be constructed in O(n ln n), has O(n) edges, only need to look at edges
• define: "fixed-order algebraic comparison tree".. where comparison is fixed-order polynomial fixed == can't change function on the fly
• use random permutation in backwards error analysis
• Rabin's approach to closest pair: take random sample, use that to calc guess of delta
• Polynomial multiplication and convolution
• partition-select -- divide into > and < some partition; look at expected number of steps in each phase, calc expected number of steps in each phase
• sample-select -- compute a sample whose size s-hat = (size s)^.75 = n^.75; look at k/n^.25 +/- n^.5
• interval scheduling:
  • greedy earliest termination time works for max number of jobs
  • interval coloring problem: use earliest start, use smallest color unused by neighbors
  • suppose weighted intervals -- greedy doesn't apply but optimal substructure property does; shortcut recursion by saving previous problem solutions. index by termination time
• cache maintenance
  • k-competitive
  • LRU
  • marking

Readings:

• divide and conquer algorithms
• recurrence / master theorem
• Linear-time deterministic median-finding, CSRL "select"
• greedy algorithms

To do:

• review asst2 carefully
• understand DFTs (office hrs 1 PM)
• review recurrence briefly
• do another divide and conquer problem
• understand = / = tree
• |p[i] - p[j]| : |p[k]-p[l]| with pairwise comparisons
• be able to write the linear median-finding algo
• review problem 3 on HW1 (2005.09.22p4) -- maybe do it for practice

On cheat sheet:

• c[k] = sum(a[i]*b[j]) for all i and all j such that i+j = k.
• the key observation from Karatsuba
• consider adding all of 2005.10.04 p4/5
• harmonic series: sum over n of 1/i = lg n + O(1)
• order stats for various sorts, including heap
• formula for k-competetive
• master method
• omega, o, theta definitions
• sterling's law
• some series
• some derivatives?
• some probability, including Chebyshev
• exponentiation/log rules
• (n/2)^(n/2) < n! < n^n
• sizes of things on binary tree
• if n' <= n^.75, can sort in linear time (why?)

At some point write up heuristics:

• divide and conquer
• look at tree of problem for intuition about running time
• if having trouble analyzing probabilities going forward, try going backwards
• randomization makes it harder for an adversary to be evil
• for partitioned things, figure the probability that something is < 3/4 original
• use equivalence classes to help figure probabilities or to figure binary decision tree

From wikipedia: In general, greedy algorithms have five pillars:

1. A candidate set, from which a solution is created
2. A selection function, which chooses the best candidate to be added to the solution
3. A feasibility function, that is used to determine if a candidate can be used to contribute to a solution
4. An objective function, which assigns a value to a solution, or a partial solution, and
5. A solution function, which will indicate when we have discovered a complete solution