Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    HW 1

    Uploaded by

    Eden
    This document contains an introduction to algorithms homework assignment with 4 problems. Problem 1 asks to determine if a power algorithm runs in linear or non-linear time. Problem 2 involves calculating probabilities of drawing balls from an urn. Problem 3 analyzes the running time of the Euclid's algorithm. Problem 4 proves properties of a multi-level insertion sort algorithm.

    Copyright:

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

    HW 1

    Uploaded by

    Eden
    31 views3 pages
    This document contains an introduction to algorithms homework assignment with 4 problems. Problem 1 asks to determine if a power algorithm runs in linear or non-linear time. Problem 2 involves calculating probabilities of drawing balls from an urn. Problem 3 analyzes the running time of the Euclid's algorithm. Problem 4 proves properties of a multi-level insertion sort algorithm.

    Original Title

    hw1

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document contains an introduction to algorithms homework assignment with 4 problems. Problem 1 asks to determine if a power algorithm runs in linear or non-linear time. Problem 2 involves calculating probabilities of drawing balls from an urn. Problem 3 analyzes the running time of the Euclid's algorithm. Problem 4 proves properties of a multi-level insertion sort algorithm.

    Copyright:

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

    HW 1

    Uploaded by

    Eden
    This document contains an introduction to algorithms homework assignment with 4 problems. Problem 1 asks to determine if a power algorithm runs in linear or non-linear time. Problem 2 involves calculating probabilities of drawing balls from an urn. Problem 3 analyzes the running time of the Euclid's algorithm. Problem 4 proves properties of a multi-level insertion sort algorithm.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    Introduction to Algorithms Homework 1

    Instructors: Xue Chen due: 3.16

    Problem 1 (20 points).


    Answer: non-linear
    The input length l = log k, cause we want be compute the power, so we assume n, q is fixed.
    Assuming that the product and modulo can be computed in Θ(1) , so the 6th line takes Θ(1),
    and the for loop iterate k times, so the total time T = Θ(k) = Θ(2log k ) = Θ(2l ) non-linear

    Algorithm 1 POWER in linear time


    function POWER(n, k, q)
    if k = 0
    return 1
    if k = 1
    return n
    if k mod 2 = 0
    return POWER(n ∗ n mod q, k/2, q)
    else
    return POWER(n ∗ n mod q, k/2, q)∗n mod q
    end function

    Correctness: base case: POWER work right for k = 0, 1.


    Say 2p ≤ k < 2p+1 , and assume that POWER work right for k/2p+1 (= 0), k/2p (= 1), ..., k/2i ,
    i = 1, .., p. Now we want want to prove it is right for k ′ = k/2i−1
    ′
    if k ′ is even, POWER(n ∗ n mod q, k ′ /2, q) ≡ nk
    ′
    if k ′ is odd, POWER(n ∗ n mod q, k/2, q)∗n mod q ≡ nk
    By conclusion we can prove for k ′ = k/20 = k, so it is correct.
    Runtime Analysis: Let T (k) be the time of POWER(n, k, q). We have T (k) = T (k/2) + O(1).
    log k
    X
    T (k) = O(1) = O(log k)
    i=1

    The input length is log k, so it’s linear


    Problem 2 (20 points).
    N!
    Answer: (a). (N −n)!N n (b). p1
    (a).The first ball have N options, and N −1 for the second ball, so the number of all the possible
    cases are N (N − 1)...(N − n + 1), so the probability is

    N (N − 1)...(N − n + 1) N!
    P = n
    =
    N (N − n)!N n
    (b).Let random varible X be the times of coin-throwing
    ∞
    X 1
    EX = i(1 − p)i−1 p =
    i=1
    p

    Problem 3 (20 points).


    Answer: O(log a + log b)
    Without losing the generality of analysis, let a ≥ b ,and let T (a, b) be the time of EUCLID(a, b)
    Lemma: a mod b < a/2
    Proof. if b > a/2, a mod b = a − b < a/2; else if b ≤ a/2, a mod b < b ≤ a/2
    We have T (a, b) = T (b, r1 ) + O(1), where r1 = a mod b . let r0 = b, we have

    T (ri , ri+1 ) = T (ri+1 , ri+2 ) + O(1)

    here ri+2 < ri /2, so r1 < a/2, r3 < a/22 ... r2 < b/2, r4 < b/22 ... until ri = 0
    So at most we have ⌈log a⌉ + ⌈log b⌉ times O(1), so the running time is O(log a + log b)
    Problem 4 (40 points).
    1. We prove for h2 = 3, h1 = 2
    After calling INSERTIONSORT(h2 ),we have S[1] ≤ S[4] ≤ S[7]..., S[2] ≤ S[5] ≤ S[8]..., S[3] ≤
    S[6] ≤ S[9]... And INSERTIONSORT(h1 ) sort independently on S1 = {S[1], S[3], ...} and
    S2 = {S[2], S[4], ...} to form a new array A[1], A[2], A[3].... What we want to prove is that
    A[i] ≤ A[i + 3], 1 ≤ i ≤ n − 3
    We have |S1 | = (n + 1)/2, |S2 | = n/2. When i is odd, because S[1] ≤ S[4], S[3] ≤ S[6]..., there
    are (n − 2)/2 elements in S1 smaller than a specific element in S2 , after sort independently,
    A[i + 3] is bigger than (i + 1)/2 elements in S2 , so it is bigger than (i + 1)/2 elements in S1 , so
    A[i] ≤ A[i + 3] ,that is to say, A[1] ≤ A[4], A[3] ≤ A[6]. Similarly, we can prove for i is even.
    2. Lemma:if ht+1 , ht is co-prime, ∀n ≥ ht ht+1 , ∃x, y ∈ N, s.t. xht+1 + yht = n
    Proof. When gcd(ht+1 , ht )=1, we have a′ , b′ ∈ Z s.t. a′ ht+1 + b′ ht = 1, let x′ = a′ n, y ′ = b′ n,
    we have x′ ht+1 + y ′ ht = n = xht+1 + yht , so x = x′ + kht , y = y ′ − kht+1 , k ∈ Z so n can be
    written in the unique form
    n = xht+1 + yht , 0 ≤ x < ht
    When n > ht ht+1 , cause 0 ≤ x < ht , we must have y ≥ 0
    Now we want to prove that each element will be moved by at most ht+1 ht /ht−1 steps when
    ht+1 , ht is co-prime.
    First we show that ∀j, l < j − ht+1 ht ,we have A[l] ≤ A[j]. This is because j − l > ht ht+1 , so
    ∃x, y ∈ N s.t. xht+1 + yht = j − l, so

    A[l] ≤ A[l + xht+1 ] ≤ A[l + xht+1 + yht ] = A[j]


    And the increment is ht−1 , so each element will be moved by at most ht+1 ht /ht−1 steps, and each
    step takes O(1), there are O(n) elements to be moved, so the time of INSERTIONSORT(ht−1 )
    is O( nhht+1
    t−1
    ht
    )

    You might also like