CS 173: Skills list for "Examlet C"
- 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).
- 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.
- 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.
- Apply the Pigeonhole Principle 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: 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.