Programming Praxis

A local store has a promotional game in which scratch-off cards have sixteen spaces that cover a random permutation of the numbers 1 through 16. Customers scratch off the spaces at random. If the scratch-off reveals the number 3, the card loses. If the scratch-offs reveal the numbers 1 and 2, in either order, the card wins. Winning cards receive a discount on store merchandise.

Your task is to write a program that determines the average winning percentage. 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

I’ve been reading Pessimal Algorithms and Simplexity Analysis by Andrei Broder and Jorge Stolfi. It’s fun. They write three programs: search for an item in a sorted array, enumerate all items in a connected graph, and sort an array into ascending order; we’ll look at the sorting algorithm, but you may want to look at the others yourself. Here is their sorting algorithm:

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

To get a firmer grasp of the multiply and surrender method, let us follow the step-by-step development of the slowsort algorithm. We can decompose the problem of sorting n numbers A_l, A₂, …, A_n in ascending order into (1) finding the maximum of those numbers, and (2) sorting the remaining ones. Subproblem (1) can be further decomposed into (1.1) find the maximum of the first [n/2] elements, (1.2) find the maximum of the remaining [n/2] elements, and (1.3) find the largest of those two maxima. Finally, subproblems (1.1) and (1.2) can be solved by sorting the specified elements and taking the last element in the result. We have thus multiplied the original problem into three slightly simpler ones (sort the first half, sort the second half, sort all elements but one), plus some overhead processing. We continue doing this recursively until the lists have at most one element each, at which point we are forced to surrender.

I didn’t copy the code from the article; if you go look at it, beware the bug! The time complexity of the algorithm is O(n^log₂(n)/2).

Your task is to write the slowsort program; you may also want to write the research and bwfs programs mentioned in the article. When you are finished, you are welcome to read or run a suggested solution, or to post your solution or discuss the exercise in the comments below.

Pages: 1 2

David Gries described today’s exercise in his 1981 book The Science of Programming; I learned it from Jon Bentley’s 2000 book Programming Pearls, second edition.

You are initially given a coffee can that contains some black beans and some white beans and a large pile of “extra” black beans. You then repeat the following process until there is a single bean left in the can.

Randomly select two beans from the can. If they are the same color, throw them both out and insert an extra black bean. If they are different colors, return the white bean to the can and throw out the black.

Prove that the process terminates. What can you say about the color of the final remaining bean as a function of the numbers of black and white beans originally in the can?

Your task is to answer the two questions asked above, then write a program that simulates the coffee can problem. 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 wrote a small library for maintaining binary search trees, including a function that traversed the tree in order. In today’s exercise we will write functions that traverse a tree in pre-order and post-order.

Given the tree shown at right, a pre-order traversal visits the node in this order: 8 3 1 6 4 7 10 14 13. At each level of the tree, pre-order traversal first handles the current node, then calls itself recursively on the left child, then calls itself recursively on the right child.

A post-order traversal visits the nodes in this order: 1 4 7 6 3 13 14 10 8. At each level of the tree, post-order traversal calls itself recursively on the left child, then calls itself recursively on the right child, then finally handles the current node.

In addition to traversing a tree in pre-order or post-order, you should write functions that reconstruct the original tree given a list of the tree nodes in pre-order or post-order.

Your task is to write the four functions 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

We have today another exercise from our limitless supply of interview questions:

You are given two arrays of integers, where the integers do not repeat, the two arrays have no common integers, and both arrays are sorted in ascending order.

Let x be any integer in the first array and y be any integer in the second array. Find min(abs(x − y)); i.e., find the smallest difference between any integers in the two arrays.

Your task is to write a program to find the smallest difference. 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 the previous exercise we implemented some basic operations on functional-style linked lists; their distinguishing feature is that the pairs that make up the lists are immutable. In today’s exercise we will implement imperative-style linked lists in which the pairs that make up the lists are mutable.

Your task is to write the same library of functions — nil, isNil, pair, head, tail, nth, length, append, and reverse — for imperative-style mutable linked lists as you wrote in the previous exercise for functional-style immutable linked lists. 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 frequently use linked lists in our programs, but Scheme makes that easy because it provides linked lists as a native data type, along with a rich set of operations on them. In today’s exercise we will implement lists in the functional style that Scheme provides natively.

In Scheme, a list is really nothing more than an array with two slots, known as the car and cdr of a pair; a list with no elements is called the null list. We frequently think of lists as a sequence of elements, but in fact a list is no more than a chain of pairs, of which the cdr of each pair is another list, the chain terminating in a null list. Depending on the version of Scheme that you use, the car and cdr of the pair may or may not be mutable; traditionally, they have been mutable, but the most recent approved standard R6RS makes pairs immutable (that is controversial, and many implementations of Scheme ignore it and leave pairs mutable). Still, immutable pairs are more closely aligned with the spirit of functional languages, and your implementation today should provide immutable pairs.

Your task is to implement a small library of list operators; you should include at least nil and a predicate to recognize it, a procedure to build pairs and two procedures to extract the pieces of a pair, functions to extract the nth item of a list and to determine its length, and functions to reverse the elements of a list and append two lists; you are welcome to provide more operators if 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

In today’s exercise we will do somebody’s homework:

Read a file containing integers, one integer per line. At the end of the file, write the number of integers in the file, their sum, and the mean, median, mode, minimum and maximum of the integers in the file.

Your task is to write the indicated program. 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 studied Fibonacci numbers in a previous exercise. In today’s exercise, we will look at a generalization of Fibonacci numbers called Lucas numbers, which were studied by Edouard Lucas in the late 1800s.

Recall that each Fibonacci number is the sum of the two previous Fibonacci numbers, with the first two being 1 and 1; thus, the Fibonacci numbers begin 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …. The definition of the Lucas numbers is similar, but the first two Lucas numbers are 1 and 3; thus, the Lucas numbers begin 1, 3, 4, 7, 11, 18, 29, 47, 76, …, and they grow faster than the Fibonacci numbers.

Lucas went on to generalize the Fibonacci numbers even further. He define two sequences U_n(P, Q) and V_n(P, Q) as follows: Start with integer P and Q satisfying D = P² − 4Q > 0. Then, by the quadratic formula, the roots of x² − P x + Q = 0 are a = (P + sqrt(D)) / 2 and b = (P − sqrt(D)) / 2. Then U_n(p, q) = (aⁿ − aⁿ) / (a − b) and V_n(P, Q) = aⁿ + aⁿ.

Now the Fibonacci and Lucas numbers are just special cases of the U and V sequences: the Fibonacci numbers are U_n(1, -1) and the Lucas numbers are V_n(1, -1).

It is easy to compute a particularU or V sequence. The formulas are similar to the method of computing the Fibonacci sequence: U_m(P,Q) = P U_m−1(P,Q) − Q U_m−2(P,Q) and V_m(P,Q) = P V_m−1(P,Q) − Q V_m−2(P,Q).

It is also easy to calculate a particular U or V in the sequence using a chain that takes only logarithmic time based on the following identities: U_2n = U_n U_n, U_2n+1 = U_n+1 V_n − Qⁿ, V_2n = V_n² − 2 Qⁿ, and V_2n+1 = V_n+1 V_n − P Qⁿ.

You can see all of these formulas at MathWorld. Our interest in Lucas sequences isn’t merely academic; we’ll see an application of Lucas sequences in a future exercise.

Your task is to write programs that compute the U and V sequences and that compute any given element of either of the two sequences. 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