Week 7: Exercises

1. Subsets, Revisited

In the lecture we wrote a function that prints all subsets of {1, ..., N} using a prefix parameter. Rewrite this function using any of the other 3 techniques that we used for solving the abc problem.

2. Permutations

Write a function void permutations(string s) that prints all permutations of a string. For example, permutations("cat") might print

cat
cta
act
atc
tca
tac

3. Permutations, Bottom Up

Write a function IEnumerable<string> permutations(string s) that returns a sequence of all permutations of a string. Use a recursive iterator function that yields the solutions.

4. Combinations

Write a function void combinations(int[] a, int k) that takes an array a and an integer k, and prints all combinations of k elements of a. For example, the call

int[] a = { 2, 4, 6, 8, 10};
combinations(a, 3);

might produce this output:

2 4 6
2 4 8
2 4 10
2 6 8
2 6 10
2 8 10
4 6 8
4 6 10
4 8 10
6 8 10

5. Compositions

A composition of a non-negative integer n is a sequence of positive integers that add up to N. Order matters: 1 + 3 and 3 + 1 are different compositions of 4.

a) Write a function compositions(n) that prints all compositions of an integer n. For example, compositions(3) will print (in some order):

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

b) Find an algebraic formula that expresses how many compositions of any integer N exist, as a function of N.

6. Even Values

Write a function IEnumerable<int> only_even(IEnumerable<int> seq) that takes a sequence seq of integers and returns another sequence containing only the even integers from seq.

7. Climbing Stairs

A student is walking up a staircase that contains N stairs. On each step, the student may walk up either 1, 2, or 3 stairs. Write a program that reads N and prints out all possible ways that exist to climb the stairs in this fashion.

8. N Queens Experiment

Using the N queens function from the lecture notes, write a C# program that measures how many milliseconds it takes to find a solution to the problem for all values of N in the range from 4 to 26. Write this timing information to a file, and then graph it using Python and matplotlib.

9. Mini-Sudoku

A mini-Sudoku puzzle looks like this:

To solve the puzzle, you must place a number from 1 to 4 in every square so that the numbers in every row, column, and mini-square are distinct.

Write a method that reads a mini-Sudoku puzzle from standard input. Empty squares will be represented by the number 0:

3040
0103
2300
1002

The method should print out a solution to the puzzle if it can find one, otherwise null.