midterm

• covers everything up to and including skyline problem (week5?)
• n+2 questions (e.g. pick 5 of 7)
• no questions from assignment 2
  • beneficial for practice
• will only be asked on best case/worst case
  • no avg case
• for the “Let $f(n)=n^3$ and…” question style, prove using limits
• for the “Solve the recurrence relation using…”, 2 levels of the tree = 3 levels (down to grandchild)

1. $nlogn$ → explain
2. faetgkhbdc
3. use $(x,x^2)$ formula to generate diff points

• study peasant multiply as well

questions

• stuff like this
• peasant multiply question
• no pseudocode
• recursion trees
• convex hull
• data structures
  • e.g. heapify on an array, we need to insert something in the front → what do we use (array vs linkedlist)
  • heap/trees/priority queue/stack
• absolute & relative difference
• notations (O, o, $\Omega$, $\omega$, $\theta$)
• some sort of merge sort proof (inc. merge)
• skyline
  • merge 2 skylines
  • give running time
• counting sort (lower bound)
• decision trees adversary reduction

glhf