CS 332: Theory of Computation, Spring 2020 Review of Discrete Math and Algorithms
A firm background in discrete math, algorithms, and mathematical problem-solving / proof-writing will set you up for success in CS 332. You should be comfortable with almost all of the topics listed below and know how to complete the suggested exercises. It’s ok if one or two of the topics are unfamiliar or rusty. You can find good expositions of those topics in the textbooks used for CS 131 (Rosen, Discrete Math and its Applications) and CS 330 (Kleinberg & Tardos, Algorithm Design) to learn these topics or refresh your memory. However, if many of the topics are unfamiliar, please seriously consider taking a different course (e.g., 131, 132, 235, 237, 330) to shore up your background.
1 Discrete Math
Set theory. Sets, subsets. Operations on sets: union, intersection, complement. Venn diagrams. Cardinality. Power set. Cartesian product. Pairs, tuples, sequences. Countable and uncountable sets.
Exercise 1. Write a short, informal English description of the following sets. 1. {1,3,5,7,…}
2. {…,−4,−2,0,2,4,…}
3. {n:n=2mforsomem∈Nandn=3kforsomek∈N}
4. {n∈Z:n=n+1}
Exercise 2. Write a formal description of each of the following sets.
1. The set containing all integers greater than 5
2. The set containing all natural numbers that are less than 5 3. The set containing the empty set
Exercise 3. Let S = {1,2} and T = {1,2,3}. Is S a subset of T? Is T a subset of S? What areS∩T andS∪T? WhatisthepowersetP(S)? WhatistheCartesianproductS×T?
Exercise 4. If |A| = a (the size of A is a) and |B| = b, what is |A × B|? What is |P(A)|?
1
Functions and relations. Function (mapping), domain, co-domain, range. Injective (one- to-one), surjective (onto), and bijective mappings. Relation. Equivalence relation (reflexiv- ity, symmetry, transitivity).
Exercise 5. Let S = {1, 2} and T = {1, 2, 3}. Give an example of an injective function f : S → T. Give an example of a function f : S → T which is not injective. Can a function f : S → T be surjective?
Define the function f : S ×T → Z by f(x,y) = x+y. What is the domain of f? What is the range of f? What is the value f(1,1)?
Exercise 6. Define the relation ∼ on the integers by a ∼ b iff a − b is even. Prove that ∼ is an equivalence relation.
Graphs. Undirected and directed graphs, vertices, edges, degrees. Paths, cycles, trees. Complete graphs. Bipartite graphs. Graph connectivity.
Exercise 7. Consider an undirected graph G = (V, E) with vertex set V = {1, 2, 3, 4} and edge set E = {{1, 2}, {2, 3}, {1, 3}, {2, 4}, {1, 4}}. Draw the graph G. What is the degree of vertex 1? of vertex 3? Draw a path from vertex 3 to vertex 4. Find a cycle of length 3. Is the graph connected?
Pigeonhole principle. If n pigeons are placed into n−1 pigeonholes, then some pigeonhole must contain more than one pigeon.
Exercise 8. Choose five distinct integers between 0 and 7, inclusive. Show that there exists a pair of them which add up to 7.
Propositional logic. Negation (not), conjunction (and), disjunction (or). Exclusive or (xor), equality, implication. Distributive laws for and/or, De Morgan’s law. Converse, inverse, contrapositive. Quantifiers (∃, ∀).
Exercise 9. Negate the following English sentence: Every CS major who is awesome is enrolled in CS 332.
Exercise 10. Show that the following Boolean formulas are equivalent: a ̄ ∧ (b ∨ c ̄) and (a ̄∧b)∨(a∨c).
Exercise 11. Which of the following statements is true? ∀x ∈ N, ∃y ∈ N, y = x + 1, or ∃x ∈ N, ∀y ∈ N, y = x + 1.
2 Algorithms
Asymptotic notation. Big-Oh O, little-oh o, Big-Omega Ω, little-omega ω, Theta Θ.
Exercise 12. Show that 3n2 + 2n − 1 = O(n2). Show that 2n = o(3n). 2
Graph algorithms. Breadth-first search, depth-first search, finding connected compo- nents.
Dynamic programming. Top-down and bottom-up recursion. DP algorithms for com- puting Fibonacci numbers, interval scheduling, and Knapsack.
Exercise 13. Design an algorithm for the following problem. Given n denominations of coins {c1,…,cn} and a target value V, find the fewest number of coins needed to make change for V . (Or report that making change for V is impossible.) Your algorithm should run in time O(nV ).
NP-completeness. Problems in NP, reductions, definition of NP-completeness. Classic NP-complete problems: SAT, clique, 3-coloring, Hamiltonian path. (It’s ok if this is unfa- miliar since building the formal theory of NP-completeness is a major topic of 332. However, it will be useful to come into that part of the course with some intuition.)
3 Proof Techniques
Constructions and counterexamples. To prove the statement that some kind of object exists, a constructive proof exhibits such an object. To disprove a statement about all members of some set of objects, it suffices to find a counterexample.
Exercise 14. Prove or give a counterexample to each of the following statements.
1. Every real number is an even integer.
2. For every positive even number n, there exists a number k ≥ n where k is divisible by 3.
Proof by contraposition. Proving a statement of the form P =⇒ Q is equivalent to proving that ¬Q =⇒ ¬P.
Exercise 15. Give a contrapositive proof of the following statement. If n is an integer for which n2 is odd, then n is odd.
Proof by contradiction. To prove that a theorem is true, assume instead that the theo- rem is false and use it to derive a false consequence.
Exercise 16. Show that if a is rational and ab is irrational, then b is irrational.
3
Proof by induction. Ingredients of an inductive proof: Basis step, induction hypothesis, induction step. Strong induction. Structural induction (i.e., induction to reason about recursively defined objects, e.g., binary trees).
Exercise 17. Prove by induction on n that 20 +21 +· · ·+2n−12n = 2n+1 −1 for every n ∈ N. +
Exercise 18. Find the error in the following “proof” that all BU students are from the same city:
Claim: For every n ≥ 1, every set of n BU students is from the same city. Proof: By induction on n.
Basis step: Let n = 1. In any set of one BU student, all students in that set are from the same city.
Induction step: For n ≥ 1, assume the claim is true for n students and prove it is true for n+1 students. Let B be any set of n+1 BU students. We show that all students in B are from the same city. Remove one student from this set to obtain the set B1. By the induction hypothesis, all the students in H1 are from the same city. Now replace the removed student and remove a different student to obtain the set H2. Again by the induction hypothesis, all the students in H2 are from the same city. Therefore all the students in H are from the same city.
4