G12FCO -- Formal Computation

Coursework 1 -- Algorithms

To be handed in:

The median problem: Write an algorithm to find the median element of an array, that is, the one which would be in the middle if the array were sorted. You may assume that the array has an odd number of elements. Hint: If you use the Dutch National Flag algorithm to partition the array, what can you deduce if the middle element is (a) red; (b) white; (c) blue? In cases (a) and (c), what will you do next?
[I will be quite happy with reasonably-detailed pseudo-code, as this module is much more about strategy than about the minutiae of particular computer languages; but you may perhaps be happier if you write real code in QBasic or C or whatever, so that you can test your algorithm.]
The integer square-root problem: You're given a positive integer N; you are required to find the integer j which is the integer part of the positive square-root of N. You may want to use as invariant something like that you have two integers lo and hi such that lo² <= N < hi², which you will have to establish by setting up suitable values for lo and hi [how?], and then you can home in on j [how?] while maintaining the invariant. [Same comments as above on pseudo vs. real code.]
A graph is bipartite if its nodes can be divided into two classes such that no edge joins members of the same class. [Example: let the nodes be modules and lecture rooms, and two nodes be joined by an edge if and only if one corresponds to a module and the other to a room into which that module will fit. Then a typical problem is to select edges to fit all the modules into suitable rooms.] Devise an algorithm which determines whether or not a given graph is bipartite. [If we colour some arbitrary node white, then all the nodes it joins to must be black, all the nodes they join to must be white, etc. until we've coloured all nodes or found one that must be both colours.] Do not assume that the graph is connected!

Hand in no later than Monday, March 8th.

Not for handing in:

We will, by then, have left a fair number of loose ends. Program up some of them. The `Eight Queens' problem is quite a nice one to try -- note that Queens in positions (i,j) and (p,q) are in the same row if i=p, same column if j=q, and same diagonal if i+j=p+q or i-j=p-q. But also the HCF problem, or one of the sorting methods. Take your pick!

top of page

G12FCO home page. border=0

Next coursework. border=0

Solutions .