CS 173, Spring 2014: Skills list for the final

The final will be timed so that most people can finish in two hours, but you will have the full three hours to work on it. You might be taking the exam in a room other than our normal one: watch for announcements about what room you will be going to.

We will assume that you still remember the topics from the skills lists for midterm 1 and midterm 2, especially general techniques that we have continued to use. However, the exam will focus on material from the second half of the term.

Here's a list of the new skills.

• Big O
  • Define what it means for a function f to be asymptotically smaller than g (<< 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 (<< 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).
• 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(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.
  • 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.
• Logic and proofs
  • Write a proof by contradiction.
• 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.
• Collections of sets
  • Be able to manipulate sets containing other sets. Be careful of getting the right number of brackets in examples involving the empty set and sets with only one element.
  • For a set A, be able to define and compute the power set P(A).
  • Be able to read definitions for functions that return sets, i.e. whose co-domain is a power set.
  • Define a partition of a set A. Determine whether a specific set is a partition of some specific set A.
  • Know that the equivalence classes of an equivalence relation form a partition.
• Counting
  • Know the shorthand notation for binomial coefficients and the formula for computing them.
  • Be able to solve practical counting problems involving combinations and combinations with repetition.
  • Know the Binomial Theorem and Pascal's Identity
• State Diagrams
  • Be able to read basic notation for state diagrams, e.g. state diagrams are directed graphs, states are the vertices, actions are labelled on the edges, how are start and end states marked, loops and multi-edges are possible.
  • Be able to trace walks in a state diagram: walks must follow the edge directions, therefore cycles and paths also must follow the edge directions, the full description of a walk contains the state sequence and the action sequence.
  • Know the basic description of the transition function δ, i.e. each input is a pair of a state plus an action, each output is a set of possible next states. Remember that this means that the co-domain is the powerset of the set of states.
  • Have a general familiarity with some common examples of state diagrams: states of a game or puzzle, memory states of a computer program, phone lattice for a set of words.
• Counting states
  • Be able to calculate (or estimate for large cases) the number of states for an example system (e.g. a game).
  • Know that some examples involve an infinite number of states.
  • Know that algorithms can be made more efficient by not creating multiple states with identical properties. Or, said another way, organizing your work so that you don't repeatedly re-solve a sub-problem.
• Representing functions
  • Know that a function can be represented mathematically, or stored in a computer, as a list of input/output pairs.
  • Know that a more efficient way to store a function is to associate each input value with a location in a 1D array.
  • Know that the transition function might be stored as a 2D array (each array cell represents a pair of a state and an action). Or it could be stored more compactly as a 1D array of states, where each cell contains a list of actions and the corresponding output states.
• Cardinality
  • Define what it means for two sets to have the same cardinality: i.e. there is a bijection mapping one onto the other.
  • Show that two sets have the same cardinality by constructing a specific bijection between them.
  • Define when |A| <= |B|, i.e. there is a one-to-one function from A to B.
  • Know that a countable set is a set with the same cardinality as the integers (or the natural numbers).
  • Know that the following sets are countable: pairs of integers or natural numbers, rational numbers, the set of finite-length strings (with some specified finite character set), the set of all finite formulas or computer programs.
  • Know that a countable union of countable sets is countable, and be able to apply this to specific examples.
  • Know that, for any set A, the power set of A has larger cardinality than A.
  • Know that the following sets are uncountable (not countable): the reals or an interval of the reals (e.g. [0,1]), the power set of the integers, the set of all functions from the integers to the integers.
  • Know that there are functions that don't have finite formulas, and functions that can't be computed by any program.
  • You won't need to reproduce the constructions (e.g. diagonalization) that were used to prove these results.