Programming Praxis

We have studied hash tables in several previous exercises, most of them of the “chaining” variety, where collisions are resolved by inserting each item in a linked list in the bucket to which it hashes. Today’s exercise looks at two different varieties of hash tables that use “open addressing,” in which all keys are stored in the buckets themselves, one key per bucket, with collisions resolved by moving them to a different bucket. We studied one type of open addressing in the exercise on cuckoo hashing, today we will see two others: linear probing and double hashing. Our hash tables consist of M memory addresses that hold N keys (or key/value pairs). Obviously, N must be less than M, and the load factor N M is critical to the performance of the algorithm; if the table becomes too loaded, search times increase dramatically. Open address hash tables work best when N can be predicted with some reliability, so an appropriate M can be chosen.

The linear probing algorithm hashes the key onto the range 0 .. M−1 and looks first in the indicated bucket. If the key is there, it is returned. If the bucket is empty, the key is not present in the table. If the bucket is non-empty, but the key doesn’t match, the search goes to the next bucket in order, wrapping around at the end of the table. Double hashing is similar, except that a second hash function determines the increment between probes. When double hashing, we must arrange that the increment is non-zero (otherwise the search will never visit any bucket except the first) and is co-prime to M (otherwise some buckets will never be visited), which is most easily arranged by making M prime.

Deletions require some care. We can’t just mark a bucket available when its key is deleted, because subsequent searches will miss keys that are beyond the newly-empty bucket. Instead, we mark the bucket with a special value showing that it is deleted, and consider that bucket to be non-empty but with a key that never matches.

Your task is to implement hash tables using linear probing and double hashing. 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 comes from Stack Overflow:

Given a text file like:

word1 word2 word3 word4
word4 word5 word6 word7
word6 word7 word8 word9
word9 word6 word8 word3
word1 word4 word5 word4

Write a program that returns those lines that have n words in common with the previous line. For instance, given the input above, the only output line would be:

word9 word6 word8 word3

The original question requested a solution in sed or awk, but you are free to use any language.

Your task is to write a program to extract lines from a text file that have n words in common with the previous line. 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 another exercise today based on a Numberphile video:

A perfect number is a number n that is equal to the sum of its divisors, excluding itself; in other words, a perfect number n satisfies the equation σn = 2n, where σ is the divisor-sum function. A triperfect number is a number n such that σn = 3n. It is believed that there are six, and only six, triperfect numbers.

Your task is to compute the six triperfect 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

Today’s exercise was inspired by a task at Rosetta Code:

An integer n > 1 is a k-almost-prime if it is the product of k primes. Further, a k-almost prime is squarefree if all k primes are distinct.

You can learn more about k-almost-primes and their uses in number theory at Wikipedia or MathWorld.

Your task is to write programs that calculate the first ten k-almost-primes and squarefree k-almost-primes for 1 ≤ k ≤ 5. 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

Over at NumberPhile, Dr Grimes (can you look at him and not smile?) discusses the pattern in the last digits of successive prime numbers. It’s not what you think.

Your task is to write a program that mimics the calculations made by Dr Grimes. 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

Here are three simple math problems. They are intended to be solved analytically, with number theory, without using a computer or a calculator. But I cheated. All three problems come from the YouTube channel Mind Your Decisions, where you will find lots of similar problems.

1. Solve for x and y where both are integers: 615 + x² = 2^y
2. Find a three-digit number abc = 100a + 10b + c with none of the digits 0 such that abc = a! + b! + c!
3. Find a three-digit number pie = 100p + 10i + e with none of the digits 0 such that √pi + e = √ pie

Your task is to solve the three problems; you can write programs to solve them, if you wish, but it is fun to solve them by hand. When you are finished, you are welcome to or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Regular readers of this blog know that. in my day job, I frequently process input files from vendors; almost always, they were created in Excel and arrive in CSV format. Sometimes I have to peek inside the files, looking for invalid data, and I have commonly used grep for that task. Sometimes grep gives me unwanted records, because there is a match in some field that is not the field of interested, and I just ignore the extra records. But the other day I had a mess, with lots of unwanted records, so I used awk to parse out the fields and find the records of interest.

I realized as I was performing that task that it would be useful to have a version of grep that understood the CSV file format. So I wrote grep-csv that takes a field number (counting from 1, like awk) and a regular expression and returns the matching rows of a CSV file.

Your task is to write a grep-csv 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 implemented Chris Okasaki’s physicist’s queues in the previous exercise. As I implemented them in Scheme, I struggled to maintain Okasaki’s clear, consise coding style, which relies heavily on pattern matching. There are several pattern-matching libraries available for Scheme, but they are rather heavy (the one I use, by Friedman, Hilsdale and Dybvig, is over six hundred lines of code). Our Standard Prelude has a simple pattern matcher, but it doesn’t fit properly with a simple binding. I finally came up with a strange method using let-values ... apply values that makes the code concise at the cost of forcing readers to think through an uncommon idiom. What I wanted was something similar to the destructuring-bind macro of Common Lisp.

So I wrote one.

Your task is to write a macro similar to the destructuring-bind macro of Common Lisp and add it to your favorite programming language. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.

Pages: 1 2

One of my favorite programming textbooks is Chris Okasaki’s Purely Functional Data Structures, which I pick up and re-read every year or so. Today’s exercise asks you to
implement Okasaki’s physicist’s queues, which you can read about in either his book (Figure 6.3 on page 73) or his thesis (Figure 3.4 on page 31). Queues provide two constructors empty and snoc, two accessors head and tail, and a single predicate isEmpty; it is an error if either head or tail are applied to an empty queue. This version comes from the book:

structure PhysicistsQueue : QUEUE
struct
    type alpha Queue = α list × int × α list susp × int × α list

    val empty = ([], 0, $[], 0, [])
    fun isEmpty (_, lenf, _, _, _) = (lenf = 0)

    fun checkw ([], lenf, f, lenr, r) = (force f, lenf, f, lenr, r)
      | checkw q = q
    fun check (q as (w, lenf, f, lenr, r)) =
        if lenr < lenf then checkw q
        else let val f' = force f
             in  checkw (f', lenf + lenr, $(f' @ rev r), 0, []) end

    fun snoc ((w, lenf, f, lenr, r), x) =
        check (w, lenf, f, lenr + 1, x :: r)

    fun head ([], lenf, f, lenr, r) = raise EMPTY
      | head (x :: w, lenf, f, lenr, r) = x
    fun tail ([], lenf, f, lenr, r) = raise EMPTY
      | tail (x :: w, lenf, f, lenr, r) =
            check (w, lenf - 1, $tl (force f), lenr, r)
end

Your task is to implement Okasaki’s physicists queues. 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