1. Devise an algorithm to generate all possible permutations of a word (that is all possible orderings of the characters making up a word). For example, given the word "the" your algorithm would generate "teh", "hte", "het", "eht", "eth" and "the" (in any order).
2. Consider two rectangles drawn on a grid (like the drawing program in the programming exercises), so the (x,y) coordinate of each corner is known. Devise a function (that is a mathematical algorithm) to determine whether the two rectangles overlap. Take into account all the different ways two rectangles can overlap.
3. During the night four travellers come to an ancient bridge over a bottomless chasm. The bridge can hold the weight of only two travellers at time, otherwise it will collapse. In addition, due to the state of the bridge, a torch is needed to light the way and avoid the holes.
The travellers need to cross the bridge but only have one torch between them. They also walk at different speeds, so the first traveller can cross in one minute, the second in two minutes, the third in five minutes and the forth in ten minutes. If two travellers cross together they have to travel at the speed of the slowest traveller.
What is the shortest time in which all the travellers can cross to the other side of the bridge?
4. Develop the algorithms to display the following patterns of characters. Note that a pattern must be displayed from left to right, line by line, one character at a time (also see programming exercises 2 questions). The algorithms should make use of loops to display repeated patterns - can you see what the patterns are? An algorithm that simply displays each character one-by-one without using loops is not an answer!
a) ++++ -+++ --++ ---+ ---- |
b) *********** ***** ***** **** **** *** *** ** ** * * ** ** *** *** **** **** ***** ***** *********** |
c) %*&%*&%*&%*& *&%*&%*&%*&% &%*&%*&%*&%* %*&%*&%*&%*& *&%*&%*&%*&% &%*&%*&%*&%* %*&%*&%*&%*& *&%*&%*&%*&% &%*&%*&%*&%* |
5. Devise a mathematical algorithm that a computer might use to generate a sequence of random numbers. A random number is a number selected at random from a specified range, for example from the range 1-9 inclusive.
If a program implementing your algorithm has to be completely deterministic, is it actually possible to generate truly random numbers? Are the numbers different every time the algorithm is run?
6a. Devise an algorithm to draw a maze. Here is an example of a simple maze:
The maze should have a single path from the starting to the end point. Hint: consider a random walk.
6b. Having generated a maze write an algorithm to find the path through the maze (such as might be used to program a robot). Do you need some idea of memory to find the path or can it be done with no memory of the path followed so far?
6c. Then write an algorithm that will visit every part of the maze.