diff options
author | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
---|---|---|
committer | Norbert Preining <norbert@preining.info> | 2019-09-02 13:46:59 +0900 |
commit | e0c6872cf40896c7be36b11dcc744620f10adf1d (patch) | |
tree | 60335e10d2f4354b0674ec22d7b53f0f8abee672 /macros/latex/contrib/brandeis-problemset/example.tex |
Initial commit
Diffstat (limited to 'macros/latex/contrib/brandeis-problemset/example.tex')
-rw-r--r-- | macros/latex/contrib/brandeis-problemset/example.tex | 294 |
1 files changed, 294 insertions, 0 deletions
diff --git a/macros/latex/contrib/brandeis-problemset/example.tex b/macros/latex/contrib/brandeis-problemset/example.tex new file mode 100644 index 0000000000..4391fa2a38 --- /dev/null +++ b/macros/latex/contrib/brandeis-problemset/example.tex @@ -0,0 +1,294 @@ +\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} |