## Ladder Range

### July 25, 2017

Once a year, or thereabouts, I pick up Jon Bentley’s book *Programming Pearls* and read a random chapter; even though I’ve read it before, re-reading always makes the material seem fresh. Today’s exercise is Exercise 7 from Chapter 4 about binary search:

A colleague faced the following problem in a program to draw lines on a bit-mapped display. An array of

npairs of reals (a,_{i}b) defined the_{i}nlinesy=m_{i}x+

b. The lines were ordered in the_{i}x-interval [0, 1] in the sense thaty<_{i}y_{i+1}for all values ofibetween 0 andn− 2 and all values ofxin [0, 1].[ Here Bentley has a picture of a ladder with rungs at various angles to the horizontal. We won’t reproduce it here; get the book if you want to see it. ]

Less formally, the lines don’t touch in the vertical slab. Given a point (

x,y), where 0 ≤x≤ 1, he wanted to determine the two lines that bracket the point. How could he solve the problem quickly?

Your task is to write a program to solve Bentley’s exercise. 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.

## Length Of A Cycle

### July 21, 2017

Our exercise today is about finding cycles in a linked list. We’ve seen algorithms due to Robert Floyd (the tortoise-and-hare algorithm) and Richard Brent (the power-of-two algorithm) in previous exercises, but in those cases all we were interested in doing was in finding a cycle if it existed. In today’s exercise we want to find the length of the cycle and the list item that begins the cycle (the list item that has two inward pointers).

Your task is to modify both Floyd’s and Brent’s algorithms to find the length and location of a cycle. 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.

## Most Common Item In A Binary Search Tree

### July 18, 2017

Today’s exercise is an interview question:

You are given a binary search tree in which all keys in the left child of a node are less than or equal to the key of the current node and all keys in the right child of a node are greater than or equal to the key of the current node. Find the most common key in the binary search tree. You may use O(

n) time and O(1) space.

Your task is to write a program to find the most common node in a binary search tree, subject to the given constraints. 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.

## Nuts And Bolts

### July 14, 2017

Today’s exercise is an interview question from Microsoft:

You are given two bags, one containing bolts and the other containing nuts, and you need to find the biggest bolt.. You may compare bolts to nuts, to see which is larger, but you may not compare bolts to bolts or nuts to nuts. Write a program to find the biggest bolt.

Your task is to write a program to find the biggest bolt. 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.

## My New Programming Environment

### July 11, 2017

I recently purchasd a Lenovo TAB2 A10 tablet computer (who thinks up these horrible names?) with 2GB RAM and a gorgeous 1920 × 1280 screen; the tablet has been on the market for about two years, so it’s no longer cutting edge, but the software is upt to date and the beautiful screen makes up for any deficiency. I bought it as a poor-man’s laptop, intending to carry it with me pretty much everywhere. I’m writing this exercise on my new tablet.

One of the programs I installed from the Google Play Store is GNUroot, which despite its name doesn’t root the tablet; it installs a Unix-like system within the sandbox of a normal Android application. It provides a console that looks like an ordinary Unix console. The sole user is `root`

, with no password; a VNC server is provided if you want to use a graphics screen. The root directory has the normal Unix file structure, with `/bin`

, `/usr`

, `/lib`

, `/var`

, `/etc`

, `/home`

and all the others, and all the normal Unix utilities are present, including `apt-get`

, which lets you install most of the GNU programs.

A simple `apt-get install guile-2.0`

gave me Guile, the GNU Scheme interpreter, which I’ve been playing with for the last few days. Guile is aggressively R5RS, with lots of extensions and libraries that are inconsistent with R6RS and R7RS; for instance, the module system is completely different. My first impression is good, even though the arguments to `(sort list-or-vector lt?)`

are in the wrong order, and I’ll be exploring the library for the next few days. My `.guile`

initialization file appears on the next page.

So there is no exercise today. You might wish to tell us about your computing environment or ask questions about GNUroot in the comments below.

## Random Number Test

### July 7, 2017

We’ve built several random number generators: [1], [2], [3], [4], [5], [6], [7], [8], [9] (I didn’t realize it was so many until I went back and looked). In today’s exercise we look at a way to test them. There are several well-known random-number testers, including Donald Knuth’s spectral test and George Marsaglia’s diehard test, but our test will be much simpler. Specifically, we test two things:

1) The numbers generated have an equal number of 0-bits and 1-bits.

2) The maximum run of consecutive 1-bits is consistent with probability theory.

Your task is to write a simple random number tester. 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.

## Prime Chains

### July 4, 2017

We studied word chains in a previous exercise; for instance, you can convert HEAD to TAIL by the word chain HEAD, HEAL, TEAL, TELL, TALL, TAIL in which each word differs from its predecessor by a single letter. Today’s exercise is similar, but asks you to find the chain from one prime number to another, with all intermediate numbers also prime, by changing one digit at a time; for instance, the chain 71549, 71569, 71069, 11069, 10069, 10067 converts 71549 to 10067.

Your task is to write a program to find prime chains. 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.

## Maximum Product Of Three, Revisited

### June 30, 2017

Today’s exercise is simply stated:

Write a program that finds the maximum product of three numbers in a given array of integers.

We studied that problem in a previous exercise, where unfortunately we got it wrong. Here is the suggested solution from that exercise:

(define (max-prod-three xs) (let ((len (length xs)) (xs (sort < xs))) (cond ((< len 3) (error 'max-prod-three "insufficient input")) ((= len 3) (apply * xs)) ((positive? (car xs)) (apply * (take 3 (reverse xs)))) ((negative? (last xs)) (apply * (take 3 (reverse xs)))) ((and (negative? (car xs)) (positive? (cadr xs))) (apply * (take 3 (reverse xs)))) ((and (negative? (cadr xs)) (negative? (caddr (reverse xs)))) (* (car xs) (cadr xs) (last xs))) ((and (negative? (cadr xs)) (positive? (caddr (reverse xs)))) (max (apply * (take 3 (reverse xs))) (* (car xs) (cadr xs) (last xs)))) (else (error 'max-prod-three "missed case")))))

Your task is to write a correct program that finds the maximum product of three numbers in a given array of integers; you might start by figuring out what is wrong with the previous 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.

## What Is S?

### June 27, 2017

We have something different today. Given this code:

int s = 0; for (int i=0; i<x; i++) for (int j=i+1; j<y; j++) for (int k=j+1; k<z; k++) s++;

What is *s*? What is a closed-form formula for computing *s*?

Your task is to compute *s*. 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.

## Leading Digits Of Powers Of 2

### June 23, 2017

John D. Cook, a programmer who writes about mathematics (he would probably describe himself as a mathematician who writes about programming) recently wrote about the distribution of the leading digits of the powers of 2, observing that they follow Benford’s Law, which we studied in a previous exercise.

Your task is to write a program that demonstrates that the distribution of the leading digits of the powers of 2 follows Benford’s Law. 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.