Homework 2 CS 3510
Author
John Schmidt
License
Creative Commons CC BY 4.0
Abstract
Template for GT Algorithms hw 2, Fall 2016
Template for GT Algorithms hw 2, Fall 2016
\documentclass[11pt]{article}
\usepackage{geometry, amsmath, amsthm, latexsym, amssymb, graphicx}
\geometry{margin=1in, headsep=0.25in}
\parindent 0in
\parskip 12pt
\begin{document}
\title{Homework 1 CS 3510}
\thispagestyle{empty}
\begin{center}
{\LARGE \bf CS 3510 A Homework 2}\\
{\large John Schmidt}\\
Fall 2016
\end{center}
\textbf{Question 1}\\
We studied in class a linear time deterministic algorithm to find the $\textit{k}$-th smallest element of a list
of $\textit{n}$ numbers A[1] through A[$\textit{n}$]. The following is a high-level description of a generalization of this
algorithm, in which the algorithm covered in class corresponds to the case d = 2 (Here d $\geq$ 1 is an
integer constant):
\begin{itemize}
\item Step 1: Divide the list into $\frac{n}{2d + 1}$ groups of (2d + 1) elements each. This takes $\textit{O}$(n) time.
\item Step 2: Sort each group and find their medians. Let S be the sequence of medians of these groups.
This takes $\textit{O}$(n) time.
\item Step 3: Recursively find the median of S. Let p be the median of S. (The size of S is $\frac{n}{2d + 1}$.)
\item Step 4: Partition the list A around this pivot into three sub-lists: A$_< p$, A$_> p$, and A$_= p$. This
takes O(n) time.
\item Step 5: Recurse appropriately on one of these three sub-lists.
\end{itemize}
(a) (5 points) Show that the size of each of A$_< p$ and A$_> p$ in Step 4 above is at most:
\begin{equation}
n - (d + 1) \times \frac{n}{2(2d + 1)}
\end{equation}
(b) (5 points) What is the recurrence for the running time of this algorithm in terms of n and d?\\
Explain the recurrence.
\\
(c) What is the solution to this recurrence for: \\
i. (3 points) d = 1? \\
ii. (2 point) d = 3? \\
Explain your answers.
\textbf{Solution:}\\
\textbf{Correctness Argument:}\\
\textbf{Algorithm:}\\
\textbf{Proof:}\\
\textbf{Analysis:}\\
\clearpage
\textbf{Question 2}\\
(15 points) Describe an algorithm that, given an n-digit decimal integer a, outputs the square of that
integer in O(n log n) time. Argue that your algorithm runs in O(n log n) time and that it is correct. \\
\textbf{Solution:}\\
\textbf{Correctness Argument:}\\
\textbf{Algorithm:}\\
\textbf{Proof:}
\textbf{Analysis:}\\
\clearpage
\textbf{Question 3}\\
Consider the butterfly network discussed in class.\\
Let N = 8. The network has four columns of 8 nodes each. Let the columns be C$_0$, C$_1$, C$_2$, C$_3$. Label
the nodes in column C$_{i}$ as C$_{i0}$, C$_{i1}$,$\dots$, C$_{i7}$. For 0 $\leq$ i $\leq$ 2, 0 $\leq$ j $\leq$ 7, from each node C$_{ij}$ in
column i there are two edges (a left edge and a right edge) to nodes in column i + 1. Label the left
edge as 0 and the right edge as 1. Denote this network by $\beta8$.\\ \\
A path in this network is such that: (a) it has three edges, and (b) it goes from a node in column 0 to
a node in column 1 to a node in column 2 to a node in column 3.\\ \\
Let (a0, a1,$\dots$, a7) be a permutation of (0, 1, 2, 3, 4, 5, 6, 7). We say that the network realizes the permutation (a0, a1,$\dots$, a7) if there are eight vertex-disjoint paths connecting C$_{0,j}$ to C$_{3,aj}$
for 0 $\leq$ j $\leq$ 7.\\ \\
Example: The network realizes the permutation (3, 6, 1, 4, 7, 2, 5, 0) with the following eight vertex-disjoint paths:\\ \\
C$_{0,0}$ $\to$ C$_{1,1}$ $\to$ C$_{2,3}$ $\to$ C$_{3,3}$ \\
C$_{0,1}$ $\to$ C$_{1,0}$ $\to$ C$_{2,2}$ $\to$ C$_{3,6}$ \\
C$_{0,2}$ $\to$ C$_{1,3}$ $\to$ C$_{2,1}$ $\to$ C$_{3,1}$ \\
C$_{0,3}$ $\to$ C$_{1,2}$ $\to$ C$_{2,0}$ $\to$ C$_{3,4}$ \\
C$_{0,4}$ $\to$ C$_{1,5}$ $\to$ C$_{2,7}$ $\to$ C$_{3,7}$ \\
C$_{0,5}$ $\to$ C$_{1,4}$ $\to$ C$_{2,6}$ $\to$ C$_{3,2}$ \\
C$_{0,6}$ $\to$ C$_{1,7}$ $\to$ C$_{2,5}$ $\to$ C$_{3,5}$ \\
C$_{0,7}$ $\to$ C$_{1,6}$ $\to$ C$_{2,4}$ $\to$ C$_{3,0}$ \\
(a) (10 points) Identify eight vertex-disjoint paths that connect C$_{0j}$ to C$_{3,aj}$
for 0 $\leq$ j $\leq$ 7, where
\begin{equation}
a_j = ( \frac{5j^2+ 5j + 10}{2})\ mod\ 8.
\end{equation}
(b) (5 points) Show, with a counter-example, that this network cannot realize all permutations of
(0, 1, 2, 3, 4, 5, 6, 7).
\textbf{Solution:}\\
\textbf{Correctness Argument:}\\
\textbf{Algorithm:}\\
\textbf{Proof:}\\
\textbf{Analysis:}\\
\clearpage
\textbf{Question 4}\\
Let A(x) = a$_0$ + a$_{1}$x +$\dots$+ a$_{N-1}$x$^{N-1}$ be a polynomial with N coefficients. Assume N is a power of 3.\\
Divide A(x) as the sum of three polynomials as shown below:\\
\begin{equation}
A(x) = p_1(x^3) + xq_1(x^3) + x^2r_1(x^3), where\\
\end{equation}
p$_1$(x) = a$_0$ + a$_{3}$x +$\dots$+ a$_{N-3}$x$^{N/3-1}$\\
q$_1$(x) = a$_1$ + a$_{4}$x +$\dots$+ a$_{N-2}$x$^{N/3-1}$, and\\
r$_1$(x) = a$_2$ + a$_{5}$x +$\dots$+ a$_{N-1}$x$^{N/3-1}$.\\ \\
Let ω be a principal N-th root of unity. Recall that an element ω is a principal N-th root of unity if
it satisfies the following two properties:
\begin{itemize}
\item $\omega$$^N$ = 1.
\item $\omega$$^j$ $\neq$ 1 for 1 $\leq$ j $\leq$ N - 1.
\end{itemize}
Let $\omega$−1 be the inverse of ω. That is, $\omega$$^{-1}$ $\times$ $\omega$ = 1.\\
(a) Assume that the following two claims are true:\\
$\textbf{Claim 1:}$ For all 0 $\leq$ j $\leq$ N/3 - 1,\\
($\omega$$^j$)$^3$ = ($\omega$$^{j + N/3}$)$^3$ = ($\omega$$^{j + 2N/3}$)$^3$.\\ \\
$\textbf{Corollary:}$ For all 0 $\leq$ j $\leq$ N/3 - 1, A($\omega$$^j$) = A($\omega$$^{j+N/3}$) = A($\omega$$^{j+2N/3}$).\\ \\
$\textbf{Claim 2:}$ Let $\omega$ be a principal N-th root of unity. Then, $\omega$$^3$
is a principal N/3-rd root of unity.\\ \\
(b) (10 points) What does the following algorithm SPOLY compute? Justify your answer.\\
SPOLY(A, N) $\to$ R
\renewcommand{\labelenumi}{\roman{enumi}}
\begin{enumerate}
\item EVAL (A, N, $\omega$) $\to$ U
\item For 0 $\leq$ j $\leq$ N - 1 do:
\begin{enumerate}
\item V [j] = U[j] $\times$ U[j]
\end{enumerate}
\item EVAL(V, N, $\omega$$^{-1}$) $\to$ R
\item For 0 $\leq$ j $\leq$ N - 1 do:
\begin{enumerate}
\item R[j] = $\frac{R[j]}{N}$
\end{enumerate}
\end{enumerate}
The procedure EVAL used by the algorithm above is:\\
EVAL(A, N, $\omega$) $\to$ U
\renewcommand{\labelenumi}{\roman{enumi}}
\begin{enumerate}
\item If N = 1 Then Return(A[0]).
\item A1 $\gets$ EV AL(p$_1$,$\frac{N}{3}$, $\omega$$^3$)
\item A2 $\gets$ EV AL(q$_1$,$\frac{N}{3}$, $\omega$$^3$)
\item A3 $\gets$ EV AL(r$_1$,$\frac{N}{3}$, $\omega$$^3$)
\item For 0 $\leq$ j $\leq$ N - 1 Do:
\begin{enumerate}
\item U(j) = A1(j) + $\omega$$^j$A2(j) + $\omega$$^{2j}$A3(j)
\end{enumerate}
\end{enumerate}
(c) (5 points) Write a recurrence for the run-time T(n) for the algorithm SPOLY and solve it.
Explain your recurrence.
\textbf{Solution:}\\
\textbf{Correctness Argument:}\\
\textbf{Algorithm:}\\
\textbf{Proof:}\\
\textbf{Analysis:}\\
\clearpage
\end{document}