#Please execute this cell
import sys;
sys.path.append('../../');
import jupman;
Data Science @ University of Trento
Bonus point: One bonus point can be earned by writing stylish code. You got style if you:
avoid convoluted code like i.e.
if x > 5:
return True
else:
return False
when you could write just
return x > 5
For example, if you are given to implement:
def f(x):
raise Exception("TODO implement me")
and you ship this code:
def my_f(x):
# a super fast, correct and stylish implementation
def f(x):
raise Exception("TODO implement me")
We will assess only the latter one f(x)
, and conclude it doesn't work at all :P !!!!!!!
Helper functions
Still, you are allowed to define any extra helper function you might need. If your f(x)
implementation calls some other function you defined like my_f
here, it is ok:
# Not called by f, will get ignored:
def my_g(x):
# bla
# Called by f, will be graded:
def my_f(y,z):
# bla
def f(x):
my_f(x,5)
To edit the files, you can use any editor of your choice, you can find them under Applications->Programming:
To run the tests, use the Terminal which can be found in Accessories -> Terminal
If you need to print some debugging information, you are allowed to put extra print
statements in the function bodies.
For example, avoid stuff like this:
x = 0
print(1/x)
1) Download datasciprolab-2019-01-10-exam.zip
and extract it on your desktop. Folder content should be like this:
datasciprolab-2019-01-10-FIRSTNAME-LASTNAME-ID
|-jupman.py
|-sciprog.py
|-other stuff ...
|-exams
|-2019-01-10
|- gaps_exercise.py
|- gaps_test.py
|- tasks_exercise.py
|- tasks_test.py
|- exits_exercise.py
|- exits_test.py
|- other stuff ...
2) Rename datasciprolab-2019-01-10-FIRSTNAME-LASTNAME-ID
folder: put your name, lastname an id number, like datasciprolab-2019-01-10-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.
3) Edit the files following the instructions in this worksheet for each exercise. Every exercise should take max 25 mins. If it takes longer, leave it and try another exercise.
4) 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
Please write the solution in the text file theory.txt
Given the following function:
def fun(N, M):
S1 = set(N)
S2 = set(M)
res = []
for x in S1:
if x in S2:
for i in range(N.count(x)):
res.append(x)
return res
let N
and M
be two lists of length n
and m
, respectively. What is the computational complexity of function fun()
with respect to n
and m
?
Given a linked list of size n which only contains integers, a gap is an index i
, 0<i<n
, such that L[i−1]<L[i]
.
For the purpose of this exercise, we assume an empy list or a list with one element have zero gaps
Example:
data: 9 7 6 8 9 2 2 5
index: 0 1 2 3 4 5 6 7
contains three gaps [3,4,7] because:
Open file gaps_exercise.py
and implement this method:
def gaps(self):
""" Assuming all the data in the linked list is made by numbers,
finds the gaps in the LinkedList and return them as a Python list.
- we assume empty list and list of one element have zero gaps
- MUST perform in O(n) where n is the length of the list
NOTE: gaps to return are *indeces* , *not* data!!!!
"""
Testing: python3 -m unittest gaps_test.GapsTest
Very often, you begin to do a task just to discover it requires doing 3 other tasks, so you start carrying them out one at a time and discover one of them actually requires to do yet another two other subtasks....
To represent the fact a task may have subtasks, we will use a dictionary mapping a task label to a list of subtasks, each represented as a label. For example:
subtasks = {
'a':['b','g'],
'b':['c','d','e'],
'c':[],
'd':['f'],
'e':[],
'f':[],
'g':[]
}
Task a
requires subtasks b
andg
to be carried out (in this order), but task b
requires subtasks c
, ð
and e
to be done. c
requires no further tasks, while d
requires to f
.
You will have to implement a function called do
and use a Stack data structure, which is already provided and you don't need to implement. Let's see an example of execution.
IMPORTANT: In the execution example, there are many prints just to help you understand what's going on, but the only thing we actually care about is the final list returned by the function!
IMPORTANT: notice subtasks are scheduled in reversed order, so the item on top of the stack will be the first to get executed !
from tasks_solution import *
do('a', subtasks)
The Stack
you must use is simple and supports push
, pop
, and is_empty
operations:
s = Stack()
print(s)
s.is_empty()
s.push('a')
print(s)
s.push('b')
print(s)
s.pop()
print(s)
Now open tasks_stack_exercise.py
and implement function do
:
def do(task, subtasks):
""" Takes a task to perform and a dictionary of subtasks,
and RETURN a list of performed tasks
- To implement it, inside create a Stack instance and a while cycle.
- DO *NOT* use a recursive function
- Inside the function, you can use a print like "I'm doing task a',
but that is only to help yourself in debugging, only the
list returned by the function will be considered in the evaluation!
"""
Testing: python3 -m unittest tasks_test.DoTest
In this exercise, you are asked to implement a slightly more complex version of the previous function where on the Stack
you push two-valued tuples, containing the task label and the associated level. The first task has level 0, the immediate subtask has level 1, the subtask of the subtask has level 2 and so on and so forth. In the list returned by the function, you will put such tuples.
One possibile use is to display the executed tasks as an indented tree, where the indentation is determined by the level. Here we see an example:
IMPORTANT: Again, the prints are only to let you understand what's going on, and you are not required to code them. The only thing that really matters is the list the function must return !
subtasks = {
'a':['b','g'],
'b':['c','d','e'],
'c':[],
'd':['f'],
'e':[],
'f':[],
'g':[]
}
do_level('a', subtasks)
Now implement the function:
def do_level(task, subtasks):
""" Takes a task to perform and a dictionary of subtasks,
and RETURN a list of performed tasks, as tuples (task label, level)
- To implement it, use a Stack and a while cycle
- DO *NOT* use a recursive function
- Inside the function, you can use a print like "I'm doing task a',
but that is only to help yourself in debugging, only the
list returned by the function will be considered in the evaluation
"""
Testing: python3 -m unittest tasks_test.DoLevelTest
There is a place nearby Trento called Silent Hill, where people always study and do little else. Unfortunately, one day an unethical biotech AI experiment goes wrong and a buggy cyborg is left free to roam in the building. To avoid panic, you are quickly asked to devise an evacuation plan. The place is a well known labyrinth, with endless corridors also looping into cycles. But you know you can model this network as a digraph, and decide to represent crossings as nodes. When a crossing has a door to leave the building, its label starts with letter e
, while when there is no such door the label starts with letter n
.
In the example below, there are three exits e1
, e2
, and e3
. Given a node, say n1
, you want to tell the crowd in that node the shortest paths leading to the three exits. To avoid congestion, one third of the crowd may be told to go to e2
, one third to reach e1
and the remaining third will go to e3
even if they are farther than e2
.
In python terms, we would like to obtain a dictionary of paths like the following, where as keys we have the exits and as values the shortest sequence of nodes from n1
leading to that exit
{
'e1': ['n1', 'n2', 'e1'],
'e2': ['n1', 'e2'],
'e3': ['n1', 'e2', 'n3', 'e3']
}
from sciprog import draw_dig
from exits_test import dig
from exits_solution import *
G = dig({'n1':['n2','e2'],
'n2':['e1'],
'e1':['n1'],
'e2':['n2','n3', 'n4'],
'n3':['e3'],
'n4':['n1']})
draw_dig(G)
You will solve the exercise in steps, so open exits_solution.py
and proceed reading the following points.
Implement this method
def cp(self, source):
""" Performs a BFS search starting from provided node label source and
RETURN a dictionary of nodes representing the visit tree in the
child-to-parent format, that is, each key is a node label and as value
has the node label from which it was discovered for the first time
So if node "n2" was discovered for the first time while
inspecting the neighbors of "n1", then in the output dictionary there
will be the pair "n2":"n1".
The source node will have None as parent, so if source is "n1" in the
output dictionary there will be the pair "n1": None
NOTE: This method must *NOT* distinguish between exits
and normal nodes, in the tests we label them n1, e1 etc just
because we will reuse in next exercise
NOTE: You are allowed to put debug prints, but the only thing that
matters for the evaluation and tests to pass is the returned
dictionary
"""
Testing: python3 -m unittest exits_test.CpTest
Example:
G.cp('n1')
Basically, the dictionary above represents this visit tree:
n1
/ \
n2 e2
\ / \
e1 n3 n4
|
e3
Implement this function. NOTE: the function is external to class DiGraph.
def exits(cp):
"""
INPUT: a dictionary of nodes representing a visit tree in the
child-to-parent format, that is, each key is a node label and as value
has its parent as a node label. The root has associated None as parent.
OUTPUT: a dictionary mapping node labels of exits to the shortest path
from the root to the exit (root and exit included)
"""
Testing: python3 -m unittest exits_test.ExitsTest
Example:
# as example we can use the same dictionary outputted by the cp call in the previous exercise
visit_cp = { 'e1': 'n2',
'e2': 'n1',
'e3': 'n3',
'n1': None,
'n2': 'n1',
'n3': 'e2',
'n4': 'e2'
}
exits(visit_cp)
#ignore this cell
#import exits_test
#jupman.run(exits_test)
#ignore this cell
#import tasks_test
#jupman.run(tasks_test)