Selection, Revisited
November 30, 2012
We studied a selection algorithm in a previous exercise. The algorithm is the same as quicksort, except that recursion follows only the partition in which the target of the selection is located. We used a randomized algorithm to select the pivot, which gives an expected O(n) time complexity but a worst-case O(n^2) time complexity. In today’s exercise we examine an algorithm due to Blum, Floyd, Pratt, Rivest and Tarjan from their 1973 paper “Time Bounds for Selection” in Journal of Computer Systems Science that provides guaranteed O(n) time complexity (actually, the time complexity is sub-linear, but the only claim is that it is linear).
The algorithm is the same as the previous exercise except in the selection of the pivot. Instead of a random pivot, the algorithm partitions the input into blocks of five elements, finds the median of each block by comparisons, then chooses the median of the medians (which is computed recursively) as the pivot. Thus, the algorithm is known as “selection by the median of the medians of five.”
Your task is to write a function that selects the kth item from a list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Amazon Interview Question
November 27, 2012
We have today another question from our inexhaustible set of interview questions; this one comes from Amazon:
Given a million points (x, y), give an O(n) solution to find the 100 points closest to (0, 0).
Your task is to write the requested function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Tonelli-Shanks Algorithm
November 23, 2012
One of the operations of modular arithmetic, and an important step in many algorithms of number theory, is finding modular square roots. In the expression x2 ≡ a (mod p), x is a modular square root of a; for instance, 62 is a square root of 2, mod 113, because 62 * 62 = 3844 = 36 * 113 + 2. Like real numbers, modular square roots come in pairs, so -62 ≡ 51 (mod 113) is also a square root of 2.
The usual method for finding modular square roots involves an algorithm developed by Alberto Tonelli in the 1890s; there are several variants, including one due to Daniel Shanks in 1973, one of which we saw in a previous exercise. The particular variant that we will look at today is described at http://www.math.vt.edu/people/brown/doc/sqrts.pdf.
We will assume that the modulus p = s · 2e + 1 is an odd prime, that the number a for which we seek a square root is coprime to p, and that the Legendre symbol (a/p) is 1, which indicates that the square root exists. Find an n such that n(p−1)/2 ≡ −1 (mod p); it won’t take long if you start from n = 2 and increase n by 1 until you find one. Then set x ≡ a(s+1)/2 (mod p), b ≡ as (mod p), g ≡ ns (mod p), and r = e. Next find the smallest non-negative integer m such that b2m ≡ 1 (mod p), which is done by repeated squarings and reductions. If m is zero, you’re finished; report the value of x and halt. Otherwise, set x to x · g2r−m−1 (mod p), set b to b · g2r−m (mod p), set g to g2r−m (mod p), and set r = m, then loop back and compute a new m, continuing until m is zero.
As an example we find the square root of 2 mod 113. First compute p = 113 = 7 · 24 + 1 and n = 3, then x = 16, b = 15, g = 40, and r = 4. The first computation of m is 2, so set x = 62, b = 1, g = 98, and r = 2. Then the second computation of m is 0, so x = 62 is a square root of 2 (mod 113), and so is 113 – 62 = 51.
Your task is to write a function that computes modular square roots according to the algorithm described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
List Difference
November 20, 2012
I receive several emails from my readers each week, and I try to answer every one of them (except those that begin “I really admire your blog. You are obviously a great programmer. It has nothing to do with your recent exercise, but I am a student just learning to program, and I need help with my Java program that doesn’t work. Can you look at this program and tell me what is wrong? And they attach 400 lines of code without even bothering to tell me what is the task, or providing sample input and output, or even their name). I love to hear from my readers; your emails sustain me, and keep me writhing.
I had an email from a reader yesterday asking why I didn’t assign list differencing as a task when I assigned list intersection and union. The answer is: because I forgot!
So today we look at list differencing. Given two lists, their difference is the items in the first list that are not in the second list. For our sample lists A containing 4, 7, 12, 6, 17, 5, and 13 and B containing 7, 19, 4, 11, 13, 2, and 15, the difference A − B is 12, 6, 17, and 5 and the difference B − A is 19, 11, 2, and 15.
Your task is to write three list differencing functions, one each with time complexities O(n2), O(n log n), and O(n), and perform timing tests to confirm the expected time complexities. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.
List Intersection And Union
November 16, 2012
You are given two linked lists of integers with no duplicates. The intersection of the two lists is a list of integers that are in both lists, and the union of the two lists is a list of integers that are in either list. For instance, if list A contains the integers 4, 7, 12, 6, 17, 5 and 13 and list B contains the integers 7, 19, 4, 11, 13, 2, and 15 their intersection is the list 4, 7, and 13 and their union is the list 4, 7, 12, 6, 17, 5, 13, 19, 11, 2 and 15.
Your task is to write as many different versions of the functions that perform intersection and union as you can think of; you should have versions with time complexities of O(n2), O(n log n) and O(n), and you should perform timing tests to show that the various time complexities are achieved. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Frobenius Primality Test
November 13, 2012
As we know, it is difficult to prove that a number n is prime, so the usual recourse is a pseudoprimality test that is easy and fast but may possibly, though with very small probability, produce an incorrect answer. The most commonly used pseudoprimality test is doubtless the Miller-Rabin test, even though it is known to have errors in some circumstances. In today’s exercise we will examine the Frobenius test, which is an extension of and improvement on the Lucas test of a previous exercise.
Frobenius Pseudoprimality Test: Given an integer n greater than 2, determine with high probability if it is COMPOSITE or PROBABLY PRIME:
1. [Choose parameters] Set a and b to distinct random numbers uniformly distributed on the range 1 to n-1 inclusive. Set d = a^2 – 4b. If d is a perfect square or if gcd(2abd, n) ≠ 1 go to Step 1.
2. [Initialization] Set m = (n – (d/n)) / 2, where (d/n) is the jacobi symbol. Set w = a^2 * b^(-1) – 2 (mod n), where b^(-1) is the modular inverse of b with respect to n. Set u = 2. Set v = w. Set ms to a list of the bits in the binary representation of m, most significant bit first.
3. [Compute Lucas chain] If ms is empty, go to Step 4. If the first element of ms is 1, set u = u * v – w (mod n), set v = v * v – 2 (mod n), remove the first element of ms, and go to Step 3. If the first element of ms is 0, set v = u * v – w (mod n), set u = u * u – 2 (mod n), remove the first element of ms, and go to Step 3.
4. [Lucas test] If w * u ≠ 2 * v (mod n), report COMPOSITE and halt.
5. [Frobenius test] Set x = b ^ ((n-1)/2) (mod n). If x * u == 2 (mod n), report PROBABLY PRIME, otherwise report COMPOSITE. Halt.
A Frobenius test by itself isn’t perfect, so it is common to combine it with a Miller-Rabin pseudoprime test to just a few small bases.
Your task is to write a primality test based on Frobenius pseudoprimes. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Taxicab Numbers
November 9, 2012
We haven’t done a coding interview question for a while. Here’s one that is supposedly asked at Google:
The mathematician G. H. Hardy was on his way to visit his collaborator Srinivasa Ramanujan who was in the hospital. Hardy remarked to Ramanujan that he traveled in a taxi cab with license plate 1729, which seemed a dull number. To this, Ramanujan replied that 1729 was a very interesting number — it was the smallest number expressible as the sum of cubes of two numbers in two different ways. Indeed, 103 + 93 = 123 + 13 = 1729.
Given an arbitrary positive integer, how would you determine if it can be expressed as a sum of two cubes?
Your task is to write a function that returns all the ways a number can be written as the sum of two non-negative cubes; use it to verify the truth of Ramanujan’s statement. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Fix Something Annoying
November 6, 2012
In the previous exercise, I needed a function to display a floating-point number to a single decimal place. Standard Scheme doesn’t provide such a function, so I wrote one; it was simple enough.
But as I thought about it, I was annoyed that Standard Scheme doesn’t provide a proper rounding function; Standard Scheme does provide a round function, but it returns the nearest integer to its argument and doesn’t permit a parameter that specifies the number of digits after the decimal place. So I wrote such a function; it is shown on the next page.
But the point of today’s exercise isn’t to write a rounding function for Scheme. Every computing environment does something annoying; for instance, I just spent two minutes and wrote down 17 things about Standard Scheme that annoy me (no, I won’t share), then I spent another minute and wrote down 7 things that annoy me about WordPress (inability to edit comments is top of that list). The point is for you to seize control of your computing environment and fix something that annoys you.
So your task today is to find something about your computing environment that annoys you and fix it. When you are finished, you are welcome to read or run how I fixed what annoyed me, or to discuss your fix to what annoyed you in the comments below.
Gasoline Mileage Log
November 2, 2012
I keep a log of gasoline mileage on a 3-by-5 card in the glovebox of my car. Recent entries on the card look like this:
Date Mileage Miles Gals MPG
---------- ------ ----- ---- --
08/18/2012 107679 290.8 13.1 22
08/26/2012 107934 255.3 10.4 24
09/05/2012 108197 262.9 12.2 22
09/16/2012 108518 321.7 13.8 23
10/02/2012 108762 243.5 12.2 20
10/09/2012 109028 265.6 11.5 24
10/18/2012 109306 278.1 12.4 22
10/27/2012 109589 283.3 11.1 26
Your task is to read a file containing mileage and gallons, compute miles per gallon, and produce an output similar to that shown above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 