\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}