CS 5633: Analysis of Algorithms Homework 1 1. Loop Invariants: Consider the code below with computes 2n for any integer n ≥ 0. function pow(n) k = 1 c = 0 while c 0; i = i− 4 do for j = 20n; j > 0; j...

Consider the code below with computes 2n for any integer n  0.


CS 5633: Analysis of Algorithms Homework 1 1. Loop Invariants: Consider the code below with computes 2n for any integer n ≥ 0. function pow(n) k = 1 c = 0 while c < n="" do="" k="k" ·="" 2="" c="c" +="" 1="" end="" while="" return="" k="" end="" function="" (a)="" state="" a="" loop="" invariant="" for="" the="" while="" loop="" that="" will="" allow="" you="" to="" prove="" the="" correctness="" of="" the="" algorithm.="" (b)="" use="" the="" loop="" invariant="" to="" prove="" the="" correctness="" of="" the="" algorithm.="" for="" this="" you="" need="" to="" prove="" by="" induction="" that="" the="" invariant="" holds="" for="" each="" iteration="" of="" the="" loop,="" and="" then="" use="" the="" loop="" invariant="" after="" the="" last="" iteration="" of="" the="" loop="" to="" prove="" the="" correctness="" of="" the="" algorithm.="" (c)="" what="" is="" the="" runtime="" of="" the="" algorithm?="" 2.="" evaluating="" runtimes:="" give="" the="" θ-running="" time="" for="" each="" example.="" justify="" your="" answers="" (a)="" for="" i="3n;" i=""> 0; i = i− 4 do for j = 20n; j > 0; j = j/3 do · · · end for end for 1 (b) for i = 3n2; i > 0; i = i− 1 do for j = i; j > 0; j = j/2 do · · · end for end for 3. Asymptotic Growth : Prove the following statements are true using the definitions of O, o,Ω, and Θ. (a) 4n5 − 50n2 + 10n ∈ Θ(n5) (b) 5n2/3 + 8 log n ∈ o(n). (c) n5 + 4n2 + 15 ∈ Ω(n3) 4. Big-Oh Sorting: Sort the following functions in order of non-decreasing asymptotic growth. That is, order them f1, f2, f3 . . . such that f1 ∈ O(f2), f2 ∈ O(f3), etc. 10n n1/3 nn log2 n n 5 2 √ log2 n 2