CS 173: Skills list for sixth examlet

• Big O
  • Define what it means for a function f to be asymptotically smaller than g (f ≪ g), O(g) and/or θ(g). where g is another function.
  • For specific functions f and g, identify whether f is asymptotically smaller than g (f ≪ g), O(g) and/or θ(g).
  • Know the asymptotic relationships among key primitive functions: constant, log n, n, n log n, polynomials of higher orders, exponentials, factorial.
  • Given functions f and g, prove that f is O(g) and/or θ(g).
• 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.
• Basic data structures
  • Be able to read code that uses basic linked list operations (first, rest, cons).
  • 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.
• 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)
    • Towers of Hanoi solver
  • Know that Karatsuba's algorithm divides a size n multiplication problem into 3 (better than 4!) half-size sub-problems. And that its running time is O(n^{log ₂ 3}), which is about O(n^1.6) and thus better than the O(n²) you get by dividing a multiplication into 4 half-size sub-problems. You aren't expected to reproduce 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.
• NP
  • Know that certain classes of sentences have exponentially many parse trees. (And thus producing all parses of a sentence requires exponential time.)
  • Know that the Towers of Hanoi puzzle has been proved to require exponential time.
  • Know that NP is the set of problems for which we can quickly (polynomial time) justify "yes" answers.
  • Know that co-NP is the set of problems for which we can quickly (polynomial time) justify "no" answers.
  • Know that problems in NP can be solved in exponential time, but it's not known whether they can be solved in polynomial time.
  • Know what an NP-complete problem is: a problem in NP for which a polynomial-time algorithm would imply that any problem in NP can be solved in polynomial time.
  • Know some examples of NP-complete problems: graph colorability, circuit satisfiability (Circuit SAT), propositional logic satisfiability, marker making, the travelling salesman problem.
  • Know that you can decide in polynomial time whether a graph is 2-colorable (aka bipartite).
• Logic and proofs
  • Recap from the past: give the negation of a statement or the contrapositive (if/then statements only), simplifying it so that all negations are on individual propositions/predicates.
  • Write a proof by contradiction. (e.g. show that a number is irrational)