CS 225
Spring 20I-6
F{omework 0
Due January 25, 20L6
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. C5225, 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 C5225.
Name: Tia”n*ei Xu
NetID: *Xq25
Section (circle one): Wednesday 7-9pm AYB
Thursday 9-11am AYC LL-1pm AYD 1-3Pm AYE
9-11am AYI
3-bpm AYL 5-7Pm AYM
Laptop Sections:
Thursday Friday
Grade Grader
1-3pm AYN 3-5pm AYO 5-7Pm AYP 9-11am AYQ 1-L-1pm AYR 1-3Pm AYS
Out of 60
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 ffHW0num1. Also, rse Piazza’s code-formatting tools to write a priaate 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 fHW0num1. (Hint: Checkhttp://support.piazza.com/customerfportalfafiiclesflTT4T56-code-blocking). Finally, please write the 2 post numbers corresponding to your posts here:
Favorite Movie Post (Public) number: Formatted Code Post (Private) number:
/ , )o t$5
2. (L2 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.
(u) g(‘-b)
rr- t)=( rttl tr- l*)
Answer for (a):
/r_+t zN
Answer for (b): I +
z> z\
l’*= (]blut 3u= t,\=\t*r l)
J6 = t)’))
=
1r’^’A ? ).
.: Slooo tn’rot 7 = lf
t, #
=
-Irtr- [])=t (3,fl)=*,3lri.T) . (+,Tl= #
(b) 3’o’o mod 7
I ^,& 1 =\) tt p.€d 1 >L
)+ =())’= t t’d 7)
cs 225
Spring 2016
r”r irlr r=1
Oo
L [*)’=&#’.,*,’^ – La”
f:t
Answer for (c): I
,T I
t, t t-,1
I .-
Answer for (d): I
I
, ,, logT 81 (“/ logr g
Z
gfl- -]tf’ q
: ) l’1′-,1
tXrl ‘
-4 _
t{r1
(e) log2 42″
‘lq6rrt’^ =
Answer for (e): I ttr. [f.) : \4^,
V n
lo, ,”‘*
–
-lr-)po
(f) log17 22L – log17 13
to3,., ” – t9,7 l} = l{,lt: ldla = I
Answer for (f): I
I
3. (8 points) Find the formula for 1* liti, and show work proving the formula is correct using
j:t #;;”4 9t^r= nFili ‘+^e^ $1n1=1″+’1t
P*4, l-t**’u,n rn- ru’ , jll= bqsi LaLL, I\=1, Srt)= Pf
induction. ^ t\
lt\= z, (n+r; l:2!>) , “‘,9r,):L(+rrl m}”;T; f^A*+r^ lu7gto,,ft, 9″W* ,”ir!j=Ln+r)l sxiet-rft ,tz l,r-, …, K
Re* { ** t,.dr.tuUtvr. i-[e? ,
s,i”1 ‘=
,* *i li ,” + r[o,) = F,rli 1l(+’1r
‘-” = lo(rttt)lt tK+t)lqv’) [h ‘tffi*)
: (!tt*’) (tt+’)
: Llt+>) ‘ LKr’) t
= t lt+t) I
0) infuutin’ S(rn r:tru+r) | +r- a.rl volt r-,.-€3). 0,t,0
4. (Spoints) Indicateforeachof thefollowingpairsof expressions (f(“),g(n)),whether/(n) is O, f,), or O of g(n). Prove your answers to the first two items, but just GIVE an answer to
the last two.
(“) f (“) : Atos+’ and g(r) :2n * 1. Answer for (a): I tt”)=g [o(“)
ita=d9*t = o $ c*l = >Yv+\
o{,ft^)(c}tr’1@YBtt{- ^N*7,I
o ( -t^,) s- ,fwl 3
vJllrr”c=I vlnr c–)
Answer for (b): I f t”l- n p(“))
tt, valua +* L,K wrh 6.*J n$ao*t og/,b\!L1l.) {rl^ utt D,V 90, &*l ir rl-Qurur;
?’rY4 {* a'(,L r’r>, I {wt ir P(furur)
\1
(b) f (“): n2 and. g(r) : (‘/211″r,”.
jwl–v{
N=
J f-
= 2t4,w’*,
0 ! Xrf!) 1 c{tn’1 w,r#\ {* a/,t tr-)r { l^/^r^- c-l
$c,,,1
Formula: I Strtl= (rL+ I ) |
!
cs 225 Spring 2016 (“) f (“): Iogz(n!) and g(n) : nlos2n.
Answer for (c): I tt”l= 0 [of”l)
(d)/(“): nkande(n): { wherekandcareconstantsandc>L.
Answer for (d): I tfO = Q0t”l)
(9 points) Solve the following recurrence relations for integer n. If no solution exists, please explain the result.
:r(t) +5,r(1): 1;assume nisapowerof2′
Answer for (a): lTtn )= 5 {rJ, ft +1
Answer for (b): I TCr)= H”
(a) Ttr”)=T[+)*
“(n)
=T (f )t sr r.UV
lLt 7 =t
..’ T(ru)=f [“Jrru+
1
(b) : T(n – 1) + fi, r1o; : s. “(n) I
=Jl?errn,
\< = [tr&
T0rrl: ltru-t)t"yv =T[("-r)+i+ h = --- =T(n-r)t n* *+ ... r .,n
TCn_)
wl,a* 16)<*e, t=*. = t-, * ***..- * *= Hr'\'
WW Hr if *[te [arnto'",c lerbl (c) Prove that your answer to part (a) is correct using induction'
ln7p (pue-: [Lzt, Tt,l=t , 5l$"rutt= f ,l9,t t\:Jx0t1 = l , rvl^ll" B .,hab wvne"\+s'ou'v' Ldr."qn^- !,?,9"$"t9: ITtGe 1t"0= sl,!yL^"tl {r ailr"=t,t'- -,J<
Lar^,tn" rtrf : T(f') =f (? )ts = Tl>t)js=y [g”r* t\+ r= sf,+s+\ cfo iU”*iu’. brr{.^In
=Jlprr) + r__ -rtoJ,tH’+\
$Y ertdu,+uw, I 1,,.,) = s teJrrt +r
t-
-u.u
5
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 rz, the size of the search array. Assume n is a power of 2. Solve the recurrence.
Jtt)>c Ttv”)rTtt;+d-
rL
tl,^,rron,, JLrurr(t)t&=Ttf;)”Lot;-‘ =T t )-, I(/d-
pLra- @7.1
T[,”): Itr )*4.1*,, :d( [$,ru r c
,K=1fl,w Recurrence:
Base case: Recurrence Solution:
Ju”l=TL*) +a” Ttrl = c
Jtn)= d’tulrw + c
(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’
Tt,; = c
T L’;= zT (*,1* d”, +f
top,tin^.’r, uv)=>TLt)*-d^*J =[t G) * znot+ $= ,. }\
= zFT (i ),’k,nrl* e*.,f
w\\o/. T =t, k–t{.v-
Ttnt. 9-. cr*totr,u . A+ (r,,”d
=l*t%rv+ crur 0″{)J
Recurrence: Base case: Running Time:
Tc”r=>T[t
#r
0 (,’t’1, -)
{ ): C
‘liltk”&u’
CS 225
Spring 2016
7. (10 points) Consider the pseudocode function below.
derp(x, n)
if (n -= 0)
return 1;
lf (n’/”2==0)
return derp(x^2, n/2); return x * derp(x-2, 6*L)/2);
(a) What is the output when passed the following parameters: a :2,’n : 72? Show your work (activation diagram or similar).
&4rJr,,,f *tf utrrt”rt’
It cn”pn:b., xN
Answer for (a): I
k ,? U
n”t,
)
,sCsUr l.–t (b) Briefly describe what this function is doing.
drrl> 125b, r (wg(“fb’, o)’
(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 i,s the most, n could be at each leuel of the recurrence?
l1o; =c lL,u)=TIt*J)+d-
(d) Solve the above recurrence for the running time of this function. Jtrv)=T(Ltl)+ot=T(.t-tt)+>ut=— =Trrsl)txa
J-,
-[ c4-@
t Ltgrtj
* l
) *ol” + c
CS 225
Spring 2016
Blank sheet for extra work.