posted on 2018-01-30

You happen upon the following note, which seems to describe a novel algorithm for sorting.

```
QUOBOSORT: a sort made by ROBERT SMITH aka STYLEWARNING
Patents Pending.
SUMMARY
-------
Permute X until the minimum is in the first position of X. When this
occurs, QUOBOSORT the rest of X until we reach an empty listte.
ALGORITHM
---------
QUOBOSORT(X) :=
-- INPUT: a list of integers X
-- OUTPUT: sorted X in ascending order
Q0. Is X an empty list?
Yes: Return X.
No : Go to Q1.
Q1. Find the minimum M of X.
Q2. Randomly permute X.
Q3. Is M in the first position of X?
Yes: Concatenate M and QUOBOSORT(REST(X))
No : Go to Q2.
```

Implement this algorithm.

*Extra Credit*: Analyse the time and memory complexity of this
algorithm.

posted on 2018-01-30

Given any $f:X\to X$ and any non-negative integer $n$, define the function

$$\mathtt{fexpt}(f, n) := \underbrace{f\circ \cdots \circ f}_{n\text{ times}}.$$

Implement `fexpt`

without mutation (i.e., without imperative loops or `set!`

).

*Extra Credit*: Try to optimize the runtime of the functions *resulting* from `fexpt`

.

The Babylonian method for computing square roots of positive numbers is as follows. To compute $\sqrt{X}$, start with an arbitrary positive number $x_0$. Define $x_n$ by the following recursive sequence:

$$x_{n+1} = \frac{1}{2}\left(x_n + \frac{x_n}{X}\right).$$

Then it can be proved that $\lim_{n\to\infty} x_n = \sqrt{X}$, and the sequence converges *quadratically* (the number of correct digits doubles with each iteration).

Implement this using `fexpt`

.

posted on 2018-01-30

Given an $m \times n$ matrix of zeros and ones, write a function `largest-identity`

that finds the size of the largest sub-matrix that is an identity matrix.

Write a version of `largest-identity`

that allows for arbitrary row swaps.

posted on 2018-01-30

Write a function `merge-2`

which takes two sorted lists and merges them into sorted order. This is an essential step of the merge sort algorithm.

Write a function like `merge-2`

that instead takes any number of sorted sequences.

Write these functions to work on infinite streams.

posted on 2018-01-30

Write a function `rle :: [Integer] -> [(Integer, Integer)]`

to compute the run-length encoding of a list of integers. The result is a list of `(<item>, <run-length>)`

pairs. Here are some test cases.

```
(rle '()) ; => ()
(rle '(1)) ; => ((1 1))
(rle '(1 1 1 2 2 3 2 3 3)) ; => ((1 3) (2 2) (3 1) (2 1) (3 2))
```

Try using your language's fold function and/or write in a functional fashion.

Run-length encoding can be applied to infinite streams as well, producing run-length encoded output. However, the function would never terminate if we were, say, given an infinite stream of `1`

's. As such, we might want to bound the size of the output run-lengths.

Write a function `rle'`

whose type, written in Standard ML notation, is

`(int option) * (int stream) -> (int, int) stream`

.

The first argument is an *option type*, which will be `None`

if we should allow unbounded run-lengths, and `Some n`

which bounds the run-lengths to at most `n`

, a positive integer. Here are some test cases in Haskell:

```
take 1 $ rle' None (repeat 1) -- never terminates
rle' None <finite list> -- equal to: rle <finite-list>
take 2 $ rle' None [1, 1, 1, 2, 2, ...] -- [(1, 3), (2, 2)]
take 3 $ rle' (Some 2) [1, 1, 1, 2, 2, ...] -- [(1, 2), (1, 1), (2, 2)]
rle' (Some n) (repeat x) -- equal to: repeat (x, n)
```

posted on 2018-01-30

The tangent of a number $\tan x$ is defined as $\sin x/\cos x$. We can compute tangent by using this definition, or we can make use of a so-called *addition formula*. The addition formula for tangent is

$$\tan (a + b) = \frac{\tan a + \tan b}{1 - \tan a \tan b}.$$

If we wish to compute $\tan x$, then we can compute $\tan(x/2 + x/2)$:

$$\tan(\tfrac{x}{2} + \tfrac{x}{2}) = \frac{\tan\tfrac{x}{2} + \tan\tfrac{x}{2}}{1-(\tan\tfrac{x}{2})(\tan\tfrac{x}{2})}=\frac{2\tan\tfrac{x}{2}}{1-(\tan\tfrac{x}{2})^2}$$

We also know something about tangent when the argument is small, namely that tangent is almost linear: $\tan x\approx x$

Write a recursive function `tangent`

using the methods above to compute the tangent of a number. It is not necessary to handle undefined cases (odd multiples of $\pi/2$).

Write an iterative version of `tangent`

called `tangent-iter`

which avoids tree recursion (i.e., doesn't consume any stack space due to recursion).

Test your code by comparing against your language's built in tangent function. Note that your results may not match precisely, due to the linear approximation ($\tan x \approx x$) and due to other floating point issues.

posted on 2018-01-30

Write a function `(@ f x y z …)`

which applies `f`

to `x`

, and then applies the result of that to `y`

, and so on. For example, `clog`

satisfies the following functional relation: `(@ clog 2 5) == ((clog 2) 5)`

. More generally, we have the functional relations:

- $(@\, f) = f$
- $(@\, f\, x_1 \ldots x_n) = ((@\,f\,x_1 \ldots x_{n-1})\, x_n)$

posted on 2018-01-30

Write `define-curried`

which defines a curried function. That is,

```
(define-curried-function (clog b x)
(/ (log x) (log b)))
```

will define `clog`

so that it's equivalent to:

```
(lambda (b)
(lambda (x)
(/ (log x) (log b))))
```

*Note*: This is difficult or impossible to write in full generality in some languages.

Write a combinator called $\mathrm{curry}_n\,f$ which takes a function $f$ of $n\ge 1$ arguments, and produces a fully curried version of $f$. (If you can compute $n$ from $f$, when you may elide $n$ as an argument.) It should satisfy the following equations:

- $\mathrm{curry}_1\,f = f$ for unary $f$, and
- $\mathrm{curry}_n\,f = x_1\mapsto\mathrm{curry}_{n-1}\big( (x_2, \ldots x_n)\mapsto f(x_1,\ldots, x_n)\big)$ for $n$-ary $f$.

posted on 2018-01-30

Write a macro `locals`

which acts sort of like `let`

, but allows uninitialized values. (If your language doesn't support uninitialized variables, then you can bind them to your false value, like `#f`

in Scheme.) For example:

```
(locals (a b (c 1) d)
(set! a 5)
(+ a c))
==> 6
```

posted on 2018-01-30

Write a unary function `appList*`

which satisfies the following equation:

`(appList L x) == ((appList* L) x)`

The function `appList*`

is said to be a *curried* version of `appList`

.