Assignment 5 Solution

The assignment is due at 3pm. Extensions are not possible for any reason. There are two questions to be solved.




[Question 1:70 points]




In this question you will implement a simple map colouring problem. We will represent a map showing countries by describing which countries share a border. A country is just a string. A chart is simply a map (in the normal sense of the word) of some countries. It is represented as a list of pairs of countries. If (a; b) is in the list it means that the countries a and b share a border. This relation is symmetric but we will not put both (a; b) and (b; a) in the list. We want to colour the chart so that two countries that share a border are not given the same colour. We will not name the colours; we simply view a colour as a set of countries that share the same colour; such a set is represented as a list of countries. A colouring is a set of colours; hence a set of sets of countries: this is represented as a list of lists of countries. The algorithm takes a chart, and an initially empty colouring and then tries to extend the colouring by adding countries from the chart. It works by naively checking if a country can be added to a given colour by making sure that it is not a neighbour of any of the countries already with that colour.




Here are the type de nitions and names of functions:




type country = string



type chart = (country * country) list



type colour = country list



type colouring = colour list



val areNeighbours : country - country - chart - bool = <fun




val canBeExtBy : colour - country - chart - bool = <fun




val extColouring : chart - colouring - country - colour list = <fun




val removeDuplicates : ’a list - ’a list = <fun




val countriesInChart : chart - country list = <fun




val colourTheCountries : chart - colouring = <fun




You are required to implement all these functions. This time you are encouraged to use functions from the list library. I found List.mem, List.for_all, List.filter and List.fold_left to be










1



useful in my solution. Of course, you can program without these for full credit but you will nd that the solutions using these are short and sweet.




[Question 2:30 points]







This exercise shows you how to do low-level pointer manipulation in OCaml if you ever need to do that. We can de ne linked lists as follows:




type cell = { data : int; next : rlist}




and rlist = cell option ref




Notice that this is a mutually recursive de nition. Each type mentions the other one. The keyword and is used for mutually recursive de nitions.




Implement an OCaml function insert which inserts an element into a sorted linked list and pre-serves the sorting. You do not have to worry about checking if the input list is sorted. The type should be




val insert : comp:(int * int - bool) - item:int - list:rlist - unit




Insert takes in three arguments: A comparison function of type int * int - bool, an element of type int and a linked list l of type rlist. Your function will destructively update the list l. This means that you will have mutable elds that get updated. Please note the types carefully. Here is the code I used to test the program.




let c1 = {data = 1;
next = ref None}


let c2 = {data = 2;
next = ref (Some
c1)}
let c3
= {data = 3;
next = ref (Some
c2)}
let c5
= {data = 5;
next = ref (Some
c3)}
(* This converts an
rlist to an ordinary list. *)
let rec displayList
(c : rlist) =


match !c with




| None - []




| Some { data =
d; next = l } -
d :: (displayList l)



(* Useful if you are creating some cells by hand and then converting them to rlists as I did above. *)




let cell2rlist (c:cell):rlist = ref (Some c)




(* Example comparison function. *)




let bigger(x:int, y:int) = (x y)




You may nd the displayList and cell2rlist functions useful.




Here are examples of the code in action:




let l5 = cell2rlist c5;; val l5 : rlist = ....



(* Messy display deleted. *)







2



# displayList l5;;




: int list = [5; 3; 2; 1]



# displayList l5;;




: int list = [5; 3; 2; 1]



# insert bigger 4 l5;;




: unit = ()



# displayList l5;;




: int list = [5; 4; 3; 2; 1]



# insert bigger 9 l5;;




: unit = ()



# displayList l5;;




: int list = [9; 5; 4; 3; 2; 1]



# insert bigger 0 l5;;




: unit = ()



# displayList l5;;




- : int list = [9; 5; 4; 3; 2; 1; 0]




The program is short (5 lines or fewer) and easy to mess up. Please think carefully about whether you are creating aliases or not. You can easily write programs that look absolutely correct but which create in nite loops. It might happen that your insert program looks like it is working correctly but then displayList crashes. You might then waste hours trying to \ x" displayList and cursing me for writing incorrect code. Most likely, your insert happily terminated but created a cycle of pointers which then sends displayList into an in nite loop.




































































































3