Homework #1 Solution

Homework should be submitted via Moodle in PDF, or plain text. To avoid reduced marks, please submit word/latex-formated PDF file, NOT scanned writing in pdf format. All assignments are due on 9 PM of the due date. Late homework will be accepted only in circumstances that are grounds for excused absence under university policy. The university provides mechanisms for documenting such reasons (severe illness, death in the family, etc.). Arrangements for turning in late homework must be made by the day preceding the due date if possible.




All assignments for this course are intended to be individual work. Turning in an assignment which is not your own work is cheating. The Internet is not an allowed resource! Copying of text, code or other content from the Internet (or other sources) is plagiarism. Any tool/resource must be approved in advance by the instructor and identified and acknowledged clearly in any work turned in, anything else is plagiarism.




If an academic integrity violation occurs, the offending student(s) will be assessed a penalty that is at least as severe as getting a 0 for the whole homework for which the violation occurred, and the case will be reported to the Office of Student Conduct.




Instructions about how to “give/describe” an algorithm (taken from Erik Demaine): Try to be concise, correct, and complete. To avoid deductions, you should provide (1) a textual description of the algorithm, and, if helpful, flow charts and pseudocode; (2) at least one worked example or diagram to illustrate how your algorithm works; (3) a proof (or other indication) of the correctness of the algorithm; and (4) an analysis of the time complexity (and, if relevant, the space complexity) of the algorithm. Remember that, above all else, your goal is to communicate. If a grader cannot understand your solution, they cannot give you appropriate credit for it.




In this assignment, the function lg indicates the binary logarithm, ln indicates the natural logarithm.




1. (12 points) Purpose: Learn about Horner’s rule and practice how loop invariants are used to prove the correctness of an algorithm. Please re-read Section 2.1 in our textbook and solve problem 2-3 on page 41 of the textbook.



2. (13 points) Purpose: Practice counting basic operations and analyzing algorithms. Assume n 0 and consider the following algorithm.




l  1
k  0
(3) for i  1 to n do

(4) l  ½ * l * i
(5) if k < n do

(6) k  i * i * i + 2

(7) return( k, l )







a) (5 points) For n = 1,2,3,4,5 what values for k and l are returned in line 7? How many multiplications (“*”) does the algorithm perform for computing these values? How many additions (“+”) does the algorithm perform for computing these values?



n
1
2
3
4
5
Return value (k)
1/2
1/2






Return value (l)
3
3






# multiplications (“*”)
4
6






# additions (“+”)
1
1









b) (2 points) As a function of n, what is the value of k returned in line 7? Justify your results.

c) (2 points) As a function of n, what is the value of l returned in line 7? Justify your results.

d) (2 points) As a function of n, how many multiplications (“*”) does the algorithm perform? Justify your results.

d) (2 points) As a function of n, how many additions (“+”) does the algorithm perform? Justify your results.




3. (12 points) Purpose: Practice working with asymptotic notation. Rank the following functions by order of asymptotic growth; that is, find an arrangement g1, g2, … of the below functions with g1(g2), g2(g3) …. Mark the functions that are asymptotically equivalent, i.e. gk (gk+1) by a “*”. Justify your solution.


a) lg(n)+ n, lg(n!), n0.99lg(n), nlg(n), n1/2+999/n, n1.01, 999n1/2


b) lg(n!), 100!, n1.01, 2lg(n)+lg(n)+n1/3, n1/3, 1+1/n, lg(nn)




4. (12 points) Prove or disprove rigorously (ie give values for c and n0 that will make your argument work) using the formal definitions of , ω (little-omega), and o (little-oh).

a) (4 points) nlg(n) + n - 1000  ω( n ) (little-omega).

b) (4 points) nlg(n) + n0.5 + n-1  ( nlg(n) ).

c) (4 points) lg(n) o( ln(n3) ) (little-oh).




5. (6 points) Purpose: Practice proving asymptotic relationships. In proving big-oh and big-omega bounds there is a relationship between the c that is used and the smallest n0 that will work (for O, the smaller the c, the larger the n0; for big-omega, the larger the c, the larger the n0). In each of the following situations, describe (the smallest integer) n0 as a function of c. You'll have to use the ceiling function to ensure that n0 is an integer. Your solution should also give you a lower bound (for big-oh) or an upper bound (for big-omega) on the constant c.

(a) (3 points) Let f(n) = 5n4 - 7n3 and prove that f(n)  O(n4).

(b) (3 points) Let f(n) = 2n4 + 4n3 and prove that f(n)  (n3).




6. (6 points) Purpose: Practice how to design, analyze, and communicate algorithms. Describe an non-recursive Θ(lg n) algorithm which computes (a/2)2n, given a and n. You may assume that a is a positive real number, and n a positive integer, but do not assume that n is a power of 2. Please follow the above instructions for describing your algorithm. Please give both, a textual description and pseudocode of your algorithm, and justify the asymptotic running time of your algorithm.