CS 173, Fall 2012: 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 since the second midterm. Since you've had less time to absorb it, the planar graphs material will be tested in less depth than earlier topics.

Here's a list of the new skills.

• Big O
  • Define what it means for a function f to be O(g) and/or θ(g). where g is another function.
  • For specific functions f and g, identify whether f is O(g) and/or θ(g).
  • Know the big-O 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
  • Know how the following algorithms work. It would be hard to reproduce the full code from scratch. Expect to fill in key tidbits of code, or hand-simulate the algorithm.
    • merge two sorted lists
    • binary search
    • merge sort
    • graph reachability
    • Towers of Hanoi solver
  • Know the big-O running times of the above algorithms.
  • 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 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, clique finding (is there a copy of K_n in a graph?).
• Sets 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.
  • 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.
  • 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.
• Planar Graphs
  • We did these very fast, so expect only fairly superficial questions on this topic.
  • Define what it means for a graph to be planar. Show that a (small!) example graph G is planar by drawing a 2D picture of G that doesn't have any crossing edges.
  • Know what a face is (including the unbounded region outside the graph).
  • Find the boundary of a face. Remember that an edge may appear twice on the boundary of a face (e.g. due to a spur edge in the graph).
  • Know what the degree of a face is (i.e. number of edges in its boundary). Remember that an edge appearing twice on the boundary must be counted twice in the degree.
  • Know (or be able to quickly reconstruct) the fact that the sum of the face degrees is twice the number of edges, for a planar graph.
  • State Euler's formula (for a connected, planar graph).
  • Know that K₅ and K_3,3 are not planar. And any graph containing one of these is not planar. (You don't have to be able to explain why.)
  • Know that any planar graph can be colored with 4 colors, and that this was proved at U. Illinois in the 1970's.