Week 5: Exercises

As always, these exercises are optional, but I recommend that you work through some of them, especially to get more practice with recursion.

1. Modified Tower of Hanoi

Suppose that we modify the Tower of Hanoi puzzle so that moves between the left peg to the right peg are disallowed: you may make moves only between the left and middle pegs, or between the middle and right pegs.

Write a program that reads an integer N and prints out the sequence of moves needed to solve this modified Tower of Hanoi, i.e. to move a tower of N disks from the left peg to the right peg.

2. Circular Hanoi

Consider another modified Hanoi in which moves are allowed only from A to B, from B to C and from C to A, where A, B and C are the left, midle and right pegs. Moves in the opposite direction (e.g. from B to A) are not allowed.

Is it always possible to move N disks from the left to right peg (A to C) even in this case? If so, write a program that prints out the sequence of moves.

3. Recursive Reverse

Write a recursive function reverse(s: string): string that reverses the string s. You may use string concatenation, but may not call any library functions or use any loops.

4. Recursive Palindrome

Write a recursive function that determines whether an array of integers is a palindrome. Do not use any loops.

5. Recursive Replacement

Write a recursive function

replaceChar(s: string, c: char, d: char): string

that returns a transformed string in which all occurrences of the character c have been replaced with the character d. Do not use any loops.

6. Trim Front And Back

Write a recursive function

trim(s: string): string

that returns a copy of s with all spaces removed from the front and end. Do not use any loops.

7. Ones and Zeros

Write a recursive function printBinary(n: integer) that prints out the binary representation of n.

8. Same As The First

Use recursion to write a function sameAsFirst(a: array of integer): integer that returns the number of integers in an array that are equal to its first element. You may use auxiliary functions, but do not use any loops.

9. Compositions

A composition of an integer N > 0 is a sequence of positive integers i ≤ N that add up to N, where different orders are considered to be distinct compositions. Write a program that reads an integer N and writes out all its compositions. For example, if N = 4, the output should be

3 + 1
2 + 2
2 + 1 + 1
1 + 3
1 + 2 + 1
1 + 1 + 2
1 + 1 + 1 + 1

10. Base 4

Write a program that reads an integer N ≥ 1 and prints all base 4 numbers that have N or fewer digits, in numeric order. Do not use the div or mod operators in your program. For example, if N is 3 then the output will be


11. Permutation Primes

Write a program that computes the sum of all prime numbers whose digits are permutations of the digits 1..9.

12. Word Subsets

Write a program that reads a word W and an integer N. Consider W to be a set of characters, and print out all subsets of W of length N. Write the characters in each subset in the same order in which they appear in W. For example, if W = ‘tram’ and N = 3, the output will be


13. ABC

Write a program which reads a number N and writes all strings of length N containing only the letters ‘a’, ‘b’ and ‘c’ and in which no adjacent characters are the same. Write the strings in alphabetical order. For example if N = 3 then the output is


14. Alternating Permutations

Write a program that reads an integer N, and writes the number of distinct permutations a1, …, aN of the integers {1, 2, … N } such that a1 < a2, a2 > a3, a3 < a4, a4 > a5 and so on. Note that the program should write the number of such permutations, not the permutations themeslves.

15. Aloha

Write a program that reads an integer N, and writes all N-letter words containing only the letters { a, o, h, k, l } in which consonants and vowels alternate. For example, if N = 4 then here are some of the words that will be printed:


16. Straight and Narrow

Write a function that for an integer N determines the number of distinct paths in the xy-plane such that

17. Back to the Beginning

Write a program that reads an integer N <= 15 and reports the number of distinct paths in the xy-plane of length ≤ N such that

18. Summit Search

Write a function summitSearch that takes an array of integers which is guaranteed to contain a strictly increasing sequence followed by a strictly decreasing sequence. For example, the array might contain these values:

3, 6, 12, 14, 18, 22, 19, 18, 15, 11, 8, 4, 3, 2, 1

The function should return the largest value in the array. It must run in time O(log n), where n is the length of the input array.

19. Highly Divisible Triangular Number

Solve Project Euler’s Problem 12.

20. Longest Collatz Sequence

Solve Project Euler’s Problem 14.