CS 173: Skills list for Examlet 11

Recursion Trees

• Given a recursively defined function, find its closed form by drawing a recursion tree and adding up the work at all levels. (Examples would look like those presented in the textbook, e.g. the level sums are constant or increase in a pattern based on the key summations given above.)
• Find a big-O solution for a simple recursive definition, of the types that we've seen as examples of unrolling and recursion trees.
• Find a big-O solution for slightly harder recursive definitions, e.g. requiring use of the change of base formula.

Big-O

This examlet may revisit the topic of Big-O from Examlet 10.

Algorithms

• Know the big-O running times of basic operations on linked lists and arrays. These include reading/writing values, adding/removing elements, and dividing the list/array at locations at/near the start, in the middle, and at the end.
• Be familiar with the overall structure and big-O running times of the following algorithms.
  • merge two sorted lists
  • binary search
  • merge sort
  • graph reachability (what's in x's connected component)
  • Towers of Hanoi solver
  • Karatsuba's algorithm (you won't have to reproduce all the details)
• Analyze the big-O running time of code involving for loops and simple types of while loops.
  • Express the running time using summations.
  • Find the overall big-O running time.
• Analyze the big-O running time of recursive code.
  • Give a recursive definition of the big-O running time.
  • Given a recursive running time function, find the corresponding big-O closed form.