Programming Praxis

I’ve recently rekindled my interest in sorting algorithms (it’s a fascination that never really goes away), and I’ve been looking at quick sort. The most common academic version of quick sort uses a partition due to Nick Lomuto, which takes a single pointer that scans through the arry, concludes with the partitioning element in the middle, all the less-than items to its left, and all the greater-than items to its right, then recurs on the two halves; the partitioning element is never part of any subsequent recursive call in the quick sort.

The original partitioning algorithm by C. A. R. Hoare works differently, with two pointers instead of one. One pointer starts at the left end of the array, and is advanced until it finds an item out of place. The other pointer starts at the right end of the array, and marches to the left end of the array until it finds an item out of place. Then the array items are swapped, each pointer takes one step toward the other, and the process continues, stopping when the two pointers cross, at which time there is a final swap. Hoare’s partition concludes by returning the right-side pointer; all items to the left of the pointer, plus the item at the pointer itself, are smaller than all items to the right of the pointer. The partitioning element is somewhere in the left-hand partition, but not necessarily at its end, which requires a change to the recursive call in the quick sort algorithm, which includes the partitioning element.

Your task is to implement Hoare’s partition and use it to write a quick sort 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

It was a gorgeous autumn weekend: brisk mornings, warm sunny afternoons, and absolutely no reason to sit at a computer screen indoors. And even though the programming on my big project at work is finished, there are still details to be looked after, so I had no time there, either. Thus, another recycled exercise today, another one that I’ve seen on the beginning-programmer message boards recently:

Write a program that determines the prime factors of a number n.

You should write at the level of a first-year programmer, nothing sophisticated. An appropriate algorithm is trial division.

Your task is to write a program to factor integers. 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 haven’t had time to prepare a new exercise because I’ve been busy finishing up a big project at work. So the bad news is we have a repeat exercise, but the good news is that my project is done! ]

We have today an exercise that has appeared on message boards at least a dozen times in the last few weeks; it must be that time in the semester when beginning programming students are working on their mid-term homework assignments.

Write a program that, given an integer, determines whether or not it is prime.

Your task is to write a program that determines if a given integer is prime, in the style of a beginning programmer who is less than confident of his knowledge of variable assignment and loops; do not use a complicated algorithm. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Today’s exercise is an interview question from Amazon:

You are to write a program that reads a stream of characters from the input and returns a random character from the stream. Any character should have an equal probability of being returned. You may only use a single character of storage space; in particular, you may not save multiple characters from the input stream.

Your task is to write a program that solves the Amazon interview task. 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 three more list-manipulation exercises today, for those students midway through their beginning programming course who need practice with linked lists:

1. Define a function that takes two lists, the second of which is a list of non-negative integers the same length as the first list, and returns a list of elements from the first list, in reverse order, each repeated a number of times as specified by the corresponding element of the second list.
2. Rearrange the integers in a list so that all the odd numbers appear before all the even numbers, with both odd and even numbers in the same relative order in the output as they were in the input.
3. Write a function that returns the nth item from the end of a list.

Your task is to write the three specified programs. 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 must be approaching the middle of the autumn academic term, because the beginning-programmer message boards are starting to fill up with linked-list exercises; one enterprising fellow even sent me an email asking for help on his homework. Here are three tasks that involve manipulating linked lists. We’ve probably done all three before, and they’re simple enough for many of the people that read and respond here, but learners seem to have trouble with them, so we’ll discuss them here:

1. Write a function that takes a linked list of integers and returns a new linked list with all the odd integers removed.
2. Write a function that removes every nth item from a linked list.
3. Write a function that reverses the two halves of a list; if the number of items in the list is odd, the middle element should go with the second half of the list

Your task is to write the three 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 continue our occasional series of textbook exercises:

You are given a bunch of sticks, each of integer length. Two sticks can be combined into a single, larger stick by a process that costs the sum of the lengths of the two sticks. Your goal is to build a single stick combining all the original sticks, at minimal cost.

For example, suppose you initially have three sticks of lengths 1, 2, and 4. You could combine sticks 2 and 4 at a cost of 6, then combine that stick with stick 1 at a cost of 7, for a total cost of 13. But it is better to first combine sticks 1 and 2 at a cost of 3, then combine that stick with stick 4 at a cost of 7, for a total cost of 10.

Your task is to write a program that combines a bunch of sticks at minimal cost. 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

Matthew Arcus pointed out a bug in my solution to the previous problem:

> (dollar 1234567.9999)
$1,234,567.100

I can’t remember a similarly bad bug in any previous Programming Praxis problem.

You get the day off today. There is no exercise for you to do. You are welcome to read or run my corrected solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2