# Midterm - Fri 16 Nov 2018¶

Scientific Programming - Data Science Master @ University of Trento

## Introduction¶

### What to do¶

1. Download sciprog-ds-2018-11-16-exam.zip and extract it on your desktop. Folder content should be like this:

sciprog-ds-2018-11-16-FIRSTNAME-LASTNAME-ID
exam-2018-11-16.ipynb
jupman.py
sciprog.py

1. Rename sciprog-ds-2018-11-16-FIRSTNAME-LASTNAME-ID folder: put your name, lastname an id number, like sciprog-ds-2018-11-16-john-doe-432432

From now on, you will be editing the files in that folder. At the end of the exam, that is what will be evaluated.

1. Edit the files following the instructions in this worksheet for each exercise.

2. When done:

if you have unitn login: zip and send to examina.icts.unitn.it

### A1 union¶

✪✪ When we talk about the union of two graphs, we intend the graph having union of verteces of both graphs and having as edges the union of edges of both graphs. In this exercise, we have two graphs as list of lists with boolean edges. To simplify we suppose they have the same vertices but possibly different edges, and we want to calculate the union as a new graph.

For example, if we have a graph ma like this:

:


ma =  [
[True, False, False],
[False, True, False],
[True, False, False]
]


:

draw_mat(ma) And another mb like this:

:

mb =  [
[True, True, False],
[False, False, True],
[False, True, False]

]

:

draw_mat(mb) The result of calling union(ma, mb) will be the following:

:


res = [[True, True, False], [False, True, True], [True, True, False]]



which will be displayed as

:

draw_mat(res) So we get same verteces and edges from both ma and mb

Show solution
:

def union(mata, matb):
""" Takes two graphs represented as nxn matrices of lists of lists with boolean edges,
and RETURN a NEW matrix which is the union of both graphs

if mata row number is different from matb, raises ValueError
"""
raise Exception('TODO IMPLEMENT ME !')

try:
union([[False],[False]], [[False]])
raise Exception("Shouldn't arrive here !")
except ValueError:
"test passed"

try:
union([[False]], [[False],[False]])
raise Exception("Shouldn't arrive here !")
except ValueError:
"test passed"

ma1 =  [
[False]
]
mb1 =  [
[False]
]

assert union(ma1, mb1) == [
[False]
]

ma2 =  [
[False]
]
mb2 =  [
[True]
]

assert union(ma2, mb2) == [
[True]
]

ma3 =  [
[True]
]
mb3 =  [
[False]
]

assert union(ma3, mb3) == [
[True]
]

ma4 =  [
[True]
]
mb4 =  [
[True]
]

assert union(ma4, mb4) == [
[True]
]

ma5 =  [
[False, False, False],
[False, False, False],
[False, False, False]

]
mb5 =  [
[True, False, True],
[False, True, True],
[False, False, False]
]

assert union(ma5, mb5) == [
[True, False, True],
[False, True, True],
[False, False, False]
]

ma6 =  [
[True, False, True],
[False, True, True],
[False, False, False]
]
mb6 =  [
[False, False, False],
[False, False, False],
[False, False, False]

]

assert union(ma6, mb6) == [
[True, False, True],
[False, True, True],
[False, False, False]
]

ma7 =  [
[True, False, False],
[False, True, False],
[True, False, False]
]

mb7 =  [
[True, True, False],
[False, False, True],
[False, True, False]

]

assert union(ma7, mb7) == [
[True, True, False],
[False, True, True],
[True, True, False]

]


## A2 surjective¶

✪✪ If we consider a graph as a nxn binary relation where the domain is the same as the codomain, such relation is called surjective if every node is reached by at least one edge.

For example, G1 here is surjective, because there is at least one edge reaching into each node (self-loops as in 0 node also count as incoming edges)

:

G1 = [
[True, True, False, False],
[False, False,  False, True],
[False, True, True, False],
[False, True, True, True],

]


:

draw_mat(G1) G2 down here instead does not represent a surjective relation, as there is at least one node ( 2 in our case) which does not have any incoming edge:

:

G2 = [
[True, True, False, False],
[False, False,  False, True],
[False, True, False, False],
[False, True, False, False],

]


:

draw_mat(G2) Show solution
:

def surjective(mat):
""" RETURN True if provided graph mat as list of boolean lists is an
nxn surjective binary relation, otherwise return False
"""
raise Exception('TODO IMPLEMENT ME !')

m1 =  [
[False]
]

assert surjective(m1) == False

m2 =  [
[True]
]

assert surjective(m2) == True

m3 =  [
[True, False],
[False, False],
]

assert surjective(m3) == False

m4 =  [
[False, True],
[False, False],
]

assert surjective(m4) == False

m5 =  [
[False, False],
[True, False],
]

assert surjective(m5) == False

m6 =  [
[False, False],
[False, True],
]

assert surjective(m6) == False

m7 =  [
[True, False],
[True, False],
]

assert surjective(m7) == False

m8 =  [
[True, False],
[False, True],
]

assert surjective(m8) == True

m9 =  [
[True, True],
[False, True],
]

assert surjective(m9) == True

m10 = [
[True, True, False, False],
[False, False,  False, True],
[False, True, False, False],
[False, True, False, False],

]
assert surjective(m10) == False

m11 = [
[True, True, False, False],
[False, False,  False, True],
[False, True, True, False],
[False, True, True, True],

]
assert surjective(m11) == True


### A3 ediff¶

✪✪✪ The edge difference of two graphs ediff(da,db) is a graph with the edges of the first except the edges of the second. For simplicity, here we consider only graphs having the same verteces but possibly different edges. This time we will try operate on graphs represented as dictionaries of adjacency lists.

For example, if we have

:

da =  {
'a':['a','c'],
'b':['b', 'c'],
'c':['b','c']
}

:

draw_adj(da) and

:

db =  {
'a':['c'],
'b':['a','b', 'c'],
'c':['a']
}


:

draw_adj(db) The result of calling ediff(da,db) will be:

:

res = {
'a':['a'],
'b':[],
'c':['b','c']
}


Which can be shown as

:

draw_adj(res) Show solution
:

def ediff(da,db):
"""  Takes two graphs as dictionaries of adjacency lists da and db, and
RETURN a NEW graph as dictionary of adjacency lists, containing the same vertices of da,
and the edges of da except the edges of db.

- As order of elements within the adjacency lists, use the same order as found in da.
- We assume all verteces in da and db are represented in the keys (even if they have
no outgoing edge), and that da and db have the same keys

EXAMPLE:

da =  {
'a':['a','c'],
'b':['b', 'c'],
'c':['b','c']
}

db =  {
'a':['c'],
'b':['a','b', 'c'],
'c':['a']
}

assert ediff(da, db) == {
'a':['a'],
'b':[],
'c':['b','c']
}

"""
raise Exception('TODO IMPLEMENT ME !')

da1 =  {
'a': []
}
db1 =  {
'a': []
}

assert ediff(da1, db1) ==   {
'a': []
}

da2 =  {
'a': []
}

db2 =  {
'a': ['a']
}

assert ediff(da2, db2) == {
'a': []
}

da3 =  {
'a': ['a']
}
db3 =  {
'a': []
}

assert ediff(da3, db3) ==   {
'a': ['a']
}

da4 =  {
'a': ['a']
}
db4 =  {
'a': ['a']
}

assert ediff(da4, db4) == {
'a': []
}
da5 =  {
'a':['b'],
'b':[]
}
db5 =  {
'a':['b'],
'b':[]
}

assert ediff(da5, db5) == {
'a':[],
'b':[]
}

da6 =  {
'a':['b'],
'b':[]
}
db6 =  {
'a':[],
'b':[]
}

assert ediff(da6, db6) == {
'a':['b'],
'b':[]
}

da7 =  {
'a':['a','b'],
'b':[]
}
db7 =  {
'a':['a'],
'b':[]
}

assert ediff(da7, db7) == {
'a':['b'],
'b':[]
}

da8 =  {
'a':['a','b'],
'b':['a']
}
db8 =  {
'a':['a'],
'b':['b']
}

assert ediff(da8, db8) == {
'a':['b'],
'b':['a']
}

da9 =  {
'a':['a','c'],
'b':['b', 'c'],
'c':['b','c']
}

db9 =  {
'a':['c'],
'b':['a','b', 'c'],
'c':['a']
}

assert ediff(da9, db9) == {
'a':['a'],
'b':[],
'c':['b','c']
}