CS 173: Skills list for Examlet 12
- Big O
- Define what it means for a function f to be O(g) (big O of g) and Θ(g) (theta of g) where g is another function.
- For specific functions f and g, identify whether f is O(g), Θ(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), Θ(g) by identifying c and k as in the definitions.
- Algorithm Analysis
- Know that the running time of an algorithm is the number of steps taken by the algorithm. Typically, we assume that each line in the pseudo code is one step.
- Given a simple iterative algorithm, know how to compute an upper bound on its running time as a function of the length of the input.
- Know how to get Big O/Theta analysis of the running time of simple algorithms.
- Pigeon Hole Principle
- Be able to state and apply the Pigeonhole Principle to problems.
- Know generalize pigeon hole principle and apply it to problems.
- Apply the pigeonhole principle in writing proofs.
- Principle of Inclusion-Exclusion
- Know the Principle of Inclusion-Exclusion. You will be expected to remember the rule for two sets and three sets. If a problem requires using this for more than 3 sets, the principle will be given as part of the problem.
- Apply it to problems to compute the size of a set expressed as a union of other sets. Students will be expected to be able to reduce a counting question to one in which the principle of inclusion-exclusion can be applied, by defining appropriate sets.