\documentclass[
gantt,
scheme,
assembly,
math,
pseudocode,
tabu
]{brandeis-problemset}
\bpsset{
coursenumber=21a,
author=Rebecca Turner,
instructor=Dr.\ Liuba Shrira,
duedate=2018-10-20,
number=3,
}
\newacronyms{io, cpu}
\begin{document}
\maketitle
\Bf{Note:} This example document is provided to demonstrate the capability
and visual style of the
\href{https://ctan.org/pkg/brandeis-problemset}{\Tt{brandeis-problemset}}
document class. The solutions below are not guaranteed to be correct,
complete, or relevant.
The source code for this document is available at
\begin{quote}
\href{http://mirrors.ctan.org/macros/latex/contrib/brandeis-problemset/example.tex}{\Tt{/macros/latex/contrib/brandeis-problemset/example.tex}}
\end{quote}
on \href{https://ctan.org/}{\textsc{ctan}} (or, if you have
\Tt{brandeis-problemset} installed, in your \TeX\ distribution's
documentation directory).
\tableofcontents
\begin{problem}[part=Textbook problems]
An assembly language program implements the following loop:
\begin{lstlisting}[language=c]
int A[51];
int i = 1;
while(i <= 50) {
A[i] = i;
i++;
}
\end{lstlisting}
The array of integers $A$ is stored at memory location $x + 200$,
where $x$ is the address of the memory location where the assembly
program is loaded. Write the assembly program using the assembly
language introduced in class.
For a completely unrelated problem, see problem~\ref{schedule} (this
is an example of a \lstinline!\label! / \lstinline!\ref! pair).
\end{problem}
\begin{assembly}
LOAD R1, $200 ; A = (program location) + 200
LOAD R2, =1 ; i = 1
LOOP: STORE R2, @R1 ; *A = i
ADD R1, =4 ; A++
INC R2 ; i++
BLEQ R2, =50, LOOP ; Ensure i <= 50
HALT
\end{assembly}
\begin{problem}[number=1.11]
Direct memory access is used for high-speed \io\ devices in order to
avoid increasing the \cpu's execution load.
\begin{enumerate}
\item How does the \cpu\ interface with the device to
coordinate the transfer?
\item How does the \cpu\ know when the memory operations are
complete?
\item The \cpu\ is allowed to execute other programs while
the \ac{dma} controller is transferring data. Does
this process interfere with the execution of user
programs? If so, describe what forms of interference
are caused.
\end{enumerate}
\end{problem}
\begin{enumerate}
\item The \cpu\ sets up ``buffers, pointers, and counters for the
\io\ device'' and then ignores the transaction entirely;
because \ac{dma} transfers don't involve the \cpu\ at all,
they're especially efficient because they don't saturate the
\cpu\ bus.
\item The device controller sends a \cpu\ interrupt when each block of
data finishes transferring.
\item A \ac{dma} transfer only interferes with user programs as much
as any other \io\ operation might, i.e.\ the program may not
be able to complete other meaningful work before the
transfer finishes. From the user's perspective, a \ac{dma}
transfer is indistinguishable from any other type of \io\
operation.
Additionally, a \ac{dma} takes a lock on \ac{ram}; while a
\ac{dma} transfer is in progress, no other processes may
access \ac{ram}, which can be extremely limiting.
\end{enumerate}
\begin{problem}
In the following, use either a direct proof for the statements (by
giving values for $c$ and $n_0$ in the definition of big-O notation)
or cite the rules given in the lecture notes.
\begin{enumerate}
\item $\max(f(n), g(n))$ is $O(f(n) + g(n))$. Assume that $f(n)$
and $g(n)$ are non-negative for $n > 0$
\item If $d(n)$ is $O(f(n))$ and $e(n)$ is $O(g(n))$, then
the product $d(n) \cdot e(n)$ is $O(f(n) \cdot g(n))$
\item $(n + 1)^5$ is $O(n^5)$
\item $n^2$ is $\Omega(n\log n)$
\item $2n^4 - 3n^2 + 32n\sqrt n - 5n + 60$ is $\Theta(n^4)$
\item $5n\sqrt n \cdot \log n$ is $O(n^2)$
\end{enumerate}
\end{problem}
An example equation which defines $e$:
\begin{equation}
\exists! e \in \Re \text{ such that }
\int_1^e \frac{1}{t} dt = 1.
\end{equation}
The definition of the Mandelbrot set:
\begin{equation}
\begin{split}
c \in \mathbb{C},\, z_0 = 0, \\
\lim_{n \to \infty} z_n = z_{n - 1}^2 + c \ne \infty
\implies c \in \mathcal{M}
\end{split}
\end{equation}
\begin{solution}
The blue text here is a solution; it will disappear if the
\Tt{solutions} class option is removed.
``Rule $n$'' should be taken to refer to the $n$th rule on page 3 of the 5th
lecture notes, and ``$a$ is faster-growing than $b$'' is written as ``$O(a)
> O(b)$''.
\begin{enumerate}
\item Given that big-O notation describes asymptotic
growth, only the fastest-growing term matters --- therefore, given some $a$
and $b$ that are functions of $n$, $O(a) > O(b) \implies O(a + b) = O(a)$.
$\max(a, b)$ is defined to be the greater of $a$ and $b$, so $\max(a, b) \ge
a$ and $\max(a, b) \ge b$. If $O(a) > O(b)$, $O(\max(a, b)) = O(a)$ (and
vice-versa).
Given these facts, if $O(f(n)) > O(g(n))$, $\lim_{n\to\infty} \max(f(n),
g(n)) = f(n)$. Alternatively, if $O(f(n)) < O(g(n))$, $\lim_{n\to\infty}
\max(f(n), g(n)) = g(n)$. More briefly, $O(\max(f(n), g(n)) = O(f(n))
\Rm{ or } O(g(n))$.
And finally, because $O(a) > O(b) \implies O(a + b) = O(a)$ and $O(a) < O(b)
\implies O(a + b) = O(b)$, we may note that $O(a + b)$ simplifies to the
faster-growing of $O(a)$ and $O(b)$. The mathematical operation for ``the
greater of two terms'' is $\max(a, b)$, so $\max(f(n), g(n)) = O(f(n) +
g(n))$.
\item This is true as stated in rule 3, although it's very similar to how $O(a) >
O(b) \implies O(a + b) = O(a)$ --- in the asymptotic case, the smaller
factor becomes irrelevant.
\item Given that $(n + 1)^5 = n^5 + 5n^4 + 10n^3 + 10n^2 + 5n +1$ and as rule 5
states, only the highest degree of a polynomial matters (because
$\lim_{n\to\infty} \sum_{i = 0}^{i = k} a_i n^i = a_k n^k$), $(n + 1)^5 =
O(n^5)$.
\item $c = 1, n_0 = 1$
\item $c_1 = 1, c_2 = 3, n_0 = 4$
\item $c = 2, n_0 = 1$
\end{enumerate}
\end{solution}
\begin{problem}
What do the following two algorithms do? Analyze its worst-case
running time and express it using big-O notation.
\begin{pseudocode}[Foo]
Foo(a, n)
Input: two integers, a and n
Output: a^n
k <- 0
b <- 1
while k < n do
k <- k + 1
b <- b * a
return b
\end{pseudocode}
\begin{pseudocode}[Bar]
Bar(a, n)
Input: two integers, a and n
Output: a^n
k <- n
b <- 1
c <- a
while k > 0 do
if k mod 2 = 0 then
k <- k/2
c <- c * c
else
k <- k - 1
b <- b * c
return b
\end{pseudocode}
\end{problem}
$\Rm{Foo}(a, n)$ computes $a^n$, and will run in $O(n)$ time always.
$\Rm{Bar}(a, n)$ \It{also} computes $a^n$, and runs in $O(\log n)$
time --- this is referred to as exponentiation by squaring.
\begin{problem}[number=5.4, part=Scheduling, label=schedule]
Consider the following set of processes, with the length of the
\cpu\ burst given in milliseconds:
\begin{center}
\begin{tabu} to 0.25\linewidth{X[1,$]rr}
\Th{Process} & \Th{Burst time} & \Th{Priority} \\
P_1 & 10 & 3 \\
P_2 & 1 & 1 \\
P_3 & 2 & 3 \\
P_4 & 1 & 4 \\
P_5 & 5 & 2 \\
\end{tabu}
\end{center}%$
The processes are assumed to have arrived in the order $P_1$, $P_2$,
$P_3$, $P_4$, $P_5$, all at time 0.
\begin{enumerate}
\item Draw four Gantt charts that illustrate the execution
of these processes using the following scheduling
algorithms: \ac{fcfs}, \ac{sjf}, nonpreemptive
priority (a smaller priority number implies a higher
priority), and \ac{rr} (quantum = 1).
\item What is the turnaround time of each process for each
of these scheduling algorithms?
\item What is the waiting time of each process for each of
the scheduling algorithms?
\item Which of the algorithms results in the minimum average
waiting time (over all processes)?
\end{enumerate}
\end{problem}
\begin{enumerate}
\item \ac{sjf}
Average wait $= 3.2$.
\begin{tabu} to 0.25\linewidth{@{}>{$P_\bgroup}X[1]<{\egroup$}rr@{}}
\Th[@{}l]{Process} & \Th{Turnaround} & \Th[r@{}]{Waiting} \\
1 & 19 & 9 \\
2 & 1 & 0 \\
3 & 4 & 2 \\
4 & 2 & 1 \\
5 & 9 & 4
\end{tabu}
\begin{ganttschedule}{19}
\burst{2}{1}
\burst{4}{1}
\burst{3}{2}
\burst{5}{5}
\burst{1}{10}
\end{ganttschedule}
\end{enumerate}
\begin{problem}
Write a Scheme procedure to calculate an arbitrary up-arrow $a \uparrow^n
b$.
\end{problem}
\begin{scheme}
;;; (up-arrow 2 3 4) = 2^^^4
(define (up-arrow a n b)
(cond ((= n 1) (expt a b))
((and (>= n 1) (= b 0)) 1)
(else (up-arrow a
(- n 1)
(up-arrow a n (- b 1))))))
\end{scheme}
\end{document}