CSC165H1, Winter 2020 Problem Set 4 CSC165H1: Problem Set 4 Due Friday March 27, 2020 before 4pm General instructions Please read the following instructions carefully before starting the problem set. They contain important information about general problem set expectations, problem set submission instructions, and reminders of course policies. • Your problem sets are graded on both correctness and clarity of communication. Solutions that are technically correct but poorly written will not receive full marks. Please read over your solutions carefully before submitting them. • Each problem set may be completed in groups of up to three. If you are working in a group for this problem set, please consult https://github.com/MarkUsProject/Markus/wiki/Student_Groups for a brief explanation of how to create a group on MarkUs. Exception: Problem Set 0 must be completed individually. • Solutions must be typeset electronically, and submitted as a PDF with the correct filename. Hand- written submissions will receive a grade of ZERO. The required filename for this problem set is problem set4.pdf. • Problem sets must be submitted online through MarkUs. If you haven’t used MarkUs before, give yourself plenty of time to figure it out, and ask for help if you need it! If you are working with a partner, you must form a group on MarkUs, and make one submission per group. “I didn’t know how to use MarkUs” is not a valid excuse for submitting late work. • Your submitted file(s) should not be larger than 9MB. You might exceed this limit if you use a word processor like Microsoft Word to create a PDF; if it does, you should look into PDF compression tools to make your PDF smaller, although please make sure that your PDF is still legible before submitting! • Submissions must be made before the due date on MarkUs. You may use grace tokens to extend the deadline; please see the Homework page for details on using grace tokens. • The work you submit must be that of your group; you may not use or copy from the work of other groups, or external sources like websites or textbooks. Additional instructions • All final Big-Oh, Omega, and Theta expressions should be fully simplified according to three rules: don’t include constant factors (so O(n), not O(3n)), don’t include slower-growing terms (so O(n2), not O(n2 + n)), and don’t include floor or ceiling functions (so O(log n), not O(dlog ne)). • For algorithm analysis questions, you can jump immediately from a closed-form step count expression to an asymptotic bound without proof (e.g., write “the number of steps is 3n+log n, which is Θ(n)”). This applies to upper and lower bounds (Big-Oh and Omega) as well. • However, you must evaluate all summations before jumping to an asymptotic bound. Page 1/6 https://github.com/MarkUsProject/Markus/wiki/Student_Groups CSC165H1, Winter 2020 Problem Set 4 • Unless specified otherwise in the question, you should use floor/ceiling to ensure you are counting steps exactly as natural numbers. • Unless specified otherwise in the question, you should count the cost of all lines of code in an algorithm, including constant-time steps. Page 2/6 CSC165H1, Winter 2020 Problem Set 4 1. [8 marks] Analyzing nested loops. Our goal for this question is to analyse the running time of the following function: def print_threes(n: int) -> None: """Precondition: n > 1""" for i in range(1, n + 1): # Loop 1 j = 1 while j < i:="" #="" loop="" 2="" ="" print(i)="" ="" j="j" *="" 3="" (a)="" [do="" not="" hand="" in—this="" question="" part="" is="" not="" graded.]="" first,="" prove="" that="" for="" all="" functions="" f,="" g="" :="" n→="" r+="" and="" b="" ∈="" r+,="" if="" all="" three="" of="" the="" following="" conditions="" are="" true:="" (i)="" g(n)="" ∈="" θ(f(n))="" (ii)="" f(n)="" and="" g(n)="" are="" eventually="" ≥="" b="" (refer="" to="" problem="" set="" 1="" for="" the="" definition="" of="" eventually)="" (iii)="" b=""> 1 then logb(g(n)) ∈ Θ(logb(f(n))). (b) Find, with proof, an exact expression for the running time of print threes in terms of its input n, assuming n > 1. Your final expression may contain summation notation (e.g., n∑ i=1 i); do not simplify to an asymptotic (Big-Oh/Omega/Theta) expression here. To simplify your analysis, ignore the cost of Line 4 (j = 1). (c) Analyze the running time of print threes in terms of its input n, concluding with a Theta bound on the running time. You may use the statement from part (a) and your answer to part (b), and the following external facts:1 ∀x ∈ R, x ≤ dxe < x="" +="" 1="" (fact="" 1)="" n!="" ∈="" θ(en="" lnn−n+="" 1="" 2="" lnn)="" (fact="" 2)="" the="" exponent="" of="" e="" in="" fact="" 2="" is="" eventually="" ≥="" 1="" (fact="" 3)="" 1some="" reminders="" of="" notation:="" n!="" is="" the="" factorial="" function="" defined="" as="" n!="1" ·="" 2="" ·="" 3="" ·="" ·="" ·="" ·="" ·="" (n−="" 1)="" ·n.="" e="" ≈="" 2.71828="" .="" .="" .="" is="" euler’s="" number;="" the="" natural="" logarithm="" is="" the="" function="" lnn="loge" n.="" page="" 3/6="" csc165h1,="" winter="" 2020="" problem="" set="" 4="" 2.="" [9="" marks]="" odds="" and="" evens.="" consider="" the="" following="" python="" function:="" ="" def="" longest_even_prefix(nums:="" list[int])="" -=""> int: """Return the length of the longest prefix of nums that contains only even numbers. (A prefix of length 0 is considered to contain only even numbers.) """ n = len(nums) for i in range(n, -1, -1): # Loop 1: i = n, n-1, ..., 0 found_odd = False for j in range(i): # Loop 2: j = 0, 1, ..., i - 1 if nums[j] % 2 == 1: found_odd = True break # Breaks out of Loop 2 (goes to Line 14). if not found_odd: return i You may find the following formula helpful (valid for all n ∈ N): n∑ i=1 i = n(n + 1) 2 (a) Find, with proof, a tight asymptotic upper bound (Big-Oh expression) on the worst-case running time of longest even prefix.2 (b) Prove an aymptotic lower bound (Omega expression) on the worst-case running time of this algorithm that matches the upper bound you proved in part (a). (c) Prove that for all n ∈ N and every list nums of integers of length n, the running time of longest even prefix(nums) is Ω(n).3 Hint: do a proof by cases based on which elements of nums are even/odd. 2Remember that tight means that it should be possible to prove a matching asymptotic lower bound (Omega) on the worst-case running time, but you shouldn’t do that in this part. 3 If you compare this to the definition of upper bound on the worst-case running time of a function, you might notice that what we’re asking you to prove here is a lower bound on the best-case (i.e., minimum) running time of longest even prefix. Page 4/6 CSC165H1, Winter 2020 Problem Set 4 3. [10 marks] Unpredictable loop variables. Consider the following function: def func(lst: List[int]) -> None: n = len(lst) i = 0 j = 1 while i < n:="" ="" if="" lst[i]="">= 0: i = i + j else: lst[i] = abs(lst[i]) i = 0 j = j * 2 (a) Find, with proof, an input family for func whose running time is Θ(log n). (b) Find, with proof, an input family for func whose running time is Θ(n) and for which the else branch (Lines 9–11) executes Ω(log n) times. To simplify your analysis, you may assume n (the length of the list) is a power of 2.4 You may use the following formula, valid for all n ∈ N and r ∈ R where r 6= 1: n−1∑ i=0 ri = 1− rn 1− r (c) Prove that the worst-case running time for func is O(n). 4Your idea will likely generalize for non-powers of 2, but this makes the analysis messier. Page 5/6 CSC165H1, Winter 2020 Problem Set 4 4. [11 marks] An average-case analysis. Consider the following algorithm. def convert_to_binary(n: int) -> str: """Return the binary representation of n with no leading zeros (as a string). Precondition: n > 0. """ s = '' x = n while x > 0: r = x % 2 x = x // 2 # Same as floor(x/2) s = str(r) + s # Note: treat + with strings as a constant-time operation return s (a) First, for all k ∈ N, we let xk denote the value of variable x in this algorithm after k loop iterations, or 0 if fewer than k iterations occur. Note that this depends on the input n. For example, when n = 9, we have the sequence x0 = 9, x1 = 4, x2 = 2, x3 = 1, and x4 = x5 = x6 = · · · = 0. Prove by induction that ∀n ∈ Z+, ∀k ∈ N, n 2k − 2 k − 1 2k ≤ xk ≤ n 2k . You may use the fact that ∀x ∈ Z, x− 1 2 ≤ ⌊x 2 ⌋ ≤ x 2 . Hint: you should do induction on k, not n, in the above formula. Introduce n first just as an arbitrary positive integer. (b) Using part (a), fill in the blanks of the statement below, and prove the resulting statement. ∀n ∈ Z+, ∀k ∈ N, (convert to binary(n) takes exactly k loop iterations)⇔ ≤ n ≤ (c) Now we define the following inputs for this function: for every n ∈ Z+, let In = {1, . . . , 2n − 1}. Using parts (a) and/or (b), find an exact, closed-form expression for the average running time of convert to binary on In (in terms of n). Do not convert to a Theta expression—we’re looking for the exact average number of steps here. To simplify your solution, you may ignore the costs of lines 6, 7, and 12 in your calculation, and treat the loop body as a single step. You may use the following formula, valid for all m ∈ N and r ∈ R where r 6= 1: m∑ i=1 iri−1 = 1− rm+1 (1− r)2 − (m + 1)r m 1− r Page 6/6