
\bigskip
\handout{Homework 2,  Due Friday,  January 20, 2023}
\bigskip

\bigskip

Turnin instructions:  Electronics submission on GradeScope.   Submit as a PDF,  with each problem on a separate page.

\problem{1 (10 points)}

Order the following functions in increasing order by their growth rate:
	\begin{enumerate}
		\item $n^3$
		\item $(\log n)^{\log n}$
		\item $n^{\sqrt{\log n}}$
		\item $2^{n/10}$
	\end{enumerate}
	
Explain how you determined the ordering.




\problem{2 (10 points)} The {\it diameter} of an undirected graph is the maximum distance between any pair of vertices.  If a graph is not connected, its diameter is infinite. Let $G$ be an $n$ node undirected graph, where $n$ is even.  Suppose that every vertex has degree at least $n/2$.  Show that $G$ has diameter at most 2.

\problem{3 (10 points)} Let  $G = (V, E)$  be an undirected graph with $n$ vertices such that the degree of every vertex of $G$ 
is at most $k$. Describe an algorithm to color the edges of $G$ with at most $2k-1$ colors such that any
pair of edges $e$ and $f$ which are incident to the same vertex have distinct colors.  Explain why your algorithm successfully colors the edges of the graph.

\medskip
You should describe your algorithm using pseudo-code, which allows you to use a mix of English language statements and control structures.  For example,  if you were asked to color a graph with maximum degree at most $k$ with $k+1$ colors you could you could give the following pseudo-code:

\begin{verbatim}
Set all vertices to uncolored
Foreach vertex v
    Select a color for v from [1,k+1] that is not used by any of v's neighbors
    
\end{verbatim}
To show that the algorithm works, you would need to argue that there is always a color available for the select statement to choose.

\program{4  (10 points)}  The {\it Coupon Collector} problem is:  There are $n$ types of coupons.   Each time you get a coupon,  you are given a coupon of a random type (with equal probability of receiving each coupon).   The question is how many coupons do you expect to receive,  on the average, before you have collected the full set of coupons.
\medskip

Your programming assignment is to write a simulator of the Coupon Collector Problem,  and run simulations to see how long how many coupons are needed to complete the set.  You should run your program for values of $n$ up to $4,000$.  Determine the average number of coupons required to complete the set. 

\medskip

A reason for looking at this process is that it can be used to analyze the performance of the M-Proposal Algorithm for stable matching.  The total number of coupons collected $C$ will correspond with the M-rank,  and $C/n$ will correspond with the average m-rank.

\program{5  (10 points)}  We now consider a variation of the Coupon Collector Problem where there are $n$ types of coupons, and each coupon has a value associated with it.  The value of a coupon is a random integer between 1 and $n$.   You want to put together a complete set of coupons of {\it minimum value},  so that of all of the coupons you receive of a certain type $c_i$,  you keep the one of minimum value.  You collect coupons until you have a full set of coupons and then you determine the value of the set of coupons.   
\medskip

Your programming assignment is to write a simulator of the Coupon Collector problem with values,  and run simulations to see what the average value is for a complete set of coupons.  You should run this up to $n=4,000$.  

\medskip
A reason for looking at this process is that it can be used to analyze the performance of the M-Proposal Algorithm for stable matching.  The total value of coupons collected $V$ will correspond with the W-rank,  and $V/n$ will correspond with the average w-rank.
