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

Welcome to Scribd!

  • 203 views

    Algorithms Assignment

    Uploaded by

    Serene In
    This document outlines an assignment for an algorithms course. It includes 9 problems dealing with analyzing the asymptotic runtime of algorithms and solving recurrences. The assignment is due on October 1st, 2013 at 5:00 pm and covers topics like divide-and-conquer algorithms, asymptotic notation, solving recurrences using various methods, and the master's theorem.

    Copyright:

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

    Algorithms Assignment

    Uploaded by

    Serene In
    203 views2 pages
    This document outlines an assignment for an algorithms course. It includes 9 problems dealing with analyzing the asymptotic runtime of algorithms and solving recurrences. The assignment is due on October 1st, 2013 at 5:00 pm and covers topics like divide-and-conquer algorithms, asymptotic notation, solving recurrences using various methods, and the master's theorem.

    Original Description:

    Algorithms Tests

    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 outlines an assignment for an algorithms course. It includes 9 problems dealing with analyzing the asymptotic runtime of algorithms and solving recurrences. The assignment is due on October 1st, 2013 at 5:00 pm and covers topics like divide-and-conquer algorithms, asymptotic notation, solving recurrences using various methods, and the master's theorem.

    Copyright:

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

    Algorithms Assignment

    Uploaded by

    Serene In
    This document outlines an assignment for an algorithms course. It includes 9 problems dealing with analyzing the asymptotic runtime of algorithms and solving recurrences. The assignment is due on October 1st, 2013 at 5:00 pm and covers topics like divide-and-conquer algorithms, asymptotic notation, solving recurrences using various methods, and the master's theorem.

    Copyright:

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

    Assignement 1

    COSC 3P03, Algorithms


    Fall, 2013
    Due: 5:00 pm, Oct. 1, Tuesday.
    1. (10) Given an array A[1..n] (not sorted), the following is a divide-and-conquer algorithm that nds the maximum
    of the array:
    find_max(A[1..n])
    if n=1 return A[n]
    else
    temp_max = find_max(A[1..n-1])
    return max(temp_max, A[n])
    Let t(n) be the time for the algorithm, give a recurrence for t(n) and solve it.
    Design a dierent divide-and-conquer algorithm by dividing the input into two (roughly) equal parts. You need
    to come up with a recurrence for its running time and solve it.
    2. (10) List the functions below from lowest order to highest order. If any two or more are of the same asymptotic
    order, group them together.
    log log n
    3
    ,

    i=0
    1/a
    i
    , where a > 1,

    2
    log

    n
    , 2
    n
    , (5/2)
    n
    , n
    4
    , e
    n
    , log
    5
    n, nlog n, log log n
    5
    , log
    1/2
    n, n
    2
    4
    log n
    , 2013,
    2 + 4 + 6 + + n(n even), 20, (n
    2
    1)/(n 1),
    3. (7) Show that

    n
    i=1
    log i = O(nlog n).
    4. (13) Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, , or of B. Assume
    that k > 1 and c > 1 are constants. Your answer should be in the form of the table with yes or no written
    in each box.
    A B O o
    log
    k
    n log n
    k
    n
    k
    k
    n
    2
    n
    2
    cn
    2
    n
    2
    n+1
    n
    log c
    c
    log n
    log
    5
    3
    n log
    500
    100
    n
    log(n!) log(n
    n
    )
    100n + log n n + (log n)
    2
    log n log(n
    2
    )
    n
    2
    / log n nlog
    2
    n
    (log n)
    log n
    n/ log n
    n
    1/2
    (log n)
    5
    n2
    n
    3
    n
    1
    5. (20) Solve the recurrence in asymptotically tight big Oh function:
    t(n) = n +
    k

    i=1
    t(a
    i
    n),
    for two cases (a) where

    k
    i=1
    a
    i
    < 1, and (b) where

    k
    i=1
    a
    i
    = 1, using both the substitution and recursion
    tree methods.
    6. (10) Use as many methods as possible to solve the following recurrence:
    t(n) = 2t(n/2) + 1.
    7. (10) Solve the following recurrences using the methods specied. You can make any reasonable assumptions
    about the parameter n and initial conditions. Note that you only need to solve t(n) in terms of the big Oh
    notation.
    (a) t(1) = 1, t(n) = 3t(n/2) + n, iteration.
    (b) t(n) = 2t(n/2) + nlog n, substitution.
    8. (10) Solve the following recurrences by the masters method, if possible. In case(s) where the method does not
    apply, state why and solve it/them by other means (hint: you may encounter the harmonic number/series).
    t(n) = 4t(n/2) + n
    t(n) = 4t(n/2) + n
    2
    t(n) = 4t(n/2) + n
    3
    t(n) = 2t(n/2) + n/ log n
    9. (10) What is the Big Oh function for each of the following functions of n, where k is an integer (it should be
    as tight and as simple as possible). There is no need to justify your answers.
    a. t(n) = (nlog n
    100
    )/2 + f(n), where f(n) = o(n)
    b. t(n) = n + (n + 1) + (n + 2) + ... + (n + n), where n is even
    c. t(n) = log
    1.5
    n + log(n
    2
    )
    d. t(n) = 16
    log n
    e. t(n) = 1 + 3 + 3
    2
    + ... + 3
    n
    + 3
    n+1
    + 3
    n+2
    f. t(n) = log 1 + log 2 + ... + log n
    g. t(n) = 4n
    3/4
    + 5nlog n + 2nlog log n
    h. t(n) = 1 + 2 + 3 + 4 + ... + 2013 + sin(n)
    i. t(n) = t(n/9) + t(9n/11) + cn
    j. t(n) =

    n
    i=0

    n
    i

    You might also like