LAB5 Agenda

Room

08:30- 10:30
Data Structures and Algorithms Ex C

C2.01 Lecture room, Ser-C

Agenda for Today: Assignments Discussion

• Discuss Assignment 2
• Do Assignment 3 - as you will have it on exam

• See Marks for Assignment 2

Assignment 3 ~ 30 min

• Ask students to do ex 1:

  • one does comparisons
  • one does couple of cases
  • other do the rest of cases

• Ask students to do ex 2:

  • take 3 students each for one

• Ask students to do ex 3:

Assignment 2 - ~1h

• How did you Assignment 2 and 3? Hard, easy?
• Let’s start with Assignment 2
• Do you have any questions?

Some observations:

• Test your code – check for errors, don’t waste points on that
• Try to organize it so it is readable – ask someone review it for you
• Or make an appointment with me to give a thorough feedback – there are some students that just send one file as submission or put their running time in the code.
• I try to repeat some of those issues on the Lab or in the comments – but still try to ask to improve bad habits
• I think majority of you are able to get best grades just if anticipate where is the problem in the approach and we try to sort it out together
• Every-week I have 2 hours reserved for office hours – try to use it on time

Ex 2.1

• Most of you did without problems

Ex 2.2

• Ascent in array again most of you did it efficiently

• Some of you had silly mistakes – test the code really thoroughly – it is like in math you know how to solve a complex polynomial equation but then you make error is simple calculations. How many of you had that?

• Explaining why the code is correct

• How do that?

• Is it enough if we just read the algorithm – perhaps for simple cases.
• Can we do a little bit better – try to be a more formal in words
• Attempt:
  * Start with some general observations:
  - The algorithm runs in linear time O(n) as it reads each element A at most once, thus it is efficient
  * Initially:
  - Algorithm assumes that maxAscent is 1
  * In the loop over A it changes maxAscent in the following way
  - it counts in currentSequence (=1 initially)
  as many A[i] <= A[i + 1] elements i
  - for the first i for which it doesn’t hold it stops
  - check currentSequence > maxAscent and if yes it sets
  - maxAscent := currentSequence
  - in any case it resets currentSequence to 1
  - [important] the algorithm continues counting from last i+1 as we know that A[i] and A[i+1] cannot belong to the same ascent
  - in case the max ascent was the last ascent in A we need another check (the last if)

Ex 3

]
What is an efficient algorithm? How do we know in principle?
The one with the best running Theta(f(n))
Draw a matrix
How you typically did a solution:

    INPUT: A (size n)
    OUTPUT: M

    tmpSum:=0
    for i:=1 to n do
            for j:=1 to n do
                if j < i  
                then M[i][j] = 0
                else M[i][j] = findAverage(A,i,j)

• what is the running time of this one? Theta(n^2) or Theta(n^3)
• can we do any better?

    for i:=1 to n do
            for j:=1 to n do
                if j < i  
                    then M[i][j] = 0
                    else
                        tmpSum += A[j];
                        M[i][j] = tmpSum/(j-i+1)

• test you code 5x at least – 1 pass is not enough – and then take average time:

n = 10      n = 100     n = 1000    n = 10000       n=100000
35637       10404086    523427658   239990361600    2342333455565
35637       10404086    523427658   239990361600    2342333455565
35637       10404086    523427658   239990361600    2342333455565
35637       10404086    523427658   239990361600    2342333455565
35637       10404086    523427658   239990361600    2342333455565
-----------------------------------------------------------------
35637       10404086    523427658   239990361600    2342333455565

• then take the growing ratio - estimate it (but also report it !!!)

• an example of cubic n^3

n = 10      n = 100     n = 1000    n = 10000      n=100000
10x         100x        1000x       1000000x       1000000000x

• an example of quadratic n^2

n = 10      n = 100     n = 1000    n = 10000      n=100000
10x         100x        1000x       100000x        100000000x

• at the beginning it looks linear
• do it for bigger inputs
• test it to the limit to ensure you get real performance

Assignment 2 ~ 30 min

• Grades are on-line
• *http://goo.gl/6q8T7m*
• Ask me question on that