Labs Homeworks |
## HW1## 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 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: Q4. (10 points) Order the following functions by their order of growth from the lowest
to the highest: ## How to submit:Your HW must be submitted in 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. |

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