EECS 376: Foundations of Computer Science Homework 1

EECS 376: Foundations of Computer Science Homework 1

We may grade a subset of the assigned questions, to be determined after the deadline, so that we can provide better feedback on the graded questions. Unless otherwise stated, each question requires sufficient justification to convince the reader of the correctness of your answer. For bonus questions, we will not provide any insight during office hours or Piazza, and we do not guarantee anything about the difficulty of these questions. We strongly encourage you to typeset your solutions in LATEX. If you collaborated with someone, you must state their name(s). You must write your own solution for all problems and may not look at any other student’s write-up. 0. If applicable, state the name(s) and uniqname(s) of your collaborator(s). Solution: 1. Extra credit: You do not have to do this question to receive full credit on this assignment. To receive the bonus points, you must typeset this entire assignment in LATEX and draw a table with two columns that includes the name (e.g., “fraction”) and an example of each of the following: • fraction (using \frac) • less than or equal to • union of two sets • an expression involving a sum (P) and product (Q ). • write a quantified formula about the reals (R) using both quantifiers (∃, ∀). Unlike most extra credit questions, we will help with this in office hours. Solution: 2. Use induction to prove the following statements for all integers n ≥ 1. (a) Pn i=0 x i = x n+1−1 x−1 , for all x 6= 1. (b) The number of binary strings of length n is 2 n . (c) In any drawing of a planar graph G having v vertices, e edges, f faces, and c connected components, v + f − e − c = 1. (A planar graph is one that can be drawn in the plane without crossing edges. A face is a connected region of the plane after removing vertices and edges. If you remove a vertex or edge from a planar graph, it is still planar. Below is a planar graph with v = 8, e = 10, f = 4, c = 1.) 1 EECS 376: Foundations of Computer Science University of Michigan, Fall 2023 Homework 1 Due 8:00pm, Sept 6 (accepted until 9:59 pm, no credit after) Solution: 3. A rational number may be written as a/b for some integers a, b, where b 6= 0. Prove that √p is not a rational number, for any prime p. Hint: Use a proof by contradiction. Solution: 4. Recall that for positive functions f(n), g(n), we say that f(n) = O(g(n)) if there exist constants c, n0 > 0 such that f(n) ≤ c·g(n) for every n ≥ n0. Alternatively, a sufficient condition is that limn→∞ f(n) g(n) is finite. (Note, however, that this condition is not necessary; it is possible that f(n) = O(g(n)) even when the limit does not exist.) For the following pairs of f(n) and g(n), is it true that f(n) = O(g(n))? Justify your answer. Hint: You might find L’Hôpital’s Rule useful for some questions: it says that limn→∞ f(n) g(n) = limn→∞ f 0 (n) g 0(n) (when the latter limit exists), where f 0 and g 0 are the derivatives of f and g, respectively. (a) f(n) = n + log2 (n 4 ), g(n) = 1 9 n + 5. Solution: (b) f(n) = (ln n) 3 , g(n) = 3log2 n Solution: (c) f(n) = 21.3n , g(n) = 1 2 e n Solution: (d) f(n) = log2 (n 100), g(n) = log2 (n) Solution: (e) f(n) = n 3 , g(n) = n 3
. Solution: 5. Suppose you want to count the number of primes less than or equal to t. You have a function is-prime(i) that takes 1 time-step and returns true if i is prime. f u n c ti o n count−prime ( t ) : // t >= 2 i s a non−n e g a ti v e i n t e g e r count = 0 f o r i from t down t o 2 i f ( i s −prime ( i ) ) count++ r e t u r n count EECS 376: Foundations of Computer Science University of Michigan, Fall 2023 Homework 1 Due 8:00pm, Sept 6 (accepted until 9:59 pm, no credit after) What is the running time of count-prime, as a function of its input size? (First determine what the input size is.) Give an asymptotic upper bound (big-O) on its running time. Solution: 6. Suppose you want to unambiguously represent all of the elements of {0, 1, . . . , n−1} as strings in Σ k . Here Σ is a set of symbols (the alphabet) and Σ k means the set of all strings over Σ with length exactly k. Given |Σ| ≥ 2 and n, what is the smallest possible k that allows this? Solution: 3