## BMI Calculator

### August 30, 2013

A person’s body mass index is a simple calculation based on height and weight that classifies the person as underweight, overweight, or normal. The formulas, for imperial and metric units, are:

BMI (imperial) = weight in pounds / (height in inches)

^{2}* 703

BMI (metric) = weight in kilograms / (height in meters)

^{2}

The usual categories are:

BMI <= 18.5: underweight

18.5 < BMI < 25: normal

25 <= BMI < 30: overweight

30 <= BMI < 40: obese

40 <= BMI: morbidly obese

For example, the BMI of a person who is 5′ 4″ and 125 pounds is 21.5 (normal) and the BMI of a person who is 190 centimeters and 95 kilograms is 26.3 (overweight).

Your task is to write a program that calculates the BMI and category given a person’s height and weight. 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 Sieving Problems

### August 27, 2013

We have today two exercises devoted to enumerating prime numbers:

1) How many prime numbers are there between 10

^{50}and 10^{50}+ 10^{6}?

2) How many prime numbers between 1,000,000 and 2,000,000 are congruent to 1 (mod 4)?

Your task is to write programs that answer the two questions given above; you might note the hint in the title of the 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.

## Three Interview Questions

### August 23, 2013

We have three simple interview questions today:

1) Verify that a binary tree is a binary search tree. In a binary search tree, all nodes to the left of the current node have values less than the value of the current node, all nodes to the right of the current node have values greater than the value of the current node, and those two rules hold for all nodes in the tree.

2) Remove duplicates from a list.

3) A girl counts on her fingers by counting 1 on her thumb, 2 on her index finger, 3 on her middle finge, 4 on her ring finger, and 5 on her pinkie. Then she continues the other way, counting 6 on her ring finger, 7 on her middle finger, 8 on her index finger, and 9 on her thumb. Then she continues the other other way, counting 10 on her index finger, 11 on her middle finger, 12 on her ring finger, and 13 on her pinkie. She continues in this way indefinitely. Write a program that, given

n, determines which finger she will be on when her count reachesn.

Your task is to write programs that solve the three interview questions given 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.

## More Bit Hacks

### August 20, 2013

We studied three bit hacks in a previous exercise. In today’s exercise we look at three more:

1) Compute the minimum (or maximum) of two integers without branching.

2) Determine if an integer is a power of two.

3) Swap the values of two variables without using any extra space.

Your task is to write bit hacks for the three tasks noted above; you may want to find multiple solutions for some of them. 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.

## Monkey Grid Puzzle

### August 16, 2013

I’m not sure of the original source of this fun little puzzle:

There is a monkey which can walk around on a planar grid. The monkey can move one space at a time left, right, up or down. That is, from (x, y) the monkey can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). Points where the sum of the digits of the absolute value of the x coordinate plus the sum of the digits of the absolute value of the y coordinate are lesser than or equal to 19 are accessible to the monkey. For example, the point (59, 79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 19. Another example: the point (-5, -7) is accessible because abs(-5) + abs(-7) = 5 + 7 = 12, which is less than 19. How many points can the monkey access if it starts at (0, 0), including (0, 0) itself?

Your task is to write a program that counts the number of available points. 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.

## Unix Paths

### August 13, 2013

[ Today’s exercise was written by guest author Robert Fisher. Having worked on shrinkwrapped consumer software, e-commerce web apps, embedded systems, and insurance OLTP systems, Robert currently writes C/C++ and Javascript for HP Tippingpoint and writes Scheme whenever he can. Suggestions for exercises are always welcome, or you may wish to contribute your own exercise; feel free to contact me if you are interested. ]

Under Unix, files are identified by paths. These are strings of directory names separated by slash characters followed by the name of the file. Paths starting with a slash are absolute, but paths that don’t start with a slash are relative to the current directory. Relative paths may include “..” elements. These represent a parent directory. Likewise, “../..” would represent a grandparent directory. For example, if the current directory is “/home/bob” then “praxis/prelude.scm” represents the file “/home/bob/praxis/prelude.scm” and “../tom/bin/scheme” represents “/home/tom/bin/scheme”.

Your task is to write a function that takes the current directory path and a target path and returns an absolute and minimal path equivalent to the target path. 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.

## Bit Hacks

### August 9, 2013

A time-honored tradition among programmers is to hack a program to reduce the number of operations it takes, and a major component of that effort goes in to bit hacks, which we can define as dealing with data structures smaller than a single byte. Embedded systems programmers use bit hacks all of the time, as do game programmers and many others. We have three tasks today:

1) Determine the sign of an integer.

2) Determine if two integers have the same sign.

3) Determine the absolute value of an integer without branching.

Your task is to write bit hacks for the three tasks noted above; you may want to find multiple solutions for some of them. 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.

## Sophie Germain Primes

### August 6, 2013

A prime number *p* is a Sophie Germain prime if 2*p*+1 is also prime. The list of Sophie Germain primes begins 2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, (A005384); it is not known if the list is infinite. Sophie Germain primes are named after the French mathematician Marie-Sophie Germain, who in 1825 proved Fermat’s last theorem for such primes; thus, if *p* is a Sophie Germain prime, then there do not exist integers *x*, *y* and *z* not equal to zero and not a multiple of *p* such that *x ^{p}* +

*y*=

^{p}*z*.

^{p}One way to find Sophie Germain primes is to enumerate the primes *p* and check the primality of each 2*p*+1. That works fine for relatively small *p*. For larger *p*, amateur mathematician Harvey Dubner developed a sieve that speeds finding Sophie Germain primes:

Define the three polynomials

f(_{p}c) =c* 3003 * 10^{b}– 1,f(_{q}c) = 2f(_{p}c) + 1, andf(_{r}c) = (f(_{p}c) – 1) / 2. Choosebwhich is the approximate number of digits for the range of Sophie Germain primes you are searching.

Sieve each of the polynomials over the range 1 ≤

c≤mfor some suitablem. Use as sieving primes the primes greater than 13 but less than some suitablefwhich is conveniently large but much less than the square root off(1). All three polynomials are sieved over the same sieving array. Sieving is done in a similar manner to sieving the polynomials in the multiple polynomial quadratic sieve._{p}

After sieving is complete, apply a primality test to each

f(_{p}c) that survived all three sievings. If it is prime, check bothf(_{q}c) andf(_{r}c) for primality. Iff(_{q}c) is prime, thenf(_{p}c) is a Sophie Germain prime. Iff(_{r}c), thenf(_{r}c) is a Sophie Germain prime.

Your task is to write a sieve that finds Sophie Germain primes as 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.

## Ordered Hash Tables

### August 2, 2013

In a normal hash table, a key is hashed then linear search is performed in the bucket where the key will be found if it exists in the hash table. A successful search terminates as soon as the key is found, on average half-way through the bucket, but an unsuccessful search requires that every item in the bucket be examined.

Donald Knuth proposed that instead of keeping keys in a bucket in random order they be kept in increasing order, so that a search can stop as soon as the search passes the value of the key. That means inserts take longer; you have to find the right place in the bucket to put the key instead of just putting it at the beginning of the bucket. But lookups are quicker, as an unsuccessful search can terminate half-way through the bucket, on average. This change also means that the data type of the hash table changes, as now the comparison function is less-than rather than equal-to.

Your task is to write a small library of ordered hash tables; you should provide lookup, insert and delete functions, at least. 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.