diff options
Diffstat (limited to 'Master/texmf-dist/doc/latex/brandeis-problemset/example.tex')
| -rw-r--r-- | Master/texmf-dist/doc/latex/brandeis-problemset/example.tex | 237 |
1 files changed, 237 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/latex/brandeis-problemset/example.tex b/Master/texmf-dist/doc/latex/brandeis-problemset/example.tex new file mode 100644 index 00000000000..e558f7fb368 --- /dev/null +++ b/Master/texmf-dist/doc/latex/brandeis-problemset/example.tex @@ -0,0 +1,237 @@ +\documentclass[gantt]{brandeis-problemset} +\author{Rebecca Turner} +\problemsetsetup{ + coursenumber=21a, + instructor=Dr.\ Liuba Shrira, + duedate=2018-10-20, + number=3, +} +\newcommand{\io}{\ac{io}} +\newcommand{\cpu}{\ac{cpu}} +\begin{document} + +\Bf{Note:} This example document is provided for illustrative purposes. The +solutions below are not guaranteed to be correct or relevant. + +\begin{problem} + 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. +\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} + +``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} + +\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] + 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} + +\end{document} |