#28: QUOBOSORT

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.

#27: Function Exponentiation

posted on 2018-01-30

Part 1

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.

Part 2

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.

#26: Finding the Identity Matrix

posted on 2018-01-30

Part 1

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.

Part 2

Write a version of largest-identity that allows for arbitrary row swaps.

#25: Merging Lists

posted on 2018-01-30

Part 1

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.

Part 2

Write a function like merge-2 that instead takes any number of sorted sequences.

Part 3

Write these functions to work on infinite streams.

#24: Run-Length Encoding

posted on 2018-01-30

Part 1

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.

Part 2

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)

#23: Computing Tangent

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$

Part 1

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$).

Part 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 Cases

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.

#22: Curried Application

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)$

#21: Defining Curried Functions

posted on 2018-01-30

Part 1

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))))

Part 2

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$.

#20: Uninitialized Locals

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

#19: Multi-Function Application, Curried

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.

This blog covers math, challenge

View content from 2018-01, 2018-02, 2018-03