1.2 Algorithmic Patterns
1.2 Algorithmic Patterns
An important aim of this course is that you develop algorithmic thinking. Here we develop useful and elegant patterns that help us organize computational ideas.1It is also intellectually satisfying to see how to build up concepts from the ground. You should learn to describe a method as a sequence of precise steps, trace what these steps do, and explain why they work. Here are a few important examples of algorithms we use throughout the course. Study them in detail; they are as important as the mathematical models we develop.
Our pseudocode focuses on the key algorithmic steps. We omit error checking and other implementation details.
It is striking how far three foundational concepts can take us: dictionaries, \(\lambda\) functions, and closures.2I use these ideas all the time when working with large language models. They help me choose algorithms for numerical problems and guide the LLMs in organizing code. The LLMs handle all of the programming-language syntax; I remain the architect of the computation. Mastering these ideas takes time, but with practice they become very useful tools. By combining the same building blocks we can count observations, normalize weights, filter lists, and avoid repeated work in recursive computations. As you read the examples below, look for these recurring patterns: recognizing how the pieces fit together is part of the pleasure of algorithmic thinking.
Dictionaries form our main building block.3We assume that dictionaries are available to us from the start. A dictionary is a mutable function \(D\) with a finite domain written as \(\pr{keys}(D)\).4In R, the keys are called `names’. If \(k \in \pr{keys}(D),\) \(D(k)\) returns its stored value for \(k\).5The call \(D(k)\) when \(k\) is absent results in an error. The assignment \(D(k)\gets v\) inserts or replaces the value at \(k\) in \(D\). The function \(\pr{values}(D)\) returns the list6In contrast to a set, a list allows for duplicates, which we want here. \(\qb{D(k) : k \in \pr{keys}(D)}\). We assume that \(\pr{keys}(D)\) returns the keys in the order in which they were inserted, and that \(\pr{values}(D)\) returns their values in the corresponding order.
Here is an example.
\begin{algorithm}
\begin{algorithmic}[1]
\State \(D\gets\) an empty dictionary.
\State \(D(\text{``Lion''})\) \Comment{Error: the key is absent.}
\State \(D(\text{``Lion''})\gets 15\)
\State \(D(\text{``Lion''})\) \Comment{Returns \(15.\)}
\State \(\pr{keys}(D)\) \Comment{Returns \(\qb{\text{``Lion''}}.\)}
\State \(\pr{values}(D)\) \Comment{Returns \(\qb{15}.\)}
\end{algorithmic}
\end{algorithm}
Lambda functions are so-called anonymous functions.7In R,
one writes \(x) h(x). They are useful
when a function is too short and simple to need a name. We write
\[
\lambdafun{x}{h(x)}
\]
for the function that takes \(x\) as its argument and returns \(h(x).\) For
example,
\begin{algorithm}
\begin{algorithmic}[1]
\State \(\pr{square}\gets\lambdafun{x}{x\cdot x}\)
\State \(\pr{cube}\gets\lambdafun{x}{\pr{square}(x)\cdot x}\)
\end{algorithmic}
\end{algorithm}
The function \(\pr{Accumulate}\) applies a function to a
running result and each item of a list.8In R, the corresponding call is
Reduce(f, L, init=start). By combining this one algorithm with
\(\lambda\)-functions, we can define many common functions as one-liners:9Recall \(\min \emptyset = +\infty\) and \(\max \emptyset = - \infty\).
\begin{algorithm}
\begin{algorithmic}[1]
\State \(\pr{Sum}\gets\lambdafun{L}{\pr{Accumulate}\rb{L,\, \lambdafun{(x,\, y)}{x+y},\, 0}}\)
\State \(\pr{Prod}\gets\lambdafun{L}{\pr{Accumulate}\rb{L,\, \lambdafun{(x,\, y)}{x\cdot y},\, 1}}\)
\State \(\pr{Minimum}\gets\lambdafun{L}{\pr{Accumulate}\rb{L,\, \lambdafun{(x,\, y)}{\Min{x,\, y}},\, +\infty}}\)
\State \(\pr{Maximum}\gets\lambdafun{L}{\pr{Accumulate}\rb{L,\, \lambdafun{(x,\, y)}{\Max{x,\, y}},\, -\infty}}\)
\State \(\pr{Length}\gets\lambdafun{L}{\pr{Accumulate}\rb{L,\, \lambdafun{(n,\, x)}{n+1},\,\, 0}}\)
\end{algorithmic}
\end{algorithm}
We call such functions as follows.
\begin{algorithm}
\begin{algorithmic}[1]
\State \(\pr{Sum}\rb{\qb{1,\, 2,\, 3}}\) \Comment{Returns \(6.\)}
\State \(\pr{Prod}\rb{\qb{1,\, 2,\, 3,\, 4}}\) \Comment{Returns \(24.\)}
\end{algorithmic}
\end{algorithm}
Here is the implementation.
\begin{algorithm}
\caption{Accumulate the items of a list.}
\begin{algorithmic}[1]
\State \textbf{Input:} a list \(L,\) a function \(f,\) and a start value \(\var{start}\).
\State \textbf{Output:} the accumulated value.
\Function{Accumulate}{\(L,\, f,\, \var{start}\)}
\State \(m\gets\var{start}\)
\For{\(x \in L\)}
\State \(m\gets f(m,\, x)\)
\EndFor
\Return \(m\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Applying a function to each entry of a list is another useful
pattern. The function \(\pr{Apply}\)10In R, the corresponding call is
lapply(L, f). returns the results in the same order as in the given list.
We write \(\pr{Append}(R,x)\) for the list obtained by adding \(x\) at the end of \(R.\)
\begin{algorithm}
\caption{Apply a function to each entry of a list.}
\begin{algorithmic}[1]
\State \textbf{Input:} a list \(L\) and a function \(f\).
\State \textbf{Output:} the list \(\qb{f(x) : x \in L}\).
\Function{Apply}{\(L,\, f\)}
\State \(y\gets\qb{}\) \Comment{\var{y} is now an empty list.}
\For{\(x \in L\)}
\State \(y\gets\pr{Append}\rb{y,\, f(x)}\)
\EndFor
\Return \(y\)
\EndFunction
\end{algorithmic}
\end{algorithm}
For example, take service times \(s=\qb{1,2,4,5}\) and a target \(\tau=3.\) The fraction above the target is computed as follows.
\begin{algorithm}
\begin{algorithmic}[1]
\State \(s,\, \tau \gets \qb{1,\, 2,\, 4,\, 5},\, 3\)
\State \(B\gets\pr{Apply}\rb{s,\, \lambdafun{x}{\1{x>\tau}}}\) \Comment{\(B=\qb{0,\, 0,\, 1,\, 1}.\)}
\State \(\var{fractionLong}\gets\pr{Sum}\rb{B}/\pr{Length}\rb{B}\) \Comment{\(\var{fractionLong}=1/2.\)}
\end{algorithmic}
\end{algorithm}
With \(\pr{Sum}\) and \(\pr{Apply},\) it is straightforward to build a function \(\pr{Normalize}\) that turns a list of non-negative weights into a list of probabilities.
\begin{algorithm}
\caption{Normalize non-negative weights into probabilities.}
\begin{algorithmic}[1]
\State \textbf{Input:} a list \(w\) of non-negative weights with positive sum.
\State \textbf{Output:} a list \(p\) of probabilities.
\Function{Normalize}{\(w\)}
\State \(\var{total}\gets\pr{Sum}\rb{w}\)
\Return \(\pr{Apply}\rb{w,\, \lambdafun{x}{x/\var{total}}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Filtering a list keeps the entries that pass a test, in their original order.
\begin{algorithm}
\caption{Keep the entries of a list that pass a test.}
\begin{algorithmic}[1]
\State \textbf{Input:} a list \(L\) and a test \(h\).
\State \textbf{Output:} the list \(\qb{x\in L:h(x)}\).
\Function{Filter}{\(L,\, h\)}
\State \(y\gets\qb{}\)
\For{\(x\in L\)}
\If{\(h(x)\)}
\State \(y\gets\pr{Append}\rb{y,\, x}\)
\EndIf
\EndFor
\Return \(y\)
\EndFunction
\end{algorithmic}
\end{algorithm}
For the service times above, \(\pr{Filter}\) selects the service times of jobs that exceed the threshold:
\begin{algorithm}
\begin{algorithmic}[1]
\State \(\pr{Filter}\rb{\qb{1,\, 2,\, 4,\, 5},\, \lambdafun{x}{x>3}}\) \Comment{Returns \(\qb{4,\, 5}.\)}
\end{algorithmic}
\end{algorithm}
Closures form the next important idea. An example is best to demonstrate this.
\begin{algorithm}
\caption{Construct a power function with a fixed exponent.}
\begin{algorithmic}[1]
\State \textbf{Input:} an exponent \(e\).
\State \textbf{Output:} a function that maps \(b\) to \(b^e\).
\Function{power}{\(e\)}
\Return \(\lambdafun{b}{b^e}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Observe that \(\pr{power}\) returns a \(\lambda\) function. This function captures the variable \(e\) from its surrounding scope.11The scope of a variable is the part of a program where it can be used. Here, the \(\lambda\) function is created where \(e\) is available. As a result, the returned function remembers the value of \(e.\) In the following example, \(\pr{power}\rb{2}\) returns a function with exponent \(2\) fixed. We name it \(\pr{square},\) then call it on a number:
\begin{algorithm}
\begin{algorithmic}[1]
\State \(\pr{power}\rb{1}\rb{9}\) \Comment{Returns \(9.\)}
\State \(\pr{square}\gets\pr{power}\rb{2}\) \Comment{\(\pr{square}=\lambdafun{b}{b^2}.\)}
\State \(\pr{square}\rb{5}\) \Comment{Returns \(25.\)}
\State \(\pr{cube}\gets\pr{power}\rb{3}\) \Comment{\(\pr{cube}=\lambdafun{b}{b^3}.\)}
\State \(\pr{cube}\rb{4}\) \Comment{Returns \(64.\)}
\end{algorithmic}
\end{algorithm}
In general terms, an outer function can return an inner function that remembers values from the call to the outer function. The returned inner function is called a closure.12It can take some time to get your head around a function that returns another function. Working through a few calls by hand helps. By calling the outer function and assigning its output to a new name, we specialize the outer, general, function. The returned function has the same structure, but with some variables bound to concrete values. In this way, we obtain a new, more specific function from a general computational template.
Dictionaries with default values are a first application of closures. The function \(\pr{Map}\) in Alg. 1.2.13 uses \(\var{default}=0\) unless another default is supplied. Each call creates a private empty dictionary \(\var{store}\) and returns a function \(\pr{f}\) that retains access to it. The same dictionary is available as \(\pr{f}.\var{store},\) and its default value as \(\pr{f}.\var{default}.\) We write \(\pr{f}(k)\gets v\) as shorthand for \(\pr{f}.\var{store}(k)\gets v.\)
\begin{algorithm}
\caption{Construct a map with a configurable default value.}
\begin{algorithmic}[1]
\State \textbf{Input:} a default value \(\var{default}\).
\State \textbf{Output:} a function \(\pr{f}\).
\Function{Map}{\(\var{default}=0\)}
\State \(\var{store}\gets\) an empty dictionary
\Function{f}{\(k\)}
\If{\(k\notin\pr{keys}(\var{store})\)}
\State \(\var{store}(k)\gets\var{default}\)
\EndIf
\Return \(\var{store}(k)\)
\EndFunction
\State \(\pr{f}.\var{store}\gets \var{store}\) \Comment{Expose stored entries for later access.}
\State \(\pr{f}.\var{default}\gets\var{default}\) \Comment{Expose the default for later access.}
\Return \(\pr{f}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The functions \(\pr{Keys}(\pr{f})\) and \(\pr{Values}(\pr{f})\) return the keys and values of the map \(\pr{f}.\)13We assumed at the start of this section that dictionaries provide \(\pr{keys}\) and \(\pr{values}.\) Since \(\pr{f}.\var{store}\) is a dictionary, we can use those operations here.
\begin{algorithm}
\caption{Return the keys of a map.}
\begin{algorithmic}[1]
\State \textbf{Input:} a map function \(\pr{f}\).
\State \textbf{Output:} its keys.
\Function{Keys}{\(\pr{f}\)}
\Return \(\pr{keys}(\pr{f}.\var{store})\)
\EndFunction
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\caption{Return the values of a map.}
\begin{algorithmic}[1]
\State \textbf{Input:} a map function \(\pr{f}\).
\State \textbf{Output:} its values.
\Function{Values}{\(\pr{f}\)}
\Return \(\pr{values}(\pr{f}.\var{store})\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Here is an example to see how to use a map.
\begin{algorithm}
\begin{algorithmic}[1]
\State \(\pr{g}\gets\pr{Map}()\) \Comment{\(\pr{g}.\var{default}=0.\)}
\State \(\pr{g}(3)\) \Comment{Returns \(0;\) stores \(0\) under key \(3.\)}
\State \(\pr{g}(3)\gets\pr{g}(3)+8\) \Comment{\(\pr{g}(3)=8.\)}
\State \(\pr{g}(3)\) \Comment{Returns \(8.\)}
\State \(\pr{Keys}\rb{\pr{g}}\) \Comment{Returns \(\qb{3}.\)}
\State \(\pr{Values}\rb{\pr{g}}\) \Comment{Returns \(\qb{8}.\)}
\end{algorithmic}
\end{algorithm}
With a map, it is easy to build a \(\pr{Count}\) function that counts the occurrences of each observed value in a list. When a value \(k\) is encountered for the first time, \(\var{counter}(k)\) therefore returns zero, and the update sets it to one. Every later occurrence increases the stored value by one. Thus, after all observations, \(\var{counter}(k)\) is the number of times \(k\) occurred.
In this and later algorithms, we use the convenient abbreviation \(v\xleftarrow{+}1\) for \(v\gets v+1.\)
\begin{algorithm}
\caption{Count observations in each state.}
\begin{algorithmic}[1]
\State \textbf{Input:} a list of observations \(L\).
\State \textbf{Output:} a map of counts \(\var{counter}\).
\Function{Count}{\(L\)}
\State \(\var{counter}\gets\pr{Map}()\)
\For{\(k\in L\)}
\State \(\var{counter}(k)\xleftarrow{+}1\)
\EndFor
\Return \(\var{counter}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
The function \(\pr{MakeMap}\) builds a map from two aligned lists. Its default value is zero unless another value is supplied.
\begin{algorithm}
\caption{Construct a map from lists of keys and values.}
\begin{algorithmic}[1]
\State \textbf{Input:} distinct keys \(\var{keys}=\qb{k_1,\, \ldots,\, k_n},\) values \(\var{values}=\qb{v_1,\, \ldots,\, v_n},\) and a default value.
\State \textbf{Output:} a map \(M\) with \(M(k_i)=v_i\) and the given default.
\Function{MakeMap}{\(\var{keys},\, \var{values},\, \var{default}=0\)}
\State \(M\gets\pr{Map}\rb{\var{default}}\)
\For{\(i=1,\, \ldots,\, n\)}
\State \(M(k_i)\gets v_i\)
\EndFor
\Return \(M\)
\EndFunction
\end{algorithmic}
\end{algorithm}
For a map we can filter its stored values by first filtering its list of keys. The result retains the original default value.
\begin{algorithm}
\caption{Keep the stored entries of a map whose values pass a test.}
\begin{algorithmic}[1]
\State \textbf{Input:} a map \(M\) and a test \(h\) on its values.
\State \textbf{Output:} a map with the same default value and retained entries.
\Function{FilterValues}{\(M,\, h\)}
\State \(S\gets\pr{Filter}\rb{\pr{Keys}(M),\, \lambdafun{k}{h(M(k))}}\)
\State \(V\gets\pr{Apply}\rb{S,\, M}\)
\Return \(\pr{MakeMap}\rb{\var{keys}=S,\, \var{values}=V,\, \var{default}=M.\var{default}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Notice how little new machinery this algorithm needs. \(\pr{Filter}\) selects the keys, \(\pr{Apply}\) retrieves their values, and \(\pr{MakeMap}\) puts the pairs into a new map. Once these small operations are understood, we can combine them to express a more complicated idea in just a few steps.
Caching is a technique to speed up recursive computations tremendously.14Caching is also called memoization. A recursive function15We will use recursion on many occasions in this book. may reach the same state more than once. By storing the result after its first computation, we can reuse it on later visits, thereby avoiding the cost of computing it again.
The Fibonacci numbers give a small example of the benefits of caching. They satisfy \(F_0=0,\) \(F_1=1,\) and \(F_n=F_{n-1}+F_{n-2}\) for \(n\geq2.\) Direct recursion computes the same values repeatedly. For example, \(\pr{Fibonacci}\rb{5}\) computes \(F_3\) twice and \(F_2\) three times.16Without caching, the number of computations increases exponentially fast as a function of \(n\).
\begin{algorithm}
\caption{Compute a Fibonacci number by direct recursion.}
\begin{algorithmic}[1]
\State \textbf{Input:} a non-negative integer \(n\).
\State \textbf{Output:} the Fibonacci number \(F_n\).
\Function{Fibonacci}{\(n\)}
\If{\(n\leq1\)}
\Return \(n\)
\EndIf
\Return \(\pr{Fibonacci}\rb{n-1}+\pr{Fibonacci}\rb{n-2}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
With a cache, we can replace recomputations with lookups, giving an algorithm for the Fibonacci numbers that runs in linear time. In general, a cache is a dictionary with states as keys and their computed results as values. \pr{Cache} packages this entire caching pattern into one function. It receives a function and returns a cached version of that function.17We call this a higher-order function.
\begin{algorithm}
\caption{Construct a cached version of a function.}
\begin{algorithmic}[1]
\State \textbf{Input:} a function \(f\).
\State \textbf{Output:} a cached version \(g\) of \(f\).
\Function{Cache}{\(f\)}
\State \(\var{cache}\gets\) an empty dictionary
\Function{g}{\(k\)}
\If{\(k\notin\pr{keys}(\var{cache})\)}
\State \(\var{cache}(k)\gets f(k)\)
\EndIf
\Return \(\var{cache}(k)\)
\EndFunction
\Return \(\pr{g}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Thus, after defining the direct recursive function in Alg. 1.2.20, we obtain its cached version with \[ \pr{Fibonacci}\gets\pr{Cache}\rb{\pr{Fibonacci}}. \] Recursive calls then use the cached binding of \(\pr{Fibonacci}.\)
To get some feeling for the difference in computation time, suppose a computer can do \(10^{10}\) operations a second. The uncached recursive computation of the \(100\)th Fibonacci number requires on the order of \(\phi^{100}\) operations, where \(\phi=(1+\sqrt{5})/2,\) giving roughly \(8\times10^{10}\) seconds, or \(9\times10^5\) days, under this simplified operation-counting model. Using \(\pr{Cache}\rb{\pr{Fibonacci}}\) instead results in \(100/10^10 = 10^{-8}\) seconds.
Sorting is another useful example of an algorithmic pattern. Alg. 1.2.22 implements quicksort, a recursive18And very efficient. algorithm to carry out the sorting.19Think deeply about this algorithm. It is very useful. The algorithm uses the function20We assume it is given. \(\pr{ChoosePivot}\) to select an element uniformly from its non-empty input list. Here, \(+\) denotes concatenation of lists.
\begin{algorithm}
\caption{Sort a list \(\Sset\) in increasing order.}
\begin{algorithmic}[1]
\State \textbf{Input:} a list $\Sset$.
\State \textbf{Output:} the elements of $\Sset$ in increasing order.
\Function{QSort}{$\Sset$}
\If{$|\Sset| \leq 1$}
\Return $\Sset$
\EndIf
\State $p \gets \pr{ChoosePivot}(\Sset)$
\State $\Lset \gets \qb{x \in \Sset : x < p}$
\State $\Mset \gets \qb{x \in \Sset : x = p}$
\State $\Rset \gets \qb{x \in \Sset : x > p}$
\Return $\pr{QSort}(\Lset) + \Mset + \pr{QSort}(\Rset)$
\EndFunction
\end{algorithmic}
\end{algorithm}
Now it is time to practice. For each True–False question, decide whether the statement is true or false.
TF 1.
Consider the following function, which returns a closure.
\begin{algorithm}
\begin{algorithmic}[1]
\Function{subtract}{\(b\)}
\Function{f}{\(a\)}
\Return \(a-b\)
\EndFunction
\Return \(\pr{f}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Let \(\pr{g}\gets\pr{subtract}\rb{3}.\) Claim: \(\pr{g}(5)=-2.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. The function \(\pr{g}\) retains \(b=3,\) so \(\pr{g}(5)=5-3=2.\)
TF 2.
Consider the following functions.
\begin{algorithm}
\begin{algorithmic}[1]
\Function{F}{\(w\)}
\Return \(2w\)
\EndFunction
\Function{g}{\(x\)}
\Return \(\lambdafun{x}{x\cdot\pr{F}(x)}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Claim: \(\pr{g}(2)\) returns \(8.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. The call \(\pr{g}(2)\) returns the function \(\lambdafun{x}{x\cdot\pr{F}(x)},\) not a number. The inner \(x\) is a new argument, so the \(2\) passed to \(\pr{g}\) is unused. Calling the returned function at \(3\) gives \(\pr{g}(2)(3)=3\cdot\pr{F}(3)=3\cdot6=18.\)
TF 3.
Consider the following function, which returns a test for whether a waiting time exceeds a threshold.
\begin{algorithm}
\begin{algorithmic}[1]
\Function{Exceeds}{\(b\)}
\Function{f}{\(w\)}
\Return \(\1{w>b}\)
\EndFunction
\Return \(\pr{f}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Let \(\pr{late}\gets\pr{Exceeds}\rb{5}.\) Claim: for waiting times \(4,5,9,\) the sum \(\pr{late}(4)+\pr{late}(5)+\pr{late}(9)\) equals \(2.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. The function \(\pr{late}\) retains the threshold \(b=5.\) It returns \(0,0,1\) for these waiting times, so the sum is \(1.\)
TF 4.
Claim: At \(\text{???},\) the algorithm should have \(d.\)
\begin{algorithm}
\begin{algorithmic}[1]
\Function{Map}{\(d\)}
\State \(\var{store}\gets\) an empty dictionary
\Function{f}{\(k\)}
\If{\(k\notin\operatorname{keys}(\var{store})\)}
\State \(\var{store}(k)\gets\text{???}\)
\EndIf
\Return \(\var{store}(k)\)
\EndFunction
\State \(\pr{f}.\var{store}\gets \var{store}\)
\State \(\pr{f}.\var{default}\gets d\)
\Return \(\pr{f}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. When a key is encountered for the first time, the function stores the default value \(d\) under that key.
TF 5.
Claim: At \(\text{???},\) the algorithm should have \(w_k/\var{total}.\)
\begin{algorithm}
\begin{algorithmic}[1]
\Function{Normalize}{\(\qb{w_1,\, \ldots,\, w_n}\)}
\State \(\var{total}\gets\pr{Sum}\rb{\qb{w_1,\, \ldots,\, w_n}}\)
\For{\(k=1,\, \ldots,\, n\)}
\State \(p_k\gets \text{???}\)
\EndFor
\Return \(\qb{p_1,\, \ldots,\, p_n}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True.
TF 6.
Apply the algorithm with threshold \(b=5\) to the times \(w= (4,9,2,11,4).\) Claim: The algorithm returns \(\bar w=6\) and \(q=2/5.\)
\begin{algorithm}
\begin{algorithmic}[1]
\State \(T\gets0,\) \(C\gets0\)
\For{\(k=1,\, \ldots,\, n\)}
\State \(T\xleftarrow{+}w_k\)
\If{\(w_k>b\)}
\State \(C\xleftarrow{+}1\)
\EndIf
\EndFor
\State \(\bar w\gets T/n,\) \(q\gets C/n\)
\Return \(q\)
\end{algorithmic}
\end{algorithm}
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. The successive values are \[ \begin{array}{c|ccccc} w & 4&9&2&11&4\\ \hline T & 4&13&15&26&30\\ C & 0&1&1&2&2 \end{array}. \] Thus, \(\bar w = 30/5=6\) and \(q=2/5.\) However, the algorithm returns only \(q\).
TF 7.
Consider the following algorithm, which assumes that at least one observation is supplied.
\begin{algorithm}
\begin{algorithmic}[1]
\State \textbf{Input:} observations \(\qb{x_1,\, \ldots,\, x_n},\) supplied one at a time.
\State \textbf{Output:} average \(\bar x\).
\State \(N\gets0,\) \(T\gets0\)
\For{\(k=2,\, \ldots,\, n\)}
\State \(N\xleftarrow{+}1\)
\State \(T\xleftarrow{+}x_k\)
\EndFor
\State \(\bar x\gets T/N\)
\Return \(\bar x\)
\end{algorithmic}
\end{algorithm}
Claim: The algorithm computes the average of the observations \(\qb{x_1,\ldots,x_n}.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. The loop should start at \(k=1\). If it did, then after the loop, \(N=n\) and \(T=\sum_{k=1}^n x_k,\) so \(T/N\) is the average.
TF 8.
Claim: The algorithm returns the largest observed waiting time. It assumes that at least one waiting time is observed.
\begin{algorithm}
\begin{algorithmic}[1]
\State \textbf{Input:} waiting times \(\qb{w_1,\, \ldots,\, w_n},\) supplied one at a time.
\State \textbf{Output:} maximum waiting time \(M\).
\State \(M\gets w_1\)
\For{\(k=2,\, \ldots,\, n\)}
\State \(M\gets\Max{M,\, w_k}\)
\EndFor
\Return \(M\)
\end{algorithmic}
\end{algorithm}
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. After iteration \(k,\) \(M=\Max{w_1,\ldots,w_k}.\) Therefore, after the final iteration, \(M\) is the largest observation.
TF 9.
There are \(N\) arrival streams, each containing \(T\) arrivals. Let \(A_i^k\) be the time of the \(i\)th arrival in stream \(k.\) Claim: the algorithm below returns the inter-arrival times of the merged stream in chronological order.
\begin{algorithm}
\begin{algorithmic}[1]
\State \textbf{Input:} arrival times \(\set{A_i^k:1\leq k\leq N,\, \ 1\leq i\leq T}\).
\State \textbf{Output:} inter-arrival times \((X_2,\, \ldots,\, X_{N\cdot T})\).
\Function{MergeArrivals}{$\set{A_i^k}$}
\State \((A_1,\, \ldots,\, A_{N\cdot T})\gets\pr{QSort}\rb{\qb{A_i^k:1\leq k\leq N,\, \ 1\leq i\leq T}}\)
\For{\(2\leq j\leq N\cdot T\)}
\State \(X_j\gets A_j-A_{j-1}\)
\EndFor
\Return \(\pr{QSort}\rb{\qb{X_2,\, \ldots,\, X_{N\cdot T}}}\)
\EndFunction
\end{algorithmic}
\end{algorithm}
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. The algorithm computes the same inter-arrival times, but sorts them before returning them. Consequently, their chronological order is lost. The two outputs are equal only when \(X_2,\ldots,X_{NT}\) are already in increasing order.
TF 10.
\begin{algorithm}
\begin{algorithmic}[1]
\State \textbf{Input:} a list $\Sset$.
\State \textbf{Output:} the elements of $\Sset$ in increasing order.
\Function{QSort}{$\Sset$}
\If{$|\Sset| \leq 1$}
\Return $\Sset$
\EndIf
\State $p \gets \pr{ChoosePivot}(\Sset)$
\State $\Lset \gets \text{???}$
\State $\Mset \gets \qb{x \in \Sset : x = p}$
\State $\Rset \gets \qb{x \in \Sset : x > p}$
\Return $\pr{QSort}(\Lset) + \Mset + \pr{QSort}(\Rset)$
\EndFunction
\end{algorithmic}
\end{algorithm}
Claim: At ???, the algorithm should have
\(\qb{x\in\Sset:x\leq p}.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. It should have \(\qb{x\in\Sset:x<p}.\) Otherwise, every copy of the pivot also occurs in \(\Lset.\) In particular, if all elements are equal, then \(\Lset=\Sset,\) so the recursive call does not receive a shorter list.
TF 11.
\begin{algorithm}
\begin{algorithmic}[1]
\State \textbf{Input:} a list $\Sset$.
\State \textbf{Output:} the elements of $\Sset$ in increasing order.
\Function{QSort}{$\Sset$}
\If{$|\Sset| \leq 1$}
\Return $\Sset$
\EndIf
\State $p \gets \pr{ChoosePivot}(\Sset)$
\State $\Lset \gets \qb{x \in \Sset : x < p}$
\State $\Mset \gets \qb{x \in \Sset : x = p}$
\State $\Rset \gets \qb{x \in \Sset : x > p}$
\State \textbf{return} ???
\EndFunction
\end{algorithmic}
\end{algorithm}
Claim: At ???, the algorithm should have
\(\pr{QSort}(\Lset)+\Mset+\pr{QSort}(\Rset).\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. The recursive calls sort the elements below and above the pivot. Every element of \(\Lset\) is smaller than every element of \(\Mset,\) and every element of \(\Mset\) is smaller than every element of \(\Rset,\) so their concatenation is sorted increasingly.
The next two questions provide some further practice with the keys and values of maps.
TF 12.
Consider the following instructions.
\begin{algorithm}
\begin{algorithmic}[1]
\State \(p\gets\pr{Map}(\var{default}=0)\)
\State \(p(0)\gets1/4\)
\State \(p(1)\gets1/2\)
\State \(p(2)\gets1/4\)
\end{algorithmic}
\end{algorithm}
Claim: \(\pr{Keys}(p)=\qb{0,1,2}\) and \(\pr{Values}(p)=\qb{1/4,1/2,1/4}.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
True. The arguments \(0,1,2\) are stored as keys in that order, and the numbers assigned to \(p(0),p(1),p(2)\) are returned as their corresponding values.
TF 13.
Consider the following instructions.
\begin{algorithm}
\begin{algorithmic}[1]
\State \(M\gets\pr{Map}()\)
\State \(M(2)\gets5\)
\State \(M(5)\xleftarrow{+}2\)
\State \(M(2)\xleftarrow{+}1\)
\end{algorithmic}
\end{algorithm}
Claim: \(\pr{Keys}(M)=\qb{2,5,6}\) and \(\pr{Values}(M)=\qb{5,2,6}.\)
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
False. We have \(\pr{Keys}(M)=\qb{2,5}\) and \(\pr{Values}(M)=\qb{6,2}.\) The value \(6\) stored under key \(2\) does not itself become a key.
Exercises require pen and paper.
Exercise 14.
For a non-negative integer-valued rv \(X\) with \(\E{X^2}<\infty,\) write \(G(k)=\P{X>k}\) and use indicator functions to prove:
- \(\E X = \sum_{k=0}^\infty G(k),\)
- \(\sum_{i=0}^\infty i G(i) = \E{X^2}/2 - \E{X}/2.\)
Hint
For (1) write \(\sum_{k=0}^\infty G(k) = \sum_{k=0}^\infty \sum_{m=k+1}^\infty \P{X=m};\) reverse the summations. Then note that \(\sum_{k=0}^\infty \1{k<m} = m.\) For (2):
\begin{equation*} \sum_{i=0}^\infty i G(i) = \sum_{n=0}^\infty \P{X=n} \sum_{i=0}^\infty i \1{n\geq i+1}, \end{equation*}and reverse the summations.
Solution
Did you actually try? Write your solution down first for comparison.
Show the solution
For (1): observe first that \(\sum_{k=0}^\infty \1{m>k} = m,\) since \(\1{m>k}=1\) if \(k<m\) and \(\1{m>k} = 0\) if \(k\geq m.\) With this,
\begin{align*} \sum_{k=0}^\infty G(k) &= \sum_{k=0}^\infty \P{X>k} = \sum_{k=0}^\infty \sum_{m=k+1}^\infty \P{X=m} \\ & = \sum_{k=0}^\infty \sum_{m=0}^\infty \1{m>k} \P{X=m} = \sum_{m=0}^\infty \sum_{k=0}^\infty \1{m>k} \P{X=m} \\ &= \sum_{m=0}^\infty m\P{X=m} = \E X. \end{align*}Since all terms are non-negative, interchanging the summations is valid.
For (2):
\begin{align*} \sum_{i=0}^\infty i G(i) &= \sum_{i=0}^\infty i \sum_{n=i+1}^\infty \P{X=n} = \sum_{n=0}^\infty \P{X=n} \sum_{i=0}^\infty i \1{n\geq i+1} \\ &= \sum_{n=0}^\infty \P{X=n} \sum_{i=0}^{n-1}i = \sum_{n=0}^\infty \P{X=n} \frac{(n-1)n}{2} \\ &= \sum_{n=0}^\infty \frac{n^2}{2} \P{X=n} - \frac{\E X}{2} = \frac{\E{X^2}}{2} - \frac{\E X}{2}. \end{align*}