Programming Praxis

[ I apologize for not posting an exercise on Tuesday. I have had intermittent internet access at home since last week that has prevented me from working on the blog. And now I published it immediately instead of scheduling it for Friday morning. Oh my! ]

Diffie-Hellman key exchange is a method for two people, traditionally named Alice and Bob, to agree on a secret key known only to the two of them using an insecure communications channel; Wikipedia gives an explanation, complete with a cheesy diagram.

The key exchange begins when Alice and Bob agree on parameters p, which should be at least a few hundred decimal digits in a real-life application, and g, which is typically small, say 2 or 3 or 5; we will follow Wikipedia’s illustration and choose p = 23 and g = 5. Then Alice chooses a secret number a, computes g^a (mod p), and sends it to Bob; in a real application, a will be of similar magnitude to p, but for illustration we choose a = 6, so Alice sends the number 5⁶ (mod 23) = 8 to Bob. Bob follows the same procedure, choosing b, computing g^b (mod p), and sending it to Alice; in a real application, b will be of similar magnitude to p, but for illustration we choose b = 15, so Bob sends the number 5¹⁵ (mod 23) = 19 to Alice. All of these exchanges can be conducted over an insecure channel, as long as Alice keeps a secret and Bob keeps b secret.

Once those exchanges have been made, Alice and Bob can both compute the same secret key s; Alice computes s = 19⁶ (mod 23) = 2, using Bob’s public number 19 and her secret number a = 6, and Bob computes s = 8¹⁵ (mod 23) = 2, using Alice’s public number 8 and his secret number b = 15. At this point, both a and b can be discarded. Using the shared secret number s = 2 as a key, Alice and Bob can encrypt and decrypt messages using any symmetric cipher, such as DES or AES, and send encrypted messages over insecure channels, confident that no one else knows their secret key. In practice, p is generally taken to be 2q+1, where q is a Sophie Germain prime of at least 512 bits, and g is generally taken to be a primitive root modulo p; these rules guarantee some desirable properties of the security of the secret key. The only way for someone with knowledge of g, p, g^a (mod p) and g^b (mod p) to determine the secret key s is to solve for a and b, but that involves computing the discreet logarithm and is intractable with current algorithms.

Your task is to write programs that perform Diffie-Hellman key exchange 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.

Pages: 1 2

Today’s exercise is another interview question from our unending supply of interview questions. Beware that it’s a tough one:

Write a function that takes a variable number of lists and returns the cartesian product (sometimes called the cross product) of the items in the lists. For instance, the cartesian product of the lists (1 2 3), (4) and (5 6) is the list of lists ((1 4 5) (1 4 6) (2 4 5) (2 4 6) (3 4 5) (3 4 6)). You should provide both recursive and iterative versions of your function.

Your task is to write the cartesian product function 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.

Pages: 1 2

I don’t like these bit hack exercises — my brain doesn’t seem to be wired that way — but I can tell from my statistics that lots of people do like them, so here’s another.

1. Compute the parity of a word, 1 if an odd number of bits is set, 0 if an even number of bits is set.

2. Reverse the bits in a word or byte.

3. Find the integer logarithm, base 2, of an integer data type.

Your task is to write programs to solve the three problems 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.

Pages: 1 2

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)² * 703

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

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.

Pages: 1 2

We have today two exercises devoted to enumerating prime numbers:

1) How many prime numbers are there between 10⁵⁰ and 10⁵⁰ + 10⁶?

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.

Pages: 1 2 3

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 reaches n.

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.

Pages: 1 2

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.

Pages: 1 2

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.

Pages: 1 2

[ 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.

Pages: 1 2

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.

Pages: 1 2