CS 225
Spring 2016
Homework 0
Due January 25, 2016
in lecture and SVN Instructions for submission into your class SVN repository are on the webpage.
The purpose of this assignment is to give you a chance to refresh the math skills we expect you to have learned in prior classes. These particular skills will be essential to mastery of CS225, and we are unlikely to take much class time reminding you how to solve similar problems. Though you are not required to work independently on this assignment, we encourage you to do so because we think it may help you diagnose and remedy some things you might otherwise find difficult later on in the course. If this homework is difficult, please consider completing the discrete math requirement (CS173 or MATH 213) before taking CS225.
Name:
NetID:
Section (circle one):
Wednesday Thursday
Friday
7–9pm AYB 9–11am AYC 3–5pm AYF 9–11am AYI 3–5pm AYL
Laptop Sections:
Thursday 1–3pm AYN Friday 9–11am AYQ
11–1pm AYD 5–7pm AYG 11–1pm AYJ 5–7pm AYM
3–5pm AYO 11–1pm AYR
1–3pm AYE 7–9pm AYH 1–3pm AYK
5–7pm AYP 1–3pm AYS
Grade
Out of 60
Grader
1
CS 225 Spring 2016
1. (3 points) Using 140 characters or less, post a synopsis of your favorite movie to the course piazza space under the “HW0 tell me something!” notice, so that your post is visible to everyone in the class, and tagged by #HW0num1. Also, use Piazza’s code-formatting tools to write a private post to course staff that includes at least 5 lines of code. It can be code of your own or from a favorite project—it doesn’t even have to be syntactically correct—but it must be formatted as a code block in your post, and also include the tag #HW0num1. (Hint: Check http://support.piazza.com/customer/portal/articles/1774756-code-blocking). Finally, please write the 2 post numbers corresponding to your posts here:
2. (12 points) Simplify the following expressions as much as possible, without using an calcu- lator (either hardware or software). Do not approximate. Express all rational numbers as improper fractions. Show your work in the space provided, and write your answer in the box provided.
n 1
1 − k2
Favorite Movie Post (Public) number:
Formatted Code Post (Private) number:
Answer for (a):
(a)
k=2
Answer for (b):
(b) 31000 mod 7
2
CS 225 Spring 2016
Answer for (c):
(c)
∞ 1 r
r=1
(2)
Answer for (d):
(d) log7 81 log7 9
Answer for (e):
(e) log2 42n
Answer for (f):
(f) log17 221 − log17 13
3
CS 225
Spring 2016
n
3. (8 points) Find the formula for 1+ j!j, and show work proving the formula is correct using j=1
induction.
Formula:
4. (8 points) Indicate for each of the following pairs of expressions (f(n),g(n)), whether f(n) is O, Ω, or Θ of g(n). Prove your answers to the first two items, but just GIVE an answer to the last two.
(a) f(n)=4log4n andg(n)=2n+1.
Answer for (a):
f (n) g(n)
(b) f(n) = n2 and g(n) = (√2)log2 n.
Answer for (b):
f (n) g(n)
4
CS 225 Spring 2016
(c) f(n) = log2(n!) and g(n) = nlog2 n.
(d) f(n)=nk andg(n)=cn wherekandcareconstantsandc>1.
5. (9 points) Solve the following recurrence relations for integer n. If no solution exists, please explain the result.
(a) T(n)=T(n)+5,T(1)=1;assumenisapowerof2. 2
(b) T(n)=T(n−1)+1,T(0)=0. n
(c) Prove that your answer to part (a) is correct using induction.
Answer for (c):
f (n) g(n)
Answer for (d):
f (n) g(n)
Answer for (a):
Answer for (b):
5
CS 225 Spring 2016
6. (10 points) Suppose function call parameter passing costs constant time, independent of the size of the structure being passed.
(a) Give a recurrence for worst case running time of the recursive Binary Search function in terms of n, the size of the search array. Assume n is a power of 2. Solve the recurrence.
Recurrence:
Base case:
Recurrence Solution:
(b) Give a recurrence for worst case running time of the recursive Merge Sort function in terms of n, the size of the array being sorted. Solve the recurrence.
Recurrence:
Base case:
Running Time:
6
CS 225
Spring 2016
7. (10 points) Consider the pseudocode function below.
derp(x, n)
if (n == 0)
return 1;
if (n % 2 == 0)
return derp(x^2, n/2);
return x * derp(x^2, (n-1)/2);
(a) What is the output when passed the following parameters: x = 2, n = 12? Show your work (activation diagram or similar).
Answer for (a):
(b) Briefly describe what this function is doing.
(c) Write a recurrence that models the running time of this function. Assume checks, re- turns, and arithmetic are constant time, but be sure to evaluate all function calls. Hint: what is the most n could be at each level of the recurrence?
(d) Solve the above recurrence for the running time of this function.
7
CS 225
Spring 2016
Blank sheet for extra work.
8