To solve these problems, you are allowed to consult your classmates, as well as the class textbook (Algorithms by Dasgupta, Papadimitriou, and Vazirani, which we will call DPV) and notes, but no other sources. We encourage you to collaborate with other students, while respecting the collaboration policy. Please write the names of all the other students you collaborated with on the homework. Everyone must write up their assignments separately.

Q1. (20 points; 10 per part) DPV Problem 0.3 (parts a and c)

Q2. (10 points) Consider the following pseudo-code which takes the integer \(n \ge 0\) as input:

Function bar(n) Print '*'; if n == 0 then Return; end for i = 0 to n − 1 do bar(i); end

Let T(n) be the number of times the above function prints a star (*) when called with input n ≥ 0. What is T(n) exactly, in terms of only n (and not values like T(n − 1) or T(n − 2))? Prove your statement.

Q3. (30 points; 5 per part) For each of the following pairs of functions, indicate whether the first function is \(O, \Omega, \Theta\) of the second function:

a. \(n(n + 1)\) and \(2000n^2\)

b. \(100 n^2\) and \(0.01 n^3\)

c. \( \log_2 n\) and \(\ln n\)

d. \(\log_2^2 n\) and \(\log_2 n^2\). Note that \(\log_2^2 n = (\log_2 n)^2\)

e. \(2^{n−1}\) and \(2^n\)

f. \((n − 1)!\) and \(n!\)

Q4. (10 points) Order the following functions by their order of growth from the lowest
to the highest:

\((n − 2)!\), \(5 \log_2(n + 100)^{10}\), \(2^{2n}\), \(0.001 n^4 + 3n^3 + 1\), \(\ln^2 n\), \((n)^{1/3}\), \(3^n\)

Your HW must be submitted in **PDF Format** only. If you submit any other type of document, points will be deducted from your overall HW score. As noted above, you must mention upfront all students you collaborated with, but **all final work must be your own**.

You should submit the PDF file via the Submitty page: https://submitty.cs.rpi.edu//index.php?semester=s18&course=csci2300

Your account has already been set up. You can login via your RCS username (NOT RIN) and RCS password. Submission deadline is 12pm (strict) on Friday, Jan 26th. Submissions after this time will get a 0.

Note, you must test out the Submitty login right away. If you cannot login on 26th and consequently cannot submit your HW, you will get a 0 on HW1.

Retrieved from http://www.cs.rpi.edu/~zaki/www-new/pmwiki.php/IntroAlgorithms/HW1

Page last modified on January 22, 2018, at 09:00 PM