Algorithms and Complexity

First homework

For each of the three pseudocodes bellow, determine how the input size must be measured, find the worst and best-case time complexity, and write a Python script that implements the pseudocode and runs it for each input of the respective input file.

Each Python script must read the ten lines of the respective input file, run the implemented function for each of these ten inputs, and print the time (in seconds) used to run it for each input (therefore, the output must consist of ten lines).

In order to measure the time, proceed as follows:

• - Import the function to measure the time: from timeit import default_timer as time


• - Call the function time immediately before and immediatley after running your function:


• start = time()
  your_function()
  end = time()
  


• - Subtract these values to obtain the time:


• print "%d seconds." % (end - start)

The three pseudocodes and their inputs are the following:

• § Naive Three Partition Finder: Pseudocode and input file.


• § Less Naive Three Partition Finder: Pseudocode and input file.


• § Naive Primality Test: Pseudocode and input file.

You must submit four files: the three Python scripts and a PDF in which you show how you have defined the input size and what are the time complexities. This PDF must also contain three tables (with ten rows and two columns each) relating the inputs' size and the seconds printed by your Python scripts.

To submit, attach them to an e-mail whose subject must be [ALGORITHMS2018] YOUR NAME and send it to vitor dot pereira at uni dot lu.

For example, if your name is Caetano Veloso, then you must send me an e-mail with the subject [ALGORITHMS2018] Caetano Veloso.

The deadline for this homework is October 4th, 2018.

Good luck.