Gonville & Caius College
Cambridge CB2 1TA

Supervision schedule

Here is a schedule of work for supervisions with Graham Titmus

Your solutions should be handed in to the main Porters' Lodge at Caius College by noon on the day preceding the supervision. The supervisions will be held in my room at Caius, P11 Tree Court, as follows:

Tuesday 14:00 Daniel & Paul
  15:00 Andrew, James & Lee
  16:00 Christopher & Jennifer
  18:00 Sonali & Max

Michaelmas Term 2000

Week 1 (due w/b 09-10-2000)

Questions 1-12 from Goldschlager & Lister Chapter 2.

Week 2 (due w/b 16-10-2000)

Exercises 1.1 to 2.3 from the Lecture notes.

A number q is rational if q = a/b, where a and b are integers with b not 0. Construct a program to perform the usual arithmetic operation on rational numbers: addition, subtraction, multiplication, division and equality. The program should also contain a function to convert a rational number to a suitable text representation.

Tackle this by doing the following

  1. Analyse the problem and identify necessary data and functions, specify the types of the functions you will write.
  2. Program to the above specification.
  3. Test the program - test examples should aim to cover every line of code!

Hint: you might need to implement Euclid's algorithm for the greatest common divisor to use in the above.


Week 3 (due w/b 23-Oct-2000)

Do exercices 3.1 to 5.3 from the lecture notes.

In addition consider the following problem, known as the Knight's tour.

Can a knight moves to all the places on a chess board but only landing on each one once?

Each time the knight has a choice of moves:-

To start work on this problem do the following work only.

  1. Decide upon a representation for the chessboard and write a function to generate a board with no moves yet taken place on it. Name the function makeboard which is of type
    int -> board_type
    where board_type is up to you. The int part is the size of the board which is square.
  2. Write a function which when given a poistion of a knight and a board will return a list of the possible moves. The functions should be called generateMoves and will be of type
    (int * int) * board_type -> (int * int) list
    where int * int is a coordinate on the board. [] being returned when no moves exist.
  3. Test these functions by placing the knight in various positions and checking that you get back the correct result. State the criteria you use to choose test values.

Week 4 (due w/b 30-10-99)

Study the following ML function definitions and answer the questions below:

fun prefix [ ]  [ ] = [ ]
  | prefix (x::xs) (y::ys) = (x::y)::prefix xs ys;

fun sep [ ] = [[ ],[ ]]
  | sep [x] = [[x],[ ]]
  | sep (x::y::rest) = prefix [x,y]  (sep rest);

fun merge [[ ],y] = y : int list
  | merge [x,[ ]] = x
  | merge [x::xs, y::ys] =
           if x < y then x :: merge [xs, y::ys]
                  else y :: merge [x::xs, ys];
  1. Deduce the ML type of the function prefix showing your method of deduction in detail. Verify by evaluating the result of the call prefix [1,2,3] [[4],[5],[6]];
  2. Give a correctly-typed call to prefix that will generate an exception when evaluated. Explain why this is possible despite the type checking by the compiler.
  3. What values do sep[l,2,3,4,5,6,7,8] and sep[1,2,3,4,5,6,7] yield?
  4. Deduce the ML type of merge, showing your working in detail, and explain why the omision of `: int list' would lead to an error.

Next do exercises from chaper 6 up to and including chapter 9.

Finally, consider the problem of getting out of a maze. Below is a schematic of the maze at Hampton Court.

  1. What sort of data structure could you use to represent this?
  2. Label up the maze as necessary and construct your representation.
  3. Design but do not code your algorithm for escaping from the maze.

Week 5 (due w/b 6-11-2000)

Do exercises from 10.1 to 12.6 from the lecture notes

Code and test the maze program that we considered last week. Document your design, your code and your test data.

Write a shortest path finding program to find the distance from the front (1) to the back (18) of the Guildhall. As before you should split this into three parts, design, code and test making each stage visible. Identify how you needed to extedn the maze program to solve this problem.

You can either start from the map of Cambridge and measure the points yourself or use this list:-

val roads = [(1,2,0.4, 1),(2,1,1.5,1),(2,3,1.0,1),
             (3,4,1.1,1),(4,5,0.8,1),(4,7,1.4,1),
             (5,6,1.0,1),(6,7,2.6,1),(7,1,1.7,1),
             (8,9,16.5,2),(10,9,2.0,2),
             (10,11,2.4,2),(9,12,0.3,2),(12,13,2.5,2),
             (12,19,4.7,2),(12,14,2.0,1),(18,14,5.8,2),
             (19,18,1.0,2),(18,17,2.8,2),(14,15,0.5,1),
             (15,16,1.5,1),(15,18,2.1,1),(18,10,1.8,1),
             (17,22,3.0,2),(22,16,2.0,2),(22,20,2.7,2),
             (17,19,4.4,2),(19,20,3.0,2),(20,21,1.5,2),
             (17,19,4.4,2),(19,20,3.0,2),(20,21,1.5,2),
             (21,16,2.3,2),(21,23,3.7,2),(23,26,7.5,2),
             (23,25,3.2,2),(5,25,2.1,2),(24,25,1.2,1),
             (26,8,8.3,2),(16,27,2.0,2),(27,24,2.4,2),
             (27,3,1.8,1)]
where each entry is as follows
    (node1, node2, distance, 1=one way|2=bidirectional)
Aim to clearly document how your code works. Then try to add a new link (8,6,3.5,2) from the matrix of connections and see what difference it makes to the distance.

Week 6 (due w/b 13-11-2000)

Binary (or higher) trees are a common data structure. Using the datatype:-
datatype 'a tree = leaf | node of 'a tree * 'a * 'a tree;
Construct the following functions
  1. InsertItem: (('a * 'a) -> boolean) * 'a * 'a tree) -> 'a tree
    given an item returns a new tree with the item inserted. Make sure your function obeys the type rule! What is the ('a * 'a) -> boolean for?
  2. BuildTree: ('a list, ('a * 'a) -> boolean)) -> 'a tree
    given alist of items returns a tree with the items in order.
  3. BuildBalancedTree: ('a list, ('a * 'a) -> boolean)) -> 'a tree
    given a list of items returns a tree with the items in order and also the tree is a balanced as possible. To do this you need to think about how you can rewrite a tree to preserve order but have a different arrangment of branches. Look at the section on Rotations under Red-Black trees in Cormen Introduction to Algroithms (p266) for a hint of how to proceed.
  4. You could consider building curried versions of these functions and examine the types you get back when you hand them a comparison function.
  5. Fringe: ('a tree) -> 'a list
    given a tree returns the items in order.
  6. TreesEqual ('a tree * 'a tree) -> boolean
    given two trees returns whether they are equal or not. You can do this by calling Fringe on each list and then comparing the two lists. However, try to do it by only examining as much of the tree as is necessary by creating a lazy fringe function
Remember to describe and test your algorithms as well as coding. Include printout to demonstrate that your code functions correctly and parts 3 and 5 discuss how you chose your test data.

Make the maze and City streets problem into Lazy List versions.


Week 7 (due w/b 20-11-2000)

Try to finish the Knight's tour problem and find a solution. You should use a list of (x,y) 2-tuples to represent the board. You need to think about how to handle the backtracking and avoid going down the same solution path twice. You should test your algorithm on a smaller board.

I want a description of how you designed your solution. Don't look for short-cuts, do a strightforward exhaustive search and return the first solution. Try it out on smaller custom boards for which a solution does exist and make sure it finds them.


The following ML declaration introduces a data type that can be used to represent a potentially infinite arrangement of cells at positions with integer coordinates in the first quadrant of the x - y plane:
datatype A = Z
           | Cell of int ref * A ref * A ref;
Each cell contains an integer value and pointers to the cells immediately to its right and above itself. These three components are all mutable so that the arrangement of the cells and the integers they contain can change during use. The constructor Z can be used in an A ref to allow a cluster to have a boundary rather than continuing through unbounded chains of cells.

Define a function mkrow(n) of type int->A that will return a row of length n + 1 cells initialised with zeros. For instance:

mkrow(1) = Cell(ref 0, ref(Cell(ref 0, ref Z, ref Z)), ref Z)

Define a function zip (rowl, row2) of type A*A->A that will return row1 with row2 joined above it. This function is entitled to change some of the ref A pointers in rowl. For example

val root = zip(mkrow(3), mkrow(2));
would give root a value representing the following arrangement.
                     0 ----> 0 ----> 0
                     ^       ^       ^
                     |       |       |
                     |       |       |
              root : 0 ----> 0 ----> 0 ---> 0

Next define a function mkarr (m, n) of type (int* int) ->A that will return a value representing a rectangular array of n + 1 rows each ofwhich are of length m + 1 in which each cell is initialised to zero.

Paths originating from the bottom leftmost cell (which will be referred to by the variable root) are represented by values of the type dir list where dir is declared as follows:

datatype dir = Right | Up;
Finally define a function inc-path-cells of type A-> dir list -> unit that will increment the integers in all the cells that lie on a specified path within a given collection of cells. For instance after root had been set up as above, the two calls
inc-path-cells root [Right, Up, Right];
inc-path-cells root [Right, Right, Right];
would leave root representing the following arrangement:
                     0 ----> 1 ----> 1
                     ^       ^       ^
                     |       |       |
                     |       |       |
              root : 2 ----> 2 ----> 1 ---> 1
You may assume that the path does not try to reach cells outside the given arrangement.

Week 8 PP&E(due w/b 27-11-2000)

Is there such a thing as a "Right to Privacy"? What are "rights" in the context of ethics? Discuss the philosophical basis of privacy in relation to the Data Protection Act (1998).

Consider whether Computer Scientists are Professionals. Look at the code of conduct of one of the professional bodies (ACM or BCS) and comment on its policies in the light of your discussion of the first question.

You may find the following site useful - Ethics and Intellectual Property Resources on the Web.


Lent Term 2001

Week 1 PP&E (due w/b 22-1-2001)

Look at the following site Ethics and Intellectual Property Resources on the Web.

Find the paper "Why Software Should Be Free" and critically evaluate Richard Stallman's position including some justification for property right especially with respect to research and product development.


Week 2 (due w/b 29-1-2001)

Revise your ML lectures. Read through the notes and look over the exercises we did last term. Hand in answers to the question you did not attempt in the test. I'll go over the ML questions from the test as well as setting a couple of problems at the supervisions.

It would be good if you attempted to do any of the ML problems from the test that you are not confident that you solved.


Week 3 (due w/b 5-2-2001)

Please attempt questions 5 and 6 from each of years 1996 and 1997.

Week 4 (due w/b 12-2-2001)

I would like you to write some Java routines to handles dates.

A date is made up of three integer values, for day, month and year. (Make sure you are Y2K compliant!) Write three procedures.

You should explain how your functions work and have tested them using suitable test data. Your not need to worry about dates in other than the current calendar system.

As for the exercises last term the design, code and testing are equally important in marking.


Week 5 (due w/b 19-2-2001)

Rewrite the exercise from last week so that all the functions are methods in a Class called MyDate. (This class may also have other methods.)

Write a different class which has the main function in so your class MyDate does not have any test code in it.


Week 6 (due w/b 26-2-2001)

This weeks work involves writing some routines to create a linked list. You should aim to construct in Java the equivalent of

datatype 'a dllist = Null | DLnode of 'a * ref dllist * ref dllist;

The nodes should each have a backward and forward pointer so the list you construct using it should be easy to traverse in either direction. Try to ensure you maintain data abstraction in your code.

Use the DLnode object you will have created as part of a second Class which provides the functions needed to build a DLlist.

Code this all up and write a simple test routine to add and remove items from a list.


Week 7 (due w/b 5-3-2001)

Use the code you constructed last week as the basis for three extensions to the DLlist class. You should try to document your code using comments and also explain its function clearly in English on a seperate sheet.

Also write a answer to the following exam style question:-

What is the meaning of the words static, public and private in relation to variables and methods in a class definition. Illustrate your answer with code fragments.

Why is the inability to declare pointers in java not a serious handicap to the use of the language?


Week 8 (due 1s23-3-2001)

A java program to draw a compass rose is needed. (See exam paper 1995 paper 1 question 9 for picture.) In this the line pointing north should be 1 unit longer than that pointing south which in turn is 1 unit longer than that pointing east and west etc If the line north is n units long then there will be 2 exp (n - 1) radial line sin a complete rose.

A graphics class G contains a method public void drawLatA(float angle, int length).

Write two versions of the rose-drawing class. One using recursion and the other iteration. The argument to the class constructor should be the length of the North line in integer units.

Try to write these as if in an exam, then have a go at writing an Applet to display it. (You'll need to look for the java.awt.Graphics class to find the actual method to draw a line.)


Easter Term Supervisions

Week 1 (due w/b 30-4-2001)

Attempt question 8 from paper 2 of the 1998 exam paper on software development process.

Write a Z schema to define a legal DATE in the Gregorian calendar. Try to get it to exclude leap days. What is the relationship between a formal method like Z and code?

What are the advantages and disadvantages of using formal methods?

Attempt question 9 from paper 2 of 1999 on structural induction.

Week 2 (due w/b 7-5-2001)

Answer the questions on ML and Java that you did not do in the exam at the start of term. Write answers as if under exam conditions then debug your answer by attempting to implement your solution. [Spend up to 3 hrs only on all parts of this question.]

Week 3 (due w/b 14-5-2001)

Do the following questions:-
  1. What are interrupts and how are they handled at the hardware and OS level of abstraction. Contrast the handling of fast devices such as discs with slow ones such as a keyboard.
  2. Define and dintinguish between process, address space and file.

Week 4 (due w/b 21-5-200s10)

Answer the following questions:-
  1. Paper 1 Question 3 from 2000
  2. Paper 1 Question 11 from 2000
  3. Paper 1 Question 12 from 2000

Week 5 (due w/b 28-5-2001)

work will be set later.
 
University of Cambridge Computer Laboratory New Museums Site Pembroke Street Cambridge CB2 3QG England E-mail: Graham.Titmus@cl.cam.ac.uk Telephone: +44 1223 334620 Facsimile: +44 1223 334678