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.
Pandigital Numbers
October 30, 2012
Today’s exercise comes to us from /r/learnprogramming:
A 3-digit number is added to another 3-digit number, and the result is a 4-digit number. If the ten digits involved are all different (the digits 0 through 9), then what is the smallest possible value for any of the three numbers?
Your tasks are to find the smallest number, as requested, and also to find all such triples of numbers. 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.
Pythagorean Triples
October 26, 2012
Today’s exercise feels like a Project Euler problem:
A pythagorean triple consists of three positive integers a, b and c with a < b < c such that a2 + b2 = c2. For example, the three numbers 3, 4 and 5 form a pythagorean triple because 32 + 42 = 9 + 16 = 25 = 52.
The perimeter of a pythagorean triple is the sum of the three numbers that make up the pythagorean triple. For example, the perimeter of the 3, 4, 5 pythagorean triple is 3 + 4 + 5 = 12. There are 17 pythagorean triples with perimeter not exceeding 100. Ordered by ascending perimeter, they are: 3, 4, 5; 6, 8, 10; 5, 12, 13; 9, 12, 15; 8, 15, 17; 12, 16, 20; 7, 24, 25; 15, 20, 25; 10, 24, 26; 20, 21, 29; 18, 24, 30; 16, 30, 34; 21, 28, 35; 12, 35, 37; 15, 36, 39; 9, 40, 41; and 24, 32, 40.
How many pythagorean triples exist with perimeter not exceeding one million?
Your task is to write a program to compute the count of pythagorean triples with perimeter not exceeding one million. 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.
Universal Hash Function
October 23, 2012
Recently, when writing a program that shall remain anonymous, I needed a hash table with keys that could be either strings or integers. That may sound weird to you — it felt weird enough to me that I rearranged things so that all the keys had the same type. But the experience got me thinking about a universal hash function that could be used with keys of any type.
Your task is to write a hash function, suitable for your normal programming environment, that can take a value of any type and return a thirty-two bit integer suitable for use in a hash table. 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.
Prime Partitions
October 19, 2012
Today’s exercise is my penance for a wrong answer at /r/math.
A partition of a number is a way to add numbers to equal the target number; for instance, 1+1+2+3+5 is a partition of 11. We studied partitions in two previous exercises. If all the numbers used in the summation are prime, it is known as a prime partition; for instance, 2+2+2+2+3 = 2+3+3 = 2+2+2+5 = 3+3+5 = 2+2+7 = 11 are the 6 prime partitions for 11. The number of prime partitions of a number is a function known by the Greek letter kappa in number theory, so κ(11)=6. You can see the sequence of prime partitions at A000607.
The usual computation of the number of prime partitions is done in two parts. The first part is a function to compute the sum of the prime factors of a number; for instance, 42=2·3·7, so sopf(42)=12. Note that sopf(12)=5 because the sum is over only the distinct factors of a number, so even though 12=2·2·3, only one 2 is included in the calculation of the sum. You can see the sequence of the sums of the distinct primes dividing n at A008472.
Given the function to compute the sum of the prime factors of a number, the number of prime partitions can be calculated using the following formula:
Your task is to write a function that computes the number of prime partitions of a number; use it to calculate κ(1000). 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.
Version Control
October 16, 2012
We looked at the make programmer’s tool in a previous exercise, and today we look at another programmer’s tool, a version control system. Version control systems allow programmers to keep multiple versions of text files in an economical manner, and there are many of them available: git, subversion, rcs, and the grand-daddy of all of them, sccs.
Our version control system provides three commands. Put takes a single filename argument, stores the file in a history file, and removes the original file from the file system; the history file has the same name as the original file with an added suffix .hist. Get takes a filename argument plus an optional version argument and writes to the file system the requested version of the file, defaulting to the current version of the file if no version number is given; versions are numbered 0 for the current version, 1 for the previous version, 2 for the version before that, and so on. Dir takes a single filename argument and shows a directory listing all available versions of a file. Unlike the bigger version control systems, there are no branches, only a single trunk of history.
The key to the version control system is the history file, which stores the most recent version of the file in its entirety, preceeded by a header line. Then follows a succession of deltas, one for each historical version, each preceeded by its own header line. Here’s a sample history file primes.ss.hist:
@@@ phil Mon Oct 15 18:52:22 CDT 2012 Factorization by trial division
(define (primes n)
(let ((bits (make-vector (+ n 1) #t)))
(let loop ((p 2) (ps (list)))
(cond ((< n p) (reverse ps))
((vector-ref bits p)
(do ((i p (+ i p))) ((< n i))
(vector-set! bits i #f))
(loop (+ p 1) (cons p ps)))
(else (loop (+ p 1) ps))))))(define (factors n)
(let loop ((n n) (f 2) (fs (list)))
(cond ((< n (* f f))
(reverse (cons n fs)))
((zero? (modulo n f)
(loop (/ n f) f (cons f fs)))
(else (loop n (+ f 1) fs)))))
@@@ phil Mon Oct 15 18:50:32 CDT 2012 Fix typo s/vectr/vector
10,17d
@@@ phil Mon Oct 15 18:49:57 CDT 2012 Sieve of Eratosthenes
7c
(vectr-set! bits i #f))
.
The header line that preceeds each delta, including the current file version, starts with three asterisks. Then comes the name of the user that created the delta, and the date and time when it was created. The rest of the line is a comment written by the user when the delta is added to the history file.
Deltas are computed by the Unix diff command with the -e option (we wrote our own version in a previous exercise) comparing the old and new versions and applied by the Unix ed command by applying edit commands to the newest version to recreate older versions. We also use the Unix wc command to count the lines in a delta.
Your task is to write a version control system as 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.
Programming Praxis 