#LyX 1.3 created this file. For more info see http://www.lyx.org/
\lyxformat 221
\textclass article
\begin_preamble
\usepackage{fullpage,ulem}
\usepackage{geometry}
\geometry{top=1.2cm,bottom=1.2cm,left=1.2cm,right=1.2cm}
%\geometry{top=0cm,bottom=0cm,left=0cm,right=0cm,nohead,nofoot}
\end_preamble
\language english
\inputencoding auto
\fontscheme default
\graphics default
\paperfontsize default
\spacing single 
\papersize Default
\paperpackage a4
\use_geometry 0
\use_amsmath 1
\use_natbib 0
\use_numerical_citations 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default

\layout Title

CSTBC Exam 2
\newline 
Due: July 30, 2007, 11:59pm
\layout Standard

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.
 
\layout Section

Pirate's Dinner
\layout Standard

After distributing their treasure, our 
\begin_inset Formula $n$
\end_inset 

 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 
\begin_inset Formula $k$
\end_inset 

 pairs of pirates that have fought each other in the past.
 Prove that you can assign pirates to dinners so that at most 
\begin_inset Formula $k/3$
\end_inset 

 of the troublesome pairs eat dinner at the same time.
 
\layout Section

Hamiltonian Paths in Tournaments
\layout Standard

In Lecture 12, we introduce the concept of a tournament.
 Prove that if 
\begin_inset Formula $T$
\end_inset 

 is a tournament on 
\begin_inset Formula $n$
\end_inset 

 vertices, then 
\begin_inset Formula $T$
\end_inset 

 contains a Hamiltonian path.
\layout Section

A Puzzle
\layout Standard

Let 
\begin_inset Formula $k\ge0$
\end_inset 

 be an integer and let 
\begin_inset Formula $n=2^{k}$
\end_inset 

.
 Suppose you are given a square which is divided into 
\begin_inset Formula $n^{2}$
\end_inset 

 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 
\begin_inset Formula $n=8$
\end_inset 

 appears below.
\layout Standard


\begin_inset Float figure
placement H
wide false
collapsed false

\layout Standard


\hfill 

\begin_inset Graphics
	filename tri-board.pdf

\end_inset 


\hfill 
 
\begin_inset Graphics
	filename tri-board-sol.pdf

\end_inset 


\hfill 

\layout Caption

A puzzle and solution with 
\begin_inset Formula $n=8$
\end_inset 


\end_inset 


\layout Section

Graphs with (almost) unique degrees
\layout Standard

In Lecture 3, we saw that a graph 
\begin_inset Formula $G$
\end_inset 

 with at least two vertices must contain two vertices of the same degree.
 Let 
\begin_inset Formula $G$
\end_inset 

 be a graph that contains a vertex 
\begin_inset Formula $u$
\end_inset 

 such that no two vertices in 
\begin_inset Formula $V(G)-\left\{ u\right\} $
\end_inset 

 have the same degree.
 What can you say about the degree of 
\begin_inset Formula $u$
\end_inset 

? 
\layout Section

Recurrences
\layout Subsection

An Exact Solution
\layout Standard

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

\end_inset 


\layout Enumerate

Find the general solution to the homogeneous recurrence 
\begin_inset Formula $S(n)=3S(n-1)+10S(n-2)$
\end_inset 

.
\layout Enumerate

Determine constants 
\begin_inset Formula $a$
\end_inset 

 and 
\begin_inset Formula $b$
\end_inset 

 such that 
\begin_inset Formula $T(n)=an+b$
\end_inset 

 solves the inhomogeneous recurrence 
\begin_inset Formula $T$
\end_inset 

.
\layout Enumerate

Find a solution for 
\begin_inset Formula $T(n)$
\end_inset 

 which respects the given base cases.
\layout Subsection

Asymptotic Solutions
\layout Standard

For each recurrence below, find a simple function 
\begin_inset Formula $f(n)$
\end_inset 

 so that 
\begin_inset Formula $T(n)=\Theta(f(n))$
\end_inset 

.
 
\layout Enumerate


\begin_inset Formula $T(n)=T(n-1)+\frac{1}{n}$
\end_inset 


\layout Enumerate


\begin_inset Formula $T(n)=T(n/2)+n$
\end_inset 


\layout Enumerate


\begin_inset Formula $T(n)=2T(n/2)+\sqrt{n}$
\end_inset 


\layout Enumerate


\begin_inset Formula $T(n)=T(n/2)+T(n/3)+T(n/6)+n$
\end_inset 


\layout Section

Probability
\layout Standard

Suppose you roll a fair, six-sided die 
\begin_inset Formula $n$
\end_inset 

 times.
 
\layout Enumerate

What is the probability that the sum of the numbers rolled is divisible
 by 3?
\layout Enumerate

What is the probability that you see the same number twice in a row?
\the_end