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

\newcommand{\stooge}{\mbox{\sc ThreeWaySort}}

\head{CSU690}{Algorithms and Data}{Fall 2006}{22 September 2006}{5}

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

{\bf 1. (15 points) Computing forces in particle physics} 

Chapter 5, Exercise 4, page 247.

{\bf 2. (15 points) Hidden surface removal in computer graphics} 

Chapter 5, Exercise 5, page 248.

{\bf 3. (3 + 5 + 7 = 15 points) Modes and majority elements}

A {\em mode}\/ of an array $A[1..n]$ is an element of $A$ that occurs
most number of times in $A$.  Thus, the mode of an array $A =
[7,4,12,4,1,1,4]$ is $4$, which occurs three times.

\begin{itemize}
\item[{\bf (a)}] Given an array $A[1..n]$ of $n$ integers, show how a
mode of $A$ can be determined in $O(n \log n)$ time.
\end{itemize}

An array $A[1..n]$ is said to have a {\em majority element}\/ if more
than half of its entries are the same.  We would like to determine
whether a given array $A$ has a majority element, and if so, find the
element.  Unlike in part (a), however, we will not restrict the
elements to be integers.  In fact, we assume that the elements of the
array are not necessarily from some ordered domain like the integers,
so there can be no comparisons of the form ``is $A[i] > A[j]$?''; only
questions of the form ``is $A[i] = A[j]$?'' can be answered.

\begin{itemize}
\item[{\bf (b)}] Show how to solve the majority element problem in
$O(n \log n)$ time.  

({\em Hint:} Split the array into two arrays $A_1$ and $A_2$ of half
the size.  Use a divide-and-conquer approach that finds the majority
element of $A$, if it exists, using the knowledge of majority elements
of $A_1$ and $A_2$, if they exist.)

\item[{\bf (c)}] Can you give a linear-time algorithm?

({\em Hint:} Another divide-and-conquer approach is as follows: (a)
pair up the elements of $A$ arbitrarily, to get $n/2$ pairs; (b) if
two elements of a pair are different, then discard both of them, else
keep just one of them.  Show that after this procedure there are at
most $n/2$ elements left, and that they have a majority element if $A$
does.)
\end{itemize}

{\bf 4. (6 + 6 + 3 = 15 points) A new 3-way sorting algorithm}

Consider the following ``3-way'' sorting algorithm.
\begin{tabbing}
\= $\stooge(A, i, j)$\\
\> 1. \= \algif\ \= $A[i] > A[j]$ \\
\> 2. \> \> exchange $A[i] \leftrightarrow A[j]$\\
\> 3. \> \algif\ $i + 1 \ge j$\\
\> 4. \> \> \algreturn\\
\> 5. \> $k \leftarrow \lfloor(j - i + 1)/3\rfloor$ \hspace{1in} \=
// Round down.\\
\> 6. \> $\stooge(A, i, j-k)$ \>  // First two-thirds.\\
\> 7. \> $\stooge(A, i + k, j)$ \> // Last two-thirds.\\
\> 8. \> $\stooge(A, i, j-k)$  \>  // First two-thirds again.
\end{tabbing}
\begin{itemize}
\item[{\bf (a)}] 
Argue that $\stooge(A, 1, n)$ correctly sorts the input array $A[1..n]$.

\item[{\bf (b)}]
Give a recurrence for the worst-case running-time of \stooge\ and a tight
asymptotic ($\Theta$-notation) bound on the worst-case running time.

\item[{\bf (c)}] Compare the worst-case running time of \stooge\ with
that of insertion sort and mergesort.
\end{itemize}

{\bf 5. (5 bonus points) A fault-tolerant OR-gate}

Assume we are given an infinite supply of two-input, one-output gates,
most of which are OR gates and some of which are AND gates.
Unfortunately the OR and AND gates have been mixed together and we
can't tell them apart.  For a given integer $k\geq 0$, we would like
to construct a two-input, one-output combinational ``$k$-OR'' circuit
from our supply of two-input, one output gates such that the following
property holds: If at most $k$ of the gates are AND gates then the
circuit correctly implements OR.  Assume for simplicity that $k$ is a
power of two.

For a given integer $k \geq 0$, we would like to design a $k$-OR
circuit that uses the smallest number of gates.  Design the best
possible circuit you can and derive a $\Theta$-bound (in terms of the
parameter $k$) for the number of gates in your $k$-OR circuit.
\end{document}

