CS 173, Spring 2012: Skills list for second midterm

The second midterm will cover the material presented in lectures 1-17. We will assume that you still remember the topics from the skills list for the first midterm, especially general techniques that we have continued to use. However, the exam will focus on material since the first midterm.

Here's a list of the new skills.

• Functions and counting
  • Prove whether a specific function is/isn't one-to-one, onto, bijective, incresing, strictly increasing.
  • Prove that a general type of function has one of these properties, e.g. a strictly increasing function is one-to-one, composition of two one-to-one functions is one-to-one.
• Functions and counting
  • Be able to apply the pigeonhole principle in writing proofs.
  • Apply permutation formuls to count the numbers of possible functions or one-to-one functions between sets of specific sizes, and count the number of graphs on a set of a specific size.
• Logic and proofs
  • Understand (but perhaps not very clearly) simplifying proofs "without loss of generality"
• Graphs
  • Define an (undirected) graph (set of vertices/nodes plus a set of edges).
  • Know what a loop and a multi-edge are, that a "simple graph" has neither, and that graphs are simple unless we specify otherwise.
  • Know how to name edges via their endpoints, e.g. vw or {v,w}.
  • Be able to write out a walk as a sequence of edges.
  • Understand terminology: adjacent/neighboring vertices, endpoints of an edge, edge connecting (incident with) two vertices, degree of a vertex
  • State the Handshaking theorem.
  • Understand terminology for walks and connectivity: walk, open walk, closed walk, cycle, path. connected graph, connected component, cut edge, acyclic.
  • Understand terminology for distances: length of a path (number of edges in it), distance between two nodes, diameter of a graph.
  • Define an Euler circuit. Know that an Euler circuit exists if and only if all vertices in the graph have even degree.
  • Define special graphs K_n, C_n, W_n, K_n,m and know their full names (e.g. "complete bipartite graph").
  • Know the numbers of vertices and edges in each special type of graph. Beware: W_n contains n+1 vertices.
  • Understand terminology: subgraph, bipartite graph
• Graph isomorphism
  • Prove that two graphs are isomorphic by giving a bijection between their vertices.
  • Find the number of isomorphisms between two graphs.
  • Prove that two graphs are not isomorphic by finding a feature that differs, e.g. different numbers of nodes/edges, different numbers of vertices with a specific degree k, small subgraph present in one graph but not in the other.
• Graph coloring
  • Know that a (vertex) coloring of a graph is labelling of each vertex with a color, such that adjacent vertices always have different colors.
  • Know that the chromatic number of a graph is the minimum number of colors required to color it.
  • Know the shorthand notation χ(G).
  • Prove that the chromatic number of a graph G is n. This requires two steps
    • show a coloring of G that uses n colors
    • show that G can't be colored with fewer than n colors (e.g. by finding a copy of K_n in the graph)
  • Know that graph coloring is useful for (among other things) register allocation in compilers for programming languages like C and Java.
• Graph coloring
  • Know that if D is the maximum degree of any vertex in a graph G, then G can be colored with D+1 colors.
  • Know that graph coloring takes exponential time if you need to be sure you use the minimum number of colors, but that the "Greedy" algorithm produces pretty good colorings fast.
• Recursive definition
  • Understand how to read a recursive definition, e.g. compute selected values or objects produced by that definition.
  • Know that a recursive definition, and an inductive proof, require a both a base case and an inductive step/formula.
  • Define the Fibonacci numbers.
  • Know the definition of the k-dimensional hypercube graph, its shorthand name Q_k, and how many vertices it contains.
• Induction
  • Given a claim, identify/state the key parts of an inductive proof: the induction variable, the claim P(n), base case, inductive step, inductive hypothesis, conclusion of the inductive step.
  • Be able to state a "strong" inductive hypothesis.
  • Use induction ("strong" or "weak") to prove a formula (equality or inequality) is correct for all integers starting at some base case.
  • For a strong inductive proof, determine whether more than one base case is required.
  • Use induction to prove that a non-formula claim (e.g. a divisibility relation) holds for all integers starting at some base case.
  • Given a recursive definition of a function, find the output value for a specific input.
  • Use induction to prove facts about a recursively defined function, e.g. that it has some specific closed form.
  • For recursively defined sets of objects (e.g. graphs), use induction to prove that they have some specific property (e.g. number of edges) and/or write a recurrence for the values of some property of the objects (e.g. number of edges).
• Recurrences and unrolling
  • Know the closed forms for three key summations: sum of the first n integers, sum of 2^k (for k from 1 to n), and sum of (1/2)^k (for k from 1 to n). (The first two were on previous skills lists but the third is new.)
  • Given a recursively defined function, find its closed form by "unrolling".
• Trees
  • Define a (full) binary tree recursively: it's either a single vertex, or a root with two subtrees children, or (for non-full trees) a root with one subtree child.
  • Define and use tree terminology: root, leaf, internal vertex, parent, child, sibling, (proper) ancestor, (proper) descendent, level of a vertex, height of tree.
  • Define what it means for a tree to be binary, n-ary, full, full and complete, or balanced.
  • Know key facts: a tree has one more vertex than edges, a full m-ary tree with i internal nodes has mi+1 nodes total, a full binary tree with n internal vertices has n+1 leaves (and thus 2n+1 vertices total),
  • Know key facts about binary trees of height h: the number of leaves is between 1 and ≤ 2^h, the number of vertices is between h+1 and &le 2^h+1 - 1
  • Know that the height of a full complete binary tree with n vertices (or n leaves) is θ(log n).
  • 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 lecture, e.g. the level sums are constant or increase in a pattern based on the key summations given above.)
• Grammar Trees and tree induction
  • Know the basic notation and terminology for a context-free grammar: variables, terminals, how to interpret a grammar rule, what it means for a rule to have ε as its righthand side, how to pack several rules into one rule using vertical bar.
  • Given a grammar G, give example of trees that are/aren't generated by G, determine whether a given tree could be generated by G.
  • Prove a claim about labelled or unlabelled trees using induction.
• Big-O and algorithm analysis are not on this exam.