# CS 173, Fall 2014: Skills list for eleventh examlet

• 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
• 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.
• NP
• 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, marker making.