<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside, 11pt]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}



%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\problemset}[3]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS~38~~~Introduction to Algorithms
                        \hfill Spring 2014} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Problem Set #1  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Out: #2 \hfill Due: #3} }
      \vspace{2mm}}
   }
   \end{center}
   \vspace*{4mm}
}
%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
            \vspace{0.2 in}
            \setlength{\epsfxsize}{#2}
            \centerline{\epsfbox{#4}}
            \begin{center}
            Figure \thelecnum.#1:~#3
            \end{center}
    }

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&amp;$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &amp;$\displaystyle{{}##}$\hfil\tabskip\@centering
    &amp;\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM
% HERE:


\newcommand{\set}[1]{\left \{{#1} \right \}}

\begin{document}
\problemset{3}{April 22}{\bf April 29}


Reminder: you are encouraged to work in groups of two or three;
however you must turn in your own write-up and note with whom you
worked. You may consult the course notes and the optional text (CLRS). The full honor code guidelines can be found in the course syllabus.


Please attempt all problems. {\bf To facilitate grading, please
turn in each problem on a separate sheet of paper and put your
name on each sheet. Do not staple the separate sheets.}
\begin{enumerate}


\item Recall that Fibonacci heaps support three operations, {\sc insert}, {\sc extract-min}, and {\sc decrease-key}, with amortized costs $O(1)$, $O(\log n)$, and $O(1)$, respectively. Describe a sequence of $n = 2^k$ operations so that a final {\sc extract-min} call takes at least $k$ operations. Assume that whenever a root is added to the root-list by any operation it is added to the left-most position, and that the consolidation process associated with {\em extract-min} processes the root list from left to right.
    
\item In a list of integers, $a_1, a_2, \ldots, a_n$, an {\em inversion} is a pair $(a_i, a_j)$
  with $i &lt; j$ but $a_i &gt; a_j$. Give a divide-and-conquer algorithm for
  computing the number of inversions in a list of $n$ integers, that
  runs in time $O(n \log n)$. Hint:
  your algorithm may resemble Mergesort.

\item Set $N = 2^n$ and consider the $N \times N$ matrix $M$ with rows and columns indexed by $\{0,1\}^n$, whose $(a,b)$ entry equals \[(-1)^{\sum_{i=1}^n a_ib_i}.\]
Give an algorithm that uses at most  $O(N \log N)$ operations for multiplying $M$ with a vector.

\item A Toeplitz matrix is a matrix whose diagonals are constant. An $n \times n$ Toeplitz matrix can thus be described by $2n-1$ values, specifying the values on each distinct diagonal. For example, here is the $4 \times 4$ Toeplitz matrix described by the values $4,3,6,7,2,5,9$:
    \[\left (\begin{array}{cccc} 7 &amp; 2 &amp; 5 &amp; 9 \\ 6 &amp; 7 &amp; 2 &amp; 5 \\ 3 &amp; 6 &amp; 7 &amp; 2 \\ 4 &amp; 3 &amp; 6 &amp; 7 \end{array} \right ).\]
    Give an algorithm to multiply two $n \times n$ Toeplitz matrices (each specified by a list of $2n-1$ values) in time $O(n^2\log n)$. Hint: reduce the problem to computing several products of polynomials. 

\item In this problem you will develop the (current) asymptotically fastest
  deterministic algorithm for factoring integers. If an integer $N$
  has a non-trivial factor, then it can be assumed to be a most
  $\sqrt{N}$, so there is a  brute force algorithm that tries
  $\sqrt{N}$ possible factors. Your algorithm will require only
  $N^{1/4}$ operations.

  In lecture we saw that degree-$n$ polynomial multiplication and division with remainder could
  be performed in $O(n \log n)$ operations when the polynomials had
  coefficients in the complex numbers. In fact those algorithms
  work without modification over any ring, and in this problem you
  will be working over the ring of integers modulo $N$, where $N$ is the number to
  be factored. In other words, all of the scalar values in this
  problem are integers between $0$ and $N-1$ and all computations on
  them are performed modulo $N$.

\begin{enumerate}
\item Remainder trees. Given a degree $n-1$ polynomial $f$ specified by its
  $n$ coefficients \[f_0, f_1, \ldots, f_{n-1},\] and $n$ evaluations
  points $a_0, a_1, \ldots, a_{n-1}$, describe a divide-and-conquer
  algorithm running in time $O(n \log^2 n)$
  that outputs $f(a_0), f(a_1), \ldots, f(a_{n-1})$. Hint: use
  these facts: (1) if $f$ is a polynomial and $a$ is a scalar,
  $f(X) \bmod (X - a)$ equals $f(a)$, and (2) if $f,g$ and $h$ are
  polynomials, $(f(X) \bmod g(X)h(X)) \bmod g(X) = f(X) \bmod g(X)$.

\item Let $M$ be an integer. Find an algorithm that outputs the integer $M! \bmod
  N$, using $O(\sqrt{M} \log^2 M)$ operations. Hint: consider the
  polynomial $\prod_{i=0}^{\sqrt{M}-1}(X - i)$, and apply the previous
  part.

\item Given $N, M$ (with $M$ satisfying $M \leq \sqrt{N}$), give an algorithm that determines whether there is a nontrivial factor (i.e., other than $1$) of $N$ that is at most $M$, using
  only $O(N^{1/4}\log^2 N)$ operations. You may use Euclid's algorithm which
  computes the greatest common divisor (GCD) of two $n$-bit integers in time $O(n^2)$, and the fact that $\mbox{GCD}(x,y) = \mbox{GCD}(x \bmod y, y)$.
\end{enumerate}
It is now standard that by using part (c) and performing a binary search on $M$, we can find the smallest non-trivial factor of $N$, divide, and repeat, until $N$ is completely factored. The resulting algorithm for factoring $N$ has running time $O(N^{1/4})\cdot$(lower-order terms) as promised.

\end{enumerate}
\end{document}

</pre></body></html>