# Midterm B - Fri 20, Dec 2019¶

Scientific Programming - Data Science @ University of Trento

## Introduction¶

You can take this midterm ONLY IF you got grade >= 16 in Part A midterm.

### What to do¶

1. Download sciprog-ds-2019-12-20-exam.zip and extract it on your desktop. Folder content should be like this:

sciprog-ds-2019-12-20-FIRSTNAME-LASTNAME-ID
exam-2019-12-20.ipynb
theory.txt
bin_tree.py
bin_tree_test.py
jupman.py
sciprog.py

1. Rename sciprog-ds-2019-12-20-FIRSTNAME-LASTNAME-ID folder: put your name, lastname an id number, like sciprog-ds-2019-12-20-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. Every exercise should take max 25 mins. If it takes longer, leave it and try another exercise.

2. When done:

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

## B1 Theory¶

Write the solution in separate theory.txt file

### B1.1 Complexity¶

Given a list 𝐿 of 𝑛 elements, please compute the asymptotic computational complexity of the following function, explaining your reasoning.

def my_fun(L):
R = 0
for i in range(len(L)):
for j in range(len(L)-1,0,-1):
k = 0
while k < 4:
R = R + L[j] - L[i]
k += 1
return R


### B1.2 Data structure choice¶

Given an algorithm that frequently checks the presence of an element in its internal data structure. Please briefly answer the following questions:

1. What data structure would you choose? Why?

2. In case entries are sorted, would you use the same data structures?

Open a text editor and edit file linkedlist.py

You are given a LinkedList holding pointers _head, _last, and also _size attribute.

Notice the list also holds _last and _size attributes !!!

## B2.1 rotate¶

✪✪ Implement this method:

def rotate(self):
""" Rotate the list of 1 element, that is, removes last node and
inserts it as the first one.

- MUST execute in O(n) where n is the length of the list
- Remember to also update _last pointer
- WARNING: DO *NOT* try to convert whole linked list to a python list
- WARNING: DO *NOT* swap node data or create nodes, I want you to
"""


Testing: python3 -m unittest linked_list_test.RotateTest

Example:

[2]:

from linked_list_sol import *

[3]:


print(ll)

LinkedList: a,b,c,d

[4]:

ll.rotate()

[5]:

print(ll)

LinkedList: d,a,b,c


## B2.2 rotaten¶

✪✪✪ Implement this method:

def rotaten(self, k):
""" Rotate k times the linkedlist

- k can range from 0 to any positive integer number (even greater than list size)
- if k < 0 raise ValueError

- MUST execute in O( n-(k%n) ) where n is the length of the list
- WARNING: DO *NOT* call .rotate() k times !!!!
- WARNING: DO *NOT* try to convert whole linked list to a python list
- WARNING: DO *NOT* swap node data or create nodes, I want you to
"""


Testing: python3 -m unittest linked_list_test.RotatenTest

IMPORTANT HINT

The line “MUST execute in O( n-(k%n) ) where n is the length of the list” means that you have to calculate m = k%n, and then only scan first n-m nodes!

Example:

[6]:

ll = LinkedList()
print(ll)

LinkedList: a,b,c,d,e,f,g,h

[7]:

ll.rotaten(0)  # changes nothing

[8]:

print(ll)

LinkedList: a,b,c,d,e,f,g,h

[9]:

ll.rotaten(3)

[10]:

print(ll)

LinkedList: f,g,h,a,b,c,d,e

[11]:

ll.rotaten(8)  # changes nothing

[12]:

print(ll)

LinkedList: f,g,h,a,b,c,d,e

[13]:

ll.rotaten(5)

[14]:

print(ll)

LinkedList: a,b,c,d,e,f,g,h

[15]:

ll.rotaten(11)  # 11 = 8 + 3 , only rotates 3 nodes

[16]:

print(ll)

LinkedList: f,g,h,a,b,c,d,e


## B3 Binary trees¶

We will now go looking for leaves, that is, nodes with no children. Open bin_tree.

[17]:

from bin_tree_test import bt
from bin_tree_sol import *


## B3.1 sum_leaves_rec¶

✪✪ Implement this method:

def sum_leaves_rec(self):
""" Supposing the tree holds integer numbers in all nodes,
RETURN the sum of ONLY the numbers in the leaves.

- a root with no children is considered a leaf
- implement it as a recursive Depth First Search (DFS) traversal
NOTE: with big trees a recursive solution would surely
exceed the call stack, but here we don't mind
"""


Testing: python3 -m unittest bin_tree_test.SumLeavesRecTest

Example:

[18]:

t = bt(3,
bt(10,
bt(1),
bt(7,
bt(5))),
bt(9,
bt(6,
bt(2,
None,
bt(4)),
bt(8))))

t.sum_leaves_rec()  #  1 + 5 + 4 + 8

[18]:

18


## B3.2 leaves_stack¶

✪✪✪ Implement this method:

def leaves_stack(self):
""" RETURN a list holding the *data* of all the leaves  of the tree,
in left to right order.

- a root with no children is considered a leaf
- DO *NOT* use recursion
- implement it with a while and a stack (as a Python list)
"""


Testing: python3 -m unittest bin_tree_test.LeavesStackTest

Example:

[19]:


t = bt('a',
bt('b',
bt('c'),
bt('d',
None,
bt('e'))),
bt('f',
bt('g',
bt('h')),
bt('i')))
t.leaves_stack()

[19]:

['c', 'e', 'h', 'i']

[ ]: