From 28dc8f73829e74da9c90bc52ba40036e3f182b00 Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Mon, 22 Oct 2018 20:35:40 +0000 Subject: brandeis-problemset (22oct18) git-svn-id: svn://tug.org/texlive/trunk@48972 c570f23f-e606-0410-a88d-b1316a301751 --- .../doc/latex/brandeis-problemset/README.md | 18 + .../brandeis-problemset-doc.sty | 30 ++ .../brandeis-problemset/brandeis-problemset.pdf | Bin 0 -> 104892 bytes .../brandeis-problemset/brandeis-problemset.tex | 435 +++++++++++++++++++++ .../doc/latex/brandeis-problemset/example.pdf | Bin 0 -> 47213 bytes .../doc/latex/brandeis-problemset/example.tex | 237 +++++++++++ 6 files changed, 720 insertions(+) create mode 100644 Master/texmf-dist/doc/latex/brandeis-problemset/README.md create mode 100644 Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset-doc.sty create mode 100644 Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.pdf create mode 100644 Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.tex create mode 100644 Master/texmf-dist/doc/latex/brandeis-problemset/example.pdf create mode 100644 Master/texmf-dist/doc/latex/brandeis-problemset/example.tex (limited to 'Master/texmf-dist/doc/latex') diff --git a/Master/texmf-dist/doc/latex/brandeis-problemset/README.md b/Master/texmf-dist/doc/latex/brandeis-problemset/README.md new file mode 100644 index 00000000000..0bb7da4cf1b --- /dev/null +++ b/Master/texmf-dist/doc/latex/brandeis-problemset/README.md @@ -0,0 +1,18 @@ +# The `brandeis-problemset` document class + +Brandeis University's computer science (“cosi”) courses often assign “problem +sets” which require fairly rigorous formatting. The `brandeis-problemset` document +class, which extends `article`, provides a simple way to typeset these problem +sets in LaTeX. + +File | Description +----------------------------|------------------------------ +brandeis-problemset.cls | The brandeis-problemset document class +brandeis-problemset.pdf | Documentation (English) +brandeis-problemset.tex | Documentation source +brandeis-problemset-doc.sty | Documentation styles +README.md | This file + +## License + +GNU GPLv3; see `LICENSE.md` diff --git a/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset-doc.sty b/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset-doc.sty new file mode 100644 index 00000000000..130b5d232e4 --- /dev/null +++ b/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset-doc.sty @@ -0,0 +1,30 @@ +\usepackage{hypdoc} +\usepackage[ + loadHyperref=false, + createIndexEntries=false +]{doctools} + +\PageIndex + +\usepackage{textcomp} % needed for listings +\usepackage{xparse} +\usepackage{hologo} % xetex, etc. logos + +\newcommand{\email}[1]{\href{mailto:#1}{\texttt{#1}}} +\newcommand{\https}[1]{\href{https://#1}{\texttt{#1}}} +\newcommand{\bps}{\ltxclass{brandeis-problemset}} +\newcommand{\cosi}[1]{\textsc{cosi}~#1} +\newcommand{\todo}[1]{\begin{itemize}\item[\textbf{To-do:}] #1 \end{itemize}} +\newcommand{\note}[1]{\begin{itemize}\item[\textbf{Note:}] #1 \end{itemize}} +\newcommand{\ctan}[1]{\href{https://ctan.org/pkg/#1}{\package{#1}}} +\NewExpandableDocumentCommand{\Th}{O{l} m} + {\multicolumn{1}{#1}{\textbf{#2}}} +\newcommand{\fontspecok}{\hologo{XeLaTeX} or \hologo{LuaTeX}} +\newcommand{\ext}[1]{\texttt{.#1}} +\newcommand{\filename}[1]{\texttt{#1}} + +% definition copied from doc package \DescribeMacro +\lstnewenvironment{latexfile}[1] + {\lstset{style=lstDemoStyleLaTeXCode}% + } + {} diff --git a/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.pdf b/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.pdf new file mode 100644 index 00000000000..da6787d2818 Binary files /dev/null and b/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.pdf differ diff --git a/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.tex b/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.tex new file mode 100644 index 00000000000..0bf25e08b0e --- /dev/null +++ b/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.tex @@ -0,0 +1,435 @@ +\documentclass{ltxdoc} +\usepackage{brandeis-problemset-doc} +\author{Rebecca Turner\thanks{Brandeis University; \email{rebeccaturner@brandeis.edu}}} +\title{The \bps\ Document Class} +\date{2018-10-19} + +\begin{document} +\maketitle + +\begin{abstract} + + Brandeis University's computer science (``\textsc{cosi}'') courses + often assign ``problem sets'' which require fairly rigorous + formatting. The \bps\ document class, which extends + \ltxclass{article}, provides a simple way to typeset these problem + sets in \LaTeX. + + Although \bps\ is compatible with all \LaTeX\ flavors, \fontspecok\ + is recommended for \ctan{fontspec} support. + +\end{abstract} + +\note{The \bps\ document class should be considered experimental; the only +stable \textsc{api} is that of the \env{problem} environment.} +\note{Browse the sources, contribute, or complain at + \https{github.com/9999years/brandeis-problemset}} + +\tableofcontents +\vfill +\pagebreak + +\section{Default behavior} + +\bps\ provides packages and well-formatted constructs (notably the +\env{problem} environment) for problem-set writers. \bps\ will always render +its body copy as a Times variant (\ctan{stix} for plain \LaTeX\ or +\ctan{xits} with \fontspecok) and always contains a useful header (which +contains the page number, author's name, course, instructor, and assignment +due date). + +\subsection{Default packages loaded} + +\begin{enumerate} +\item \ctan{hyperref}, for a nicely-linked table of contents; + \cs{href}|{url}{label}|. +\item \ctan{listings}, for verbatim code listings (including the + \env{assembly}, \env{java}, and \env{pseudocode} environments). +\item \ctan{xcolor}, for gray line numbers in code listings (and perhaps + colored listings in the future); e.g.\ \cs{color}|{gray}|. +\item \ctan{enumitem} for better control over the margins and spacing of + the \env{enumerate}, \env{itemize}, and \env{description} + environments. +\item Math packages: \begin{enumerate} + \item \ctan{amsmath} for tons of useful math commands, including + \cs{text}, \cs{intertext}, and \cs{boxed} as well as the \env{bmatrix}, + \env{multiline}, \env{gather}, \env{align}, and + \env{alignat} environments. See + \href{http://texdoc.net/texmf-dist/doc/latex/amsmath/amsldoc.pdf}{``User's + Guide for the \package{amsmath} Package''} for a more + complete listing. + \item \ctan{mathtools} for other useful/utilitarian commands. +\end{enumerate} +\item Table packages: \begin{enumerate} + \item \ctan{multirow} for cells spanning multiple rows. + \item \ctan{booktabs} for good-by-default tables and the \cs{cline} + macro. + \item \ctan{tabu}, the best table package with dynamically resizable + columns, easy creation of new column types, and more. +\end{enumerate} +\end{enumerate} + +\section{Class configuration} + +\subsection{Class options} + +\bps\ defines a limited set of key-value options that may be set at +\cs{documentclass}-time. These may be removed entirely in a future release, +as it seems ``messy'' to have three configuration methods +(\cs{documentclass} options, \cs{problemsetsetup}, and singular option +commands). + +\begin{Optionlist} + duedate & Assignment due date in full \\ + instructor & Instructor name in full \\ + course & Course name in full \\ + assignment & Assignment name in full \\ + gantt & Load packages for the \env{ganttschedule} environment \\ + antonella & Use Dr.\ Antonella DiLillio's preferred styles (Courier + for code) \\ +\end{Optionlist} + +Given that \cs{documentclass} option parsing is much more limited than other +key-value interfaces, these options have limited capabilities. + +\subsection{Setting options after loading \bps} + +\begin{macro}{\problemsetsetup}\marg{options}\AfterLastParam Sets global +\bps\ options; see table~\ref{tab:problemset-options} for a list of valid +options. + +\begin{table}[h] + \centering + \caption{Options for \cs{problemsetsetup}; many of these are just used + in document headers.} + \label{tab:problemset-options} + \begin{Optionlist} + course & Course name in full. \\ + coursenumber & Course name shorthand; use \texttt{21a} for + ``\cosi{21a}''. \\ + assignment & Assignment name in full. \\ + number & Assignment name shorthand; use \texttt{3} for ``Problem Set + 3''. \\ + duedate & Due date, e.g.\ \texttt{2018-10-18}; not parsed at all. \\ + instructor & Course instructor. \\ + codefont & With \fontspecok, pass the given font to \cs{setmonofont} + and enable Unicode shortcuts for the \env{pseudocode} + environment. (If you need to specify options to + \cs{setmonofont}, use \cs{setcodefont}.) \\ + gantt & Load packages for the \env{ganttschedule} environment \\ + antonella & True/false (default: false; if no value specified, + assumes true); use Dr.\ Antonella DiLillio's preferred + styles (Courier for code) \\ + \end{Optionlist} +\end{table} +\end{macro} + +\bps\ additionally provides a number of configuration commands with similar +interfaces as the \TeX\ macros \cs{author}, \cs{title}, and \cs{date}. + +\begin{macro}{\duedate}\marg{date} sets the due date in full.\end{macro} +\begin{macro}{\instructor}\marg{name} sets the instructor name.\end{macro} +\begin{macro}{\course}\marg{name} sets the course name in full.\end{macro} +\begin{macro}{\coursenumber}\marg{number} sets the course name by number; e.g. + |\coursenumber{21a}| gives a course of ``\cosi{21a}''.\end{macro} +\begin{macro}{\assignment}\marg{name} sets the assignment name in full.\end{macro} +\begin{macro}{\problemsetnumber}\marg{number} sets the assignment name by + number; e.g. |\problemsetnumber{3}| gives an assignment of ``Problem + Set 3''.\end{macro} + +\begin{macro}{\setcodefont}\oarg{fontspec options}\marg{font +name}\AfterLastParam Sets the monospaced font to \meta{font name} and uses +it for shortcuts in the \env{pseudocode} environment. + +\end{macro} + +\subsection{Practical usage} + +You may find it useful to define a \ext{sty} file for each course. For +instance, \filename{cosi21a.sty} might read: + +\begin{latexfile}{cosi21a.sty} +% set course/author data +\problemsetsetup{ + instructor=Dr.\ Antonella DiLillio, + coursenumber=21a, +} +\author{Rebecca Turner} + +% get a prettier code font -- these can be pretty big so they're not loaded +% by default +\setcodefont[ + Extension = .otf, + UprightFont = *-Regular, + BoldFont = *-Bold, +]{FiraMono} +\end{latexfile} + +and then \filename{ps1.tex} might read: + +\begin{latexfile}{ps1.tex} +\documentclass{problemset} +\usepackage{cosi21a} +\problemsetnumber{1} +\duedate{2018-10-29} +\begin{document} +% etc. +\end{document} +\end{latexfile} + +See section~\ref{sec:example} for a more complete example. + +\section{User commands and environments} + +\bps\ provides a number of commands for typesetting problems. + +\begin{macro}{problem}\oarg{options}\AfterLastParam Defines a problem. A +problem is set 1~inch from the left margin (although this amount may be +customized by modifying the \cs{problemindent} length) and begins a new +page. + +\begin{Optionlist} +title & A problem title, to be displayed after ``Problem'' and the problem's + number.\\ +number & A problem number; if given, the problem-number counter + will not advance. The number must be robust, because it goes inside + a \cs{section}. \\ +pagebreak & True/false (default: true). Add a pagebreak before the problem? \\ +\end{Optionlist} + +Vertical material is allowed in a~\env{problem}. +\end{macro} + +\begin{macro}{\subproblem}\oarg{description}\AfterLastParam Prints a sub-problem, i.e.\ a +\cs{subsection}. It doesn't do very much at the moment. +\end{macro} + +\begin{macro}{\Th}\oarg{colspec}\marg{header}\AfterLastParam Prints a table-header in bold. +By default, the header is left-aligned, but arbitrary alignments can be +specified with \meta{colspec}. \cs{Th} is backed by \cs{multicolumn}. +\end{macro} + +\begin{macro}{pseudocode}\oarg{keywords}\AfterLastParam Prints +pseudocode.\footnote{Designed for \cosi{21a} as taught by Dr.\ Antonella +DiLillo} Several shortcuts are defined, as shown in +table~\ref{tab:pseudocode}. + +These shortcuts display in +\cs{pseudocodesymbolfont} (default: \cs{ttfamily}), which may be redefined +if you prefer something else. The easiest way to change +\cs{pseudocodesymbolfont} is with \cs{setcodefont}. If you use the +\option{antonella} option with \fontspecok, \bps\ will load \ctan{lm-math} +and display the symbols seen in table~\ref{tab:pseudocode}, which look +significantly better with Courier than \textsc{stix}' symbols. + +\begin{table}[h] + \centering + \caption{Shortcuts provided by the \env{pseudocode} environment} + \label{tab:pseudocode} + \begin{tabular}{>{\ttfamily}lll} + \Th{Input} & \Th{Display} & \Th{Codepoint} \\ + <- & ← & U+2190 \\ + -> & → & U+2192 \\ + (/) & $\emptyset$ & U+2205 \\ + inf & $\infty$ & U+221E \\ + != & $\ne$ & U+2260 \\ + >= & $\ge$ & U+2265 \\ + <= & $\le$ & U+2264 \\ + \end{tabular} +\end{table} + +\todo{Improve the font selection mechanism; maybe provide a command for each + symbol?} +\note{If your \TeX\ engine doesn't support \textsc{utf}-8 input, the + shortcuts might appear totally blank or garbled. Good luck! It will surely + work with \fontspecok.} + +\begin{latexcode} +% the optional [Bar] makes [Bar] bold like the other keywords +\begin{pseudocode}[Bar] +Bar(a, n) + Input: two integers, a and n + Output: a^n + k <- n # k is a counter + 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{latexcode} +\end{macro} + +\begin{macro}{assembly}\oarg{extra options}\AfterLastParam typesets assembly +code.\footnote{Designed for \cosi{131a} as taught by Dr.\ Liuba Shrira} +Several considerations are taken into account; most notably, line numbers +are printed as \texttt{x + n}, where $n$ starts at 0 and counts by 4; the +line number actually indicates the instruction's location in memory as an +offset from the program start. Additionally, all valid instructions are +treated as keywords and styled appropriately. + +Any extra options are passed directly to the \ctan{listings} package. + +\begin{latexcode} +\begin{assembly} + LOAD R4, $200 ; sum addr + LOAD R1, =0 ; sum + LOAD R2, =0 ; i + LOAD R3, =0 ; j + BR OUTER ; we know i < 10 +INNER: ADD R1, R3 ; sum += j + INC R3 ; j++ +OUTER: BLT R3, R2, INNER ; while j < i goto inner + INC R2 ; i++ + LOAD R3, =0 ; j = 0 + BLT R2, =10, OUTER ; while i < 10 + STORE R1, @R4 ; store sum into sum address + HALT +\end{assembly} +\end{latexcode} +\end{macro} + +\begin{macro}{java}\oarg{extra options}\AfterLastParam Tragically-common +shorthand environment for a listing of Java code. + +Any extra options are passed directly to the \ctan{listings} package. +\end{macro} + +\begin{macro}{ganttschedule}\marg{total cell count}\oarg{title}\AfterLastParam +An environment for drawing Gantt charts indicating process scheduling. The +mandatory argument indicates how small the grid should be; \texttt{19} +subdivides the line into 19 cells. + +Within a \env{ganttschedule}, use the \cs{burst} command to indicate an +active process (i.e.\ a process burst). + +\begin{macro}{\burst}\marg{pid}\marg{burst length}\AfterLastParam +Draw a burst for process \marg{pid} of time length \meta{burst length}. +\end{macro} + +\note{These aren't really Gantt charts, but that's what Dr.\ Shrira calls + them, so that's what they're called here.} +\note{Because \env{ganttschedule} relies on \ctan{tikz}, \ctan{fp}, and + \ctan{calc}, it can add significantly to document compile times. + If you intend to use the \env{ganttschedule} + environment, make sure to use the \option{gantt} class option or set + \option{gantt} in \cs{problemsetsetup}.} + +\begin{latexcode} +\begin{ganttschedule}{19} + \burst{2}{1} + \burst{4}{1} + \burst{3}{2} + \burst{5}{5} + \burst{1}{10} +\end{ganttschedule} +\end{latexcode} +\end{macro} + +\subsection{General formatting commands} + +\begin{macro}{\ac}\marg{acronym}\AfterLastParam +Typesets an acronym. The \meta{acronym} should be lowercase (e.g.\ +\cs{ac}|{cpu}| rather than \cs{ac}|{CPU}|). Currently, \cs{ac} simply +delegates to \cs{textsc}. In the future, I'd like to support a bit of +letterspacing; ``for abbreviations and acronyms in the midst of normal text, +use spaced small caps.''\footnote{\textit{The Elements of Typographic Style} by +Robert Bringhurst, 2nd.\ ed, \S\ 3.2.2} +\end{macro} + +\begin{macro}{\Sc}\marg{text}\AfterLastParam +An abbreviation for \cs{textsc}\end{macro} +\begin{macro}{\Rm}\marg{text}\AfterLastParam +An abbreviation for \cs{textrm}\end{macro} +\begin{macro}{\Up}\marg{text}\AfterLastParam +An abbreviation for \cs{textup}\end{macro} +\begin{macro}{\Bf}\marg{text}\AfterLastParam +An abbreviation for \cs{textbf}\end{macro} +\begin{macro}{\It}\marg{text}\AfterLastParam +An abbreviation for \cs{textit}\end{macro} +\begin{macro}{\Tt}\marg{text}\AfterLastParam +An abbreviation for \cs{texttt}\end{macro} + +\section{Example}\label{sec:example} + +A brief example usage of \bps\ follows. For a longer, more in-depth example, +see +\href{https://github.com/9999years/brandeis-problemset/blob/master/example.tex}{\filename{example.tex} +in the \bps\ repository.} + +\begin{latexcode} +\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} + +\begin{problem} + Write an assembly program! +\end{problem} + +\begin{assembly} + LOAD R1, $200 ; A = (program location) + 200 + LOAD R2, =1 ; i = 1 +\end{assembly} + +\begin{problem} + What does this algorithm 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} +\end{problem} + +$\Rm{Foo}(a, n)$ computes $a^n$, and will run in $O(n)$ time always. + +\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}%$ + + Draw a Gantt chart to illustrate the execution of these processes + using the \ac{sjf} scheduling algorith. +\end{problem} + +\begin{ganttschedule}{19} + \burst{2}{1} + \burst{4}{1} + \burst{3}{2} + \burst{5}{5} + \burst{1}{10} +\end{ganttschedule} +\end{document} +\end{latexcode} + +\end{document} diff --git a/Master/texmf-dist/doc/latex/brandeis-problemset/example.pdf b/Master/texmf-dist/doc/latex/brandeis-problemset/example.pdf new file mode 100644 index 00000000000..a9855c0dd25 Binary files /dev/null and b/Master/texmf-dist/doc/latex/brandeis-problemset/example.pdf differ 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} -- cgit v1.2.3