Note: You will do this project in groups of 3 people. If your group has 4 members you will need to do some extra work.
Your assignment will be to write a Lisp program (use Python if you must) to solve the Map-Coloring problem using cutset conditioning method. The objective is to color a map using as few colors as possible. The method is described in the textbook. After a cutset is removed from the graph the remaining map will be a tree that can be easily colored using an O(n) method described in the book. To color the cutset you need to attempt all possible colorings.
You will use the greedy algorithm (GA) described in the \Approximation Algorithms for the Loop Cutset Problem" paper which was posted in the General Resources. You should assume that all edges have unit (1) weight. If your group has 4 members you should implement the modi ed greedy algorithm (MGA) described in the paper. To compute cycles you should use the method described in cycles.pdf.
You are given two maps which you need to color with four colors (R,G,B,Y) using your method. To start here is a simple map to test your method. The objective is to color the map in the gure below using as few
GREEN
RED
colors as possible.
The idea of map-coloring is to avoid coloring Figuradjacent4.9A countriesmap-coloingproblemwithafterthe firstsametwo variablescolor(A. Aand B)wellhave knownbeeselectedtheorem. Which country should we color next?
states that any map can be colored using 4 colors. How many colors are needed for the map in this gure? You can represent the map as an assoc list where each country has an associated list of neighboring
countries. The map in the gure would be given by the following assoc list:
’((A (B C E)) (B (A E F)) (C (A E F)) (D (F)) (E (A B C F)) (F (B C D E)))
The second map states.cl is an assoc list representing the map of the United States.
Instructions for submission:
Send a SINGLE email to ple13gmu.edu formatted in the following way:
{ the subject eld of the email should read: CS480 Project
{ the content of the email should be a tar or a zip le containing: (i) commented version of the Lisp code for your Project; comments at the top should include:
Group member names
CS480 Fall 2017
Dr. Duric
Project
Within the code you should include comments documenting the contributions of the group members.
a dribble le le showing testing of your code on the two maps, and (iii) assoc list with the map of the USA
As a safety precaution, always CC yourself when you submit homework this way and keep it around until it has been graded and returned.
Final note: we will test all code using MOSS.
