Assignment 1

Changed 2017-08-28

NOTE: It is vital to solve problems in a course like this and I urge you to solve as many as possible. We have prepared several assignments with two problems each that you can hand in and get feedback on. But the assigments are optional, you can submit none, one or two of the problems. If you submit them we will grade them and give you feedback (and no bonuspoints are given for the exam).

Problem 1

Complexity analysis of prime(n): In the basic programming course (at least on Physics dept.) there has been a programming assignment where you generate all primes between 2..n. One simple way of doing it is to use Eratosthenes sieve: create an array 2..n filled with “true” booleans. Traverse the array and change all (elements whose indexes are) multiples of 2 to false, traverse once more and change all multiples of 3 to false, then multiples of 5 and so on up till n. The primes corresponds to the true values left in the array.

This naive solution takes O(n2) time. The solution can be improved in several ways. It's for instance enough to try primes up to sqrt(n) instead of to n and if you are marking multiples of 7 it's enough to start from 72 = 49 because all multiples between 7 and 49 must be marked already.

An algorithm for the problem could look like this:

prime: array [1..n] of boolean = all true
for p in 2..sqrt(n) loop
    if prime[p] then
        m = p*p
        while m <= n loop
            prime[m] = false
            m = m+p
        end loop
    end if
end loop
A trivial upper bound is O(n2) (or O(n*sqrt(n)) ) but empirical experiment (=running the program) suggest that the worst case complexity is even better. Analyse the program and determine it's complexity and show that it infact is better. (Use uniform cost criteria)
You should set up the sums and solve them. Don't forget to motivate what you do.

Tip: It's simpler to analyse if you rewrite the while loop to a for loop, then it's a double sum isn't it?
How to handle the statement: "if prime(p)" in worst case? You don't need to find the best complexity, you only need to show that it is better than O(n*sqrt(n)) so you could use "worst case" here and see what you get.

Submission to problem 1

The analysis in a pdf file, named as ass1.1.pdf. You should also put your names first in the pdf file. The easiest way is to prepare your solution in a word processor, like Open Office, and save it as pdf.
Handwritten math can also be submitted, take a picture and submit a jpg file. Make sure that it is readable.

Answers should be written in English.


Problem 2

The "blit" problem: can be found in a separate file.

Submission to problem 2

Same as for problem 1 but the name should be ass1.2.pdf.