%-*- LaTeX -*- \NeedsTeXFormat{LaTeX2e} \documentclass[leqno]{assign} \usepackage{newcent} \usepackage{amsmath,amsthm,amssymb,enumitem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Start reading here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % The four commands below are used to define the ordinal number of the % lecture (can be found on the lecture syllabus), the title of the lecture % (formulate the best description you can come up with; you can always % resort to the tentative title on the lecture syllabus if you have % difficulty), the date of the lecture (in this format: DD Month YYYY), % and the name of the scribe (that's you). % % Please supply correct arguments for the four commands below: % \lecturenumber{} \lecturetitle{Final } \lecturedate{Dec 12, 2008} \duedate{Dec 15, 2008} \lecturescribe{} % % In the space indicated below, please type out your lecture notes. You % should use all the standard LaTeX typesetting conventions, plus a couple % of additional commands described below. If you are unfamiliar with using % LaTeX to typeset technical documents, please read the very useful summary % entitled ``The Not So Short Introduction to LaTeX2e'' which is available % on BlackBoard. You can also examine the source files for the scribed % lecture notes from lectures 1, 2, and 3 for some formatting ideas. % % Use the standard commands \section{}, \subsection{}, and \subsubsection{} % to format your document logically into sections, subsections, and % subsubsections (as needed). % % If you reference a URL anywhere, use the provided command \urlclick{} % like this: \urlclick{http://www.web.com/foo.html}. This will create a % clickable hyperlink in the resulting .pdf file. % % To add a figure to your notes, use the provided command \figureadd{} % like this: \figureadd{basename}{label}{caption}. In this command, % basename is the base name of your figure, which must exist in both .eps % and .jpg formats. For example, if you have created a figure named both % foo.jpg and foo.eps, then the basename is simply foo. The label field % creates a label which you can reference elsewhere using the standard % command \ref{}. Please use the caption field to provide a descriptive % caption for any figure you create. When you submit your scribed notes, % please also submit all your figure files in both .eps and .jpg formats. % % For a theorem, corollary, lemma, claim, fact, definition, assumption, % observation, or example, consider using these provided commands to set it % apart from other text: % \theorem{...} % \corollary{...} % \lemma{...} % \claim{...} % etc. % % For proofs, or sketches of proofs, use these provided environments: % \begin{proof} ... \end{proof} % \begin{proof_sketch} ... \end{proof_sketch} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\reals}{{\mathbb R}} \newcommand{\integers}{{\mathbb Z}} \newcommand{\ch}{\ensuremath\mathcal{CH}} % \newtheorem{theorem}{Theorem}[section] % \newtheorem{lemma}{Lemma}[section] % \newtheorem{corollary}{Corollary}[section] % \newtheorem{claim}{Claim}[section] % \newtheorem{prop}{Proposition}[section] % \newtheorem{fact}{Fact}[section] \newtheorem*{problem}{Problem} \newtheorem*{defn}{Definition} % \numberwithin{equation}{section} \renewcommand{\thesection}{\arabic{section}} \begin{document} %\label{begin} \textbf{Instructions:} \begin{itemize} \item The exam MUST be submitted no later than 5pm Monday Dec 15, whether electronically or by hand. \item The exam is open-book: you may use any reference material from the textbook, or from the Cormen/Leiserson/Rivest/Stein book, or from any handout I have provided/linked to. You MAY NOT use answers found on the web at large. If I discover that you have done so, you will be severely penalized. \item If you need a desired result (running time of Kruskal's algorithm, etc) that is not directly related to the problem you're solving, you may cite it. For example, you can say, ``We can compute an MST in $O(m\log n)$ time using Kruskal's algorithm (Kleinberg/Tardos, Chapter 4.5). Citations must come from one of the two textbooks indicated above. \item Unless clearly specified, all statements require proofs. If an algorithm is randomized, you must provide either an analysis of the expected running time, or a proof that the probability of failure is no greater than $\frac{1}{3}$. \end{itemize} \newpage \section{Approximate Medians} \label{sec:approximate-medians} The \emph{median} of a set of $n$ distinct numbers $x_1 \ldots x_n$ is the number $x_j$ such that the sets $L = \{ x_i < x_j \}$ and $R = \{ x_i > x_j\}$ each have cardinality $(n-1)/2$ (we'll assume for convenience that $n$ is odd. Another way of defining the median is via its \emph{rank}. Let the rank of a number $x_i$ be given by \[ r(x_i) = | \{ x \le x_i\} | \] In other words, the minimum element of the set has rank 1, the maximum has rank $n$, and the median has rank $(n+1)/2$. For many applications, we use the median as a way of creating a balanced split in the data for performing recursion (\textsc{quicksort} is one such example). For such applications, it's not critical that we compute the exact median, since any reasonably balanced splitter will suffice as well. This could potentially benefit us, since computing an approximate median might be faster than computing the exact median. Let an $\epsilon-$approximate median be an element $x$ such that \[ (1-\epsilon)(n+1)/2 \le r(x) \le (1+\epsilon)(n+1)/2 \] In other words, the rank of $x$ \emph{approximates} the rank of the median element. \paragraph*{Question.} \label{sec:question} Show that given a set of $n$ distinct numbers, we can compute an $\epsilon$-approximate median in time \emph{that depends only on $\epsilon$}. In other words, your algorithm running time \emph{will not depend on n}. \newpage \section{Sloppy Search} \label{sec:fast-binary-search} We know that binary search on a set of $n$ numbers takes $O(\log n)$ time. Suppose we are now given a set $S$ of $n$ numbers in the range $[1..n^2]$. Further, we are willing to be sloppy: given a query number $q$, instead of determining whether $q$ is exactly contained in the set, we are willing to tolerate an answer $\tilde{q} \in S$ such that \[ |q - \tilde{q}| \le \epsilon q \] For example, if we set $\epsilon = .1$, then for a query $q=5$, we are allowed to return any number in $S$ in the range $[4.5, 5.5]$. \paragraph*{Question.} \label{sec:question-1} Given linear preprocessing time, show that you can process the input such that a query can be answered sloppily in time $O(g(\epsilon)\log\log n + h(\epsilon))$, where $g(\epsilon), h(\epsilon)$ are some (could be constant) functions of $\epsilon$. \textbf{HINT:} Think about reducing the size of the input so that ``regular'' binary search can be applied. \newpage \section{To claim the Clay, or not to claim...} \label{sec:claim-clay-or} You've just been promoted to assistant CAO (Chief Algorithms Officer) at the offices of Church, Turing and G\"{o}del, Esq. Things are going smoothly: you've debunked three fake P = NP proofs, and spotted at least one attempted violation of the Halting Problem. But then, one day, your underlings Alice and Bob burst into your office, and the following conversation ensues: \begin{description} \item[\textsc{alice}] I just discovered this amazing approximation algorithm ! \item[\textsc{bob}] So did I ! \item[\textsc{alice}] In fact, it's a $(1+\epsilon)$-approximation. \item[\textsc{bob}] So's mine ! \item[\textsc{alice}] Mine runs in linear time \item[\textsc{bob}] And so does mine. \item[\textsc{alice}] Aha, but my actual running time is $O(n/\epsilon^{10})$. \item[\textsc{bob}] Mine is even better: $O(n/\epsilon^2)$. \item[\textsc{You}] (trying to cut through the clamor) But which problem did you solve ? \item[\textsc{alice}] \textsc{vertex cover} \item[\textsc{bob}] \textsc{knapsack} \item[\textsc{you}] Well, that's impressive. Bob, you can take your result down to the department of really boring algorithms. Alice, you'll need to book a plane ticket to Boston to collect your \$1,000,000 prize for proving $P = NP$. \end{description} \paragraph*{Question.} \label{sec:question-3} Explain your responses to Alice and Bob. \newpage \section{Greedy Colorings} \label{sec:greedy-colorings} As usual, a coloring of a graph is an assignment of colors $1, \ldots, k$ to vertices so that no two vertices connected by an edge have the same color. Consider the following greedy strategy for coloring a graph: \begin{enumerate} \item Order the vertices in some manner. \item Color the vertices in order, assigning the lowest-numbered available color to a vertex (in other words, check its colored neighbours and pick the lowest numbered color not used on the neighbors). \end{enumerate} For example, if we're given a path $v_1 - v_2 - \cdots - v_n$, and we order the vertices in the path order, then we use color 1 for $v_1$, color 2 for $v_2$, color 1 for $v_3$, and so on. More generally, we use as many colors as we need to color the graph in this manner. \paragraph*{Question.} \label{sec:question-4} \textbf{a)} Show that for any graph, there exists a sequence of vertices such that the greedy coloring uses the optimal number of colors. Note that since graph coloring is NP-complete, you're not expected to find this sequence in polynomial time (but if you do, there's an instant A+ for you !). \textbf{b)} On the other hand, the greedy coloring scheme can be quite bad. Show that there exists a 2-colorable graph and a vertex ordering for which the greedy coloring algorithm uses $\Theta(n)$ colors. \textbf{HINT:} A 2-colorable graph is bipartite. \end{document} %%% Local Variables: %%% mode: latex %%% TeX-master: "final" %%% End: