CS 173: Skills list for "Examlet F"

• Algorithms
  • 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)
  • 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.