\documentstyle[fancyheadings,12pt]{article}

\pagestyle{fancy}

\lhead{EECS Dept.}

\chead{Algorithms Ph.D. Comp. Exam.}

\rhead{Aug. 1996}

\cfoot{}

\addtolength{\headheight}{5pt}

\setlength{\headrulewidth}{1pt}



\setlength{\topmargin}{-0.6in}		%for dvi-imagen
\setlength{\oddsidemargin}{0.0in}   	%prev:-0.1 for dvi-imagen, -ve needed.
\setlength{\headheight}{.3in}
\setlength{\headsep}{.3in}
\setlength{\textheight}{8.8in}
\setlength{\textwidth}{6.5in} 
\setlength{\marginparwidth}{0in}
\setlength{\marginparsep}{0in}
\setlength{\marginparpush}{0in}
\setcounter{secnumdepth}{3}	%to get numbers on subsubsection in text
				%default is 2.
\setcounter{tocdepth}{3}	%to get numbers on subsubsection in toc
				%default is 2.
\setlength{\unitlength}{1mm}
\renewcommand{\baselinestretch}{1.2}  % for kind of double spacing
%\setlength{\parskip}{.3in}
\setlength{\baselineskip}{0.5cm} %JUST CHANGED FROM 0.5
\setlength{\parindent}{0.3in} %JUST CHANGED FROM 0.2
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55

\newcommand{\mod}{{\mbox{mod}}}
\newcommand{\ria}{\rightarrow}
\newcommand{\Ria}{\Rightarrow}
\newcommand{\ul}{\underline}
\newcommand{\ol}{\overline}
\newcommand{\xsp}{\hspace{0.5em}}
\newcommand{\ysp}{\vspace{1.1ex}}
\newcommand{\appr}{\sqsubseteq}
\newcommand{\trr}{\triangleright}
\newcommand{\lf}{\tt} %%%%%%%%%%%%%%%%%%%%%%%%%%%% LISP FONT, MAYBE CHANGE LATER
\newcommand{\etal}{{\em et al.}} 
\newcommand{\etc}{{\em et cetera}} 
\newcommand{\eto}{ evaluates to }
\newcommand{\col}{ Common Lisp}

\def\heading#1{ \begin{center} {\bf \ul{#1}} \end{center}}

\newcommand{\asmtabs}
	{mmmmm\=mmmmmmmm\=mmmmmmmm\=mmmmmmmmmmmmmmm\=  \kill}
\newtheorem{thm}{Theorem}
\newtheorem{propn}[thm]{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{examp}{Example}
\newtheorem{exercises}{Exercises}
\newtheorem{program}{Program}

\def\correct#1{\relax \ifmmode \expandafter #1 \else
$\expandafter #1$\fi}            % forces mathmode

\def\db#1{\correct{[\![ #1 ]\!]}}
\def\exer#1{\begin{exercises} \rm
{ #1 }
\end{exercises}}
\def\th#1{\begin{thm} \rm
{ #1 }
\end{thm}}
\def\exam#1{\begin{examp} \rm
{ #1 }
\end{examp}}
\def\lem#1{\begin{lemma} \rm
{ #1 }
\end{lemma}}
\def\prog#1{\begin{program} \rm
{ #1 }
\end{program}}
\def\verba#1{\begin{verbatim}
{ #1 }
\end{verbatim}}

\begin{document}
\setlength{\itemsep}{\parskip} 
\normalsize
%%%%%%%%%%%%%%%%%%%%%%555
\begin{enumerate}
\item
Prove or disprove the following properties of running time functions:
\begin{enumerate}
\item
If $f(n) \in O(n)$, then $[f(n)]^2 \in O(n^2)$.
\item
If $f(n) \in O(n)$, then $2^{f(n)} \in O(2^n)$.
\end{enumerate}
%%%%%%%%%%end 1
\item
Consider the following algorithm:
\begin{quote}
{\bf procedure} {\sf waste}$(n)$:
\\ \hspace*{1.0cm} {\bf for} $i$ ranging from 1 to $n$, {\bf do}
\\ \hspace*{2.0cm} {\bf for} $j$ ranging from 1 to $i$, {\bf do}
\\ \hspace*{3.0cm} write $i,j,n$;
\\ \hspace*{1.0cm} {\bf if} $n>0$ {\bf then}
\\ \hspace*{2.0cm} {\bf for} $i$ ranging from 1 to 4, {\bf do} 
\\ \hspace*{3.0cm} {\sf waste}$(n+2)$.
\end{quote}

Let $T(n)$ stand for the number of lines of output generated by
 a call of {\sf waste}$(n)$.
Provide a recurrence equation for $T(n)$,
 and determine the exact value of $T(n)$ or its order,
 in the simplest possible form.
%%%%%%%%%%end 2
\item
Let $m,n,z$ be positive integers.
\begin{enumerate}
\item
Prove that
 $(m~n) ~ \mod ~ z ~~=~~
  [(m ~\mod~ z) \times (n ~ \mod ~ z)]~\mod~z $
\\ and
 $(m^n) ~ \mod ~ z ~~=~~
  [(m ~\mod~ z)^n]~\mod~z $.
\item
How would you use these equations, if possible, to 
 develop divide and conquer algorithms to evaluate
 $(m~n) ~ \mod ~ z$
 and
 $(m^n) ~ \mod ~ z$?
\item
Provide recurrence equations for the running time for each of the
 divide and conquer algorithms you were able to construct in part (b).
You do not have to solve the recurrence equation(s).
\end{enumerate}
%%%%%%%%%%end 3
\item
Answer the following questions for (each of) Kruskal's algorithm
 and Prim's algorithm  to obtain the minimal spanning tree of a graph.
\begin{enumerate}
\item
What happens if each algorithm is executed on a graph that is not connected?
\item
What happens if each algorithm is executed on a graph 
 some of whose edges have negative weights?
\end{enumerate}
%%%%%%%%%%end 4
\newpage
\item
The problem of ``making change'' requires
 paying a specified amount to a customer using the smallest possible 
 number of coins.
Develop a dynamic programming solution to solve  the ``making change'' problem,
 assuming that we have an unlimited supply of coins,
 the amount to be paid to the customer is $N$ units,
 and that there are coins of $n$ different denominations,
 with each coin's value $\in \{d_1, ~ d_2, ~ \ldots , ~ d_n\}$
 (where each $d_i$, $n$ and $N$ is a positive integer).

For example, if we live in a country that has
 coins for 1, 4 and 6 units,
 and the specified amount to be paid to a customer is 8 units
 (i.e., $n=3, ~d_1=1, ~d_2=4, ~d_3=6, ~N=8$),
 then the optimum solution consists of two coins, both of value 4 units.
The greedy algorithm that uses a 6-unit coin first, 
 followed by two 1-unit coins, is not optimal.
%%%%%%%%%%end 5
\item
\begin{enumerate}
\item
Discuss the relationship between inserting into a binomial hep
and incrementing a binary number.
\item
Discuss the relationship between uniting two binary heaps
 and adding two binary numbers.
\item
Can your answer above be used to formulate an algorithm
 for uniting two binary heaps?
Explain.
\end{enumerate}
%%%%%%%%%%end 6
\item
An algorithm to find the greatest common denominator (GCD)
 of positive integers $u,~v$ is given below.
\begin{quote}
\hspace*{0.5cm} $n := 0$; 
\\ L1: $t := | u-v |$;
\\ \hspace*{0.5cm} if $t=0$ then return $u$ as the GCD and halt;
\\ L2: $t := t/2$;
\\ \hspace*{0.5cm} if $t$ is even then go to L2;
\\ L3: $n := n-1$;
\\ \hspace*{0.5cm} if $u \geq v$  then $u := t$ else $v := t$;
\\ \hspace*{0.5cm} go to L1.
\end{quote}
Let one ``iteration'' refer to one execution of step L3 in the algorithm.
\begin{enumerate}
\item
Why can we assume, without loss of generality, 
 that $u$ and $v$ are odd?
\item
Use this algorithm to find GCD(395, 275).
\item
How many iterations were performed to find GCD(395, 275)?
\item
How many iterations will be required to find GCD(u,v)
 for arbitrary $u,v$?
Comment on the worst case behavior of the algorithm.
\end{enumerate}
%%%%%%%%%%end 7
\end{enumerate}

\end{document}