## Modular Testing

### November 19, 2013

Today’s exercise is my reminder to myself to do a better job of testing. I was porting some prime-number code to Python, one of several preliminary steps to writing a new essay. I am comfortable enough with Python (mostly), and there is nothing particularly tricky about the code, so I wrote the code, tested it quickly, and went on. Later, a different part of the code was failing, and I couldn’t find the problem. Of course, the problem was in the earlier code that I had quickly tested, and therefore hard to spot, since I was looking in the wrong place. The failing code is shown below.

`def primes(n):`

ps, sieve = [], [True] * (n + 1)

for p in range(2, n + 1):

if sieve[p]:

ps.append(p)

for i in range(p * p, n + 1, p):

sieve[i] = False

return ps

`def isPrime(n):`

if n % 2 == 0:

return n == 2

d = 3

while d * d <= n:

if n % d == 0:

return False

d = d + 2

return True

`def inverse(x, m):`

a, b, u = 0, m, 1

while x > 0:

q = b // x

x, a, b, u = b % x, u, x, a - q * u

if b == 1: return a % m

raise ArithmeticError("must be coprime")

`def jacobi(a, p):`

a = a % p; t = 1

while a != 0:

while a % 2 == 0:

a = a / 2

if p % 8 in [3, 5]:

t = -t

a, p = p, a

if a % 4 == 3 and p % 4 == 3:

t = -t

a = a % p

return t if p == 1 else 0

`def modSqrt(a, p):`

a = a % p

if p % 4 == 3:

x = pow(a, (p+1)/4, p)

return x, p-x

if p % 8 == 5:

x = pow(a, (p+3)/8, p)

c = pow(x, 2, p)

if a != c:

x = (x * pow(2, (p-1)/4, p)) % p

return x, p-x

d = 2

while jacobi(d, p) != -1:

d += 1

t, s = p-1, 0

while t % 2 == 0:

t, s = t / 2, s + 1

at, dt, m = pow(a, t, p), pow(d, t, p), 0

for i in range(0, s):

if pow(at * pow(dt, m), pow(2, s-i-1), p) == p - 1:

m = m + pow(2, i)

x = (pow(dt, m) * pow(a, (t+1)/2, p)) % p

return x, p-x

Your task is to write a proper test suite, discover the bug in the code shown above, and fix it. 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.

## Twitter Puddle

### November 15, 2013

We have today an interview question from Twitter:

Consider the following picture:

In this picture we have walls of different heights. This picture is represented by an array of integers, where the value at each index is the height of the wall. The picture above is represented with an array as [2,5,1,2,3,4,7,7,6].

Now imagine it rains. How much water is going to be accumulated in puddles between walls?

We count volume in square blocks of 1X1. So in the picture above, everything to the left of index 1 spills out. Water to the right of index 7 also spills out. We are left with a puddle between 1 and 6 and the volume is 10.

Your task is to write a program to compute the volume of water in the puddle; you should strive for an algorithm that completes the task in a single pass. 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.

## Minimum Hamming Distance

### November 12, 2013

Every autumn, a month or two after the start of a new academic year, I receive a handful of emails from students who expect me to help them with their homework. I never respond. Some of the requests are polite — “Dear Kind Sir;” most of them are demanding — “It has to be in C# and cannot exceed 200 lines;” all of them have spelling and grammar mistakes. Today’s exercise is from an email that demanded a response by midnight (the writer didn’t say what time zone), but that was a few weeks ago, and the homework deadline is well past, and at least the question is entertaining.

The Hamming distance between two numbers is the number of bits that must be changed to make the bit representations of the two numbers equal. For instance, the number 79 is represented as 1001111 in binary, the number 83 is represented as 1010011 in binary, and the Hamming distance between them is 3, as the second, third and fourth bits (counting from the right, starting with zero) differ. The assignment was to read a list of numbers and find the two with the minimum Hamming distance between them.

Your task is to write somebody’s homework assignment, as described above — you must finish it before midnight! 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.

## Two Stacks Make A Queue

### November 8, 2013

In the previous exercise we used two queues to make a stack. In today’s exercise, we do the opposite: use two stacks to make a queue. This is exercise 10.1-6 from CLRS. In addition to solving the exercise, you should also create functions to implement a stack.

Show how to implement a queue using two stacks. Analyze the running time of the queue operations.

Your task is to write functions that use two stacks to implement a queue. 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.

## Two Queues Make A Stack

### November 5, 2013

In the previous exercise we implemented queues. Today’s exercise will use those queues to solve exercise 10.1-7 from CLRS:

Show how to implement a stack using two queues. Analyze the running time of the stack operations.

You may assume that the queue operations enqueue, dequeue, and isEmpty are provided. You should provide the stack operations push, pop and isEmpty.

Your task is to implement stacks using two queues, as directed above. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

## Queues

### November 1, 2013

One of the basic data structures in computer science is the *queue*, in which items are inserted into the data structure and retrieved in the order in which they were inserted; the standard operations on a queue are *enqueue*, *dequeue*, and *isEmpty*.

Your task is to write functions to implement a queue. 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.

## The 16 Game

### October 29, 2013

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.

## Pessimal Algorithms and Simplexity Analysis

### October 25, 2013

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

slowsortalgorithm is a perfect illustration of themultiply and surrenderparadigm, 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 ﬁrmer grasp of the multiply and surrender method, let us follow the step-by-step development of the

slowsortalgorithm. We can decompose the problem of sortingnnumbers A_{l}, A_{2}, …, A_{n}in ascending order into (1) ﬁnding the maximum of those numbers, and (2) sorting the remaining ones. Subproblem (1) can be further decomposed into (1.1) ﬁnd the maximum of the ﬁrst [n/2] elements, (1.2) ﬁnd the maximum of the remaining [n/2] elements, and (1.3) ﬁnd the largest of those two maxima. Finally, subproblems (1.1) and (1.2) can be solved by sorting the speciﬁed elements and taking the last element in the result. We have thus multiplied the original problem into three slightly simpler ones (sort the ﬁrst 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*^{log2(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.

## David Gries’ Coffee Can Problem

### October 22, 2013

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.

## Binary Tree Traversal

### October 18, 2013

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.