CS 173: Skills list for Fifth CBTF Test
The fifth CBTF test will have 5 questions on topics related to undirected graphs, trees, and asymptotic analysis. The specific skills it will test are
- Graph basics
- Know that a graph is a set of vertices/nodes plus a set of edges.
- Know that an edge is a subset of vertices of cardinality 2.
- Know how to name edges via their endpoints as {v,w}.
- Be able to specify a walk as an alternating sequence of vertices and edges that begins and ends with a vertex.
- Be able to model problems as graphs.
- Graph terminology and notation
- Basics: adjacent/neighboring vertices, endpoints of an edge, edge connecting
(incident with) two vertices, degree of a vertex, subgraph
- Special example graphs:
Kn, Cn, Wn,
Kn,m. Know shorthand, full names, structure, numbers of vertices and edges.
Beware: Wn contains n+1 vertices.
- Walks: walk, open walk, closed walk, cycle, path.
- Connectivity: connected graph, connected component, acyclic.
- Distances: length of a path (number of edges in it), distance between two nodes.
- Other facts and concepts: Euler circuit, Handshaking theorem, bipartite graph
- Graph properties
- Find the number of connected components in a graph
- Know what a Euler tour of a graph is.
- Determine if a graph has an Euler circuit (all vertices in the graph must have even degree).
- Know what a Hamiltonian cycle in a graph is.
- Graph isomorphism
- Prove that two graphs are isomorphic by giving a bijection between their vertices.
- 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 the definition of coloring of a graph.
- Know how to give a coloring for an example graph.
- Know the definition of chromatic number of a graph.
- Be able to argue that a graph has a certain chromatic number.
- Know that a graph is bipartite if and only if its chromatic number is 2.
- Trees
- Know that free (unrooted) tree is an undirected connected, acyclic graph.
- Know key properties of unrooted trees: existence of unique paths between vertices,
and that number of edges in an n vertex tree is n-1.
- Know what a rooted tree is.
- Define and use tree terminology: root, leaf, internal node,
parent, child, sibling, (proper) ancestor, (proper) descendent,
level of a node, height of tree, level of a vertex.
- Define what it means for a tree to be binary, n-ary,
full, full and complete, or balanced.
- Define rooted trees recursively: starting from root and some rooted trees with disjoint
vertices, it is formed by making the rooted trees children of the root.
- Know key facts: a full m-ary tree with i internal nodes has mi+1 nodes total,
a full binary tree with n internal nodes has n+1 leaves (and thus 2n+1 nodes total),
- Know key facts about binary trees of height h:
the number of leaves is between 1 and
2h, the number of nodes is between (h+1) and
(2h+1 - 1)
- Know that the height of a full complete
m-ary tree with n nodes (or n leaves)
is θ(log_m n).
- Algorithm Analysis
- Know that the running time of an algorithm is the number of steps taken by the algorithm.
Typically, we assume that each line in the pseudo code is one step.
- Given a simple iterative algorithm, know how to compute an upper bound on its running
time as a function of the length of the input.
- Know how to get Big O/Theta analysis of the running time of simple algorithms.
- Big O
- Define what it means for a function f to be o(g) (little o of g),
O(g) (big O of g), θ(g), \Omega(g) where g is another function.
- For specific functions f and g, identify whether f is o(g),
O(g), θ(g), \Omega(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), θ(g), o(g), \Omega(g).