CS 173 [B], Spring 2015

Final-Exam Checklist

• Basic knowledge of/familiarity with all the topics covered in the course. Good proof writing style.
• Functions
  • Basics: Notation f:A→B, when is it well-defined (exactly one value f(a) for each a in A); various representations (matrix, plot, bi-partite-graph-like diagram); terms like domain, co-domain, image (of the function), pre-image (of a value in B); monotonically increasing/decreasing functions.
  • Composition: what is g○f, when is it well-defined, and its properties (domain, co-domain, image, and being one-to-one, onto, bijective etc.) based on the properties of f and g.
  • Number of functions, number of one-to-one functions.
  • Pigeonhole principle.
• Graphs
  • Basics: Simple graphs, G=(V,E). Various representations (drawing, mathematical description of the sets V and E, adjacency matrix). Degree, regularity, subgraphs, walks, paths, cycles, connectivity, distance, diameter.
  • Graph isomorphism.
  • Eulerian circuits, trails.
  • Graph coloring, chromatic number χ(G), relation to degree
  • Bipartite graphs.
  • Various graph families (K_n, C_n, W_{n, Qn etc.) and their properties.}
• Proof by Contradiction
  • The structure of a proof by contradiction.
  • Examples.
• Induction:
  • The structure of an inductive proof: base case and the induction step. Induction hypothesis (used in the induction step).
  • Strong induction.
  • Examples (e.g., involving more than one base case; involving graphs and trees; strong induction).
• Recursive Definitions:
  • Basics: Base case and the recursive part of a recursive definition.
  • Unrolling a recursive definition, and finding closed form.
  • Examples: Functions of integers (T(n)), Fibonacci numbers, the hypercube graph family, rooted trees.
  • Using induction to prove properties of recursively defined objects (e.g., summations, trees).
• Algorithms:
  • Analyzing the (worst-case) running time of loops, nested loops, recursive functions.
  • Examples from class: binary search, merge sort, graph reachability, Karatsuba's algorithm for multiplication.
  • P, NP, NP-completeness.
• State Diagrams:
  • Basics: States, transition functions (for transducers and acceptors, both deterministic and non-deterministic).
  • Be able to recognize the number of states needed by a deterministic machine for a certain problem, and construct it.
  • Examples: modular arithmetic (LSB first or MSB first), detecting patterns.
  • Examples of non-deterministic state machines.
• (Un)Countability:
  • Definition of |A|=|B| and |A|≤|B| (for possibly infinite sets) in terms of bijections and one-to-one functions.
  • Countably infinite sets: definition, examples with explicit bijections to ℕ.
  • CSB Theorem. Example applications to proving the existence of bijections.
  • Uncountable sets. Examples. Familiarity with Cantor's diagonalization, and its consequence that there is no bijection between a set and its powerset.
  • Existence of uncomputable functions.