Gonville & Caius College

Michaelmas Term 2010

Week 1 (due w/b 7-Oct-2010)

Do the work shown in the Prepartion section for this week

Week 2 (due w/b 14-Oct-2010)

Do the following questions:-
  1. Draw a diagram of the system components in a modern PC. Show how they are connected and the speeds of the various interconnects and devices. What are the challenges that the speed dislocations within the hardware poses for utilising the system efficiently?
  2. 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.
  3. How are integers, real numbers and strings represented in memory? Describe the advantages and dissadvatages of different representations

Week 3 (due w/b 21-Oct-2010)

  1. Write and run a MIPS program to print out all the factors of a number you input to it.

Week 4 (due w/b 28-Oct-2010)

Exercises 1.1 to 2.7 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.

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 using only aspects of ML that have been covered so far in the lectures.
  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 5 (due w/b 4-Nov-2010)

Do exercices from chapters 3 to 4 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, returning to the position it strated form, but only landing on each sqaure 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.

Remember for this part to design, code and test your solution and document each part clearly.

Week 6 (due w/b 11-Nov-2010)

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 chapers 6 and 7.

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 7 (due w/b 18-Nov-2010)

Code a solution to escape from the maze given in week 6. You should then modify this program to produce a lazy list of routes with shortest route first.

Do questions from chapters eight to eleven.

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 (Hint: unbalance the tree).

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.

Week 8 (due w/b 25-Nov-2010)

Answer questions from chapter 13 to 15 of the lecture notes.

Attempt question 2009 paper 1 question 1

Write a solution to the Knight's Tour.

Vacation Work

Revise all the material covered so far in the course for a test at the start of the Lent Term.

Write a program to solve Suduko puzzles. Tread the data as tuples rather than using arrays. Aim to complete you solution in less than 80 lines fo code.