CSTBC Exam 2
Due: July 30, 2007, 11:59pm

This exam is open notes/open lecture and covers 
material from lectures 7-17. You are welcome to use any 
of the course material linked from the CSTBC website. 
You should not use other reference materials. Please 
send me your solutions to the exam via email. If you 
have any questions, please ask me. 

1 Pirate's Dinner

After distributing their treasure, our n pirates from 
Exam 1 have worked up an appetite. The pirate ship's 
cafeteria offers three different, non-overlapping 
dinner times. As the strongest pirate, you are in 
charge of assigning each pirate to one of the three 
dinner slots. Unfortunately, not all pirates get along 
with each other. You have a list of k pairs of pirates 
that have fought each other in the past. Prove that you 
can assign pirates to dinners so that at most k/3 of the 
troublesome pairs eat dinner at the same time. 

2 Hamiltonian Paths in Tournaments

In Lecture 12, we introduce the concept of a 
tournament. Prove that if T is a tournament on n 
vertices, then T contains a Hamiltonian path.

3 A Puzzle

Let k\ge0 be an integer and let n=2^{k}. Suppose you are given a 
square which is divided into n^{2} smaller squares. The 
small squares are all colored blue, except that one 
special square is colored red. You are also given 
access to green game pieces which can be placed on the 
board. Each game piece comes in an 'L' shape and covers 
three of the smaller squares. Show that you can place 
the game pieces on the board in such a way that the 
pieces do not overlap and cover all the blue squares, 
leaving the red square uncovered. An example with n=8 
appears below.

	<Graphics file: tri-board.pdf>
	 <Graphics file: tri-board-sol.pdf>
	

A puzzle and solution with n=8

4 Graphs with (almost) unique degrees

In Lecture 3, we saw that a graph G with at least two 
vertices must contain two vertices of the same degree. 
Let G be a graph that contains a vertex u such that no 
two vertices in V(G)-\left\{ u\right\}  have the same degree. What can you say 
about the degree of u? 

5 Recurrences

5.1 An Exact Solution

In this problem, we will solve a linear homogeneous 
recurrence (see Lecture 16). Let T(n)=\begin{array}{cc}
0 & n\in\left\{ 0,1\right\} \\
3T(n-1)+10T(n-2)+n-2 & n\ge2\end{array}.

1. Find the general solution to the homogeneous 
  recurrence S(n)=3S(n-1)+10S(n-2).

2. Determine constants a and b such that T(n)=an+b solves the 
  inhomogeneous recurrence T.

3. Find a solution for T(n) which respects the given base cases.

5.2 Asymptotic Solutions

For each recurrence below, find a simple function f(n) so 
that T(n)=\Theta(f(n)). 

1. T(n)=T(n-1)+\frac{1}{n}

2. T(n)=T(n/2)+n

3. T(n)=2T(n/2)+\sqrt{n}

4. T(n)=T(n/2)+T(n/3)+T(n/6)+n

6 Probability

Suppose you roll a fair, six-sided die n times. 

1. What is the probability that the sum of the numbers 
  rolled is divisible by 3?

2. What is the probability that you see the same number 
  twice in a row?