Midterm B - Fri 20, Dec 2019

Scientific Programming - Data Science @ University of Trento

Download exercises and solution

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
    linked_list.py
    linked_list_test.py
    bin_tree.py
    bin_tree_test.py
    jupman.py
    sciprog.py

2. 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.

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/studente

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

Part B

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?

B2 LinkedList

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
                  change existing node links !!
    """

Testing: python3 -m unittest linked_list_test.RotateTest

Example:

from linked_list_sol import *

ll = LinkedList()
ll.add('d')
ll.add('c')
ll.add('b')
ll.add('a')
print(ll)

LinkedList: a,b,c,d

ll.rotate()

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
                   change node links !!
    """

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:

ll = LinkedList()
ll.add('h')
ll.add('g')
ll.add('f')
ll.add('e')
ll.add('d')
ll.add('c')
ll.add('b')
ll.add('a')
print(ll)

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

ll.rotaten(0)  # changes nothing

print(ll)

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

ll.rotaten(3)

print(ll)

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

ll.rotaten(8)  # changes nothing

print(ll)

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

ll.rotaten(5)

print(ll)

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

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

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.

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:

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

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:

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

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