CS 577 –.1.

Consider n points arranged on a circle, connected by all possible line segments. Assume they are in general position, which means that no point inside the circle is on more than two of the segments. Let R(n) denote the number of regions (inside the circle) thus formed.

a) Find R(n) for n = 0, 1, 2, 3, 4, 5. You should see a pattern.

b) Looks can be deceiving! Show that

R(n + 1) ≤ R(n) + O(n^3).

(1)c) Explain, using induction and the definition of O-notation, why your recurrence implies that R(n) = O(n^4).

Hints: Suppose the first n points are arranged along the upper semicircle. Put the (n+ 1)-st point near the bottom of the circle, and connect it to the i-th “old” point. Find a formula for the number of lines crossed (it should involve n and i), and thereby determine the number of new regions created when this line is added. Proving that R(n) = O(n^4)will be aided if you first replace the O(n^3) in (1) by an explicit function of n

 

.2.Consider the following non-recursive version of DFS, which counts the vertices reachable from s in G:

P(G,s)

count := 0

push s onto stack

while stack nonempty

     u:= pop stack

     if u is not marked "counted" then

          mark u "counted"

          count := count + 1

          for each neighbor v of u

                 push v onto stack

return count

Initially all nodes are unmarked. Show:

a) At the end of each iteration of the while loop (including the 0th iteration, i.e., the beginning of the first iteration), the correct count equals count + |A|, where A is the set of uncounted nodes reachable from some node on the stack

.b) P terminates.

c) P outputs the correct count upon termination.