CS 173, Fall 2016: Skills list for final exam

Specific skills you should know include:

• Math prerequisites
  • Algebraic manipulations with
    • equations
    • inequalities
    • fractions
    • absolute value
    • squares and square roots
  • 2nd order polynomials: solving, factoring, finding roots. Easy cases only: don't worry if you don't remember the quadratic formula.
  • Basic rules for manipulating exponents and logs
  • Defining and composing numerical functions. E.g. if f(x) = x-6 and g(x) = 7x, then g(f(x)) = 7(x-6).
  • Prime numbers, factoring a number into primes. (Where we only consider numbers >= 2.)
  • Know how to read summation notation, i.e. convert between it and a list of terms with ellipsis (...). Same for product notation.
• Numbers and sets
  • Know what sets these symbols represent: R, N, Z, Z⁺, Q, C.
  • Notation for set membership, e.g. x ∈ Z
  • Know that 0 belongs to N but not Z⁺. (There's two conventions about what's in N. This is the one we are using this term.)
  • Know the notation and definition of n factorial (n!).
  • Know the notations [a,b] and (a,b) for closed and open intervals of the real line.
  • Know the definitions of the floor and ceiling functions, i.e. ⌈ x ⌉ and ⌊ x ⌋
• Propositional and predicate logic
  • Know the truth tables for basic logical operators, especially implies. Know that, unless there is specific indication otherwise, "or" means inclusive or.
  • Know the meaning of the universal and existential quantifier, shorthand notation, and basic terminology such as "scope" of a quantifier.
  • Translate between English and logical shorthand. But we realize that it's hard to pin down the exact meaning of some English sentences.
  • Be able to simplify the negation of a complex statement by moving the not's from the outside of the statement onto its individual propositions. This requires knowing certain key logical equivalences: double negation, DeMorgan's laws, and the rules for negating if/then statements and quantifiers.
  • Know the distributive, commutative, and associative laws and that "p implies q" is equivalent to "(not p) or q".
  • Given a new, fairly simple logical equivalence, figure out whether it's correct or not and explain why using a truth table or counter-example.
  • Identify statements which are neither true not false, because they contain variables not bound by a quantifier.
  • Decide whether a complex statement is true, given information about the truth of the basic statements it's made out of.
  • Given a statement, give its negative, converse, and contrapositive. Know that the contrapositive is equivalent to the original statement, but the converse is not.
  • Be able to identify the hypothesis and the conclusion of an if/then statement.
• Number Theory
  • Quote back definitions, decide if simple statements involving them are true, understand the corresponding shorthand notation:
    • a divides b, b is a multiple of a,
    • x is odd, x is even
    • x is prime, x is composite
    • x is a perfect square
    • x is a rational number
    • x and y are relatively prime
  • Special cases for divides: zero is even, zero divides itself but not any other integer, and every integer divides zero.
  • Special cases for prime: 0 and 1 are not prime (primes must be greater than or equal to 2).
  • Know the definitions of gcd(a,b) and lcm(a,b) and be able to compute gcd(a,b) and lcm(a,b) for specific (smallish) values of a and b.
  • Write any (small) positive integer as a product of primes.
  • Know that sqrt(2) is not rational.
  • Know that there are infinitely many primes.
  • Be able to state the Fundamental Theorem of Arithmetic: Any positive integer can be written as the product of primes and each integer has only one prime factorization (except for the order in which you write the factors).
  • Define what it means for x and y to be congruent mod k
  • Be able to state the "Division Algorithm" theorem.
  • Compute the gcd of two larger numbers using the Euclidean algorithm, i.e. trace the execution of the algorithm. Be able to reproduce its pseudocode.
  • Prove simple number theory claims using direct proof and the definitions of the terms involved. For example, if a divides b and a divides c, then a divides b+c.
  • For congruence mod k, know which integers are in the equivalence class of x. Know the shorthand notation [x].
  • In Z_k, do simple arithmetic: addition, multiplication, taking small integer powers, deciding if two elements are equal.
• Logic and Proof techniques.
  • Write a simple direct proof, using familiar concepts, with good mathematical style. Make sure your statements are in logical order, starting with the given information and ending with what you needed to show.
  • Write the negation or contrapositive of a statement, moving all negations onto individual propositions.
  • Write a proof by cases
  • Convert a claim to its contrapositive and prove that using direct proof.
  • Know the following standard ways to approach parts of a proof:
    • prove a universal claim by choosing a representative object of the appropriate type
    • prove an if/then statement by assuming whatever's in the hypothesis and proving the conclusion,
    • disprove a universal claim by exhibiting a counterexample.
    • prove an existential claim by exhibiting specific values that make the claim true
  • Know what it means for a statement to be "vacuously true."
  • Know how to prove claims using a proof by contradiction.
• Pseudocode
  • Be able to read and write simple bits of pseudocode. (We aren't picky about the precise syntax.)
• Set Theory
  • Notation
    • set builder notation for defining sets
    • set membership and inclusion notation: ⊆, ∈
    • special symbol for the empty set: ∅
    • an ordered pair, triple, n-tuple
  • Define formally, be familiar with standard notation, compute the values for concrete input sets
    • A is a subset of B
    • The cartesian product of two sets A and B, of three or more sets
    • The cardinality of a set
    • The complement of a set (given some specified universe).
    • The union, intersection, and difference of two sets.
  • Know the meaning of the term disjoint.
  • Know what happens if one of the inputs to these operations is the empty set.
  • Given a simple set relationship, recognize whether it's correct or not. If not, show a counter-example.
  • Know DeMorgan's laws and the distributive laws for sets.
  • Prove a set inclusion by choosing an element from the smaller set and showing it's in the larger set.
  • Cardinality
    • Know the inclusion-exclusion formula relating the cardinality of sets A and B to that of their union and intersection.
    • Given the cardinality of two sets A and B, compute the cardinality of their Cartesian product.
    • Apply these two formulas to real-world counting problems.
• Relations
  • Define a relation on a set A.
  • Represent a relation as a set of pairs or a directed graph, convert between the two representations.
  • Define reflexive, irreflexive, symmetric, anti-symmetric, transitive. For any of these problems, determine if a specific relation has the property.
  • Prove that a relation does or doesn't have one of the standard properties (reflexive, irreflexive, symmetric, anti-symmetric, transitive).
  • Know what it means for two elements in a relation to be comparable.
  • Define equivalence relation, partial order, strict partial order, linear order.
  • Prove that a relation is, or isn't, an equivalence relation, an partial order, a strict partial order, or linear order.
  • For an equivalence relation R, define the equivalence class [x] of an element x. For a specific element x, determine what's in [x].
  • List or describe all of R's equivalence classes.
• Functions
  • Know the basic notation f:A→B. Know the meaning of the terms domain, co-domain, and image.
  • Identify when a formula or diagram defines something that is not a function (e.g. two output values for a single input).
  • Define the composition of two functions. Compute the composition of two specific functions.
  • Be able to identify whether a function is onto, one-to-one, and/or bijective.
• Functions and counting
  • Know the meaning of the term pre-image.
  • Define what it means for a function function to be one-to-one, onto, bijective, increasing, strictly increasing.
  • Identify whether a specific function has one of these properties. Prove that your answer is correct.
  • 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.
  • Define the identity function on a set A and know its shorthand name (id_A)
  • Know that a strictly increasing function is always one-to-one.
• Logic and proofs
  • Understand (but perhaps not very clearly) simplifying proofs "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
  • Be able to state the Pigeonhole Principle and apply it to simple concrete examples.
  • Apply these formulas to solve simple concrete word problems.
  • Apply the pigeonhole principle in writing proofs.
  • Know the formulas for counting permutations, and permutations with indistinguishable objects.
  • Apply permutation formuls 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.
• Graphs
  • Define an (undirected) graph (set of vertices/nodes plus a set of edges). Know undirected graphs and directed graphs and the difference between them.
  • Know what a loop and a multi-edge are, that a "simple graph" has neither, and that graphs are simple unless we specify otherwise.
  • Know how to name edges via their endpoints, e.g. vw or {v,w}.
  • Be able to write out a walk as a sequence of edges.
  • Understand terminology: adjacent/neighboring vertices, endpoints of an edge, edge connecting (incident with) two vertices, degree of a vertex
  • State the Handshaking theorem.
  • Understand terminology for walks and connectivity: walk, open walk, closed walk, cycle, path. connected graph, connected component, cut edge, acyclic.
  • Understand terminology for distances: length of a path (number of edges in it), distance between two nodes, diameter of a graph.
  • Define an Euler circuit. Know that an Euler circuit exists if and only if all vertices in the graph have even degree.
  • Define special graphs K_n, C_n, W_n, K_n,m and know their full names (e.g. "complete bipartite graph").
  • Know the numbers of vertices and edges in each special type of graph. Beware: W_n contains n+1 vertices.
  • Understand terminology: subgraph, bipartite graph
• Graph isomorphism
  • Prove that two graphs are isomorphic by giving a bijection between their vertices.
  • Find 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 if D is the maximum degree of any vertex in a graph G, then G can be colored with D+1 colors.
• Bipartite graphs and matching
  • Know definitions of bipartite graphs and the matching problem.
  • Know Hall's theorem for bipartite matching and simple applications of it.
• 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 that a set is included in another set.
  • Prove a set equality by proving inclusion in both directions.
• Recursive definition
  • Understand how to read a recursive definition, e.g. compute selected values or objects produced by that definition.
  • Know that a recursive definition, and an inductive proof, require a both a base case and an inductive step/formula.
  • Define the Fibonacci numbers.
  • Know the connection between recursive definitions of functions and recursive programs/computation, in particular that well-formed recursive programs that recurse on strictly smaller values are a kind of recursive definition.
• Induction
  • Given a claim, identify/state the key parts of an inductive proof: the induction variable, the claim P(n), base case, inductive step, inductive hypothesis, conclusion of the inductive step.
  • Be able to state a "strong" inductive hypothesis.
  • Use induction ("strong" always) to prove a formula (equality or inequality) is correct for all integers starting at some base case.
  • For a strong inductive proof, determine whether more than one base case is required.
  • Use induction to prove that a non-formula claim (e.g. a divisibility relation) holds for all integers starting at some base case.
  • Given a recursive definition of a function, find the output value for a specific input.
  • Use induction to prove facts about a recursively defined function, e.g. that it has some specific closed form.
  • For recursively defined sets of objects (e.g. graphs, trees), use induction to prove that they have some specific property (e.g. number of edges) and/or write a recurrence for the values of some property of the objects (e.g. number of edges).
  • Be able to prove, by induction, properties of graphs, free trees, and rooted trees.
• Summations and unrolling
  • Know how to read summation notation, i.e. convert between it and a list of terms with ellipsis (...). Same for product notation.
  • Extract the first or last term in a sum or product.
  • Rewrite a sum or product so that its index variable starts at a different number.
  • Know the closed forms for three key summations: sum of the first n integers, sum of 2^k (for k from 1 to n), and sum of (1/2)^k (for k from 1 to n). (The first two were on previous skills lists but the third is new.)
  • Given a recursively defined function, find its closed form by "unrolling".
• Free Trees
  • Know the definition of free trees; definition of a leaf in a free tree;
  • Know properties of free trees and different characterizations such as a tree with more than more node always has two leaves, that if you add an edge to a free tree, it is guaranteed to produce a cycle, that if you remove an edge from a tree, it is guaranteed to make it not connected, etc.
• Rooted Trees
  • Define and use tree terminology: root, leaf, internal vertex, parent, child, sibling, (proper) ancestor, (proper) descendent, level of a vertex, height of tree.
  • Define what it means for a tree to be binary, n-ary, full, full and complete, or balanced.
  • Know key facts: a tree has one more vertex than edges, a full m-ary tree with i internal nodes has mi+1 nodes total, a full binary tree with n internal vertices has n+1 leaves (and thus 2n+1 vertices total),
  • Know key facts about binary trees of height h: the number of leaves is between 1 and ≤ 2^h, the number of vertices is between h+1 and ≤ 2^h+1 - 1
  • Know that the height of a full complete binary tree with n vertices (or n leaves) is θ(log n).
• Collections of sets
  • Be able to manipulate sets containing other sets. Be careful of getting the right number of brackets in examples involving the empty set and sets with only one element.
  • For a set A, be able to define and compute the power set P(A).
  • Be able to read definitions for functions that return sets, i.e. whose co-domain is a power set.
  • Define a partition of a set A. Determine whether a specific set is a partition of some specific set A.
  • Know that the equivalence classes of an equivalence relation form a partition.
• Counting
  • Know the shorthand notation for binomial coefficients and the formula for computing them.
  • Be able to solve practical counting problems involving combinations and combinations with repetition.
  • Know the Binomial Theorem and Pascal's Identity
• Cardinality
  • Define what it means for two sets to have the same cardinality: i.e. there is a bijection mapping one onto the other.
  • Show that two sets have the same cardinality by constructing a specific bijection between them.
  • Define when |A| <= |B|, i.e. there is a one-to-one function from A to B.
  • Know that a countable set is a set with the same cardinality as the integers (or the natural numbers).
  • Know that the following sets are countable: pairs of integers or natural numbers, rational numbers, the set of finite-length strings (with some specified finite character set), the set of all finite formulas or computer programs.
  • Know that a countable union of countable sets is countable, and be able to apply this to specific examples.
  • Know that, for any set A, the power set of A has larger cardinality than A.
  • Know that the following sets are uncountable (not countable): the reals or an interval of the reals (e.g. [0,1]), the power set of the integers, the set of all functions from the integers to the integers.
  • Know that there are functions that don't have finite formulas, and functions that can't be computed by any program.
  • You won't need to reproduce the constructions (e.g. diagonalization) that were used to prove these results.
• Big O
  • Define what it means for a function f to be asymptotically smaller than g (<< g), O(g) and/or θ(g). where g is another function.
  • For specific functions f and g, identify whether f is asymptotically smaller than g (<< g), O(g) and/or θ(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) and/or θ(g).
• Algorithms
  • Be familiar with the overall structure and big-O running times of algorithms with recursion and iteration
  • Given an unfamiliar but fairly simple function in pseudo-code, analyze how long it takes using big-O notation. You should be able to analyze nested for loops, while loops using a resource consumption argument, and recursive functions.
  • Given a recursive algorithm (familiar or unfamiliar) express its big-O running time as a recursive definition.