Homework Solution

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     7–9pm AYB

 

Thursday      9–11am AYC    11–1pm AYD    1–3pm AYE

 

3–5pm AYF       5–7pm AYG      7–9pm AYH Friday             9–11am AYI      1–3pm AYK      3–5pm AYL

5–7pm AYM

 

Laptop Sections:

 

Thursday
9–11am AYS

 

3–5pm AYP
11–1pm AYN

 

5–7pm AYT
1–3pm AYO
Friday
9–11am AYU

 

5–7pm AYV
1–3pm AYQ
3–5pm AYR
 

 

 

 

 

 

Grade
 
 

Out  of 60
 

Grader
 

 

 

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:

 

 

Favorite Movie Post  (Public)  number:
 
 

Formatted Code Post  (Private) number:
 
 

 

 

 

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.

 

(a)


n

Y

 

k=2


 1

1 − k2


 

 

Answer for (a):

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(b)  31000  mod 7                                             Answer for (b):

 

 

(c)


∞



1                                                        Answer for (c):
 
X(   )r

2

r=1

 

 

 

 

 

 

 

 

 

 

 

 

 

(d)


log7 81 log7 9


 

Answer for (d):

 

 

 

 

 

 

 

 

 

 

 

 

 

(e)  log2 42n                                                                   Answer for (e):

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(f )  log17 221 − log17 13                                 Answer for (f ):

 

 

n

3.  (8 points)  Find the formula for 1+ X 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) = 4log4 n and g(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)

 

 

(c)  f (n) = log2(n!) and g(n) = n log2 n.

 

Answer for (c):        f (n)            g(n)

 

 

 

 

 

 

 

(d)  f (n) = nk  and g(n) = cn where k and c are constants and c 1.

 

Answer for (d):        f (n)            g(n)

 

 

 

 

 

 

 

 

 

5.  (9 points)  Solve the following recurrence  relations  for integer  n.  If no solution  exists,  please explain the result.

 



2
 
(a)  T (n) = T ( n ) + 5, T (1) = 1; assume n is a power of 2.

 

Answer for (a):

 

 

 

 

 

 

 



n
 
(b)  T (n) = T (n − 1) +  1 , T (0) = 0.


 

Answer for (b):

 

 

 

 

 

 

 

(c)  Prove  that your answer to part  (a) is correct  using induction.

 

 

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:
 

 

 

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.

 

 

Blank sheet for extra  work.