CS 173: Skills list for Examlet 3
- Functions
- Know the basic notation f:A→B. Know the meaning of the terms domain, co-domain, image (of the function), pre-image (of a value in B).
- Define the composition of two functions. Compute the composition of two specific functions.
- Identify when a formula or diagram defines something that is not a function (e.g. two output values for a single input).
- Define the identity function idA on a set A
- One-to-one and Onto
- Define what it means for a function function to be one-to-one, onto, bijective, increasing, strictly increasing.
- Be able to identify whether a function (presented via a formula, diagram, or other method) has one of these properties.
- Prove that a function has one of these properties.
- 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.
- 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).
- Graph basics
- Know that a graph is a 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 in this class are simple unless we specify otherwise.
- Know how to name edges via their endpoints, e.g. vw or {v,w}.
- Be able to specify a walk using an edge sequence and/or node sequence.
- 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, and Kn,m is not the same thing as a normal complete graph.
- Walks: walk, open walk, closed walk, cycle, path.
- Connectivity: connected graph, connected component, cut edge, acyclic.
- Distances: length of a path (number of edges in it), distance between two nodes, diameter of a graph.
- Other facts and concepts: Euler circuit, Handshaking theorem, bipartite graph
- Graph properties
- Find the number of connected components in a graph
- Determine if a graph has an Euler circuit (all vertices in the graph must have even degree).
- Count the number of paths between two fixed nodes
- Graph isomorphism
- Prove that two graphs are isomorphic by giving a bijection between their vertices.
- Count 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 often produces pretty good colorings fast, but is not guaranteed to produce the best solution.
- 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.