CS 173, Fall 2014: Skills list for eleventh examlet
- 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
- 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(nlog 2 3), which is
about O(n1.6) and thus
better than the O(n2) you get by dividing a multiplication
into 4 half-size sub-problems.
You aren't expected to reproduce the details.
- 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, while loops using a resource
consumption argument, and recursive functions.
- Given a recursive algorithm (familiar or unfamiliar)
express its big-O running time as a recursive definition.
- Know that certain classes of sentences have exponentially many parse trees.
- 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 problems in NP can be solved in exponential time, but it's
not known whether they can be solved in polynomial time.
- Know some examples of problems in NP: graph colorability,
circuit satisfiability (Circuit SAT), propositional logic satisfiability,