CS 173: Skills list for Examlet 6
- 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).
- Induction
- Use induction to prove claims involving inequalities
- 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
- 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.
- 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).