Assignment 1: Algorithm Complexity Solution

General Comments:

In CS4310, most assignments will be completed using high-level informal pseudo codes. To avoid confusion and to make sure you’ll receive the best score that your homework deserves, please document in detail all your work clearly.
State all your assumptions.
No algorithm is complete without its time and space complexities given.
When presenting an algorithm,
indicate if it is similar to a well-known algorithm,
describe intuitively how the algorithm works (which may be supported by examples),
give its pseudo code,
finally analyze its time and space complexity.
Always describe general idea of the algorithm before giving its pseudo-code. Do not reinvent the wheel, i.e., if a well-known algorithm can be modified to solve a problem efficiently, use that solution and clearly indicate the changes you made. If you just write pseudo-code of a well-known algorithm without indicating how it is applied or modified to the problem at hand, no credit will be given.
Do not unnecessarily complicate a solution.
Here comes our first homework assignment.

(20pts) For each of the code snippets below, first derive the time complexity using summation notation, then find the close form and finally express it using tight asymptotic (big-Oh, big-Theta, big-Omega) notation. Assume constant overhead per iteration of a loop. Keep details of your calculation until the last step of expressing your solution using tight asymptotic notation.




sum = 0;
for(i = 1; i  n; i++)
for(j = (n/2); j  1; j--)
sum++;



for (i = 1; i < n; i++) {
y = y + 1;
for (j = 0; j ≤ 2n; j++)
x++;
}



for (i = 1; i ≤ n; i++)
for (j = 1; j ≤ i; j++)
for (k = j; k ≤ n; k++)
x = x + 2;



for (i = 1; i ≤ n; i += 2);



for (i = 1; i ≤ n; i *= 2)
x = y+2;




(20pts) This question concerns the asymptotic relations between functions; you can assume that all logarithmic functions are in base 2. Sort the following functions in an asymptotically non-decreasing order of growth using big-oh and big-theta notations. Again, you must justify your answers, otherwise no credit.




 
 
 
 
 
 
 
 
 
 
 




(20pts)

Design and analyze an algorithm to find the median, upper quartile and lower quartile from a list of integers (unordered). Your time complexity should be no more than .
Can you improve your algorithm if the input list is sorted? If so, design and analyze such an algorithm. If not, justify why no improvement in time/space complexity can exist.




(20pts)




Algorithm A uses operations, while algorithm B uses operations. Determine the value n0 such that A is better than B for n ≥ n0.
Are there values of such that B is better than A? If yes, list the ranges. If not, justify why not.
Determine the value n0 such that A is better than B for n ≥ n0, when B uses operations.




(20pts) Solve the following recurrence relation:
 





Find a closed form of and then express your solution using tight asymptotic notation.





How to prepare and submit your homework:

Use a word processor (e.g MS Word, LaTeX) that you prefer. Include the original questions in your answer by typing your answers immediately after each question. Proofread your answers several times.

Submit your homework (MS Word or PDF) by uploading it to E-learning Dropbox by the due date.