How to Solve it by Computer #9

Algorithm 5.2: Given a randomly ordered set of n integers, sort them into non-descending order using the selection sort.

So implementing selection sort. Should be easy, let’s see.

Was easy enough. Not quite as nice as writing it in Haskell but okay. The idea is that we take the smallest element put it in front, then repeat this until our list is empty. This is a bit different from the ‘traditional’ implementation which swaps the minimum result with that at the current lowest unsorted index. But the idea is the same.

Algorithm 5.6: Sorting by Partitioning. Implement quicksort.

I love quicksort. It’s such an easy and efficient algorithm.

Look at that beautiful algorithm. The idea is that you take a pivot – often the first element and create a new list which consists of elements smaller as the pivot, the pivot, and elements larger than the pivot. And you just apply quicksort to these other lists. That’s it.

 

Algorithm 6.1 Given a set of lines of text of arbitrary length, reformat the text so that no lines of more than n characters are printed. In each output line the maximum number of words that occupy less than n characters, should be printed and no world should extend across two lines. Paragraphs should also remain indented.

Good old textwrap. Let’s take a look at an example.

 

Imagine that we want to have n = 10. In this case the output is

 

We don’t want to break words which is problematic in case the word is longer than n.

I’m quite tired right now but a short explanation before going to bed. The software starts by splitting the current string into words and rebuilding the string with whitespaces. E.g. “ABC DEF” -> “ABC” ” ” “DEF”. Afterwards, it does two things:

a) In case the current-length of the temporary sentence is less than n -> append new word
b) In case the current-length is bigger, append the temporary sentence to the output and start with a new word

Here’s the example from above:

You can see that it forms:

Exactly like above.

How to Solve it by Computer #8

Algorithm 4.7: Given a set of n distinct numbers, find the length of the longest monotone increasing subsequence.

Example: [2 9 4 7 3 11 8] -> [2 4 7 11] with length 4

Quite an interesting problem. I thought and tried different approaches. Here’s the problem I had or which I neglected. I thought the problem required all subsets. The idea of the algorithm in the book is to find the largest sequence given an end and then compare the length appending the next element.

However, I thought that it wouldn’t work in a case like this:

I’m still wondering whether there’s a case in which we throw away a sequence which could work out as the longest one. Sadly, the author didn’t discuss the problem.

I see that there’s an inherent sub-structure. If we find the longest sequence in the last X numbers we can lengthen it by prepanding more stuff. Hm, thinking about it, that’s a good idea.

Let’s reverse the list:

[59 58 57 56 5 4 55 3 2]

Strangely, this does make more sense. Although, it’s probably equivalent. OK, new code.

We want a function which takes a list and returns a list with the largest subsets. More interesting however are the intermediate steps. We want it to give various things:

a) the current longest subsets
b) the next number

And it should return the longest subsets.

Let’s code. This took a while :D. So, we start with get-lengthy-subsets which returns a list of the largest subsets for each ‘level’.

Basically very straight forward. We start with a set with just one empty vector. Then check for each element in our set whether adding the next number is monotone bigger. We use the function get-increasing-coll for that. In case it is increasing, it returns the new vector with the number added. Otherwise it just returns the current variable.

This function uses increasing? which checks for the increment – which also works if we start with an empty vector.

The last function which helps us to get longest subset is easy:

We just sort by the length and select the last one. Done. Finally :D

How to Solve it by Computer #7

Algorithm 3.6: Use the linear congruential method to generate a uniform set of pseudo-random numbers.

This is great and something I never did before – like most of the stuff here. The method were using is the linear congruential method which should create a uniform distribution of numbers.

The basic idea is to use the following formula to create the next pseudo-random number:

x_{n+1} = (ax_n + b) mod n for n >= 0

However, there are specific criteria for each parameter.

Parameter x_0: 0 <= x_0 < m
Parameter m: m >= length sequence required, (ax+b) mod m is an integer
Parameter a: if m is a power of 2 then a mod 8 = 5; if m is a power of 10 then a mod 200 = 21
sqrt(m) < a < m – sqrt(m)
(a-1) should be a multiple of every prime dividing into m
if m is a multiple of 4 then (a-1) should be a multiple of 4
Parameter b: b should be odd, not a multiple of 5

These are a lot of requirements and the easiest thing to do is use existing values. Wikipedia provides common parameters.

The ones provided by the book are:

m = 4096
b = 853
a = 109

Here’s the code:

Super straight forward. Let’s see how good it works. We want to compare the average.

Problem 3.6.1: Confirm that the algorithm repeats after generating m random numbers. Compute the mean value and variance for the set of m pseudo-numbers.

Seems to work.

Looks fine. Let’s see how big the variance over the average over the set is.

 

Yup. By the way, here are the functions for calculating the average and variance:

 

Pretty standard.

How to Solve it by Computer #6

Problem 2.7.1: Design an algorithm that counts the number of digits in an integer.

Again, not a super interesting problem but one which we can solve for free. And I love free stuff.

So is the next one.

Problem 2.7.2: Design an algorithm to sum the digits in an integer.

 

And this one is good too.

Problem 2.7.3: Design an algorithm that reads in a set of n single digits and converts them into a single decimal integer. For example, the algorithm should convert the set of 5 digits {2,7,4,9,3} to 27493.

 

And that’s why it’s cool to make small complete functions without side-effects. Reusability, baby.

Problem 3.4.2: It is possible to implement a sieving algorithm which crosses out each composite (non-prime) number exactly once rather than a number of times. […] Try to implement this algorithm aka. Sieve of Eratosthenes.

The wikipedia page got a cool animation of this algorithm. It’s a great starting point to start with this.

Let’s make this interactive. I start with a list of all integers from 2 to 40:

Now, imagine we know already that 2 is a prime number.

What we would now do is remove every number which is a multiple by 2. Or whose characteristic is mod 2 = 0.

 

Neat. Now we just need to find the next prime. We know that the next bigger number in our number list is a prime, in this case 3. And then we start again.

Let’s write a function:

I was surprised how small and easy to function is. Let’s go through it. We start easily with creating a list of numbers, like before. It starts with 2 and ends with n. Also we have an empty collection primes in which we put our primes. We know that the first element of our list numbers is always a prime, so we can put that into there. The next step is to remove all multiplies of that prime in our list. Now we just recursively call that function again. This runs so long until there’s no number left in numbers and the function returns our – now – big list of primes.

 

Neat.