• selection sort
• bubble sort
• quicksort
• mergesort
• insertion sort

(the final arrangement is of course ``aegpru'')

2.   Write down the pseudocode for an algorithm which determines if four given lengths can form a rectangle.

3.   90 candidates take an exam. Each exam is marked between 0 and 100 (i.e. as a percentage). Write an algorithm to determine the number of marks obtained in the ranges 0 to 40, 41 to 55, 56 to 70, 71 to 100.

4.   The Towers of Hanoï problem comes originally from a legend associated with the Temple of Brahma, in which the problem had to be solved with 64 gold discs on a diamond tower (see http://geminga.it.nuigalway.ie/~gettrick/courses/CT102/hanoi.html). Supposing that these discs could be moved by the priests of the Temple at the (reasonably fast) speed of 1 every second

1. calculate how long (in years) it takes them to solve the problem
2. if the priests were allowed move 2 two discs at a time (but all the other rules are as before), how long (in years) would it take?

5.   A perfect square is a number that is the square of another Natural number, e.g. 1 (= 1x1), 4 (= 2x2), 9 (= 3x3), etc. Write an algorithm that takes as input a positive number n and calculates as output the number of different perfect squares less than or equal to n [e.g. if n were 18, the program should count 4 perfect squares: 1, 4, 9, 16].

6.   A prime number is one which can only be divided by itself and 1. For example, 7 is prime but 9 is not (it can be divided by 3). Develop an algorithm to find (and output) all prime numbers up to a given (input) number n . Write the algorithm in pseudocode, with comments to explain its progress.

7.  It turns out that n is prime if it cannot be divided by any of the numbers from 2 up to n/2. Based on this fact, write an improved version of the algorithm in question 6.

8.   The matrix (table) below gives distances between five cities (numbered 1 to 5, corresponding to the rows and columns of the matrix).

0	79	205	107	115
79	0	158	97	77
205	158	0	137	105
107	97	137	0	175
115	77	105	175	0

1. Draw the graph corresponding to the table.
2. In a travelling salesperson problem, the salesperson must visit each city exactly once, and we wish to determine the shortest such route. Using the Greedy approach to algorithm design, state the proposed solution if the salesperson starts at
   • city 3
   • city 4
   In each case state (by observation) whether the solution is optimum.

9.   For each of the following graphs,

1. Draw the graph
2. State whether or not it is connected
3. State whether or not it is cyclic
4. If it is a tree, state its depth (height) and degree (i.e. binary, ternary,...) (In the case where it is a tree, take the first element of the Vertex set V as the root).

• V = {v₁, v₂, v₃, v₄}  E={(v₁, v₂), (v₁, v₃), (v₃, v₄), (v₃, v₃), (v₄, v₁), (v₄, v₂)}
• V= {a, b, c, d, e}  E= {(a,c),(a,a),(a,b),(e,e),(d,d),(d,e)}
• V= {p,q,r,s,t}  E= {(p,q),(q,r),(q,s),(q,t)}

10.   The Fibonacci sequence is a sequence in which each number is the addition of the previous two numbers and the first two numbers in the sequence are both 1:

1. recursion
2. iteration