Design and Analysis of Algorithms
Not what you're looking for?
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.
Purchase this Solution
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.
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 ...
Purchase this Solution
Free BrainMass Quizzes
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Basic UNIX commands
Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.
C++ Operators
This quiz tests a student's knowledge about C++ operators.
Excel Introductory Quiz
This quiz tests your knowledge of basics of MS-Excel.