Reference no: EM132263659

Mathematical Expression and Reasoning for Computer Science Assignment -

Problem 1 - Printing multiples

Consider the following algorithm:

1 def print_multiples(n: int) -> None:

2 """Precondition: n > 0."""

3 for d in range(1, n + 1): # Loop 1

4 for multiple in range(0, n, d): # Loop 2 (also, see Python Note below)

5 print(multiple)

Python Note: range(0, n, d) consists of the multiples of d ≥ 0 and < n: 0, d, . . . , d(⌈n/d⌉ - 1).

(a) Find, with proof, a Theta bound for _i=1∑ⁿ⌈n/i⌉ in terms of elementary functions (e.g., n, log n, 2ⁿ, etc.). You may not use any properties of Big-Oh/Omega/Theta; instead, only use their definitions, as well as the following Facts (clearly state where you use them):

_i=1∑ⁿ 1/i ∈ Θ(log n) (Fact 1)

∀ x ∈ R, x ≤⌈x⌉ < x + 1 (Fact 2) 

(b) Using your answer to part (a), analyse the running time of print_multiples to determine a Theta bound on the running time.

(c) Now consider the following variation on the above algorithm.

1 def print_multiples2(n: int) -> None:

2 """Precondition: n > 0."""

3 for d in range(1, n + 1): # Loop 1

4 for multiple in range(0, n, d): # Loop 2

5 print(multiple)

6

7 if d % 5 == 0:

8 for i in range(d): # Loop 3

9 print(i)

Analyse the running time of print_multiples2 to determine a Theta bound on the running time. To simplify your analysis, you can focus on just counting the steps taken by Lines 5 and 9.

You may use your work from previous parts of this question, and the summation formula _i=1∑ⁿ i = (n(n+1))/2.

Problem 2 - Varying running times, input families, and worst-case analysis

1 def alg(lst: List[int]) -> None:

2 n = len(lst)

3 i = 1

4 j = 1

5 while i < n: # Loop 1

6 if lst[i] % 2 == 0:

7 i = i + 1

8 j = j * 2

9 else:

10 i = i * 2

11 for k in range(j): # Loop 2

12 print(k)

To simplify your analyses for this question, ignore the costs of Lines 2-4 and Line 10. (Of course, you'll have to understand what these lines do to analyse the running time, but you don't need to count them as "steps.")

(a) Find, with proof, an input family for alg whose running time is Θ(2ⁿ).

(b) Find, with proof, an input family for alg whose running time is Θ(log n x 2^√n), where the else branch of Loop 1 runs Θ(log n) times.

You can use the fact that log n - log(log n) ∈ Θ (log n) in your proof.

(c) Prove that the worst-case running time of alg is O(2ⁿ) (note that this matches the worst-case lower bound we can derive from part (a)).

Hint: unlike other examples we've looked at in class, there are no "early returns" here. Instead, use what you've learned about analysing loops with non-standard loop variable changes, and remember that you don't need exactly 2ⁿ steps, just an at most O(2ⁿ).

Problem 3 - Rearrangements, best-case analysis

We define the best-case running time of an algorithm func as follows:

BC_func(n) = min{running time of executing func(x) |x ∈ I_n}

Note that this is analogous to the definition of worst-case running time, except we use min instead of max.

(a) Review the definitions of what it means for a function f : N → R^≥0 to be an upper bound or lower bound on the worst-case running time of an algorithm.

Then, let I_n denote the set of all inputs of size n for rearrange, and write two symbolic definitions:

(i) What it means for a function f : N → R^≥0 to be an upper bound on the best-case running time of an algorithm.

(ii) What it means for a function f : N → R^≥0 to be a lower bound on the best-case running time of an algorithm.

Clearly state which definition is which in your answer? Your definitions should be very similar to the definitions we mentioned above from the Course Notes.

Hint: it is easier to first translate the simpler statements "M is an upper bound on the minimum of set S" and "M is a lower bound on the minimum of set S" to make sure you have the right idea.

(b) Consider the following Python function.

1 def rearrange(lst: List[int]) -> None:

2 for i in range(2, len(lst)): # Loop 1

3 if i % 2 == 0:

4 j = i - 2

5 while j >= 0 and lst[j+2] < lst[j]: # Loop 2

6 lst[j+2], lst[j] = lst[j], lst[j+2] # Swap lst[j] and lst[j+2]

7 j = j - 2

8 else:

9 j = i - 2

10 while j >= 0 and lst[j+2] > lst[j]: # Loop 3

11 lst[j+2], lst[j] = lst[j], lst[j+2] # Swap lst[j] and lst[j+2]

12 j = j - 2

Analyse the best-case running time of rearrange to find a Theta bound for it. Your analysis should consist of two parts, proving matching upper and lower bounds on the best-case running time separately, and then using them to conclude a Theta bound.

To simplify your analysis, you only need to count the total number of steps taken inside Loops 2 and 3, and not the other operations (e.g., Lines 4 and 9).

Problem 4 - An average-case analysis

Note: we'll introduce this type of analysis with an example similar to this problem on Monday, March 18. We recommend prioritizing the other problems on this problem set until then.

Consider the following algorithm.

1 def find_one_or_two(lst: List[int]) -> Optional[int]:

2 """Return the index of the first 1 or 2 in lst, or None if neither of them appear."""

3 for i in range(len(lst)):

4 if lst[i] == 1 or lst[i] == 2:

5 return i

6

7 return None

We consider the following inputs for this function: for every n ∈ N, we define the set I_n to be the set of lists of length n that are permutations of the numbers {1, 2, . . . , n}. We know that |I_n| = n! (where n! = n x (n - 1) x · · · x 2 x 1).

Note that if n ≥ 1, then every list in I_n contains a 1 or 2, and so the algorithm find_one_or_two will always return an index.

For this question, you can use your answer for each part in all subsequent parts.

(a) Let n ∈ N, and assume n ≥ 2. Let I, j ∈ N, and assume i ≠ j, and that both are between 0 and n - 1, inclusive.

Find a formula, in terms of n, i, and/or j, for the exact number of lists 1st in I_n where 1st[i] equals 1 and 1st[j] equals 2. Prove that your formula is correct.

(b) Let n ∈ N, and assume n ≥ 2. Let i ∈ N, and assume i is between 0 and n - 1, inclusive. Find a formula, in terms of n and/or i, for the exact number of lists 1st in I_n where 1st[i] equals 1, and 2 appears in 1st at an index greater than i.

(c) Let n ∈ N, and assume n ≥ 2. Find an exact expression for the average running time of find_one_or_two on I_n.

Count each iteration of the loop as just 1 step, and include the last partial iteration (the one that executes return i) in your count. Note that for this set of inputs, the loop will always return early, so the final return None will never execute.

You may use the following formulas in your calculation, valid for all m ∈ N:

_i=1∑^m i = (m(m+1))/2

_i=1∑^m i² = (m(m+1)(2m+1))/6

Hint: you can use your work from part (b), but make sure in your analysis here to consider the cases where 2 appears before 1 in the list.

Attachment:- Assignment File.rar