2020/11/19 Copy of CSE 140 - Assignment 4
%matplotlib inline
Turn in the assignment via Canvas.
To write legible answers you will need to be familiar with both Markdown and Latex
Make sure you ¦ll in any place that says "YOUR CODE HERE" or "YOUR ANSWER HERE", as well
as your name below:
Assignment 4
NAME = ""
STUDENT_ID = ""
Sadly, many physicians and almost all (non-mathematician) patients would get this problem
wrong!
Suppose that a certain form of cancer has a test that correctly detects cancer (if one has it)
99.5% of the time. The prevalence of the cancer in the general population is 1 person in 14,000.
Also, if one doesn't have cancer, the test will incorrectly say that one does, % of the time (one
out of 200).
NOTE: For each of the following questions, please give each answer to at least 2 signi¦cant digit
accuracy. To accomplish this, don't round off your results until the very last step of each
calculation.
Problem 1 - Bayes' Theorem
12
a. What's the probability that someone picked at random has this form of
cancer?
[YOUR ANSWER HERE]
b. If you take the test and it comes out positive, what is the probability that
you have this form of cancer?
[YOUR ANSWER HERE]
2020/11/19 Copy of CSE 140 - Assignment 4.ipynb - Colaboratory
2/8
c. If you take the test and it comes out negative, what is the probability that
you have this form of cancer?
[YOUR ANSWER HERE]
Consider the following constraint satisfaction problem. A linear graph has nodes of the
following colors:
Red
Yellow
Green
Blue
Violet
Each node has a domain of {1, 2, ..., 9}.
Each node type has the following constraints on its value:
Red - No contraints
Yellow - equals the rightmost digit of of the product of all its neighbors
Green - equals the rightmost digit of the sum of all its neighbors
Blue - equals the leftmost digit of the sum of all its neighbors
Violet - equals the leftmost digit of the product of all of its neighbors
As a reminder here is the pseudo code for the Min-Con§icts search algorithm:
Notes:
Problem 2 - CSP
2020/11/19 Copy of CSE 140 - Assignment 4.ipynb - Colaboratory
3/8
It's possible that you won't converge to a solution in a single run. Try a few runs to see if
you get to a solution.
The example is to show you what a problem looks like, we will test/grade your program on
different examples
Complete the function solve_csp de¦ned below. You may ¦nd some helper functions useful.
def solve_csp(nodes, arcs, max_steps):
"""
This function solves the csp using the MinConflicts Search Algorithm.
INPUTS:
nodes: a list of letters that indicates what type of node it is,
the index of the node in the list indicates its id
letters = {R, Y, G, B, V}
arcs: a list of tuples that contains two numbers, indicating the
IDs of the nodes the arc connects.
max_steps: max number of steps to make before giving up
RETURNS: a list of values for the solution to the CSP where the
index of the value corresponds the value for that
given node.
"""
node_values = []
return node_values
Below we've included 4 test cases to help you debug your code. Your submitted code will be
tested on other cases as well, but if your implementation of the above Min-Con§icts search
algorithm is able to solve these problems, you should be good to go.
Test Cases
# Test Case 1
nodes = 'YGVRB'
arcs = [(0,1), (0,2), (1,2), (1,3), (1,4), (2,3), (2,4)]
max_steps = 1000
for _ in range(max_steps):
sol = solve_csp(nodes, arcs, max_steps)
if sol != []:
break
all_solutions = [[1, 1, 1, 7, 2],[2, 1, 2, 4, 3],[2, 6, 7, 6, 1],[2, 8, 9, 6, 1],
[3, 3, 1, 5, 4],[6, 2, 8, 7, 1],[6, 7, 8, 2, 1],[6,
if sol == []:
2020/11/19 Copy of CSE 140 - Assignment 4.ipynb - Colaboratory
4/8
---------------------------------------------------------------------------
NameError Traceback (most recent call last)
in ()
6
7 for _ in range(max_steps):
----> 8 sol = solve_csp(nodes, arcs, max_steps)
9 if sol != []:
10 break
NameError: name 'solve_csp' is not defined
SEARCH STACK OVERFLOW
print('No solution')
else:
if sol in all_solutions:
print('Solution found:', sol)
else:
print('ERROR: False solution found:', sol)
# Test Case 2
nodes = 'YVBGR'
arcs = [(0,1), (0,2), (1,3), (2,4)]
max_steps = 1000
for _ in range(max_steps):
sol = solve_csp(nodes, arcs, max_steps)
if sol != []:
print(nodes)
break
all_solutions = [[1, 1, 1, 1, 9], [1, 3, 7, 3, 6], [1, 7, 3, 7, 2], [1, 9, 9, 9
if sol == []:
print('No solution')
else:
if sol in all_solutions:
print('Solution found:', sol)
else:
print('ERROR: False solution found:', sol)
No solution
# Test Case 3
nodes = 'VYGBR'
arcs = [(0,1), (1,2), (2,3), (3,4)]
max_steps = 1000
for _ in range(max_steps):
sol = solve_csp(nodes, arcs, max_steps)
if sol != []:
print(nodes)
2020/11/19 Copy of CSE 140 - Assignment 4.ipynb - Colaboratory
5/8
break
all_solutions = [[2, 2, 1, 9, 8],[3, 3, 1, 8, 7],[4, 4, 1, 7, 6],[5, 5, 1, 6, 5],
[6, 6, 1, 5, 4],[7, 7, 1, 4, 3],[8, 8, 1, 3, 2],[8,
if sol == []:
print('No solution')
else:
if sol in all_solutions:
print('Solution found:', sol)
else:
print('ERROR: False solution found:', sol)
No solution
# Test Case 4
nodes = 'YGVBR'
arcs = [(0,1), (0,2), (1,3), (2,3), (3,4), (1,2)]
max_steps = 1000
for _ in range(max_steps):
sol = solve_csp(nodes, arcs, max_steps)
if sol != []:
print(nodes)
break
all_solutions = [[4, 4, 1, 9, 4],[4, 7, 2, 1, 1],[4, 7, 2, 1, 2],[4, 7, 2, 1, 3],
[4, 7, 2, 1, 5],[4, 7, 2, 1, 6],[4, 7, 2, 1, 7],[4,
[4, 8, 3, 1, 1],[4, 8, 3, 1, 2],[4, 8, 3, 1, 3],[4,
[4, 8, 3, 1, 6],[4, 8, 3, 1, 7],[4, 8, 3, 1, 8],[5,
[5, 1, 5, 1, 6],[5, 1, 5, 1, 7],[5, 1, 5, 1, 8],[5,
if sol == []:
print('No solution')
else:
if sol in all_solutions:
print('Solution found:', sol)
else:
print('ERROR: False solution found:', sol)
No solution
Rooks can move any number of squares horizontally or vertically on a chess board. The n rooks
problem is to arrange rooks on an board in such a way that none of the rooks could bump
into another by making any of its possible horizontal or vertical moves.
For this problem, the variables are each column (labeled 0, 1, ... , ), the the domain
consists of each possible row (also labeled 0, 1, ... , ). In each column we place a rook on
Problem 3 - the n rooks problem
n × n n − 1 n − 1
2020/11/19 Copy of CSE 140 - Assignment 4.ipynb - Colaboratory
6/8 row 0, row 1, ... , row . For example, if we have only two solutions to this problem:
R @ @ R
or
@ R R @
a. How many possible solutions are there to this CSP, in terms of n?
Also, give a simple proof that your answer is correct.
n − 1 n = 2
[YOUR ANSWER HERE]
One useful Python module for solving these types of problems is called constraint. In the next
cell you'll see how to load this module into a Jupyter notebook running in Colab.
We'll use this module to solve the following simple CSP. Suppose our variables are x and y, and
the values they are allowed to assume are numbers in the domain {1, 2, ... , 100}, and with
constraints be that and that is odd.
Python Library to solve CSPs
x = y 2 x
# The following line imports the constraint module into a Jupyter notebook running in
# (This only needs to be done once per session)
!pip install python-constraint
# Let's load all the functions available in this module
# (This only needs to be done once per session)
from constraint import *
# Now we initialize a new problem and add the two variables.
problem = Problem()
problem.addVariables(["x", "y"], list(range(1, 101)))
# So far there are no constraints. If we solve the problem with no constraints,
# then every possible combination of x and y values from 1 to 100 are valid solutio
solutions = problem.getSolutions()
# Total number of solutions
print( len(solutions) )
Requirement already satisfied: python-constraint in /home/rafa/anaconda3/lib/python3.6/site-p
10000
2020/11/19 Copy of CSE 140 - Assignment 4.ipynb - Colaboratory
7/8
# Add the given constraints:
problem.addConstraint(lambda a, b: a**2 == b and (a % 2) == 1, ("x", "y"))
# There are only 5 solutions that satisfy those constraints:
solutions = problem.getSolutions()
print( len(solutions) )
5
# Here are all 5 solutions:
print(solutions)
[{'x': 9, 'y': 81}, {'x': 7, 'y': 49}, {'x': 5, 'y': 25}, {'x': 3, 'y': 9}, {'x': 1, 'y': 1}]
Notice that the solutions consist of a list of dictionaries, where each dictionary represents a
solution. For example, the ¦rst solution is {'x': 9, 'y': 81}, since with and it's true
that . x = 9 y = 81 x = y 2
b. Modify the example before to solve the n rooks problem.
The n-rooks problem revisited
# YOUR CODE HERE
40320
c. How many ways are there of arranging rooks on an board so that none impede the
others?
d. How many ways are there arranging rooks on an board so that none impede the
others?
8 8 × 8 11 11 × 11
c. [YOUR ANSWER HERE]
d. [YOUR ANSWER HERE]