\documentclass[12pt]{article}
\textwidth = 6.7 in
\textheight = 9.2 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 8}
\\[1ex]}
\end{center}

This homework contains 3 problems worth a total of 30 regular points.
It is due on Friday, October 30 at noon.   Put your homework in
the appropriate dropbox in the Siebel basement.


\begin{enumerate}

%----------------------------------------------------------------------
\item 
\textbf{More on recurrences [10 points]}

In the discussion of Karatsuba's algorithm for multiplying integers
(end of lecture 25), I left out some details of the analysis.   Let's
fill in some of them:

\begin{enumerate}
\item  I claimed that if $T$ has the following recurrence
(where $c$ and $d$ are constants)

$$T(1) = c$$
$$T(n) = 4T(n/2) + dn$$

then $T$ is $O(n^2)$.   Show that this is true by unrolling the recurrence,
assuming that $n$ is a power of two.

\item I claimed that $n(\frac{3}{2})^{log_2 n}$ is $O(n^{log_2 3})$.
Show that this is correct.   Hint: use algebra and standard properties
of logs and exponentials.

\end{enumerate}



%----------------------------------------------------------------------
\item 
\textbf{Algorithm analysis [10 points]}

Consider the following mystery function:

\noindent
1. foo ($a_1,a_2,\ldots a_n$: real numbers) 
\vspace{-0.1in}
\begin{itemize}
\item[] 2. D = $|a_1 - a_2|$
\item[] 3. for $x = 1$ to $n$
  \begin{itemize}
  \item[] 4. for $y = 1$ to $n$
     \begin{itemize}
     \item[] 5. Q = $|a_x-a_y|$
     \item[] 6. if ($x \not = y$ and $Q < D$) D = Q
     \end{itemize}
  \end{itemize}
return D
\end{itemize}

\begin{enumerate}
\item Give a brief English description of what the function foo computes.
\item How many times are lines 5 and 6 executed, as a function of $n$?
\item What is the big-O running time of this algorithm?   Briefly
justify your answer.
\item This is a really bad algorithm for this task.   Write pseudocode
for a function with a better big-O running time.   Hint:  your new
function can call any of the standard algorithms we've seen in lecture
e.g. binary search.   
\item What is the big-O running time of your new function from part d?
Hint: if your new function called a standard library function, you
need to include its cost in your big-O analysis.   For example, 
a call to binary search requires $O(\log n)$ time, where $n$ is the
size of the array you're feeding to binary search.
\end{enumerate}

%----------------------------------------------------------------------
\newpage
\item 
\textbf{Son of algorithm analysis [10 points]}

A particularly irritating student in the beginning programming class submitted
the following function.   (The max function returns the largest of the
numbers given to it.)

\begin{itemize}
\item[] 1. bar($a_1,a_2,\ldots a_n$: real numbers) 
  \begin{itemize}
  \item[] 2. if (n = 1) then return 0
  \item[] 3. else
     \begin{itemize}
     \item[] 4. L = bar($a_2$,$a_3$,\ldots,$a_n$)
     \item[] 5. R = bar($a_1$,$a_2$,\ldots,$a_{n-1}$)
     \item[] 6. Q = $|a_1 - a_n|$
     \item[] 7. return max(L,R,Q)
     \end{itemize}
  \end{itemize}

\end{itemize}

\begin{enumerate}
\item Give a succinct English description of what bar computes.
\item Suppose that $T(n)$ is the running time for bar on the input $n$.
Write a recurrence (with initial condition!) for $T(n)$.
\item Draw a recursion tree for $T(n)$.
\item Use the tree to derive a big-O solution for $T(n)$.
\item Briefly explain why this isn't a good design and how you would write
a more efficient algorithm for this task.
\end{enumerate}

\end{enumerate}

\end{document}
