CS 173: Skills list for third examlet

• 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 on a set A and know its shorthand name (id_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.
  • Know that a strictly increasing function is always one-to-one.
• Counting
  • Know the formulas for counting permutations, and permutations with indistinguishable objects.
  • Apply permutation formulas 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.
  • Know how a function being onto or one-to-one constrains the size of its domain relative to its co-domain. (Finite sets only.)
  • Apply these formulas to solve simple concrete word problems.
  • Be able to state the Pigeonhole Principle and apply it to simple concrete examples.
  • Apply the pigeonhole principle in writing proofs. Straightforward examples only.
• 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: K_n, C_n, W_n, K_n,m. Know shorthand, full names, structure, numbers of vertices and edges. Beware: W_n contains n+1 vertices.
  • 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 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.