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

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