Problem # 2 in the attached document. 

Let me know if you need anything else.

CS 577 – Sections 1 and 2Fall 2016Homework #1Due at beginning of class 9/21 and 9/22Rules for Homework.i.) Everyone must do his or her own work. Any sources beyond your class notes andtextbook must be cited. In any case, there must be signifcant “value added” byyour work.ii.) Grading is based on correctness and clarity. In particular, computations andresults need to be explained.1.Considernpoints arranged on a circle, connected by all possible line segments. As-sume they are ingeneral position, which means that no point inside the circle is on morethan two oF the segments. LetR(n) denote the number oF regions (inside the circle) thusFormed.a) ±indR(n) Forn= 0,1,2,3,4,5. You should see a pattern.b) Looks can be deceiving! Show thatR(n+ 1)≤R(n) +O(n3).(1)c) Explain, using induction and the defnition oFO-notation, why your recurrenceimplies thatR(n) =O(n4).Hints: Suppose the frstnpoints are arranged along the upper semicircle. Put the (n+1)-st point near the bottom oF the circle, and connect it to thei-th “old” point. ±ind aFormula For the number oF lines crossed (it should involvenandi), and thereby determinethe number oF new regions created when this line is added. Proving thatR(n) =O(n4)will be aided iF you frst replace theO(n3) in (1) by an explicit Function oFn.

• 1495170339-hw1.pdf

ComputerScienceExpert

(11)

Status NEW Posted 19 May 2017 03:05 AM My Price 9.00

-----------

Attachments

file 1495170342-Solutions file 2.docx preview (51 words )

H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly -----------onl-----------ine----------- an-----------d g-----------ive----------- yo-----------u e-----------xac-----------t f-----------ile----------- an-----------d t-----------he -----------sam-----------e f-----------ile----------- is----------- al-----------so -----------sen-----------t t-----------o y-----------our----------- em-----------ail----------- th-----------at -----------is -----------reg-----------ist-----------ere-----------d o-----------n -----------THI-----------S W-----------EBS-----------ITE-----------. ----------- Th-----------ank----------- yo-----------u -----------

Not Rated(0)

• Buy Answer