CS 173: Skills list for Examlet 6

• (Recap) Earlier algorithms and big-O content
• 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.
• Algorithms
  • Be familiar with the overall structure and big-O running times of the following algorithms.
    • Towers of Hanoi solver
    • Karatsuba's algorithm (you won't have to reproduce all the details)
  • Find a big-O solution for slightly harder recursive definitions than the ones for examlet 10, e.g. requiring use of the change of base formula.
  • Given an unfamiliar but fairly simple function in pseudo-code, analyze how long it takes using big-O notation. You should be able to analyze nested for loops, recursive functions, and simple examples of while loops.
  • For an algorithm involving loops (perhaps nested), express its running time using summations.
  • Given a recursive algorithm (familiar or unfamiliar) express its running time as a recursive definition.
• Proof by Contradiction
  • (Recap from the past:) Give the negation of a statement, simplifying it so that all negations are on individual propositions/predicates.
  • Write a proof by contradiction.