Programming Praxis

Our exercise today studies a famous problem solved by the great Swiss mathematician Leonhard Euler in 1735, which marked the beginning of what is now the “graph theory” branch of mathematics. Euler proved that it was impossible to cross all seven bridges once without retracing your path. He proved that a complete circuit, returning to the starting point, is possible only if all vertices connect to an even number of neighbors, and a complete path that doesn’t return to the starting point is possible if exactly two of the vertices have an odd number of neighbors, the rest being even, in which case the two odd-count vertices are the starting and ending points of the path.

The following algorithm to determine a eulerian path in a graph, if it exists, is ancient; I would be happy if anybody can provide a pointer to the source of the algorithm:

1) If a complete circuit is possible, choose any vertex at random as the current vertex. If a complete path but not a circuit is possible, choose either of the two odd-degree vertices at random. Otherwise, quit.

2a) If the current vertex has neighbors, add it to the stack, choose any of its neighbors as the new current vertex, and remove the edge between the two vertices.

2b) If the current vertex has no neighbors, add it to the path, remove the last vertex from the stack and make it the current vertex.

3) Repeat step 2 until the current vertex has no neighbors and the stack is empty.

4) Add the current vertex to the path and quit.

Your task is to write programs that determine if a graph is an eulerian circuit or eulerian path and, if it is, determine the 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

We discussed modular arithmetic in a previous exercise. In a comment on that exercise, Matthew asked what you can do when you have a fixed size integer datatype (say 64-bit unsigned integers) and a modulus that is close to the maximum. That’s a good question, which we will answer today. The answer is straight forward if the modulus is at least one bit less than the maximum, and rather trickier if it’s not. We’ll look at multiplication, but the other operations are all similar.

As long as the modulus is at least one bit less than the maximum, the solution is to split the numbers in low-bit and high-bit halves, then perform the arithmetic piecemeal, kind of like grade-school multiplication where you multiply by the one’s digit, then shift the sum and multiply by the ten’s digit, and so on, except that the “digits” are the size of the square root of the maximum number than can be represented in the integer datatype.

If m is within one bit of the maximum for the integer data type, things get messier; the basic answer is to split into three parts, compute the intermediate products, and recombine. But we won’t bother with that.

Your task is to write a function that performs modular multiplication without overflow. 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

Our exercise today is similar to the two previous exercises on the coin change problem, but doesn’t directly involve coins. But we’ll still call it a coin change problem because I can’t think of a better name.

As in the coin change problems, we are given a target to which a set of coins is intended to sum. But instead of a list of coins, we are given a number n and assume that we have one of each denomination of coin from 1 through n. Unlike the coin change problems, we have only one of each coin, not an infinite number of them.

The problem is to figure out all the ways to combine coins to reach the desired sum. For instance, if the sum s is 10 and n is 10, the ways to combine the coins are (10), (9 1), (8 2), (7 3), (7 2 1), (6 4), (6 3 1), (5 4 1), (5 3 2), and (4 3 2 1). Note that a set like (6 2 2) is not possible because only one 2-coin is available. As in the two previous exercises, we are interested in both a function to make a list of all the solutions and a separate function that simply counts them.

Your task is to write the two programs 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

In the previous exercise we studied the classic coin change problem to find all the ways to make a given amount of change using a given set of coins. Sometimes the problem in a different way: find the minimum set of coins needed to make a given amount of change. As with the prior exercise, sometimes the task is to find just the count and sometimes the task is to find the actual set of coins.

Your task is to write the two programs 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

It is a classic problem from computer science to determine the number of ways in which coins can be combined to form a particular target; as an example, there are 31 ways to form 40 cents from an unlimited supply of pennies (1 cent), nickels (5 cents), dimes (10 cents) and quarters (25 cents), ranging from the 3-coin set (5 10 25) to the 40-coin set consisting only of pennies.

The solution is usually stated in recursive form: if c is the first coin in the set of coins cs and n is the target, the solution is the number of ways to reach the target after removing c from cs plus the number of ways to reach n − c using all the coins in cs. The algorithm to make a list of the coins, instead of the count, is the same, but keeping track of the list of coins instead of the count.

Your task is to write two functions, one to determine the count and one to determine the list of coins. 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 comes from the book Making the Alphabet Dance: Recreational Wordplay by Ross Eckler, but I found it at http://www.math.cmu.edu/~bkell/alpha-order/:

Assume we have a list of all the words in the English language. Under the normal ordering of the alphabet in English (A, B, C, …, Z), some number of these words have all their letters in alphabetical order (for example, DEEP, FLUX, and CHIMPS). However, if we change the ordering of the alphabet, we will change the number of words having their letters in “alphabetical” order. What arrangement of the letters of the alphabet maximizes this number?

Your task is to write a program to find such an arrangement. 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

According to their masthead, the MindCipher website is “a social repository of the world’s greatest brain teasers, logic puzzles and mental challenges.” Some of the problems lend themselves to brute force computation, others are better solved with pencil-and-paper or solely with mental effort. We look at three MindCipher exercises today.

1: Coin Flip: On Monday, you flip a coin all day. You start flipping it until you see the pattern Head, Tail, Head. You record the number of flips required to reach this pattern, and start flipping again (and counting up from 1 again) until you see that pattern again, you record the second number, and start again. At the end of the day you average all of the numbers you’ve recorded. On Tuesday you do the EXACT same thing except you flip until you see the pattern Head, Tail, Tail.

Will Monday’s number be higher than Tuesday’s, equal to Tuesday’s, or lower than Tuesday’s?

2: 1978: The year 1978 is such that the sum of the first two digits and the latter two digits is equal to the middle two digits, i.e. 19 + 78 = 97. What is the next year (after 1978) for which this is true?

3: Sum of Two Prime Numbers: If p, q > 2 are consecutive in set of primes. Since p,q can only be odd number, (p+q) is an even number.

Can (p+q)/2 be prime?

Your task is to solve the three problems given above; write a computer program to help you 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

Today’s exercise provides three little exercises on linked lists, designed to help beginning programmers learn more about how lists work; there is also a special invitation for more experienced programmers.

1. Write a function that takes an input list and an interval n and returns a new list with all the elements of the original list, in order, except that every nth item has been removed. For instance, given the input list (1 2 3 4 5 6 7 8 9 10) and n = 4, the function should return the list (1 2 3 5 6 7 9 10).

2. Write a function that takes an input list and returns a new list with all the elements of the original list, in order, except that in the case of duplicate elements all of the duplicates except the first has been removed. For instance, all of the following lists should be transformed into the list (1 2 3 4 5): (1 2 3 4 5), (1 1 2 3 4 5), (1 2 1 3 1 4 1 5 1), and (1 2 2 3 3 3 4 4 4 4 5 5 5 5 5).

3. Write a function that takes an input list and splits the list in half; for instance, given the input list (1 2 3 4 5) the two outputs are the lists (1 2) and (3 4 5). If the list has odd length the middle element can be placed in either half, at your option, so the lists (1 2 3) and (4 5) are an alternate acceptable solution for the example problem.

Your task is to write the three indicated functions. If you find that to be too simple, write one or more exercises for your student friends. 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 teacher wants to create several sets of pairs of her students to work together on class projects; over the several sets, each student should be paired with each other student only once. For instance, with four students, there are three sets of pairings:

{Anne, Beth}, {Chet, Dirk}
{Anne, Chet}, {Beth, Dirk}
{Anne, Dirk}, {Beth, Chet}

Your task is to write a program that, given a list of students, produces a list of all possible sets of pairings, without duplicates. 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