Ocaml代写 | CSCI 2041: Advanced Programming Principles

这个作业是完成两道高级编程的题目
CSCI 2041: Advanced Programming Principles
Homework 6
Posted: April 12, 2020
Due: April 22, 2020 by 23:59
Submission Protocol
We are expecting to see your work in your private github repository for this course within a
folder named hw6 that is itself within the hws folder. The folder should contain two files named
prob1.ml and prob2.ml that respectively contain solutions to Problem 1 and Problem 2 described
below. You will find skeleton versions of these files in the hw6 folder within the hws folder in the
the public repository for this course. You should check this folder out, understand the skeleton
code in the context of the problems that you are to solve and then fill in the missing code in
each for the files before submitting your work.
As always, it would be a good idea to read the comments on the protocol for homeworks and to
pay close attention to the quality of your code in developing your solutions. This will make a
difference to our assessment of your work.
The Preliminary Feedback Process
We will write scripts that will run tests on the programs asked for in this homework aimed at
giving you preliminary, non-exhaustive feedback on your work. Starting on the day before the
submission deadline, we will enable the feedback script on what you push as a solution. This
script will generate output which will be written to your repository. After pushing to your
repository, wait a little while (about a minute), pull from your repository, and check if a file called
hw6_Feedback.md has been created. If this file has not been created, it would mean that the
script is not yet active and so you should repeat the process of pushing and then pulling at a
later time.
2020/4/13 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw6.html 2/6
If the file hw6_Feedback.md appears in your repository after a pull, open it and look for lines in it
that begin with the string “+ Fail:”. These lines indicate failures of some kind in your code. The
text that follows should help you understand what the failure is and, hopefully, how to correct it.
After correcting any mistakes, you should push again to your repository, wait a little while, and
pull again to receive updated feedback. Note that, as already indicated with earlier homeworks,
you must not rely too much on this feedback mechanism; the real feedback will come when we
grade your work.
A couple of important points that bear repeating: First, the feedback file will be created only
when you push a commit that affects the files under hws/hw2 after the script has been enabled.
If you pushed your homework before that time, you will have to push it again later in a way that
actually changes the contents of the folder in order to trigger the feedback. You can do this by,
for example, adding some (otherwise) inconsequential white space somewhere to one of your
files in the folder before pushing the repository. The second point to note is that if you do not
pull the feedback before trying to make another push, then you will encounter a conflict and your
commit will fail. If this happens, you will need to pull from your repository, make a merge and
only then try to push. As long as you do not modify the feedback file yourself, i.e. you treat it as
a read-only file, such merges should succeed automatically.
The Context for this Assignment
In this homework, you are going to try your hand at writing programs that utilize the
programming techniques for implementing search that have been discussed in the lectures and
that you have also worked on in Lab 11. The particular problem to be solved is that of graph
coloring. This problem is the following: given a collection of nodes connected by undirected
edges and a palate of colours, we are to find a way to assign colours to the nodes in such a way
that two nodes that are adjacent do not get assigned the same color.
This is a problem that turns out to be of significant practical importance. One place where it is
useful is in coloring maps: here the nodes are countries or states or counties, depending on what
kind of map you are looking at, and two nodes are adjacent if they represent distinct regions
that share a border. Another place where graph coloring shows up is in assigning space (such as
registers) to the variables in a program. Think here of the space or register as a color (the palate
is especially limited if we are thinking of the registers in a real machine as the colors), the
variables are nodes and two variables share an edge if their values are “live” at the same time
somewhere in the program; clearly, they can be assigned the same space/register only if they do
not share an edge. Looked at differently, if we are able to color the variables satisfactorily, then
the coloring gives us a way to allocate space for them.
Graph coloring is a problem for which we do not know a good algorithm currently and for which
it is conjectured we will never know one; to put this more precisely, it is what is known as an
NP-complete problem. Problems of this kind that are practically important are often solved using
search. Typically, the search uses heuristics that help in cutting down the work in practice. In
this homework, we will take a simplistic approach, using search to solve graph coloring but
2020/4/13 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw6.html 3/6
without building in any heuristics. If the problem excites you, I can suggest some heuristics for
you to try later.
The two problems below for which you have to write code differ in the way they want you to
implement the search. Before getting to them, we describe some things that are common to
their setup. We will represent graphs using two components: a list of nodes and, for each node a
list of nodes adjacent to it. As an example, consider the complete graph with 4 nodes named 1,
2, 3 and 4; for simplicity we will use numbers for nodes. (Recall that a complete graph is one in
which every node is connected to every other node.) This graph would be represented by the
nodes list [1;2;3;4] and the adjacency list
[(1,[2;3;4]); (2,[1;3;4]); (3,[1;2;4]); (4,[1;2;3])]
The functions you will define will also be parameterized by a collection of colors. These will be
provided in the form of a list of strings such as the following:
[“R”; “B”; “G”; “Y”]
Problem 1 (10 points)
The goal in this problem is to define a function called color_graph that takes a graph and a set
of colors presented in the fashion described above and determines a coloring for the graph.
There are, however, two special requirements:
Like in the problems in Lab 11, the function will display the coloring to user and interact
with them to decide if the coloring is satisfactory. Thus, the type of the function should be
the following:
color_graph : int list -> (int * int list) list -> string list -> unit
The expected usage of this function is illustrated by the following interaction:
# color_graph [1;2;3;4] [(1,[2;3;4]); (2,[1;3;4]); (3,[1;2;4]); (4,[1;2;3])]
[“R”; “B”; “G”; “Y”];;

Coloring for the graph: [(4,Y), (3,G), (2,B), (1,R)]
More solutions (y/n)? y
Coloring for the graph: [(4,G), (3,Y), (2,B), (1,R)]
More solutions (y/n)? n
– : unit = ()
# color_graph [1;2;3;4] [(1,[2;3;4]); (2,[1;3;4]); (3,[1;2;4]); (4,[1;2;3])]
[“R”; “B”; “G”];;

No (more) colourings possible
– : unit = ()
#
I am giving you the functions necessary for arranging the interactions; see below. Your task
will be mainly to organize the search in the problem.
2020/4/13 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw6.html 4/6
For credit in this problem, you must organize the search in this problem using
exceptions.
How should we go about solving the graph coloring problem? Here is the basic structure:
1. We pick the first node that has still not been colored and try to color it; if we are
successful, i.e. if it can be given a color that is different from the colors given to its
neighbours, we add the coloring and move on to the next node.
2. The color that we have picked for the node in the previous step may turn out to be “bad” in
that the rest of the graph cannot be colored with that choice. In this case, we would
backtrack to considering another color for the node. In the model to be used in this
problem, the failure must be treated by raising an exception, specifically, the exception
Search_Failure, and backtracking must be treated by catching and handling the exception.
3. On the other hand, we may succeed in coloring all the nodes satisfactorily. In this case, we
should interact with the user using the ask_user function provided to you and whose
behavior is described below.
To let you focus on the core task, that of organizing the search using exceptions, I have
provided you the code for displaying a coloring once one has been found and for checking if the
user is satisfied. Read this code and try to understand it so that you can write such functions
yourself in the future. However, here is an example that shows you how you would use the code
when you are defining color_graph:
# ask_user show_coloring [(1,”R”); (2,”B”); (3,”G”); (4,”Y”)];;
Coloring for the graph: [(1,R), (2,B), (3,G), (4,Y)]
More solutions (y/n)? y
Exception: Search_Failure.
# ask_user show_coloring [(1,”R”); (2,”B”); (3,”G”); (4,”Y”)];;
Coloring for the graph: [(1,R), (2,B), (3,G), (4,Y)]
More solutions (y/n)? n
– : unit = ()
#
Note that colorings are represented by lists of node and color pairs. After displaying the
coloring, the function awaits an input from the user. If the input is “y”, it raises the exception
Search_Failure, otherwise it finishes normally.
A comment in the file prob.ml indicates where you must put the code that you will write for this
problem. The comment also repeats information about how to structure the search in solving this
problem. Following these comments is a skeleton definition for the color_graph function that you
must complete for this problem.
Problem 2 (10 points)
2020/4/13 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw6.html 5/6
In this problem, we are going to solve the same graph coloring task but this time using success
and failure continuations to handle the situations were search ends in success and where it ends
in failure. The overall task is still to define the color_graph with the same type as in Problem 1
and that must exhibit the same outward behavior. However, this time, the search must be
organized using the idea of continuations for credit, that is the main point of this problem.
Here is a brief description of structure that the definition of the color_graph should have in this
problem:
1. We pick the first node that has still not been colored and try to color it; if we are
successful, i.e. if it can be given a color that is different from the colors given to its
neighbours, we add the coloring to the ones we have already determined, and move on to
coloring the next node.
2. The color that we have picked for the node in the previous step may turn out to be “bad” in
that the rest of the graph cannot be colored with that choice. To prepare for this
contingency, we should pass on a suitable failure continuation to the function that we are
calling. Similarly, it should get a suitable success continuation that would enable it to do
the right thing in case of success.
3. We may also fail to find a suitable color for the node in the first step. In this model, we deal
with this situation by calling the failure continuation.
4. Finally, we may have succeeded in coloring all the nodes in the graph. Now we need to
interact with the user. To do this, we use the function ask_user_cps as described below. Of
course, we have to pass it the right success and failure continuations to prepare for the
situations where the user is happy with the coloring or rejects it.
The only remaining thing to be explained is how to use the code I have provided you for
displaying a solution and getting a response from the user. If coloring is bound to a good
coloring, then you would invoke
(ask_user show_coloring coloring succ fail)
where succ and fail are suitable continuations. Some examples that illustrate the use of this
function are the following:
# ask_usr show_coloring [(1,”R”); (2,”B”); (3,”G”); (4,”Y”)]
(fun () -> ())
(fun () -> Printf.printf “\nNo (more) colorings\n”);;

Coloring for the graph: [(1,R), (2,B), (3,G), (4,Y)]
More solutions (y/n)? n
– : unit = ()
# ask_usr show_coloring [(1,”R”); (2,”B”); (3,”G”); (4,”Y”)]
(fun () -> ())
(fun () -> Printf.printf “\nNo (more) colorings\n”);;

Coloring for the graph: [(1,R), (2,B), (3,G), (4,Y)]
More solutions (y/n)? y
No (more) colorings
2020/4/13 CSCI 2041, Advanced Programming Principles
www-users.cselabs.umn.edu/classes/Spring-2020/csci2041/resources/hws/hw6.html 6/6
– : unit = ()
#
Check out how the two continuations impact on behavior after the user’s response.
For completeness, here is an interaction I got when I ran my code:
# color_graph [1;2;3;4] [(1,[2;3;4]); (2,[1;3;4]); (3,[1;2;4]); (4,[1;2;3])]
[“R”; “B”; “G”; “Y”];;

Coloring for the graph: [(4,Y), (3,G), (2,B), (1,R)]
More solutions (y/n)? y
Coloring for the graph: [(4,G), (3,Y), (2,B), (1,R)]
More solutions (y/n)? n
– : unit = ()
# color_graph [1;2;3;4] [(1,[2;3;4]); (2,[1;3;4]); (3,[1;2;4]); (4,[1;2;3])]
[“R”; “B”; “G”];;

No (more) colorings
– : unit = ()
#
The same behavior in Problem 1, but a different approach to defining the function.
Last modified: April 12, 2020. Created by ngopalan atsign umn dot edu.
The views and opinions expressed in this page are strictly those of the page author(s). The contents of this page have
not been reviewed or approved by the University of Minnesota.