15-381 Spring 2007Assignment 2: Constraint Satisfaction ProblemsFor questions contact Arthur ([email protected])and Gil ([email protected])Spring 2007Out: Feb. 6Due: Feb. 20, 1:30pm TuesdayThe written p ortion of this assignment must be turned in at the beginning of class at 1:30pm on February20th. Type or write neatly; illegible submissions will not receive credit. Write your name and andrew idclearly at the top of your assignment. If you do not write your andrew id on your assignment, you will lose5 points.The code portion of this assignment must be submitted electronically by 1:30pm on February 20th. Tosubmit your code, please copy all of the necessary files to the following directory:/afs/andrew.cmu.edu/course/15/381/hw2 submit directory/yourandrewidreplacing yourandrewid with your Andrew ID. The TAs grading this assignment would prefer that you useC/C++, Java, or Matlab. If you would like to use a different programming language, please give instructionson how to execute your code and comment it very thoroughly or you risk decreased partial credit. Feel freeto use standard data structures and algorithms in your chosen language (like the C++ STL). If you usenon-standard data structures or algorithms (like someone’s internet C queue c ode) make sure you turn thatin as well and indicate in the comments if you did not write a particular piece of code. All code will betested on a Linux system, we will not accept Windows binaries. No matter what language you use, you mustensure that the code compiles and runs in the afs submission directory. Clearly document your program.Late Policy. Both your written work and code are due at 1:30pm on 2/20. Submitting your work late willaffect its score as follows:• If you submit it after 1:30pm on 2/20 but before 1:30pm on 2/21, it will receive 90% of its score.• If you submit it after 1:30pm on 2/21 but before 1:30pm on 2/22, it will receive 50% of its score.• If you submit it after 1:30pm on 2/22, it will rece ive no score.Collaboration Policy.You are to complete this assignment individually. However, you are encouraged to discuss the generalalgorithms and ideas in the class in order to help each other answer homework questions. You are alsowelcome to give each other examples that are not on the assignment in order to demonstrate how to solveproblems. But we require you to:• not explicitly tell each other the answers1• not to copy answers• not to allow your answers to be copiedIn those cases where you work with one or more other people on the general discussion of the assignmentand surrounding topics, we ask that you specifically rec ord on the assigment the names of the people youwere in discussion with (or “none” if you did not talk with anyone else). This is worth five points: for eachproblem, you solution should either contained the names of people you talked to about it, or “none.” If youdo not give references for each problem, you will lose five points. This will help resolve the situtaion where amistake in general discussion led to a replicated weird error among multiple solutions. This policy has beenestablished in order to be fair to everyone in the class. We have a grading policy of watching for cheatingand we will follow up if it is detected.2Problem 1 (20 total points)Alby-Bach University (ABU) wants to s tart a new degree program: B.S in Judgment Day Prevention (JDP).Supp ose the degree program is associated with the following courses:15-211 Fundamental Data Structures and Algorithms15-212 Principles of Programming15-381 Artificial Intelligence: Representation and Problem-Solving15-681 Machine Learning80-310 Logic and Computation21-484 Graph Theory70-122 Accounting70-311 Organizational Behavior19-601 Information WarfareIn order to graduate from the degree program, one must complete the following four requirements:Algorithms Requirement: (15-211 AND 15-212) OR (15-211 AND 15-381) OR (15-681 AND 21-484)Machine Learning Requirement: 15-381 OR 15-681 OR 80-310Communications Requirement: 21-484 OR 70-311 OR 70-122Information Warfare Requirement: 15-381 OR 19-601In addition, the department imposes the following restrictions:Information Aggressiveness Restriction: So that they can’t make their programs TOO smart, studentscan take only one class from the set 15-381, 15-681, and 19-601.Basic Arithmetic Restriction: Students can’t take both 15-211 and 70-122.Organization Restriction: Students can’t take both 21-484 and 70-311.Finally, courses cannot be used to count towards multiple graduation requirements - so if you use 15-381 tofulfill part of the Algorithms requirement it can’t count towards either the Machine Learning Requirementor the Information Warfare Requirement.Question 1.1 (5 points)John Conner just started his junior year at ABU, and needs to graduate as soon as possible. Suppose all hehas left to take are JDP required classes. Model the problem of his trying to find a set of classes to satisfyall requirements as a CSP (Hint: the requirements should be your variables). What are the initial domainsfor each of your variables?Question 1.2 (8 points)Show a DFS with backtracking tree for finding a set of classes that fulfill all requirements using a variableorder of the requirements in the order they are listed above, and using a value order that selects the lowestdepartment/course number remaining in a variable’s domain. Indicate which constraints were violatedwhenever the DFS needs to backtrack. (Note: to get full credit you must show the full DFS tree and notjust the classes that are used to fulfill each requirement).3Question 1.3 (7 points)Supp ose John has already taken 19-601 towards his Information Warfare Requirement and 15-211 towardshis Algorithms Requirement. Use constraint propagation to determine other classes he must take to graduate- indicate which requirements the classes fulfill. Can you create a schedule that satisfies all constraints withoutusing search?Problem 2 (20 total points)Arthur is looking for a group of friends for his start-up, which develops and provides some web-based p2pdownloading solutions to college students (this is before the lawsuits). Arthur has determined that he needs2 C# Programmers, 2 Flash Designers, 1 Photoshop Guru, 1 Database Admin, and 1 Systems Engineer.Assume that if a person knows two languages/softwares, he or she can take on two roles in the company.So Arthurs narrowed down his selections to the following people:Name AbilitiesPeter C# and
View Full Document
Unlocking...