CSCI 3650
Spring 2015
Homework Assignment 3

1. From the book: 33.1-5 [page 1020]. Do not assume that the input polygon is simple.

   1. Show that Professor Amundsen's algorithm does not correctly tell whether a given polygon is convex.
   2. Show how to modify the algorithm so that it gives the correct answer.

2. From the book: 33-1(a) [page 1044]. Convex layers.

3. To within a constant factor, how much time does the following algorithm take, in terms of n?

     twoToTheN(n)
       if n == 1
         return 0
       else
         return twoToTheN(n-1) + twoToTheN(n-1)
   

4. From the book: 15-6 [page 408] Planning a company party. Do not worry about the details of how the tree is organized. Each person is either invited or not invited. Consider computing two scores for each persion (or, equivalently, for each node of the tree).

   1. Define what the scores are.
   2. Derive equations that can be used to compute each score for a given node. Shop around.
   3. Explain how to compute all of the scores and write them in the nodes of the tree. Store the scores in an order so that, any time you need to get another score, you have already recorded that other score.
   4. Explain how to decide whom to invite, using a tree with the scores recorded in its nodes.
   5. How much time does it take, in terms of the number of employees, to plan the party?