Recent Changes - Search:

Main Page



Piazza Site




edit SideBar

HW1: Due Jan 26th, Before Midnight (i.e., by 11:59:59PM on 26th)

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
   for i = 0 to n − 1 do

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\)

How to submit:

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:

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.

Edit - History - Print - Recent Changes - Search
Page last modified on January 22, 2018, at 09:00 PM