CSci 4511 - Homework 3
Homework 3 -- due date Wednesday extended to Saturday March 21
This homework will be graded out of 100 points. It will count 5% of the
grade.
Written questions
- [10 points]
Given a constraint satisfaction problem with (1) a
finite number of variables and (2) a finite domain for each variable
- how does the number of variables affect the size of the search space?
- how does the size of the domains affect the size of the search space?
Explain your reasoning.
- [20 points] Show in detail how to solve the following
crypto-arithmetic problem I + DID = TOO. Write the constraint equations
and show the search tree explored by the backtracking algorithm.
- [20 points]
This question is on the arc consistency AC-3 algorithm
- Show how the arc consistency AC-3 algorithm is able to detect
the inconsistency of the partial assignment {Wa=red,V=blue} in the map of
Australia.
- Try the same AC-3 algorithm to detect the inconsistency of the partial
assignment {WA=red,NSW=red}. Does the algorithm detect the inconsistency
or not?
- If not, why AC-3 is not always capable of detecting inconsistencies?
- [10 points]
How many solutions are there for the map-coloring problem for the Australia
map (textbook Figure 6.1) when using three colors? Explain your results.
- Extra credit [20 points]
Use the AC-3 algorithm to label the following figure. Explain step by step
how the algorithm works.
Programming questions
For this part you need to submit your source files and the output.
For these questions we will use the constraint satisfaction aima software.
There are two algorithms implemented, backtracking-search and
forward-checking.
In the test file there are examples on how to call those functions.
Here are specific instructions for how to submit the programming part.
Please folllow these instructions, this will save a lot of time for the TAs
and reduce the chance of missing your work. Thank you!
- All programming related content including output, and code should be in a
zip file named prog.zip. Your solution to the written problem questions should
be in PDF and should NOT be part of this zip file.
- Do NOT submit any unmodified aima functions, classes or files. Any
functions that need to be called from within your code should be imported
using import statements. You should only submit your own code (function,
class, driver, etc).
- Your output to the programming part should in a plain text file called
output (or output.txt). Instructions for creating this output file directly
from the terminal can be found in hw1. You may submit multiple output files
for each programming question and name them output_1, output_2, etc. However,
NO screenshot, images, PDFs will be accepted for the output. Any written
answer within the programming section should also be in the output file.
- If you have NOT attempted any part of the programming questions or have a
partial solution you should submit a README file (in plain text) that has a
brief description of your attempt (or just say no attempt if you have not
tried them).
- [5 points]
Use the the AIMA backtracking-search function to solve the n-queens problem
with 4, 12, and 20 queens.
- [5 points]
For the same n-queens problems (4, 12 and 20 queens) use instead
forward-checking.
- [5 points]
Use the the AIMA backtracking-search function to solve the
map-coloring problem with 3 colors shown in the textbook in Figure 6.1.
- [5 points] Repeat the same problem on the Australia map this
time using 4 colors. Is the solution different? Do you need 4 colors or
are 3 enough?
- [5 points ]
What happens if you use just 2 colors to color the Australia map?
- [5 points ]
Use the AC-3 algorithm for the Australia map.
- [10 points]
Use the the AIMA backtracking-search function to solve the
map-coloring problem for the USA map.
Copyright: © 2020 by the Regents of the University
of Minnesota
Department of Computer Science and
Engineering. All rights reserved.
Comments to: Maria Gini
Changes and corrections are in red.