CS 173, Spring 2013: Skills list for second midterm
The second midterm will cover the material presented in lectures 1-19.
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.
- 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 Kn, Cn, Wn,
Kn,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: Wn 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
Qk, 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.
- 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
≤ 2h, the number of vertices is between h+1 and
≤ 2h+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.)
- 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.
- 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.
- Algorithms
- 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.