HomeWork 1 Solution

General Comments: Show all your work, otherwise no partial credit. No credit without proper justifications. State all your assumptions. No Algorithm is complete without its time and space complexity. When presenting an algorithm, first indicate if it is similar to a well-known algorithm, second describe intuitively how the algorithm works (which may be supported by examples), third give its pseudo code and 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 required. Do not unnecessarily complicate a solution, i.e., if a simple but efficient solution exists then we should use it. Finally, if you just write pseudo-code of a well-known algorithm without indicating how it applies or modified to the problem at hand, no credit will be given.

1. (20pts) For 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 c10 overhead per iteration for a loop. Don’t burry / hide lower order terms or all constants into one until the last step of expressing your solution using tight asymptotic notation.





2. (20pts) This question concerns the asymptotic relations between functions; you can assume that all logarithmic functions are in base 2. It’s a repeat from general comments above, but you must justify your answers, otherwise no credit. Sort the following functions in an asymptotically non-decreasing order of growth using big-oh and big-theta notations; in other words, provide an ordering of these functions such that g1 = O(g2), g2 = O(g3), g3 = Q(g4), g4 = O(g5), . . .

(sqrt(4))^logn, 2^(6n), 2*nlogn, n^4, (n * 2^n), (n+1)*n!, 8^logn, log(n^2), (log n)^2, 2^100000, 2^(4^n)

3. (20pts) (3.a) Design and analyze an algorithm to find the lower-median from a list of n-elements (unordered). And your time complexity should be no more than O(n logn). Is your time-complexity also big-Theta rather than simply big-Oh? (3.b) Extend the algorithm to find lower-median of two lists, first list has length n1 and the second list has length n2. What is the input size of this problem? What is the output-size of this problem? What are the time and space complexities of your extended algorithm? (3.c) Can you improve your algorithm of (3.b) if the input lists were sorted? If so, design and analyze such an algorithm. If not, justify why no improvement in time/space complexity can exist.

4. (20pts) (4.a) Algorithm A uses 10n log n operations, while algorithm B uses n2 operations. Determine the value n0 such that A is better than B for n ≥ n0. (4.b) Are there values of n such that B is better than A? If yes, list the ranges. If not, justify why not. (4.c) Determine the value n0 such that A is better than B for n ≥ n0, when B uses n1.5 operations. (Problems from the GT book.)

5. (20pts) Solve the following recurrence relation

T(n) = 2*T(n/2) + 4*n^2. if n=2,

= 3 otherwise.

First find a closed form using expansion (aka substitution) method and then express your solution using tight asymptotic notation. These kind of recurrence relations arise in solutions when manipulating n X n matrices.

General Instructions on submitting your homeworks.

· For assignments, submit a SINGLE zipped file of your source codes, scripts (to run your program if any) and a brief report along with a copy of a couple of sample executions of your solution to the class's Elearning. No need to say, but you should be using good conventions and programming practices in developing your programs [just in case you forgot, refresh them from some of the coding conventions etc links provided on the TopicsCovered page.]

· Use <hw#cs4310_yourlastname_mmddyy.{zip,ppt,doc,tex} as the naming convention for your zipped, ppt, MS-Word, or LaTex files when submitting on Elearning. Replace '#' with the appropriate homework number.

· There will be significant point penalties for not following the naming convention above, good coding practices, submitting a different format of archive file or if your program does not run. Make sure it is a .zip and NOT another format (no .rar, .tar, .tar.gz, etc)

· Beginning of the first file should clearly identify you, the class, submission date, and the main goals of the homework / programming assignment. Also add credit to others if you had to resort to looking up the solution elsewhere. Finally add one of the sentences: “ I give permission to the instructor to share my solution(s) with the class." or “ I do NOT give permission to the instructor to share my solution(s) with the class."

· Attach Plagiarism-free declaration.

 

Any student may be asked to show and discuss his or her solution in class, so be ready with your presentation.