Exams¶

See exams schedule on Alberto Montresor's site

Exam modalities¶

Algolab exams are open book. You can bring a printed version of the material listed below.

Exam will take place in the lab with no internet access. You will only be able to access a folder with this documentation:

• Sciprog Algolab website
• Alberto Montresor slides
• Stefano Teso slides
• Python 2.7 documentation
  • In particular, Unittest docs
• The course book 'Problem Solving with Algorithms and Data Structures using Python'

So if you need to look up some Python function, please start today learning how to search documentation using the search functionality on Python website.

Past exams¶

See page here.

Course website¶

Theory

See Alberto Montresor website:

http://cricca.disi.unitn.it/montresor/teaching/scientific-programming

Lab

davidleoni.github.io/algolab

Chapters¶

Worksheets are meant to be used online - pdf quality is not very good, if they result unreadable please tell me

0. Testing (pdf)

1. Lists (pdf)

2 Data Structures

2.1 ComplexNumber (pdf)

2.2 Stacks and linked lists (pdf)

3. Trees (pdf)

4. Graphs (pdf)

A. Past exams

Commandments¶

def myfun(i, s, L, D):

        # You shall not do any of such evil, no matter what the type of the parameter is:
        i = 666            # basic types (int, float, ...)
        s = "666"          # strings
        L = [666]          # containers 
        D = {"evil":666}   # dictionaries

        # For the sole case of composite parameters like lists or dictionaries, 
        # you can write stuff like this IF AND ONLY IF the function specification 
        # requires you to modify the parameter internal elements (i.e. sorting a list
        # or changing a dictionary field):

        L[4] = 2          # list
        D.my_field = 5    # dictionary

This also applies to class methods. Never ever write horrors such as:

class MyClass
    def my_method(self, x, y):
        self = {a:666}  # since self is a kind of dictionary, you might be tempted to do like this
                        # but to the outside world this will bring no effect.
                        # For example, let's say somebody from outside makes a call like this:
                        #    mc = MyClass()
                        #    mc.my_method()
                        # after the call mc will not point to {a:666}
        self = ['666']  # self is only supposed to be a sort of dictionary and passed from outside
        self = 6        # self is only supposed to be a sort of dictionary and passed from outside

WRONG WRONG STUFF

my_fun() = 666
my_fun() = '666'
my_fun() = [666]

CORRECT STUFF

With the assignment operator we want to store in the left side a value from the right side, so all of these are valid operations:

x = 5
y = my_fun()
z = []
z[0] = 7
d = {}
d["a"] = 6

Function calls such as my_fun() return instead results of calculations in a box that is created just for the purpose of the call and Python will just not allow us to reuse it as a variable. So whenever you see 'name()' at the left side, it can't be possibly follewed by one equality = sign (but it can be followed by two equality signs == if you are performing a comparison).

If there is no return in the pseudocode, the function is intended to return None. In this case you don't even need to write return None, as Python will do it implicitly for you.

Slides¶

Lab 1 Slides

3 Nov 2016

Lab Goals

• Going from theory taught by Prof. Alberto Montresor to implementation
• Pseudo code --> Python

How

• Hands-on approach
• Performance considerations
• Focus on correct code
• Few Python functions

Lab Midterm?

Probably not. Still, will provide exam example.

Lab 2 Slides

Date: Nov 11th, 2016

• More practical than last time!
• Finish selection_sort and gap implementation
• midlab pause ;-)
• implement a Python class

Lab 3 Slides

Nov 17th, 2016

• Recursion
  • gap_rec, binary_search_rec
• binary_search_iter
• Will give you more tests
• Write also on paper!
• Copy exactly the same function definitions!
  • For example don't write def MY_selection_sort(A):
• use return command only if you see written return in the pseudocode!
  • If there is no return in the pseudocode, the function is intended to return None. In this case you don't even need to write return None, as Python will do it implicitly for you.

Lab 4 Slides

Nov 18th, 2016

• Divide et Impera
  • binary_search_iter
• Implement ComplexNumber ( see Chapter 2.1 )

New Commandment:

You shall never ever reassign function parameters:

def myfun(L, i, s):

    # You shall not do any of this evil:
    L = [666]
    i = 666
    s = "666"

Previous commandments:

• You shall also write on paper!
• You shall copy exactly the same function definitions as in the exercises!
• For example don't write def MY_selection_sort(A):
• You shall use return command only if you see Written return in the pseudocode!
• If there is no return in the pseudocode, the function is intended to return None. In this case you don't even need to write return None, as Python will do it implicitly for you.

Lab 5 slides

24 Nov 2016

• Implement ComplexNumber ( see Chapter 2.1 )
• Implement Stack

Lab 6 slides

1 Dic 2016

• Implement CappedStack ( see Chapter 2.2 )
• Implement UnorderedList

Lab 7 slides

• UnorderedList

Lab 8 slides

• will start writing tests (will be required during exams)
• invariants in particular
• UnorderedList ( see Chapter 2.2 ) until fast size() and append() included

Lab 9 slides

15 Dic 2016

• Implement GenericTree, see Trees chapter

Lab 10 slides

19 Dic 2016

• GenericTree see Graphs chapter

Lab 11 slides

21 Dic 2016

Exam simulation !

For exam solution, see Appendix A in Chapters

Office hours¶

You can schedule a meeting by emailing me at david.leoni [AT] unitn.it , more or less I'm available every day until 19.00

Then you will find me in Povo 1 building at DISI, in room 226 DKM :

Resources¶

• Online book: Problem Solving with Algorithms and Data Structures using Python by Brad Miller and David Ranum
• Theory slides by Alberto Montresor
• Will try to be consistent with other lab module notes of Stefano Teso and Toma Tebaldi
• PythonTutor , a visual virtual machine (very useful! can also be found in examples inside the book!)
• Source code of these worksheets (download zip), in Jupyter Notebook format.
• The internet ....

Editors¶

• Spyder: Seems like a fine and simple editor
• Jupyter Notebook: Nice environment to execute Python commands and display results like graphs. Allows to include documentation in Markdown format