WARNING: THIS IS THE OLD ALGOLAB WEBSITE FOR ACADEMIC YEAR 2016-17.
NEW WEBSITE IS AT: sciprog.davidleoni.it
In [1]:
import algolab
algolab.init()
Out[1]:
Exam Simulation

Scientific Programming Algolab

Wednesday 21 Dec 2016

Introduction

  • This is just an exam simulation. If you don't ship it or do a poor work, you lose nothing. If you make a good work, you earn nothing.
  • To make you feel more comfortable, all what you produce and submission process will be completely anonymous
  • Anonymous doesn't imply private. In fact, in this simulation, the work will be made public and corrections will be public as well. The anonimity means your work and corrections won't be associated to your name or student id.
  • So don't put your name or id number around in the files ;-)

Allowed material

Real exam will be in the lab with restricted internet access. You will only be able to access:

You won't be able to use anything else, in particular:

  • no Google
  • no StackOverflow

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.

Grading

  • We need still need to define a grading system for the exam. Here we just put provisional rules.
  • Correct implementations with the required complexity grant you full grade.
  • One extra point can be earned by writing stylish code. You got style if you:

    • do not infringe the Commandments
    • write pythonic code
    • avoid convoluted code like i.e.

        if x > 5:
            return True
        else:
            return False

      when you could write just

        return x > 5
In [2]:
%%HTML

<p class="algolab-warn">

!!!!!!!!! WARNING !!!!!!!!!
    
    <br/>
    <br/>
!!!!!!!!!  **ONLY** IMPLEMENTATIONS OF THE PROVIDED FUNCTION SIGNATURES WILL BE EVALUATED !!!!!!!!! <br/>    

</p>

!!!!!!!!! WARNING !!!!!!!!!

!!!!!!!!! **ONLY** IMPLEMENTATIONS OF THE PROVIDED FUNCTION SIGNATURES WILL BE EVALUATED !!!!!!!!!

For example, if you are given to implement:

def cool_fun(x):
        raise Exception("TODO implement me")

and you ship this code:

def cool_fun_non_working_trial(x):
    # do some absurdity

def cool_fun_a_perfectly_working_trial(x):
    # a super fast, correct and stylish implementation

def cool_fun(x):
    raise Exception("TODO implement me")

We will assess only the latter one cool_fun(x), and conclude it doesn't work at all :P !!!!!!!

Still, you are allowed to define any extra helper function you might need. If your cool_fun(x) implementation calls some other function you defined like my_helper here, it is ok:

def my_helper(y,z):
    # do something useful

def cool_fun(x):
    my_helper(x,5)

# this will get ignored:
def some_trial(x):
    # do some absurdity

What to do

1) Download this zip and extracts its contents on your disk. You will see a folder like this:

exam
|- exercise1.py
|- exercise2.py

2) Edit the files following the instructions in this worksheet for each exercise.

In [3]:
%%HTML 

<p class="algolab-warn">
WARNING: <i>DON'T</i> modify function signatures! Just provide the implementation.
</p>

<p class="algolab-warn">
WARNING: <i>DON'T</i> change the existing test methods, just add new ones !!!  You can add as many as you want.
</p>

<p class="algolab-warn">
WARNING: <i>DON'T</i> create other files. If you still do it, they won't be evaluated.
</p>

<p class="algolab-important">
IMPORTANT: Pay close attention to the comments of the functions.
</p>

WARNING: DON'T modify function signatures! Just provide the implementation.

WARNING: DON'T change the existing test methods, just add new ones !!! You can add as many as you want.

WARNING: DON'T create other files. If you still do it, they won't be evaluated.

IMPORTANT: Pay close attention to the comments of the functions.

3) Every exercise should take max 25 mins. If it takes longer, leave it and try another exercise.

4) When you're done, proceed with the submission

Submission

1) Zip your files into a file named exam.zip

2) Upload the zip to file.io

2) After the upload you should see a download link (something like https://file.io/C40YFy)

3) Copy paste the link into the common ethercalc here:

https://ethercalc.org/2sp752kuzqqy

In [4]:
%%HTML

<p class="algolab-warn">
WARNING: REMEMBER TO WRITE SOMEWHERE (IN YOUR COMPUTER OR ON PAPER) YOUR DOWNLOAD LINK, OTHERWISE IT 
    WILL BE HARD FOR YOU TO UNDERSTAND WHICH ZIP WAS CORRECTED.
</p>

WARNING: REMEMBER TO WRITE SOMEWHERE (IN YOUR COMPUTER OR ON PAPER) YOUR DOWNLOAD LINK, OTHERWISE IT WILL BE HARD FOR YOU TO UNDERSTAND WHICH ZIP WAS CORRECTED.

Exercises

1) insertion sort

Insertion sort is a basic sorting algorithm. This animation gives you an idea of how it works:

Here is the pseudo code:

In [5]:
%%HTML

<p class="algolab-warn">
WARNING: The following pseudo code contains a bug (just one!).
</p>

<p class="algolab-important">
IMPORTANT: <br/>
    Array <i>A</i> in the pseudo code has indexes starting from zero included. <br/>
    <i>n</i> is the length of the input array.
</p>

WARNING: The following pseudo code contains a bug (just one!).

IMPORTANT:
Array A in the pseudo code has indexes starting from zero included.
n is the length of the input array.

Start editing the file exercise1.py:

1.1) insertion_sort

Implement in Python the pseudocode for insertion_sort. Make sure at least the provided tests pass (they won't check for the bug).

1.2) Fixing insertion_sort

We said the given pseudo code has a bug. Write additional test cases that show where the bug is, and then fix the code accordingly.

In [6]:
%%HTML

<p class="algolab-warn">
WARNING: <i>DON'T</i> modify function signatures! Just provide the implementation.
</p>

<p class="algolab-warn">
WARNING: <i>DON'T</i> change the existing test methods, just add new ones !!!  You can add as many as you want.
</p>

<p class="algolab-important">
IMPORTANT: Pay close attention to the comments of the functions.
</p>

WARNING: DON'T modify function signatures! Just provide the implementation.

WARNING: DON'T change the existing test methods, just add new ones !!! You can add as many as you want.

IMPORTANT: Pay close attention to the comments of the functions.

2) UnorderedList

We are going to have some more fun with good old UnorderedList, which is a monodirectional linked list.

Start editing the file exercise2.py:

2.1) rev(self)

Implement the method rev(self) that you find in the skeleton and check provided tests pass.

2.2) copy(self)

Implement the method copy(self) that you find in the skeleton and check provided tests pass.