%---------change this every homework
\def\yourname{}
% -----------------------------------------------------
\def\homework{1} % 0 for solution, 1 for problem-set only
\def\duedate{sat may 7, 2016 at midnight}
\def\duelocation{via course website}
\def\hnumber{e}
\def\prof{abhi shelat}
\def\course{\href{https://www.cs.virginia.edu/~shelat/16s4102}{cs4102 - algorithms - s'16}}%------
%-------------------------------------
%-------------------------------------
\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.5in,right=1.5in,centering]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.3,0.02,0.02}
\definecolor{cit}{rgb}{0.05,0.2,0.45}
\pagestyle{myheadings}
\markboth{\yourname}{\yourname}
\usepackage{clrscode}
\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\qed}{$\Box$}
\newcommand{\alg}[1]{\mathsf{#1}}
\newcommand{\handout}{
\renewcommand{\thepage}{H\hnumber-\arabic{page}}
\noindent
\begin{center}
\vbox{
\hbox to \columnwidth {\sc{\course} --- abhi shelat \hfill}
\vspace{-2mm}
\hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}H\hnumber.\yourname}}
}
\end{center}
\vspace*{2mm}
}
\newcommand{\solution}[1]{\medskip\noindent\textbf{Solution:}#1}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{practice}{\sc\color{cit}practice}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\begin{document}
\thispagestyle{empty}
\handout
You may collaborate with other students on
the homework but you must submit your own individually written
solution, identify your collaborators, and acknowledge any
external sources that you consult. Do no submit a solution that you cannot explain to me.
These extra credit problems will augment your grade, but they need to be \emph{perfectly correct}.
\begin{problem}{Arrays}\end{problem}
Many algorithms use arrays as a data structure; and good programming practice requires us to first initialize an
array before using it. The time to initialize or ``zero-out" the array is usually proportional to the size of the array.
In some cases, however, the time it takes to zero-out the array will overwhelm the actual running time of the algorithm. This problem
develops a way to overcome this problem.
Suppose your algorithm needs to access an array $A[1,\ldots,n]$ only $k$ times during its execution. Design a method
that ``simulates" access to a zeroed array $A$ using only $O(k)$ time (thus, you cannot spend $O(n)$ time to initialize $A$ since $k$ might be, say $\sqrt{n}$ and
therefore much smaller). By ``simulate access," we mean devise two functions {\sc read}$(i)$ and {\sc write}$(i,x)$ so that when you call read on an index $i$ that has not already been set, it will read 0. When you call read on
an index $i$ that has been written to before, it returns the most recent value of $x$
for which there has been a call to {\sc write}$(i,x)$.
The array $A$ may initially contain garbage (assume it is adversarially chosen garbage). You can also use extra memory in order to run your simulation (but this extra memory may also initially contain garbage). Both {\sc read} and {\sc write} should run in constant time.
\begin{problem}{Fibonacci}\end{problem}
Recall that the $n$\textsuperscript{th} Fibonacci number is $F_n= F_{n-1}+F_{n-2}$.
The naive recursive method for computing the $n$\textsuperscript{th} Fibonacci number
takes exponential time. Through dynamic programming, one can compute $F_n$ using $n$ integer operations (i.e., additions and multiplications). Surprisingly, there is an even faster method to compute $F_n$ using only integer operations. Devise and analyze and algorithm that computes $F_n$ in $\Theta(\log n)$ integer operations. Hint, consider the matrix-vector product
$$ A = \left[ \begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]\left[\begin{array}{c} x_1 \\ x_2 \end{array}\right] $$
\begin{problem}Balance\end{problem}
A binary tree is \emph{adjusted} if the length of any two paths from root to leaves differs by at most 1. Write an algorithm \textsc{check}$(r)$, that on input the root of a tree $r$ determines if tree $r$ is adjusted.
\end{document}