Programming Praxis

School children learning to spell English words are taught a series of rules. One of them is:

I before E except after C, or when sounded as AY as in NEIGHBOR and WEIGH.

Your task is to write a program that finds exceptions to that rule; you may want to look at the pronouncing dictionary at http://svn.code.sf.net/p/cmusphinx/code/trunk/cmudict/cmudict.0.6d. 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

In many voting systems, when there are more than two candidates and the rules require a majority of the votes to win, if no candidate receives a majority a runoff election is held between the two candidates who finished with the two highest vote totals. Some voting systems, instead of asking each voter to vote for a single candidate, instead ask voters to rank the candidates, which permits a runoff to be held instantly as follows: the votes are tallied, and a winner is declared if one of the candidates receives more than half the votes; otherwise, the candidate with the fewest votes is removed from all ballots and the votes are tallied again, the process repeating until some candidate has more than half the votes. This process is used in some political elections, and is often used in voting for awards such as the Hugo awards for science fiction writing and the Oscars for motion pictures.

Your task is to write a program that determines a winner in an instant-runoff voting system. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercises in the comments below.

Pages: 1 2

We have seen the SYSV and BSD checksum algorithms in previous exercises. In today’s exercise we look at another checksum algorithm developed by John Fletcher at Lawrence Livermore Labs in the late 1970s.

Fletcher’s original algorithm reads a file one byte at a time and computes a 16-bit checksum. Each byte is added to an accumulating sum, mod 255; to detect transposition errors, each accumulating sum is itself added to a second accumulating sum, mod 255. When the input is exhausted, the second sum is multiplied by 256 and added to the first sum, giving the checksum. Variants of Fletcher’s algorithm read a file two bytes at a time and compute a 32-bit checksum (the modulus is 65535), or read a file four bytes at a time and compute a 64-bit checksum (the modulus is 4294967295).

Your task is to write the three checksum 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

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2