Write a function connected(a: array of array of boolean):
boolean that takes a 2-dimensional array of booleans
representing a maze, where the value true represents a
wall. The function should return true if the maze is connected, i.e.
every two empty squares in the maze are connected by some path.
Write a procedure that takes a 2-dimensional array of booleans representing a maze. The procedure should print out the maze, indicating the shortest path from the upper-left corner to the lower-right corner. For example, the output might look like this:
..###### #.# # #.# # # #...# # ## ....# ######..
If no such path exists, print the maze without any path.
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.
Is it still possible to move N disks from the left to the right peg in this case? If so, (a) write a procedure that reads an integer N and prints out a sequence of moves to perform this task; (b) determine the big-O running time of this procedure.
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 still possible to move N disks from the left to right peg (A to C) in this case? If so, (a) write a program that reads an integer N and prints out a sequence of moves to perform this task; (b) determine the big-O running time of this procedure.
Write a procedure combinations that takes two
integers N and K, and writes all K-element subsets of { 1 .. N }. For
example, combinations(4, 3) may write
1 2 3 1 2 4 1 3 4 2 3 4
A composition of a positive integer N is a sequence of positive integers whose sum is N. Two compositions that contain the same integers in a different order are distinct. For example, the compositions of 4 are
4 = 4 4 = 3 + 1 4 = 1 + 3 4 = 2 + 2 4 = 2 + 1 + 1 4 = 1 + 2 + 1 4 = 1 + 1 + 2 4 = 1 + 1 + 1 + 1
(a) How many compositions exist of any integer N?
(b) Write a procedure compositions that takes an
integer N and prints all its compositions in the format above.
A partition of a positive integer N is a set of positive integers whose sum is N. For example, the partitions of 4 are
4 = 4 4 = 3 + 1 4 = 2 + 2 4 = 2 + 1 + 1 4 = 1 + 1 + 1 +1
Write a procedure partitions that takes an integer N and
prints all its partitions in the format above.
Write a program that computes the sum of all prime numbers whose digits are permutations of the digits 1..9.
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
aba abc aca acb bab bac ...
Write a program that reads an integer N, and writes all permutations a1, …, aN of the integers {1, 2, … N } such that a1 < a2, a2 > a3, a3 < a4, a4 > a5 and so on.
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:
kola haha lala okok akah
Write a function that takes a graph and two vertices v and w, and returns the length of the longest path between v and w. (No efficient algorithm is known to compute this function, so you will need to enumerate all possible paths.)
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 a graph and an integer N, and
returns true if the graph has any clique of size N. (No efficient
algorithm is known to compute this function, so you will need to
enumerate all possible cliques.)
Two graphs G and H are isomorphic if there is a bijective function f between the vertex sets V(G) to V(H) such that two vertices v and w of G are adjacent if and only if f(v) and f(w) are adjacent in H. Write a function that takes two graphs and returns true if they are isomorphic. (No efficient algorithm is known to compute this function, so you will need to enumerate all possible isomorphisms.)