CS 173, Spring 2014: 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
  • Know the meaning of the term pre-image.
  • Define what it means for a function function to be one-to-one, onto, bijective, increasing, strictly increasing.
  • Identify whether a specific function has one of these properties. Prove that your answer is correct.
  • Prove general results about these properties, e.g. a strictly increasing function is one-to-one, composition of two one-to-one functions is one-to-one.
  • Define the identity function on a set A and know its shorthand name (id_A)
  • Know that a strictly increasing function is always one-to-one.
• Logic and proofs
  • Understand how to simplify proofs using "without loss of generality"
  • Negate a statement containing multiple quantifiers.
  • Understand the difference in meaning between the statement ∀ x, ∃ y P(x,y) and the statement ∃ y, ∀ x, P(x,y).
• Counting
  • Be able to state the Pigeonhole Principle and apply it to simple concrete examples.
  • Apply these formulas to solve simple concrete word problems.
  • Apply the pigeonhole principle in writing proofs.
  • Know the formulas for counting permutations, and permutations with indistinguishable objects.
  • 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.
• 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).
  • Know that graph coloring is useful for (among other things) register allocation in compilers for programming languages like C and Java.
  • 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 the "greedy" coloring algorithm produces pretty good colorings fast.
• Two-way bounding
  • Understand the difference between an exact result, an upper bound, and a lower bound.
  • Prove an equality by establishing upper and lower bounds. E.g. prove that the chromatic number of a graph G is n.
  • Prove a set equality by proving inclusion in both directions.
• 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).
• Summations and unrolling
  • Know how to read summation notation, i.e. convert between it and a list of terms with ellipsis (...). Same for product notation.
  • Extract the first or last term in a sum or product.
  • Rewrite a sum or product so that its index variable starts at a different number.
  • 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 the textbook, e.g. the level sums are constant or increase in a pattern based on the key summations given above.)
• String notation and regular expressions
  • The empty string (ε)
  • Concatenation, *, and | operations
  • A^* is the set of all finite-length strings with characters from A.
  • Know what a "bit string" is (a string of one's and zero's)
• Grammar Trees and tree induction
  • Correctly interpret the definition of a context-free grammar: variables, terminals, start symbols, terminal symbols
  • Correctly interpret a grammar rule, e.g. what does ε or a vertical bar mean on the righthand side of a rule.
  • 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.