Nothing Special   »   [go: up one dir, main page]
Scribd Logo
Upload

Welcome to Scribd!

  • 15 views

    CS251 HW1

    Uploaded by

    saiyan.sly

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    CS251 HW1

    Uploaded by

    saiyan.sly
    15 views4 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    15 views4 pages

    CS251 HW1

    Uploaded by

    saiyan.sly

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 4

    CS251 HW1

    1)

    a)

    We can conjecture the power law here, the input sizes are increasing by a factor of 3 and the
    runtime ratio between these consecutive sizes is on average a 3.
    The runtime T(n) is linear for a given input size [O(n)]
    Because the ratio between run time and input size is on average 0.16 (2d.p)
    So T(n) = 0.16n
    O(T(n)) ⋴ O(n)
    One way we can predict the runtime for size 60750 is by multiplying the previous runtime by 3
    which is :
    3331.519*3 = 9994.557
    T(60750) = 9994.557
    b)
    It is not possible to state a conjecture for this experimental data because if we try using the
    doubling hypothesis, the ratio of consecutive runtimes is not following a constant value and
    therefore we can’t use the power law to make an accurate assumption.
    2)

    a) ∑𝑛−1 𝑛−1
    𝑖=0 ∑𝑗=𝑖+1 4 (there are 4 array accesses for every if statement)

    =∑𝑛−1
    𝑖=0 4(𝑛 − 𝑖 − 1)

    =4(∑𝑛−1 𝑛−1 𝑛−1


    𝑖=0 𝑛+∑𝑖=0 −𝑖 + ∑𝑖=0 −1)

    n(n+1)
    = 4(n2-( 2
    – n)-n)

    =4n2 -2n2-2n
    =2n2-2n
    T(n)=2(n2-n)
    b) Yes, it does in the new case there will only be 2 array accesses per if statement so the runtime
    expression will be cut by half so it would be:
    T(n) = n2 -n
    c) The output describes the number of non-equal pairs of elements in the array.
    d) The lowest possible value of count would be 0 , this is when the array has only identical
    elements.
    e) The highest possible value of count would be the maximum amount of pairs possible which is
    given by nC2 , an example would be increasing order of elements where no two elements are the
    same.
    3)
    Ignoring runtime in loops and only calculating the number of iterations for all subparts.

    a)
    2
    T(n)=( ∑𝑛−1 𝑛−1 𝑛 −1
    𝑖=1 ∑𝑗=0 1 ) + ∑𝑘=0 1

    T(n) = (∑𝑛−1
    𝑖=1 𝑛) + n
    2

    T(n) = (n-1)*n +n2


    T(n) = (n2-n) +n2
    T(n) = 2n2 -n
    b)
    n=2k
    k = log2n
    k is the number of iterations of the outer loop

    𝑖
    T(n)=( ∑𝑘𝑖=0 ∑2𝑗=1 1 )

    =( ∑𝑘𝑖=0 2𝑖 )

    =(2k+1-1) [sum of powers of 2]

    = (2𝑙𝑜𝑔2 𝑛+1 − 1)
    T(n)= 2n-1
    c)
    3
    T(n)=( ∑𝑛𝑖=0 ∑𝑛𝑗=𝑖=0 1 +∑𝑛𝑛+1
    −1
    1) [the outer loop will run in synergy with the inner loop until (i =
    n+1)because the inner for loop won’t run once i exceeds n. (i) starts at 0]
    T(n)=( ∑𝑛𝑖=0(𝑛 + 1) ) + n3- n-1

    T(n)= (𝑛 + 1)2 + n3- n-1


    T(n)=n3+n2+n
    4)
    a)
    Base case: Increment(0) = 1
    So when x is 0 , the returned value is 1 , so the base case holds.
    b) IH: Assume Increment(k) is true where k mod 2 ==1, then 2 * increment (⌊𝑘/2⌋ )= k + 1
    c)
    To Prove : Increment(k+1) is true and increment (k+2) is true
    Increment(k+1) = (k+1) +1 [since k+1 is odd]
    Increment(k+1) = k+2
    So it holds.
    Increment(k+2) = 2* increment( ⌊𝑘 + 2/2⌋) [since k+2 is even]
    𝑘
    Increment(k+1) = 2*increment (⌊2 + 1⌋)

    Increment(k+1) = 2*increment (⌊𝑘/2⌋) +1 (floor(k/2 +1) = floor(k/2) +1)


    Increment(k+1) = (k+1) +1 [I.H]
    Increment(k+1) = k+2
    True
    Therefore proved by induction.

    You might also like