May 12, 2015
An interesting variant on binary search is Fibonacci search. Invented by Jack Kiefer in 1953 to find the zeros of a function, and first applied to searching in an array by David Ferguson in 1960, its initial appeal was to improve locality when searching for a record on magnetic tape. It was later applied to searching on paged memory when it was expensive to read a segment of an array from disk, and it is now used to improve locality of cache memory; a good idea never goes away! Here is a description of Fibonacci search, taken from Wikipedia:
Let Fk represent the k-th Fibonacci number where Fk+2=Fk+1 + Fk for k>=0 and F0 = 0, F1 = 1. To test whether an item is in a list of n ordered numbers, proceed as follows:
1) Set k = m, where Fm is the smallest Fibonacci number greater than or equal to n.
2) If k = 0, halt and report failure.
3) Test item against entry in position Fk-1.
4) If match, halt and report success.
5) If item is less than entry Fk-1, discard entries from positions Fk-1 + 1 to n. Set k = k – 1 and go to 2.
6) If item is greater than entry Fk-1, discard entries from positions 1 to Fk-1. Renumber remaining entries from 1 to Fk-2, set k = k – 2 and go to 2.
May 8, 2015
We have today a famous puzzle:
Five sailors are shipwrecked on a desert island. They quickly determine that the only other inhabitant of the island is a monkey and that the only food is coconuts. They set about collecting as many coconuts as they can and put them all in a pile. By nightfall they are too tired to divide the harvest; so they agree to go to sleep and divvy up the coconuts the next morning.
During the night one sailor awakens, suspicious that the others might try to cheat him, and desides to take his portion then and there and not wait until morning. He divides the coconuts into five piles and finds there is one coconut left over, which he gives to the monkey. He hides one of the five piles, then puts the rest of the nuts together and returns to sleep. About an hour later a second sailor awakens with the same suspicions and does the same thing: He divides the coconuts into five piles, leaving one extra, which he gives to the monkey. Then he hides what he thinks is his share and goes back to sleep.
One after another the rest of the sailors do the same: they each take one fifth of the coconuts in the pile (after giving the extra one to the monkey) and then return to sleep.
When the sailors awaken the next morning they all notice the coconut pile is much smaller than it was the night before, but since each man is as guilty as the others, no one says anything. They divide the coconuts (for the sixth time), but this time there is no coconut left for the monkey.
How many coconuts were in the original pile?
Your task is to determine how many coconuts were in the original pile; first solve the problem for 5 sailors, then again for 6 sailors, and finally for 30 sailors. 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.
May 5, 2015
I saw this question on a beginning programmer’s forum a couple of weeks ago. There were several answers, some of them wrong. So we’ll do it right:
Given an angle expressed in degrees, minutes, and seconds, convert it to radians. Given an angle in radians, convert it to degrees, minutes and seconds.
Your task is to write programs that perform the two conversions. 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.
May 1, 2015
Today’s exercise comes from the world of recreational mathematics; I found it at Stack Overflow:
The Collatz sequence starting at n continues with n / 2, if n is even, and 3 n + 1 if n is odd. For instance, the Collatz sequence that starts from 19 is 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. It is conjectured that all Collatz sequences eventually end at 1, but has never been proven. The Collatz sequence that starts from 19 contains 7 prime numbers: 19, 29, 11, 17, 13, 5 and 2. Find the smallest starting number for a Collatz sequence that contains 65 or more primes.
Your task is to find the requested Collatz sequence. 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.
April 28, 2015
Two words are anagrams if they consist of the same letters, with the same number of occurrences, in a different order. For instance, DEPOSIT and DOPIEST are anagrams (aren’t you glad you know that), and OPTS, POTS, TOPS and STOP form an anagram class.
Your task is to write a program that takes two strings as input and determines whether or not they are anagrams; you may assume that the strings consist of only the letters A through Z in upper case. You must provide at least two different algorithms that work in fundamentally different ways. 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.
April 24, 2015
We have today another from our inexhaustible list of interview questions:
Given a list of positive integers, find the smallest number that cannot be calculated as the sum of the integers in the list. For instance, given the integers 4, 13, 2, 3 and 1, the smallest number that cannot be calculated as the sum of the integers in the list is 11.
Your task is to write a program that solves the interview question. 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.
April 21, 2015
Today’s exercise is a simple little interview question:
Generate the pairs of cartesian coordinates within a square bounded by (1,1) and (n,n) ordered by their product in ascending order. For instance, when n is 3, the coordinates are (1,1), (1,2), (2,1), (1,3), (3,1), (2,2), (2,3), (3,2) and (3,3). Can you find a solution with time complexity better than O(n2)?
Your task is to write a program to solve the interview question. 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.
April 17, 2015
Fermat’s Last Theorem, which dates to the seventeenth century states that there are no solutions in integers to the equation xn + yn = zn for n > 2; the Theorem was finally proved a few years ago by Andres Wiles. In the eighteenth century, Euler conjectured that for any n > 2, it would take at least n terms of the form xin to sum to an n th power. That conjecture held until the age of computers, in 1967, when Lander and Parkin found the counter-example 275 + 845 + 1105 + 1335 = 1445.
Your task is to write a program that finds counter-examples to Euler’s Conjecture. 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.
April 14, 2015
We studied mixed-radix arithmetic in a previous exercise. In today’s exercise we look at a different kind of non-standard positional notation: balanced ternary, which is a base-3 number system that uses -1, 0 and 1 as its “trits” rather than 0, 1 and 2. For instance, the number -47 is written as (-1 1 1 -1 1) in balanced ternary, which is equivalent to -34 + 33 + 32 – 31 + 30. No separate sign is needed when using balanced notation; the sign of the leading trit is the sign of the whole number.
Arithmetic on balanced ternary numbers is done using the grade-school algorithms. Addition is done right-to-left with a carry; it is easy and fun to work out the plus-table. Subtraction is done by adding the negative, which can be computed by changing the sign of every trit. Multiplication works trit-by-trit through the multiplier, shifting at each trit.
Your task is to write functions that perform arithmetic on balanced ternary integers. 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.
April 10, 2015
Today’s exercise won’t ask you to write code. Let me tell you why.
I bought a new printer to replace my old printer that had failed. Both the salesman at Micro Center and the printer manufacturer’s sales rep, who was in the store that day, assured me that the printer would work with my Debian Linux system, and the manufacturer’s sales rep even gave me the web page where I could download the driver. I bought the printer, took it home, and installed the driver.
It didn’t work. My computer would no longer boot. I took computer and printer to the Knowledge Bar at Micro Center, but they don’t have sufficient Linux experience to figure out what’s wrong. After a few days, I resigned myself to re-installing the operating system.
That’s when I found out what had happened. At the point where the Linux installer asks you to specify the partition table, it told me that I had an invalid partition table and asked me to fix it, manually, before proceeding with the installation. Somehow, installing a printer driver corrupted the partition table. I won’t tell you the name of the printer manufacturer that was stupid enough to manage that trick, but it’s a big name that you would certainly recognize. Needless to say, I will be returning the printer and buying a different printer from a different manufacturer.
But before I do that, I have to fix my partition table, re-install my operating system, and restore my data from backups. As I write this on Thursday afternoon, I’m partway through that process, but I have already verified that I have a list of all installed software and that my file backup is readable.
Your task is to make sure that your backup and restore procedures are effective; if they aren’t, fix them. You should at least perform a single-file restore to demonstrate that your backup and restore procedure has at least a minimal chance of working when you need it. It looks like I will end up okay, but not without a lot of worry and a few choice words directed at a printer manufacturer that ought to know better.