%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~38~~~Introduction to Algorithms
                        \hfill Spring 2014} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:

\newcommand{\set}[1]{\left \{{#1} \right \}}

\begin{document}
\problemset{2}{April 15}{\bf April 22}


Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the optional text (CLRS). The full honor code guidelines can be found in the course syllabus.


Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}
\begin{enumerate}


\item
Recall that a prefix-free encoding scheme can be represented by a binary tree, and that the Huffman code algorithm gives an efficient way to construct an optimal such tree from the probabilities $p_1, p_2, \ldots, p_n$ of $n$ symbols. In this problem, you will show that the average length of such an encoding scheme is at most one larger than the {\em entropy} (which is the information-theoretic best-possible). The {\em entropy} of the distribution given by ${\mathbf p} = (p_1, p_2, \ldots, p_n)$ is defined to be
    \[H({\mathbf p}) = \sum_{i=1}^n -\log(p_i) \cdot p_i.\]
\begin{enumerate}
\item Prove that for any list of positive integers $\ell_1, \ell_2, \ldots, \ell_n$ satisfying
\[\sum_{i=1}^n 2^{-\ell_i} \le 1,\]
there is a binary tree with distinct root-leaf paths having lengths $\ell_1, \ell_2, \ldots, \ell_n$. Hint: start from the full binary tree and delete subtrees.
\item Let ${\mathbf p} = (p_1, \ldots, p_n)$ give the probabilities of $n$ symbols. Prove that if $\ell_1, \ldots, \ell_n$ are the encoding lengths in an optimal prefix-free encoding scheme for this distribution, then the average encoding length,
    \[\sum_{i=1}^n \ell_i p_i,\]
    is at most $H({\mathbf p}) + 1$.
\end{enumerate}

\item
A {\em matroid} is a family ${\mathcal I}$ of subsets of a universe $E$, satisfying the following three axioms:
    \begin{itemize}
    \item ${\mathcal I}$ contains the empty set,
    \item if $A \in {\mathcal I}$ and then every subset $B \subseteq A$ is also in ${\mathcal I}$, and
    \item if $A$ and $B$ are subsets in ${\mathcal I}$ with $|B| > |A|$, then there exists $x \in B \setminus A$ such that $A \cup \{x\}$ is in ${\mathcal I}$.
    \end{itemize}
The subsets in ${\mathcal I}$ are called {\em independent sets}. The maximal independent sets are called {\em bases}. A consequence of the third axiom is that all of the bases have the same cardinality.

\begin{enumerate}
\item Two standard examples of matroids are the {\em graphic matroid} which is defined relative to a graph $G$, and whose independent sets are all subsets of the edges of $G$ that are forests, and the {\em matric matroid} which is defined relative to an $n \times m$ real matrix $M$, and whose independent sets are all subsets of columns of $M$ that are linearly independent. Prove that these two structures are indeed matroids.
\item Given a matroid ${\mathcal I}$ and nonnegative integer weights for each element of the universe $E$, we want to find an independent set of {\em maximum} weight (the weight of a subset is the sum of the weights of its elements). Give a greedy algorithm for this problem that runs in time $O(|E| \log |E|)$ plus $O(|E|)$ calls to a procedure that determines whether or not a given set $A$ is independent, and prove that it is correct.
\item The {\em dual} of a matroid ${\mathcal I}$ over a universe $E$ is the family of subsets ${\mathcal I'}$ over the same universe $E$, consisting of the complements of bases of ${\mathcal I}$, and all subsets of these sets. Prove that the dual ${\mathcal I'}$ is itself a matroid.
\item Consider a matroid ${\mathcal I}$ over a universe $E$, and for a parameter $k$, define the following family of subsets
\[{\mathcal I}_k = \{A : A \in {\mathcal I} \mbox{ and } |A| \le k\}.\]
Prove that for each positive integer $k$, ${\mathcal I}_k$ is a matroid.
\end{enumerate}


\item Here are some problems that can be solved greedily, via formulating them as matroids.
\begin{enumerate}
\item Formulate the minimum cost spanning tree problem as the problem of finding a maximum weight independent set in a matroid.

\item A {\em pseudo-forest} in an undirected graph is a subset of the edges containing at most one cycle. Formulate the problem of finding a maximum weight pseudo-forest in an undirected graph with non-negative edge weights as the problem of finding a maximum weight independent set in a matroid.

\item An Internet Service Provider maintains a network of links described by a connected undirected graph. Each link has a yearly cost associated with it. The company decides to decommission $k$ links, but it needs the graph to remain connected. Formulate the problem of finding which $k$ links to retire so as to maximize the yearly savings as the problem of finding a maximum weight independent set in a matroid. Hint: you may want to use the last two parts of the previous problem.
\end{enumerate}

\item We are given a rooted tree $T$ on $n$ nodes and $m$ pairs of vertices. For each pair, we wish to output its least common ancestor in the tree $T$. Give an algorithm solving this problem, that runs in time $O((n + m) \log^* n)$, using the Union-Find data structure and the ``$\log^* n$ analysis'' from class. Hint: perform a DFS of the tree, union-ing subtrees as you encounter them until the entire tree constitutes one set in the union-find data structure.

\end{enumerate}
\end{document}
