\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newif\ifanswer
\answertrue
\head{Directed Study}{Algorithms}{Summer 2011}{29 June 2011}{1}

\begin{center}
\Large{\bf Final Exam}
\end{center}

{\bf Problem~1. (15 points) Recurrence} 

Solve the following recurrence.  You may assume that $T(1) = 1$.

\[
T(n) = 5 T(n/5) + n.
\]

{\bf Problem~2. (15 points) Heavy-hitter: the most frequent element}

Given a list $L$ of $n$ elements, the {\em frequency}\/ of an element
$x$ in $L$ is the number of times $x$ occurs in $L$.  For instance, if
$L$ is the list $[A, B, B, A, C, C, C, A, B, A, D]$, then the
frequencies of $A$, $B$, $C$, and $D$ in $L$ are $4$, $3$, $3$, and
$1$, respectively.

Give an algorithm that takes as input a list $L$ of $n$ elements and
returns the element in $L$ that has the highest frequency.  Analyze
the worst-case running time of your algorithm.  The more efficient
your algorithm is in terms of its worst-case running time, the more
credit you will get.

{\bf Problem~3. (20 points) Identifying kingpins} 

You work for a public relations firm and have just acquired complete
information on the Washington lobbying network.  In particular, you
have a list $V$ of $n$ persons (congressmen, bureaucrats, lobbyists,
businessmen, etc.) and for each person $i$ in $V$, a list of persons
in $V$ that $i$ can {\em influence}.  (Note that it is possible that
$i$ can influence $j$ but $j$ cannot influence $i$.)

Having just studied graph algorithms, you immediately capture the
above information by a directed graph $G$ with $V$ as the set of
vertices and the set $E$ of edges defined as follows.
\[
E = \{(i,j): i \mbox{ can influence } j\}.
\]

We call a person $i$ a {\em kingpin}\/ if for every other person $j
\in V$, there is a path from $i$ to $j$ in $G$.

Give a polynomial-time algorithm to determine {\em all}\/ kingpins in
the given lobbying network.  If there are no kingpins, then your
algorithm must indicate so.  State the running time of your algorithm.
The more efficient your algorithm is in terms of its worst case
running time, the more credit you will get.

{\bf Problem~4 (15 points) Dijkstra's Algorithm}

Show a complete run of Dijkstra's algorithm on the graph given on page
127 of text, with source vertex being A.  Assume the edges are
directed in alphabetical order; i.e., from A to B, A to C, B to C,
etc.

{\bf Problem~5 (10 + 10 = 20 points) Short-answer questions on minimum
  spanning trees}

For each of these questions, if your claim is ``True'', then give a
brief proof; if your claim is ``False'', then provide a
counterexample.

\begin{itemize}
\item[{\bf (a)}] True or False: For any connected weighted undirected
  graph $G$, any minimum spanning tree $T$ of $G$, and vertices $u$
  and $v$ of $T$, the unique path from $u$ to $v$ in $T$ is the
  shortest path from $u$ to $v$ in $G$.

\item[{\bf (b)}] True or False: For any connected weighted undirected
  graph $G$, if edge $(u,v)$ has minimum weight among all edges of $G$
  then $(u,v)$ belongs to some minimum spanning tree of $G$.
\end{itemize}

{\bf Problem~6 (15 points) Huffman encoding}

Exercise 5.14 of text.

\end{document}