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. 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

4. 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. For example, if N = 4 then the program might print (in some order)

1 + 1 + 1 + 1

1 + 1 + 2

1 + 2 + 1

1 + 3

2 + 1 + 1

2 + 2
3 + 1

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. Partitions

A partition of a non-negative integer n is a sequence of positive integers that add up to n. Order does not matter: 1 + 3 and 3 + 1 are the same partition of 4.

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

1 + 1 + 1
2 + 1
3

7. 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.

8. Graph Coloring

Write a function that takes an undirected graph G in adjacency-list representation. The function should determine whether it is possible to color the graph with three colors (red, green, blue) such that no two adjacent vertices have a same color. If it is, it should print out a valid coloring.

9. Clique

A clique of a graph is a subgraph that is connected, i.e. in which there are edges between all pairs of vertices. Write a function clique that takes an undirected graph in adjacency-matrix representation and an integer N, and returns true if the graph has any clique of size N. (No efficient algorithm is known to solve this problem, so you will need to enumerate all possible cliques.)