Explore BrainMass
Share

Explore BrainMass

    Design and Analysis of Algorithms

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    Consider a table B that consists of m integers B [1], B [2] ... B [m]. Design an algorithm to produce a two-dimensional m x m table C such that each element C[i,j] for i <j contains the sum of the B [i] up to the B [j], that is, (B [i] + B [i +1] + ... + B [j]). The values C[i,j] for i >= j are left unspecified, that is, these can take any value.

    a) Design an algorithm that creates the table C according to the above description and has time complexity Theta(m^3).
    In response give either pseudocode or the description of the steps of the algorithm, and calculate the time complexity.

    b) Design an algorithm that creates the table C according to the above description and has time complexity Theta(m^2).
    In response give either pseudocode or the description of the steps of the algorithm, and justify the time complexity.

    © BrainMass Inc. brainmass.com October 10, 2019, 4:11 am ad1c9bdddf
    https://brainmass.com/computer-science/java/design-analysis-algorithms-451339

    Attachments

    Solution Preview

    It is pretty detailed answer, so please go through it thoroughly and patiently.

    I am not giving a cooked response but instead providing enough guidance in form of number of times each step executes in the presented algorithms which should help you put together the final answer for time complexity of respective algorithms.

    When we talk about execution of a for-loop, if the for-loop-body executes m times, then the for-loop-condition-test executes (m+1) times - m times for success (that is, executing the loop-body) and once for failure (coming out of loop). For sake of simplicity in this discussion, I am not making distinction between the number of times the loop-condition executes and the number of time the loop-body executes, and instead consider the number of times for-loop executes as the number of times the for-loop-body executes.

    (a)
    S1: for i = 1 to m // Go over each row of matrix C.
    S2: for j = 1 to m // Go over each column of matrix C.
    // Compute C[i,j] as per the given description for computing C[i,j].
    S3: if (i < j) // Otherwise C[i,j] is left unspecified.
    S4: sum_itoj = 0
    S5: for k = i to j
    S6: sum_itoj += B[k]
    S7: endfor
    S8: C[i,j] = sum_itoj
    S9: endif
    S10: endfor
    S11: endfor

    In the above logic, the statement

    for i = l to u

    means same as

    for (i=l; i <= u; i++)

    when expressed in a programming language like C/C++/Java etc..

    Body of for-loop in S1, that is, S2-S10, will execute m times.

    Body of for-loop in S2, that is, S3-S9, will execute m*m times; as for-loop in S2 executes m times in itself, and the entire for-loop-block S2-S10 will execute once for each iteration of outer for-loop in S1.

    If-statement in S3 will execute m*m times (for each iteration of for-loop in S2).
    However the if-body comprising of S4-S8 will ...

    Solution Summary

    Solution explains in detail how the algorithms take shape in this case, but for the time complexity computation part it does not give a cooked response. Instead it provides enough guidance in form of number of times each step executes in the presented algorithms which should help you put together the final answer for time complexity of the respective algorithms.

    $2.19