DuckyCs500Midterm < Main

Tags: view all tags
---+ Ducky notes for CS 500 Midterm
The midterm is 20% of the grade.

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
   * <strike>review problem 3 on HW1 (2005.09.22p4) -- maybe *do* it for practice</strike>


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) %Y%
   * order stats for various sorts, including heap %Y%
   * formula for k-competetive %Y%
   * master method %Y%
   * omega, o, theta definitions %Y%
   * sterling's law %Y%
   * some series %Y%
   * some derivatives? %Y%
   * some probability, including Chebyshev %Y%
   * exponentiation/log rules %Y%
   * (n/2)^(n/2) < n! < n^n %Y%
   * sizes of things on binary tree %Y%
   * if n' <= n^.75, can sort in linear time  (why?)  %Y%
  

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
Raw edit | More topic actions
Topic revision: r3 - 2005-10-20 - TWikiGuest