Programming Praxis

We have seen priority queues on several different occasions in the past, including this implementation using imperative heaps; such priority queues allow items to be inserted in any order and retrieved in order of priority. In today’s exercise we will look at a similar data structure called an interval heap that permits access at both ends, to either the minimum or maximum item in the heap. The permitted operations are:

isEmpty — is the priority queue empty?
insert item — insert a new item in the priority queue
getMin — get the smallest item in the priority queue
getMax — get the largest item in the priority queue
deleteMin — delete the smallest item from the priority queue
deleteMax — delete the margest item from the priority queue

Operation of an interval heap is similar to operation of an imperative heap, with a tree embedded in an array and the children if the ith node at 2i and 2i+1, except that each array element stores two items instead of one; all children of the array element are greater than or equal to the “lo” item of the array element and less than or equal to the “hi” item of the array element, at every node of the tree. The lo items from each element form a min-heap, in which each item is less than its children, and the hi items from each element form a max-heap, in which each item is greater than its children. New items are inserted at the end of the tree; if the new item is less then the lo item in the last element, it is sifted up to its proper position in the min-heap of lo items, if the new item is greater than the hi item in the last element, it is sifted up to its proper position in the max-heap of hi items, otherwise the new item is in its proper position. The minimum or maximum item in the interval heap can be deleted by removing it, replacing it with the corresponding minimum or maximum item from the last array element of the heap, then sifting down through the corresponding min-heap or max-heap.

Your task is to write functions that implement a double-ended priority queue using an interval heap 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 told you in a previous exercise that I was having internet connectivity issues at home. It took three weeks, but a repairman from the local telephone company finally found that, during repairs on the soffit underneath my roof overhang, the roofer nailed through a board with a nail that was too long, so it penetrated the board and the telephone cable that was nailed to the other side of the board. As the temperature and humidity changed during the day, sometimes the nail made contact with two ends of the same conductor, and everything worked properly, but sometimes the nail made contact with two different conductors, causing a short circuit and preventing the telephone from working. At the same time, my wifi router developed some kind of internal problem, also intermittent. I have now replaced both the wire and the router and everything seems to be working. The problems were hard to solve because both of them were intermittent. ]

Today’s problem comes from one or another of the competitive programming sites, I’m not sure which:

Search every power of two below 2¹⁰⁰⁰⁰ and return the index of the first power of two in which a target string appears. For instance, if the target is 42, the correct answer is 19 because 2¹⁹ = 524288, in which the target 42 appears as the third and fourth digits, and no smaller power of two contains the string 42.

Your task is to write the search program 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

John McCarthy’s 91 function is a recursive function designed as a test case for formal verification of computer programs. It is defined as follows:

M(n) = n - 10,     if n > 100
     = M(M(n+11)), if n <= 100

For instance, when n = 87:

M(87)
M(M(98))
M(M(M(109)))
M(M(99))
M(M(M(110)))
M(M(100))
M(M(M(111)))
M(M(101))
M(91)
M(M(102))
M(92)
M(M(103))
M(93)
M(M(104))
M(94)
M(M(105))
M(95)
M(M(106))
M(96)
M(M(107))
M(97)
M(M(108))
M(98)
M(M(109))
M(99)
M(M(110))
M(100)
M(M(111))
M(101)
91

Your task is to write a program that shows the call history of a call to the 91 function in a manner similar to that shown for M(87) 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 found this problem on a discussion board for beginning programmers. It feels like a Project Euler problem, but I looked and didn’t find it there:

The smallest pair of consecutive natural numbers that each have two distinct prime factors are 14 = 2 * 7 and 15 = 3 * 5. The smallest triplet of consecutive natural numbers that each have three distinct prime factors are 644 = 2^2 * 7 * 23, 645 = 3 * 5 * 43 and 646 = 2 * 17 * 19. What is the smallest set of four consecutive natural numbers that each have four distinct prime factors?

Your task is to write a program that finds the set of four natural 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

[ 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