diff options
Diffstat (limited to 'Master')
| -rw-r--r-- | Master/texmf-dist/doc/latex/brandeis-problemset/README.md | 18 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset-doc.sty | 30 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.pdf | bin | 0 -> 104892 bytes | |||
| -rw-r--r-- | Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.tex | 435 | ||||
| -rw-r--r-- | Master/texmf-dist/doc/latex/brandeis-problemset/example.pdf | bin | 0 -> 47213 bytes | |||
| -rw-r--r-- | Master/texmf-dist/doc/latex/brandeis-problemset/example.tex | 237 | ||||
| -rw-r--r-- | Master/texmf-dist/tex/latex/brandeis-problemset/brandeis-problemset.cls | 344 | ||||
| -rwxr-xr-x | Master/tlpkg/bin/tlpkg-ctan-check | 3 | ||||
| -rwxr-xr-x | Master/tlpkg/libexec/ctan2tds | 1 | ||||
| -rw-r--r-- | Master/tlpkg/tlpsrc/brandeis-problemset.tlpsrc | 0 | ||||
| -rw-r--r-- | Master/tlpkg/tlpsrc/collection-publishers.tlpsrc | 1 |
11 files changed, 1068 insertions, 1 deletions
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 Binary files differnew file mode 100644 index 00000000000..da6787d2818 --- /dev/null +++ b/Master/texmf-dist/doc/latex/brandeis-problemset/brandeis-problemset.pdf 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 Binary files differnew file mode 100644 index 00000000000..a9855c0dd25 --- /dev/null +++ b/Master/texmf-dist/doc/latex/brandeis-problemset/example.pdf 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} diff --git a/Master/texmf-dist/tex/latex/brandeis-problemset/brandeis-problemset.cls b/Master/texmf-dist/tex/latex/brandeis-problemset/brandeis-problemset.cls new file mode 100644 index 00000000000..d6aa05ae5a1 --- /dev/null +++ b/Master/texmf-dist/tex/latex/brandeis-problemset/brandeis-problemset.cls @@ -0,0 +1,344 @@ +\ProvidesClass{brandeis-problemset}[2018-10-20 0.2.0 COSI Problem sets at Brandeis University] +% Description: A document class for Brandeis University's computer science +% courses' problem sets +% License: GPL-3.0 +% Homepage: https://github.com/9999years/brandeis-problemset +% https://ctan.org/pkg/brandeis-problemset +% Maintainer: Rebecca Turner <rebeccaturner@brandeis.edu> + +\errorcontextlines 10 + +\PassOptionsToClass{12pt}{article} +\LoadClass{article} + +\RequirePackage{xparse} + +\newif\iffontspec@ok +\fontspec@okfalse +\ExplSyntaxOn +\sys_if_engine_luatex:T +{ + \fontspec@oktrue +} +\sys_if_engine_xetex:T +{ + \fontspec@oktrue +} +\ExplSyntaxOff + +% pages +\PassOptionsToPackage{ + letterpaper, + margin=1.25in, + tmargin=1.5in, + bmargin=1.5in, +}{geometry} + +\PassOptionsToPackage{ + warnings-off={mathtools-colon,mathtools-overbracket} +}{unicode-math} + +% utility +\RequirePackage{xkeyval} +\RequirePackage{geometry} +\RequirePackage{changepage} % for adjustwidth env + +% formatting +\RequirePackage{hyperref} +\RequirePackage{xcolor} +\RequirePackage{listings} +\RequirePackage{fancyhdr} +\RequirePackage{enumitem} +\RequirePackage{titlesec} +\RequirePackage{titletoc} + +% math +\RequirePackage{amsmath} +\RequirePackage{mathtools} + +% tables +\RequirePackage{multirow} +\RequirePackage{booktabs} +\RequirePackage{longtable} +\RequirePackage{tabu} + +% package options +\RequirePackage{kvoptions} +\SetupKeyvalOptions{ + family=problemset, + prefix=problemset@, +} +\DeclareStringOption[\relax]{duedate} +\DeclareStringOption[\relax]{assignment} +\DeclareStringOption[\relax]{instructor} +\DeclareStringOption[\relax]{course} +\DeclareBoolOption{antonella} +\DeclareBoolOption{gantt} +\ProcessKeyvalOptions* + +\newif\ifpseudocode@loaded +\newif\ifpseudocode@unicode +% pseudocode commands +\let\pseudocodesymbolfont\ttfamily + +% fonts +\iffontspec@ok + \RequirePackage{unicode-math} + + \setmainfont[ + Extension = .otf, + UprightFont = *-regular, + BoldFont = *-bold, + ItalicFont = *-italic, + BoldItalicFont = *-bolditalic, + ]{texgyretermes} + + \setmathfont{XITSMath-Regular.otf} + \setmathfont{XITSMath-Bold.otf}[range={bfup->up,bfit->it}] +\else + \RequirePackage{tgtermes} + \RequirePackage{stix} +\fi + +\newcommand{\@antonella}{% + \ifproblemset@antonella + \instructor{Dr.\ Antonella DiLillio} + \iffontspec@ok + \setmonofont{Courier New}% + \else + \RequirePackage{couriers}% package courier-scaled + \fi + \fi +} +\AtBeginDocument{\@antonella} + +% lazily loads pseudocode environment +\newcommand{\ensure@pseudocode}{% + \ifpseudocode@loaded + \else + \iffontspec@ok + % use unicode shortcuts + \ProvideDocumentCommand{\pseudocodeleftarrow} {}{\pseudocodesymbolfont ←} + \ProvideDocumentCommand{\pseudocoderightarrow}{}{\pseudocodesymbolfont →} + \ProvideDocumentCommand{\pseudocodele} {}{\pseudocodesymbolfont ≤} + \ProvideDocumentCommand{\pseudocodege} {}{\pseudocodesymbolfont ≥} + \ProvideDocumentCommand{\pseudocodeemptyset} {}{\pseudocodesymbolfont ∅} + \ProvideDocumentCommand{\pseudocodene} {}{\pseudocodesymbolfont ≠} + \ProvideDocumentCommand{\pseudocodeinfty} {}{\pseudocodesymbolfont ∞} + \let\lmmath\undefined% ensure no '\lmmath already defined' errors + \newfontface{\lmmath}{latinmodern-math.otf}% + \let\pseudocodesymbolfont\lmmath + \else + % use math-mode fallbacks + \ProvideDocumentCommand{\pseudocodeleftarrow} {}{\ensuremath{\leftarrow}} + \ProvideDocumentCommand{\pseudocoderightarrow}{}{\ensuremath{\rightarrow}} + \ProvideDocumentCommand{\pseudocodele} {}{\ensuremath{\le}} + \ProvideDocumentCommand{\pseudocodege} {}{\ensuremath{\ge}} + \ProvideDocumentCommand{\pseudocodeemptyset} {}{\ensuremath{\emptyset}} + \ProvideDocumentCommand{\pseudocodene} {}{\ensuremath{\ne}} + \ProvideDocumentCommand{\pseudocodeinfty} {}{\ensuremath{\infty}} + \fi + \pseudocode@loadedtrue + \fi +} + +% loads the ganttschedule environment dependencies +\newif\ifgantt@loaded +\newcommand{\ensure@gantt} + {\ifgantt@loaded + \else + \RequirePackage{tikz} + \RequirePackage{fp} + \RequirePackage{calc} + \newcounter{@gantt@time} + \newcounter{gantt@time@after} + \newlength{\gantt@unit} + \gantt@loadedtrue + \fi} +\newcommand{\@loadgantt} + {\ifproblemset@gantt + \ensure@gantt + \fi} +% if 'gantt' package option was given +\@loadgantt + +% additional options +\newcommand{\duedate}[1] {\renewcommand{\problemset@duedate}{#1}} +\newcommand{\instructor}[1] {\renewcommand{\problemset@instructor}{#1}} +\newcommand{\course}[1] {\renewcommand{\problemset@course}{#1}} +\newcommand{\coursenumber}[1] {\renewcommand{\problemset@course}{\Sc{cosi} #1}} +\newcommand{\assignment}[1] {\renewcommand{\problemset@assignment}{#1}} +\newcommand{\problemsetnumber}[1]{\renewcommand{\problemset@assignment}{Problem Set #1}} +\newcommand{\setcodefont}[2][]{% + % don't fail if fontspec isn't loaded + \ifx\setmonofont\undefined\else + \let\pseudocodesymbolfont\texttt + \setmonofont[#1]{#2}% + \fi +} + +\define@cmdkeys{problemset}[problemset@]{duedate, instructor, course, assignment} +\define@key{problemset}{number}{\problemsetnumber{#1}} +\define@key{problemset}{coursenumber}{\course{#1}} +\define@key{problemset}{codefont}{% + \setcodefont{#1} +} +\define@boolkey{problemset}[problemset@]{antonella}[true]{} +\define@boolkey{problemset}[problemset@]{gantt}[true]{\@loadgantt} +\newcommand{\problemsetsetup}[1] {\setkeys{problemset}{#1}} + +% listings +\lstset{ + basicstyle=\ttfamily, + numbers=left, + numberstyle=\color{gray}\ttfamily, + aboveskip=1em, + belowskip=0.5em, + breaklines, + tabsize=4, +} + +\lstnewenvironment{assembly}[1][] + {\lstset{ + keywords={LOAD,STORE,ADD,SUB,MUL,DIV,INC,SKIP,BR,BLT,BGT,BLEQ,BGEQ, + BEQ,BNEQ,READ,WRITE,HALT}, + firstnumber=-3, + numberstyle={\color{gray}\ttfamily\addtocounter{lstnumber}{3}x +\ }, + morecomment=[l]{;}, + #1 + }}{} + +\lstnewenvironment{pseudocode}[1][] + {\ensure@pseudocode + \lstset{ + keywords={Input,Output,Complexity,while,do,return,for,to,if,then,else,True,False,None,and,or,nil,len}, + literate={<-}{{\pseudocodeleftarrow}}2 + {->} {{\pseudocoderightarrow}}2 + {(/)}{{\pseudocodeemptyset}}2 + {inf}{{\pseudocodeinfty}}3 + {!=} {{\pseudocodene}}2 + {>=} {{\pseudocodege}}2 + {<=} {{\pseudocodele}}2, + morecomment=[l]{\#}, + morekeywords={#1}, +}}{} + +\lstnewenvironment{java}[1][] + {\lstset{language=java, #1}} + {} + +\errorcontextlines 10 +\widowpenalties 1 10000 +\raggedbottom +\setlength{\parindent}{0em} +\setlength{\parskip}{0.5em} + +\let\Sc\textsc +\let\Rm\textrm +\let\Up\textup +\let\Bf\textbf +\let\It\textit +\let\Tt\texttt +\let\ac\textsc + +\renewcommand{\labelitemi}{---} +\setlist[1]{ + leftmargin=0em, +} +\setlist{ + partopsep=0em, + topsep=0em, + %bottomsep=1em, + leftmargin=2em, +} + +\NewExpandableDocumentCommand{\Th}{O{l} m} + {\multicolumn{1}{#1}{\Bf{#2}}} + +% page headers +\fancyhf{} +\lhead{\@author + \hfill + \if\relax\problemset@assignment\else\problemset@assignment\fi + \if\relax\problemset@duedate\else\ (due \problemset@duedate)\fi\hfill + \if\relax\problemset@instructor\else\problemset@instructor\hfill\fi + \thepage} +\setlength{\headheight}{24pt} +\fancypagestyle{plain}{\fancyhead[L]{}} +\AtBeginDocument{\pagestyle{fancy}} + +\titleformat{\section}{}{}{0em}{\bfseries\large}[] +\titleformat{\subsection}{}{}{0em}{\llap{\alph{subsection}.\hspace{1em}}}[] +\titlespacing{\section}{0em}{1em}{0em}[0em] +\titlespacing{\subsection}{0em}{1em}{0em}[0em] + +\titlecontents{section} + [3.8em] % ie, 1.5em (chapter) + 2.3em + {} + {\hspace*{-3.8em}\contentspage\hspace*{3.8em}} + {\hspace*{-2.3em}} + {} + +\newlength{\problemindent} +\setlength{\problemindent}{1in} + +\newcounter{problemnumber} +\newcommand{\problem@title}{} +\define@key{problem}{title}{\renewcommand{\problem@title}{: #1}} +\define@boolkey{problem}{pagebreak}[true]{\ifKV@problem@pagebreak + \vfill\pagebreak + \else\fi} +\define@cmdkey{problem}{number}{} +\presetkeys{problem}{pagebreak}{} + +\NewDocumentEnvironment{problem}{O{}}{% + \setkeys{problem}{#1}% + \ifx\cmdKV@problem@number\undefined\stepcounter{problemnumber}% + \newcommand{\cmdKV@problem@number}{\arabic{problemnumber}}% + \else\fi + \section{Problem \cmdKV@problem@number\problem@title} + \begin{adjustwidth}{\problemindent}{0pt}} + {\end{adjustwidth}} + +\newcommand{\subproblem}[1][]{\subsection{#1}} + +\newcommand{\maketitlepage}{\thispagestyle{empty}% + \vspace*{2in}% + \begin{center}% + \Large\begin{tabular}{r|l} + \if\relax\problemset@assignment\else assignment & \problemset@assignment \\\fi + by & \@author \\ + \if\relax\problemset@course\else course & \problemset@course \\\fi + \if\relax\problemset@instructor\else instructor & \problemset@instructor \\\fi + \if\relax\problemset@due\else due & \problemset@due \\\fi + \end{tabular}% + \end{center}% + \pagebreak} + +\NewDocumentEnvironment{ganttschedule}{m o} % total size, title + {\ifgantt@loaded + \else + \PackageError{brandeis-problemset}{ganttschedule enviornment + not loaded in preamble}{Did you mean to use the 'gantt' + option for the brandeis-problemset document class?} + \fi + \setlength{\gantt@unit}{\linewidth / \real{#1}}% + \setcounter{@gantt@time}{0}% + \DeclareDocumentCommand{\burst}{m m} % pid, burst + {\setcounter{gantt@time@after}{\value{@gantt@time}}% + \addtocounter{gantt@time@after}{##2}% + \FPeval\gantthalf{(\arabic{@gantt@time} + + \arabic{gantt@time@after}) / 2}% + + \draw (\value{@gantt@time}, 0) rectangle + (\value{gantt@time@after}, 1); + \node at (\gantthalf, 0.5) {$P_{##1}$}; + \draw [|<->|] (\value{@gantt@time} + 0.05, 1.25) + -- node[above=1mm] {##2} + (\value{gantt@time@after} - 0.05, 1.25); + + \setcounter{@gantt@time}{\value{gantt@time@after}}}% + + \IfValueT{#2}{\begin{center} #2 \end{center}}% + \begin{tikzpicture}[x=\gantt@unit]} + {\end{tikzpicture}} diff --git a/Master/tlpkg/bin/tlpkg-ctan-check b/Master/tlpkg/bin/tlpkg-ctan-check index 1dcba712b82..e9e9fe74082 100755 --- a/Master/tlpkg/bin/tlpkg-ctan-check +++ b/Master/tlpkg/bin/tlpkg-ctan-check @@ -125,7 +125,8 @@ my @TLP_working = qw( booktabs booktabs-de booktabs-fr boolexpr boondox bophook borceux bosisio boxedminipage boxedminipage2e boxhandler bpchem bpolynomial - br-lex bracketkey braids braille braket brandeis-dissertation + br-lex bracketkey braids braille braket + brandeis-dissertation brandeis-problemset breakcites breakurl bredzenie breqn bropd brushscr bullcntr bundledoc burmese businesscard-qrcode bussproofs bxbase bxcalc bxcjkjatype bxdpx-beamer bxdvidriver diff --git a/Master/tlpkg/libexec/ctan2tds b/Master/tlpkg/libexec/ctan2tds index 9e6aa452b4d..71f810b4d13 100755 --- a/Master/tlpkg/libexec/ctan2tds +++ b/Master/tlpkg/libexec/ctan2tds @@ -1625,6 +1625,7 @@ $standardtex 'blockdraw_mp','NULL', # skip .sty's 'booktabs-de', 'NULL', # doc package 'booktabs-fr', 'NULL', # doc package + 'brandeis-problemset', '\.cls', # not *-doc.sty 'breqn', '\.sty|\.sym', 'c-pascal', '^[^d].*\.tex|' . $standardtex, # not demo*.tex 'calxxxx', 'cal.*\.tex', diff --git a/Master/tlpkg/tlpsrc/brandeis-problemset.tlpsrc b/Master/tlpkg/tlpsrc/brandeis-problemset.tlpsrc new file mode 100644 index 00000000000..e69de29bb2d --- /dev/null +++ b/Master/tlpkg/tlpsrc/brandeis-problemset.tlpsrc diff --git a/Master/tlpkg/tlpsrc/collection-publishers.tlpsrc b/Master/tlpkg/tlpsrc/collection-publishers.tlpsrc index aa63b70b5c7..5b22302376b 100644 --- a/Master/tlpkg/tlpsrc/collection-publishers.tlpsrc +++ b/Master/tlpkg/tlpsrc/collection-publishers.tlpsrc @@ -36,6 +36,7 @@ depend beilstein depend bgteubner depend br-lex depend brandeis-dissertation +depend brandeis-problemset depend cascadilla depend cesenaexam depend chem-journal |