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

If you don’t have unitn login: tell instructors and we will download your work manually

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:

[2]:

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

[3]:
draw_mat(ma)
../../../_images/exams_2018-11-16_solutions_exam-2018-11-16-sol_6_0.png

And another mb like this:

[4]:
mb =  [
            [True, True, False],
            [False, False, True],
            [False, True, False]

      ]
[5]:
draw_mat(mb)
../../../_images/exams_2018-11-16_solutions_exam-2018-11-16-sol_9_0.png

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

[19]:

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

which will be displayed as

[20]:
draw_mat(res)
../../../_images/exams_2018-11-16_solutions_exam-2018-11-16-sol_13_0.png

So we get same verteces and edges from both ma and mb

Show solution
[6]:
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)

[7]:
G1 = [
        [True, True, False, False],
        [False, False,  False, True],
        [False, True, True, False],
        [False, True, True, True],

     ]

[8]:
draw_mat(G1)
../../../_images/exams_2018-11-16_solutions_exam-2018-11-16-sol_21_0.png

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:

[9]:
G2 = [
        [True, True, False, False],
        [False, False,  False, True],
        [False, True, False, False],
        [False, True, False, False],

     ]

[10]:
draw_mat(G2)
../../../_images/exams_2018-11-16_solutions_exam-2018-11-16-sol_24_0.png
Show solution
[11]:
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

[12]:
da =  {
          'a':['a','c'],
          'b':['b', 'c'],
          'c':['b','c']
        }
[13]:
draw_adj(da)
../../../_images/exams_2018-11-16_solutions_exam-2018-11-16-sol_32_0.png

and

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

[15]:
draw_adj(db)
../../../_images/exams_2018-11-16_solutions_exam-2018-11-16-sol_35_0.png

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

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

Which can be shown as

[17]:
draw_adj(res)
../../../_images/exams_2018-11-16_solutions_exam-2018-11-16-sol_39_0.png
Show solution
[18]:
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']
                         }