Due: Friday, March 13th at the beginning of class

Problem 1: Using pseudocode, describe an algorithm for decomposing a convex polygon into disjoint triangles whose union is the original polygon. You may assume that the polygon is represented by a list of its corners in clockwise order.

Problem 2: Give an example of a non-convex polygon for which your algorithm fails.

Problem 3: Consider the rendering of a 3-D scene from a given camera. Imagine a second camera positioned and oriented that same way as a spotlight. Suppose a point visible from the first camera's position is not visible from the second camera's position. How should that point be rendered by the first camera?

Problem 4: Suggest an algorithm for rendering shadows cast by a spotlight.

Problem 5: The backtracking algorithm presented in class

BACKTRACKING-SOVLE(State s)
  if s is a solution then hooray!
  else
    for each legal move m from s
      make that move to produce a new state s'
      if BACKTRACKING-SOLVE(s') then report m as next move
    report no solution possible from s

Problem 6: Consider the Rush Hour puzzle. Formulate a yes/no question that you could use to solve the puzzle. Assuming that you have a subroutine that answers your yes/no question, give an efficient algorithm for solving Rush Hour.