Shortcut to this term's work or to Operating Systems supervisions
Find reference on WWW to the algorithm for calculating leap years. Write an implementation of that as a predicate isleap which will work for well into the next millenium. Use that to write Qu12 from last week in ML. (That is to determine which day a birthday will fall on in a given year knowing the bithday and the day of week a person was born on.)
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.
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];
Write a shortest path finding program to find the distance from the front (1) to the back (18) of the Guildhall.
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.
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 and show that the solution is a magic square. You need to think about how to handle the backtracking and avoid going down the same solution path twice. You could test your algorithm on a smaller board if you like.
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 ---> 1You may assume that the path does not try to reach cells outside the given arrangement.
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.
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.
It would be good if you attempted to do any of the problems from the test that you are not confident that you solved.
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 some suitable test data. Your not need to worry about dates in other than the current calendar system.
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 anbd remove items from a list.
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 ability to declare pointers in java not a serious handicap to the use of the language?
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.
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?
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