|
META TOPICPARENT |
name="DuckyHomework" |
Ducky notes for CS 500 Midterm
The midterm is 20% of the grade. |
|
-
- 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-rder algebraic comparison tree".. where comparison is fixed-order polynomial fixed == can't change function on the fly
|
> > |
- 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 lowest idle time
|
> > |
-
- 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: |
|
On cheat sheet: |
|
< < |
- 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
|
|
- c[k] = sum(a[i]*b[j]) for all i and all j such that i+j = k.
- the key observation from Karatsuba
|
|
< < |
- sizes of things on binary tree
- if n' <= n^.75, can sort in linear time (why?)
|
|
- 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
|
> > |
- 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: |