Programming Praxis

In a previous exercise, we wrote a small library for maintaining binary search trees, including a function that traversed the tree in order. In today’s exercise we will write functions that traverse a tree in pre-order and post-order.

Given the tree shown at right, a pre-order traversal visits the node in this order: 8 3 1 6 4 7 10 14 13. At each level of the tree, pre-order traversal first handles the current node, then calls itself recursively on the left child, then calls itself recursively on the right child.

A post-order traversal visits the nodes in this order: 1 4 7 6 3 13 14 10 8. At each level of the tree, post-order traversal calls itself recursively on the left child, then calls itself recursively on the right child, then finally handles the current node.

In addition to traversing a tree in pre-order or post-order, you should write functions that reconstruct the original tree given a list of the tree nodes in pre-order or post-order.

Your task is to write the four functions 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

We have today another exercise from our limitless supply of interview questions:

You are given two arrays of integers, where the integers do not repeat, the two arrays have no common integers, and both arrays are sorted in ascending order.

Let x be any integer in the first array and y be any integer in the second array. Find min(abs(x − y)); i.e., find the smallest difference between any integers in the two arrays.

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

In the previous exercise we implemented some basic operations on functional-style linked lists; their distinguishing feature is that the pairs that make up the lists are immutable. In today’s exercise we will implement imperative-style linked lists in which the pairs that make up the lists are mutable.

Your task is to write the same library of functions — nil, isNil, pair, head, tail, nth, length, append, and reverse — for imperative-style mutable linked lists as you wrote in the previous exercise for functional-style immutable linked lists. 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 frequently use linked lists in our programs, but Scheme makes that easy because it provides linked lists as a native data type, along with a rich set of operations on them. In today’s exercise we will implement lists in the functional style that Scheme provides natively.

In Scheme, a list is really nothing more than an array with two slots, known as the car and cdr of a pair; a list with no elements is called the null list. We frequently think of lists as a sequence of elements, but in fact a list is no more than a chain of pairs, of which the cdr of each pair is another list, the chain terminating in a null list. Depending on the version of Scheme that you use, the car and cdr of the pair may or may not be mutable; traditionally, they have been mutable, but the most recent approved standard R6RS makes pairs immutable (that is controversial, and many implementations of Scheme ignore it and leave pairs mutable). Still, immutable pairs are more closely aligned with the spirit of functional languages, and your implementation today should provide immutable pairs.

Your task is to implement a small library of list operators; you should include at least nil and a predicate to recognize it, a procedure to build pairs and two procedures to extract the pieces of a pair, functions to extract the nth item of a list and to determine its length, and functions to reverse the elements of a list and append two lists; you are welcome to provide more operators if you wish. 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

In today’s exercise we will do somebody’s homework:

Read a file containing integers, one integer per line. At the end of the file, write the number of integers in the file, their sum, and the mean, median, mode, minimum and maximum of the integers in the file.

Your task is to write the indicated 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 studied Fibonacci numbers in a previous exercise. In today’s exercise, we will look at a generalization of Fibonacci numbers called Lucas numbers, which were studied by Edouard Lucas in the late 1800s.

Recall that each Fibonacci number is the sum of the two previous Fibonacci numbers, with the first two being 1 and 1; thus, the Fibonacci numbers begin 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …. The definition of the Lucas numbers is similar, but the first two Lucas numbers are 1 and 3; thus, the Lucas numbers begin 1, 3, 4, 7, 11, 18, 29, 47, 76, …, and they grow faster than the Fibonacci numbers.

Lucas went on to generalize the Fibonacci numbers even further. He define two sequences U_n(P, Q) and V_n(P, Q) as follows: Start with integer P and Q satisfying D = P² − 4Q > 0. Then, by the quadratic formula, the roots of x² − P x + Q = 0 are a = (P + sqrt(D)) / 2 and b = (P − sqrt(D)) / 2. Then U_n(p, q) = (aⁿ − aⁿ) / (a − b) and V_n(P, Q) = aⁿ + aⁿ.

Now the Fibonacci and Lucas numbers are just special cases of the U and V sequences: the Fibonacci numbers are U_n(1, -1) and the Lucas numbers are V_n(1, -1).

It is easy to compute a particularU or V sequence. The formulas are similar to the method of computing the Fibonacci sequence: U_m(P,Q) = P U_m−1(P,Q) − Q U_m−2(P,Q) and V_m(P,Q) = P V_m−1(P,Q) − Q V_m−2(P,Q).

It is also easy to calculate a particular U or V in the sequence using a chain that takes only logarithmic time based on the following identities: U_2n = U_n U_n, U_2n+1 = U_n+1 V_n − Qⁿ, V_2n = V_n² − 2 Qⁿ, and V_2n+1 = V_n+1 V_n − P Qⁿ.

You can see all of these formulas at MathWorld. Our interest in Lucas sequences isn’t merely academic; we’ll see an application of Lucas sequences in a future exercise.

Your task is to write programs that compute the U and V sequences and that compute any given element of either of the two sequences. 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 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