Programming Praxis

Children just learning the basic facts of arithmetic need repetitious drill to certify their knowledge, something that a computer does well. Toy stores purvey many brightly-colored plastic boxes that do the job, at a price. Today’s exercise asks you to do the same, minus the plastic box. Consider the following dialog, where the computer’s output is in roman and the child’s response is in italic:

4 + 4 = 8
Right!
8 + 3 = 12
Wrong, try again!
8 + 3 = 11
Right!
9 + 4 = 13
Right!
7 + 8 = ?
15
9 + 5 = 14
Right!
8 + 0 = ^Z
Goodbye!

After the drill program presents a problem, the child either enters his answer, asks for help by entering a question mark, or quits by entering an end-of-file. Correct answers are rewarded, incorrect answers cause the problem to be asked again.

Your task is to write a program that drills children on their addition facts. 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.

Pages: 1 2

Pierre de Fermat’s little theorem states that if p is prime, then for any integer a, a^p − a is evenly divisible by p, which is usually stated as a^p ≡ a (mod p); Fermat’s little theorem is often stated as the corollary a^p−1 ≡ 1 (mod p).

By turning it around, Fermat’s little theorem may be used as a primality test: if you can find an a for which a^p−1 ≢ 1 (mod p), then p is certainly composite; for instance, 2⁶² ≡ 4 (mod 63), so 63 is composite, and 2 is a witness to its compositeness. Thus Fermat’s primality test consists of choosing many numbers and checking if they are witnesses to the compositeness of the number being tested.

Unfortunately, there are some composite numbers which pass Fermat’s primality test for all possible witnesses; they are called Carmichael numbers, after Robert Carmichael, who studied them. Carmichael discovered in 1910 that 561 is a Fermat pseudo-prime to all possible bases.

One way to test that a number is a Carmichael number is to test all primes less than the number that are coprime to it. A faster test, due to Alwin Korselt, notes that Carmichael numbers are odd, composite, square-free (no factors appear more than once) and f−1 ∣ n−1 for all factors f of n.

Because there exist numbers that fool Fermat’s primality test for all bases, a strong pseudo-primality test is often used. A composite number n = d · 2^s + 1 with d odd is a strong pseudoprime to a relatively prime base a if and only if either a^d ≡ 1 (mod n) or a^d·2r ≡ −1 (mod n) for some 0 ≤ r ≤ s−1. For instance, 2³¹ ≡ 2 (mod 63), so 63 = 31 · 2¹ + 1 is composite, and 2 is a witness to that compositeness. The beauty of the strong pseudo-primality test is that it harbors no “Carmichael numbers;” every composite has at least one strong witness.

Your tasks are to write two functions that test if a number is a Fermat pseudo-prime or a strong pseudo-prime to a given base, two functions that test primality using the Fermat and strong pseudo-prime tests, and two functions that test if a number is a Carmichael number, and to identify all the Carmichael numbers less than 10,000. 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.

Pages: 1 2

Each year since 1955, Norad has tracked Santa Claus on his annual journey to deliver toys to good little girls and boys around the world. Since Santa must file his flight plan in advance, we already know where his journey will take him: the route at http://www.noradsanta.org/js/data.js is reproduced on the next page.

Your task is to calculate the number of miles that Santa will travel during his journey; you might find Wikipedia’s Great-circle distance page helpful. 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.

Pages: 1 2 3

Over at his blog, where he has been solving the exercises in SICP, Bill Cruise reached the section of the book that discusses interval arithmetic; if you want an introduction to the topic, you might want to look at http://www.cs.utep.edu/interval-comp/hayes.pdf.

Given an interval [x,y] with x the lower bound and y the upper bound, the basic operations of interval arithmetic are defined as follows:

• [a,b] + [c,d] = [a+c,b+d]
• [a,b] − [c,d] = [a−d,b−c]
• [a,b] × [c,d] = [min(ac,ad,bc,bd), max(ac,ad,bc,bd)]
• [a,b] ÷ [c,d] = [min(a/c,a/d,b/c,b/d), max(a/c,a/d,b/c,b/d)], where division by an interval containing zero is undefined

Your task is to write a basic library for interval arithmetic; you may do as many of the SICP exercises as you wish. 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.

Pages: 1 2

A number is polite if it can be written as the sum of two or more consecutive numbers; for instance, 7 is polite because it can be written at 3 + 4. Some numbers can be written as the sum of two or more consecutive numbers in more than one way; for instance, 15 = 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8. The number of ways that a number can be written as the sum of two or more consecutive numbers is its politeness. Any number that is a power of 2 cannot be written as the sum of two or more consecutive numbers; such a number has a politeness of 0, and is thus impolite.

There is a set of consecutive integers that sum to a given number for each odd divisor of the number greater than 1. For instance, the divisors of 28 are 1, 2, 4, 7, 14, 28. The only odd divisor of 28 greater than 1 is 7, so 28 has a politeness of 1. The set of consecutive integers has length 7 (the divisor) and is centered at 4 = 28 ÷ 7: 1 + 2 + 3 + 4 + 5 + 6 + 7; that works because there are 7 numbers with an average of 4 (since they are centered on 4). In some cases, such as the divisor 11 of the number 33, the set of numbers includes negative integers: -2 + -1 + 0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8; in that case, the negative integers cancel out the corresponding positive integers, so the remaining set is 3 + 4 + 5 + 6 + 7 + 8 = 33.

Your task is to write a program that calculates all the ways that a number can be written as the sum of two or more consecutive 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.

Pages: 1 2

In a previous exercise, we looked at the problem of finding the longest palindrome in a string. In today’s exercise, we look at a similar problem, finding the longest duplicated substring in a string.

The algorithm for this task is well known. First build a suffix list that has all the substring suffices of the input string. For instance, if the input is “banana”, the suffix list is “a”, “na”, “ana”, “nana”, “anana”, “banana”. Then sort the suffix list, bringing suffices with common beginnings together. Finally, scan the sorted suffix list, computing the common lengths of adjacent pairs, and report the longest.

Your task is to write a program to find the longest duplicated substring within a string. 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.

Pages: 1 2

In today’s exercise, we look at two programs that make random selections.

The first program picks an item from a list whose size is not known in advance, making a single pass through the list. The algorithm selects the first item in the list with probability ¹/₁, then replaces that item with the second item in the list with probability ¹/₂, then replaces whichever item is currently selected with the third item in the list with probability ¹/₃, and so on; when the end of the list is reached, each item will be selected with probability ¹/_n, where n is the number of items in the list. This algorithm is used in the unix fortune program, which randomly selects a line from a file of pithy sayings, and appears in the Standard Prelude under the name fortune.

The second program is used by auditors, pollsters, and others who need to randomly select m items from a population of n items. The program outputs a list of m numbers in the range 1 to n, in order; the user then selects the sampled items from a numbered list of the items in the population. The algorithm runs through the integers from 1 to n and selects each item with probability ^m/_n, where at each step m is the number remaining to be selected and n is the number remaining in the population.

Your task is to write the two programs 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.

Pages: 1 2

This puzzle is due to Jeffrey Ullman:

Given a list of n real numbers, a real number t, and an integer k, determine if there exists a k-element subset of the original list of n real numbers that is less than t.

For instance, given the list of 25 real numbers 18.1, 55.1, 91.2, 74.6, 73.0, 85.9, 73.9, 81.4, 87.1, 49.3, 88.8, 5.7, 26.3, 7.1, 58.2, 31.7, 5.8, 76.9, 16.5, 8.1, 48.3, 6.8, 92.4, 83.0, 19.6, t = 98.2 and k = 3, the 3-element subset 31.7, 16.5 and 19.6 sums to 67.8, which is less than 98.2, so the result is true.

This is a puzzle, so you’re not allowed to look at the suggested solution until you have your own solution.

Your task is to write a function that makes that determination. 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.

Pages: 1 2

We’ll categorize today’s exercise as part of our on-going series of interview questions, but it’s really more than that:

Given a sequence of integers, both positive and negative, find the contiguous subsequence with the maximum sum. For instance, given the sequence 31, -41, 59, 26, -53, 58, 97, -93, -23, 84, the maximum sum subsequence is 59, 26, -53, 58, 97, which sums to 187.

Your task is to write a series of functions that takes a sequence (use either a list or an array, whichever is convenient for your programming language) and returns the sum of the maximum sum subsequence; you should find solutions with time complexities of O(n³), O(n²), O(n log n), and O(n). 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.

Pages: 1 2