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

https://colab.research.google.com/drive/1C-ZUmWOuhOi6Rh1_vmyy6hn3Zplh3fAr?authuser=1#scrollTo=nBzBpOscZ7q5&printMode=true 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

https://colab.research.google.com/drive/1C-ZUmWOuhOi6Rh1_vmyy6hn3Zplh3fAr?authuser=1#scrollTo=nBzBpOscZ7q5&printMode=true 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

https://colab.research.google.com/drive/1C-ZUmWOuhOi6Rh1_vmyy6hn3Zplh3fAr?authuser=1#scrollTo=nBzBpOscZ7q5&printMode=true 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

https://colab.research.google.com/drive/1C-ZUmWOuhOi6Rh1_vmyy6hn3Zplh3fAr?authuser=1#scrollTo=nBzBpOscZ7q5&printMode=true 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

https://colab.research.google.com/drive/1C-ZUmWOuhOi6Rh1_vmyy6hn3Zplh3fAr?authuser=1#scrollTo=nBzBpOscZ7q5&printMode=true 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

https://colab.research.google.com/drive/1C-ZUmWOuhOi6Rh1_vmyy6hn3Zplh3fAr?authuser=1#scrollTo=nBzBpOscZ7q5&printMode=true 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]