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

\head{CS7800}{Advanced Algorithms}{Fall 2014}{30 September 2014}{8}

\begin{center}
\Large{\bf Problem Set 3 (due Monday, October 6)}
\end{center}

{\bf Instructions:}
\begin{itemize} \small
\item The assignment is due at the beginning of class on the due date
  specified.  Late assignments will not be accepted.

    \item We encourage you to attempt and work out all of the problems
      on your own.  You are permitted to study with friends and
      discuss the problems; however, {\em you must write up you own
        solutions, in your own words}. 

    \item If you do collaborate with any of the other students on any
      problem, please list all your collaborators in your submission
      for each problem.

    \item Finding solutions to homework problems on the web, or by
      asking students not enrolled in the class is prohibited.

\item
We require that all homework submissions be neat, organized, and {\em
  typeset}.  You may use plain text or a word processor like Microsoft
Word or LaTeX for your submissions.  
\end{itemize}

{\bf 1. (10 points) Matroids}

Exercise 16.4-4 of text.

{\bf 2. (5 + 5 = 10 points) Minimizing average completion time}

Problem 16-2 of text.

{\bf 3.  (10 points) Minimum-length encoding}

This is a continuation of Problem 4 of PS2.  Recall that Alice and Bob
are using an encoding scheme based on a set $S$ of $m$ {\em code
words} that they both share.  Alice wants to send a data string $D$ of
length $n$ to Bob.  In this exercise, we assume that $S$ is an {\em
arbitrary}\/ set of $m$ code words.  

Design a polynomial-time algorithm to determine a minimum-length
encoding of a given string $D$ using code words from $S$. If no such
encoding exists, then the algorithm must indicate so.  Analyze the
worst-case running time of your algorithm.  Make your algorithm as
efficient as you can, in terms of its worst-case running time.
\end{document}
