CS240 - Fall 2022 Assignment 1

Problem 1    [3+3+3+3+3=15 marks]

Provide a complete proof of the following statements from first principles (i.e., using the original definitions of order notation).

a)  12n3 + 11n2 + 10 e O(n3 )                        d)  1000n e o(n log n)

b)  12n3 + 11n2 + 10 e Ω(n3 )

c)  12n3 + 11n2 + 10 e Θ(n3 )

e) nn  e ω(n20 )

Problem 2    [4+4=8 marks]

For each pair of the following functions, fill in the correct asymptotic notation among Θ, o, and ω in the statement f(n) e 门(g(n)).  Provide a brief justification of your answers.  In your justification you may use any relationship or technique that is described in class.

a)  f(n) =^n versus g(n) = (log n)2

b)  f(n) = n3 (5 + 2 cos 2n) versus g(n) = 3n2 + 4n3 + 5n

Problem 3    [6+6=12 marks]

Prove or disprove each of the following statements. To prove a statement, you should provide a formal proof that is based on the definitions of the order notations. To disprove a statement, you can either provide a counter example and explain it or provide a formal proof.   All functions are positive functions.

a)  f(n) e\ o(g(n)) and f(n) e\ ω(g(n)) ÷ f(n) e Θ(g(n))

b) min(f(n), g(n)) e Θ ╱ ←

Problem 4    [6 marks]

Suppose n is a power of two and θ is a parameter in the range 2 < θ < 3.  Derive an exact

closed form for the sum

log2 n

i=0

in terms of n and θ .  Hiηt． Re-write the formula as a geometric series, and treat θ = 2 as a special case.

Problem 5    [2+2+4+4=12 marks]

Consider the following procedure.

pre: n  is  a positive  integer

pre:  v[1 . .n]  is  a binary  vector  of  length n,

i .e . ,  each  entry  is  either  0  or  1

foo(v,n)

1 .      i  :=  1;

2 .     while  i<=n  and  v[i]=0  do

3               i  :=  i+1

4       od;

5 .     for  j  from  1  to  i  do

6 .             print("Hello world!")

7 .     od;

a) How many inputs are there are of size n?

b) What is the worst case number of calls to print? Give an exact formula in terms of n and justify your answer by giving an example of a worst case input of size n.

c) For i e {1, 2, . . . , n}, let Si  denote the subset of inputs of size n for which the number of calls to print is i. Describe what an element of Si looks like, and derive an expression for |Si |, the number of elements of Si .

d) What is the average case number of calls to print? Derive an exact closed form formula in terms of n.

Problem 6    [5 marks]

Prove that the following code fragment will always terminate.

s  :=  3*n    // n  is  an  integer

while  (s>0)

if  (s  is  even)