University Of Toronto CSC 165 H1F December 2019 Exam PDF

UNIVERSITY OF TORONTO Faculty of Arts & Science December 2019 Examinations CSC 165 H1F Do not turn this page until Instructor(s): Danny Heap you have receiv...

UNIVERSITY OF TORONTO Faculty of Arts & Science December 2019 Examinations CSC 165 H1F Do not turn this page until Instructor(s): Danny Heap you have received the signal to start. In the meantime, write your name, student Duration: 3 hours number, and UTORid below (please do this now!) and carefully read all the information Aids Allowed: Sorry, no aids. on the rest of this page. First (Given) Name(s): Last (Family) Name(s): 10-Digit Student Number: UTORid (e.g., pitfra12): This final examination consists of 8 questions on 18 pages (including this one), printed on both sides of the paper. When you receive the signal to start, please Marking Guide make sure that your copy of the examination is complete. No 1: / 8 Answer each question directly on the examination paper, in the space provided, and use a “blank” page for rough work. If you need more space for one of your No 2: / 8 solutions, use one of the “blank” pages and indicate clearly the part of your work No 3: / 8 that should be marked. No 4: / 4 Remember that, in order to pass the course, you must achieve a grade of at least 40% on this final examination. No 5: / 8 As a student, you help create a fair and inclusive writing environment. If you No 6: / 8 possess an unauthorized aid during an exam, you may be charged with an No 7: / 8 academic offence. No 8: / 8 You may reference and use external facts only from course notes, problem set solutions, lecture examples, and worksheet solutions, provided the external facts TOTAL: /60 have not been prohibited. students must hand in all examination materials at the end  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Use the space on this “blank” page for scratch work, or for any solution that did not fit elsewhere. Clearly label each such solution with the appropriate question and part number.  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Question 1. (short answer) [8 marks] Part (a) (binary representation) [1 mark] Give the binary representation of 61 that has no leading 0s on the left. Part (b) (predicates) [1 mark] Define predicates 𝑃(𝑛) and 𝑄(𝑛) so that one of the statements below is true, and the other is false. (∀𝑛 ∈ ℕ, 𝑃(𝑛) ⇒ 𝑄(𝑛)) ⇒ (∃𝑚 ∈ ℕ, 𝑃(𝑚) ∧ 𝑄(𝑚)) (∃𝑛 ∈ ℕ, 𝑃(𝑛) ⇒ 𝑄(𝑛)) ⇒ (∀𝑚 ∈ ℕ, 𝑃(𝑚) ∧ 𝑄(𝑚)) Part (c) (moduli) [1 mark] What number 0 ≤ 𝑖 < 15 satisfies 𝑖 ≡ 2 (mod 3) and 𝑖 ≡ 4 (mod 5)? Part (d) (run-time) [1 mark] How many times does the the loop iterate for doubler(17)?  def doubler(n):  i = 1  while i * i < n:  i = 2 * i  return loops Part (e) (𝒊 for iterations?) [1 mark] Give a formula for 𝑖(𝑠), the value of 𝑖 at the end of 𝑠 iterations of the loop in doubler. Part (f ) (iterations for 𝒏?) [1 mark] Give a general formula for the number of iterations of the loop for doubler(n), where 𝑛 ∈ ℕ+. Part (g) (dogs...) [1 mark] Define the set of dogs as 𝐷, and the predicate 𝐴(𝑑): ”𝑑 lives in the arctic.” and 𝐹 (𝑑): ”𝑑 has fleas.” Write a predicate logic statement that says there is exactly one dog that has fleas and lives in the arctic. You may not use the short-form ∃! Part (h) units digit... [1 mark] What is the units digit (ones-place digit) of 398312  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Question 2. (number theory) [8 marks] Part (a) (moduli) [4 marks] Prove that for any 𝑎, 𝑏 ∈ ℤ if 𝑎 ≡ 𝑏 (mod 17) and 𝑎 ≡ 𝑏 (mod 19) then 𝑎 ≡ 𝑏 (mod 17 × 19). You may use, without proof, the following theorem (Example 2.16 in notes): ∀𝑖, 𝑗, 𝑝 ∈ ℕ, 𝑃𝑟𝑖𝑚𝑒(𝑝) ∧ 𝑝 ∣ 𝑖𝑗 ⇒ 𝑝 ∣ 𝑖 ∨ 𝑝 ∣ 𝑗 You may not use the result of Q2(a) in Problem Set #2. December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Part (b) (prime free?) [4 marks] Recall that for natural number 𝑛, the quantity 𝑛! (aka “𝑛 factorial”) is defined: { ∏𝑖=𝑛 𝑖=1 𝑖 if 𝑛 > 0 𝑛! = (informally, 𝑛! = 𝑛(𝑛 − 1)(𝑛 − 2) ⋯ 1) 1 if 𝑛 = 0 Assume 𝑚 is some natural number bigger than 1. Prove that there does not exist a prime number 𝑝 such that (𝑚! + 2) ≤ 𝑝 ≤ (𝑚! + 𝑚).  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Question 3. big-omega/oh [8 marks] In what follows use the following definitions for 𝑓 ∈ Ω(𝑔) and 𝑓 ∈ (𝑔): 𝑓 ∈ Ω(𝑔) ∶ ∃𝑐Ω , 𝑛Ω ∈ ℝ+ , ∀𝑛 ∈ ℕ, 𝑛 ≥ 𝑛Ω ⇒ 𝑓 (𝑛) ≥ 𝑐Ω 𝑔(𝑛) 𝑓 ∈ (𝑔) ∶ ∃𝑐 , 𝑛 ∈ ℝ+ , ∀𝑛 ∈ ℕ, 𝑛 ≥ 𝑛 ⇒ 𝑓 (𝑛) ≤ 𝑐 𝑔(𝑛) Define 𝑓 (𝑛) = 𝑛4 and 𝑔(𝑛) = 2𝑛. You may not use techniques of calculus such as limits, and you may not use external facts from the notes or elsewhere stating 𝑛𝑎 ∉ Ω(𝑏 𝑛 ) or that 𝑛𝑎 ∈ (𝑏 𝑛 ). You may assume, without proof, that for any integer 𝑘 greater than 5, 2𝑘 > 8𝑘 (although you are not required to use this). You may also assume, without proof, that (𝑛 + 1)4 = 𝑛4 + 4𝑛3 + 6𝑛2 + 4𝑛 + 1. Part (a) (big-omega) [4 marks] Prove that 𝑓 ∉ Ω(𝑔). December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Part (b) (big-oh) [4 marks] Prove that 𝑓 ∈ (𝑔).  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Question 4. (runtime) [4 marks] Read the code for has_dominator below:  def has_dominator(integer_list):  n = len(integer_list)  for i in range(n):  for j in range(i + 1, n):  if integer_list[i] < integer_list[j]:  return True  return False If it helps, in the questions below you may assume without proof: 𝑖=𝑚 𝑚(𝑚 + 1) ∑𝑖= 𝑖=0 2 Part (a) (upper bound) [1 mark] State and prove a “good” upper bound, 𝑈 (𝑛), on the worst-case (i.e. maximum) run-time for has_dominator on inputs of length 𝑛. By “good” I mean it should have the same asymptotic complexity as the lower bound. Part (b) (lower bound) [3 marks] State and prove a “good” lower bound, 𝐿(𝑛) on the worst-case (i.e. maximum) run-time for has_dominator on inputs of length 𝑛. By “good” I mean it should have the same asymptotic complexity as the upper bound. December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Use the space on this “blank” page for scratch work, or for any solution that did not fit elsewhere. Clearly label each such solution with the appropriate question and part number.  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Question 5. (hunting primes) [8 marks] In the code below integer_list contains numbers from {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, with duplicates allowed. The code is intended to return True if integer_list contains one of the primes in {2, 3, 5, 7}, and False otherwise. In what follows, if has_prime returns True right after examining 𝑘 entries in integer_list, count this as 𝑘 steps. If has_prime returns False after examining all entries in integer_list, count this as the length of the list + 1 steps.  def has_prime(integer_list) -> bool:  for i in range(len(integer_list)):  if integer_list[i] in [2, 3, 5, 7]:  return True  return False Part (a) (length 3) [4 marks] Calculate the average number of steps has_prime takes on lists of length 3. Be sure to show the number of lists that have their first prime in the first, second, or third position, and how many have no primes at all. December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Part (b) (general case) [4 marks] Derive a closed formula for the average number of steps has_prime takes on lists of length 𝑛. Explain how your formula is derived. You may use, without proof, the following summation (although you are not required to use it): 𝑚 (𝑚 + 1)𝑟 𝑚+1 𝑟 − 𝑟 𝑚+2 ∑ 𝑖𝑟 𝑖 = + 𝑖=1 𝑟 −1 (𝑟 − 1)2  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Question 6. (sets) [8 marks] Part (a) (subsets) of size 5 [5 marks] Define: 𝑛(𝑛 − 1)(𝑛 − 2)(𝑛 − 3)(𝑛 − 4) 𝑃(𝑛) ∶ ∀ sets 𝑆, |𝑆| = 𝑛 ⇒ 𝑆 has exactly subsets of size 5 120 Use induction on 𝑛 to prove ∀𝑛 ∈ ℕ, 𝑃(𝑛). You may assume, without proof, that any set with 𝑛 elements has 𝑛(𝑛−1)(𝑛−2)(𝑛−3) 24 subsets of size 4. December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Part (b) (reverse quantification?) [3 marks] Suppose we modify your proof by changing the introduction of 𝑆 and 𝑛 as follows: Let 𝑆 be an arbitrary set. Define: 𝑛(𝑛 − 1)(𝑛 − 2)(𝑛 − 3)(𝑛 − 4) 𝑃(𝑛) ∶ |𝑆| = 𝑛 ⇒ 𝑆 has exactly subsets of size 5 120... followed by the base case and inductive step you have in the previous part. Is your proof still valid? Explain why, or why not.  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Question 7. (connected?) [8 marks] Part (a) (enough vertices?) [3 marks] Assume 𝐺 = (𝑉 , 𝐸) is a finite, undirected graph where every vertex 𝑣 ∈ 𝑉 has degree at least |𝑉 | − 5, and |𝑉 | ≥ 9. Prove that 𝐺 is connected. December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Part (b) (too few vertices?) [2 marks] Assume 𝐺 = (𝑉 , 𝐸) is a finite, undirected graph where every vertex 𝑣 ∈ 𝑉 has degree at least |𝑉 | − 5, and |𝑉 | = 8. Prove that 𝐺 is not necessarily connected. Part (c) (what’s wrong with this?) [3 marks] Read the following “proof.” What is the smallest 𝑛 for which 𝑃(𝑛) does not imply 𝑃(𝑛 + 1)? Explain how the argument breaks down in this case, and why the proof is invalid. Define 𝑃(𝑛) ∶ ∀𝐺 = (𝑉 , 𝐸), |𝐸| = |𝑉 | − 1 ⇒ 𝐺 is connected. I will “prove” by induction that ∀𝑛 ∈ ℕ+ , 𝑃(𝑛). base case 𝑷(𝟏): Any graph with |𝑉 | = 1 vertex and 1 − 1 = 0 edges, has its sole vertex connected to itself, which verifies 𝑃(1). inductive step: Let 𝑛 ∈ ℕ+ and assume 𝑃(𝑛). Let 𝐺 = (𝑉 , 𝐸) be an arbitrary graph with |𝑉 | = 𝑛 and |𝐸| = 𝑛 − 1. By the inductive hypothesis 𝐺 is connected. Add an arbitrary vertex 𝑣, and an arbitrary edge (𝑣, 𝑢) connecting 𝑣 to an arbitrary vertex in 𝑉 , so 𝐺 ′ = (𝑉 ′ , 𝐸 ′ ), where 𝑉 ′ = 𝑉 ∪ {𝑣} and 𝐸 ′ = 𝐸 ∪ {(𝑣, 𝑢)}. Now |𝑉 ′ | = 𝑛 + 1, |𝐸 ′ | = 𝑛, and 𝑣 is connected to 𝑢 and hence, by transitivity, to every vertex in 𝑉 ′. So 𝐺 ′ has 𝑛 + 1 vertices, 𝑛 edges, and is connected.  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Question 8. (more graphs...) [8 marks] Part (a) (connected?) [5 marks] Assume 𝐺 = (𝑉 , 𝐸) is a finite, undirected, bipartite graph, that is 𝑉 = 𝑉1 ∪ 𝑉2 , 𝑉1 ∩ 𝑉2 = ∅, and (𝑢, 𝑣) ∈ 𝐸 ⇒ (𝑢 ∈ 𝑉1 ∧ 𝑣 ∈ 𝑉2 ) ∨ (𝑣 ∈ 𝑉1 ∧ 𝑢 ∈ 𝑉2 ). Also assume that 𝐺 is complete, that is 𝑢 ∈ 𝑉1 ∧ 𝑣 ∈ 𝑉2 ⇒ (𝑢, 𝑣) ∈ 𝐸 — every possible edge between partitions is present. Finally, assume |𝑉 | ≥ 2, |𝑉1 | = ⌊|𝑉 |/2⌋, and |𝑉2 | = ⌈|𝑉 |/2⌉. Prove that 𝐺 is connected. December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Part (b) (paths) [3 marks] Suppose 𝑘 ∈ ℕ and path 𝑃 = (𝑉 , 𝐸), where 𝑉 = {𝑣𝑖 ∶ 0 ≤ 𝑖 ≤ 𝑘} and 𝐸 = {(𝑣𝑖 , 𝑣𝑖+1 ) ∶ 0 ≤ 𝑖 < 𝑘} is a path from 𝑣0 to 𝑣𝑘. Recall that 𝑃 is connected means that for any pair of vertices 𝑢, 𝑣 in 𝑃, there is a path from 𝑢 to 𝑣. Prove that 𝑃 is connected. You may not use the result from Problem Set #4 that says a cycle with one edge removed is connected, nor Example 6.8 from the course notes that says a connected graph containing a cycle remains connected if an edge is removed from the cycle.  December 2019 Examinations CSC 165 H1F — Danny Heap Duration: 3 hours Use the space on this “blank” page for scratch work, or for any solution that did not fit elsewhere. Clearly label each such solution with the appropriate question and part number. Total Marks = 60