Performance and Test, Spring 2008: Episode 1.1

Lecture Wednesday, January 30, 9:00—11:00, Room 3A14

Subject : Measuring Performance

Text : RS 1.0—1.1, 2.0—2.4, 2.7 Students with technical background should also read 2.5 [approx. 30 pages, expected reading time 3 hrs].

Prerequisites: Students with little programming experience should also read RS 3.0—3.2. If you are fluent in Java, feel free to skip. This is not a part of our course, but a refresher from a basic programming course.

Comments: This lecture introduces fundamental notions of modeling and analysing performance. The most important sections are 2.3—2.4. It is particularly important to fully understand the example on p.46. It is slightly more subtle than you may expect at first sight.

Lectureslides and a more clear derivation of the problem of increasing the size have now been uploaded.

Exercises, Wednesday, February 6, 9:00—12:00, Room 3A14

Some of the following exercises will be discussed at the exercise session:

1. RS exercise 2.28, 2.30, 2.31, 2.20, 2.21be page 48

2. Prove that lg(n+c) is O(lgn)

3. Prove that lg(n+c) is about lgn

4. Prove that lg(n+c) is proportional to lgn [trivial!]

5. Simplify the following expressions:
1. O(n*n/4 + n)
2. proportional to n*n/2 + n
3. about n*n/2 + n
4. O(ln m + lg (m + 203) + 1945 - 2006)
5. about ln m + lg (m + 203) + 1945 - 2006
6. proportional to ln m + lg (m + 203) + 1945 - 2006
7. proportional to 2 lg (3m - m^-1)
8. O(m + n + lg m + n*n)

6. (The next two exercises depend on Section 2.6 in RS.) Assume we run the sequential search algorithm from lecture 2.1 (Program 2.1, page 54 in RS) on an array consisting of all current inhabitants of Denmark (let us say n=5*10⁶) sorted by their CPR numbers. We are searching for a particular person (a CPR number). The running time of a single execution of the body of the for-loop has been benchmarked to be a=10^-7 seconds if run on a machine performing a single task at a time. What is the expected running time for a single successful search on this machine? What is the expected running time for 10000 consecutive successful searches?

7. Repeat the above exercise for binary search (Program 2.2, page 56 in RS.) Use the following rough estimate: the running time of a single execution of the body of the while-loop is 10^-7 seconds, i.e., the same as for the loop in Program 2.1.

8. How long does it take your computer to count to one billion (using a particular programming environment)? Try to run the following Java code:

      long before = System.currentTimeMillis();
      int M = 1000000000;
      int i;
      for (i = 0; i < M; i++); 
      long after = System.currentTimeMillis();
      System.out.println("Took " + ((double) after - before)/1000 + " seconds");
   

   This should give you a rough idea how long it takes a Java program on your computer to perform in the order of one billion operations. Compare with the number 10^-7 from the previous exercises.

In addition, you must one week later hand in solutions to any two of the following four exercises. The deadline is Wednesday February 13, at 11:00. You can hand in at the beginning of the lecture Wednesday morning, or at any other time in the course pigeon hole, in front of the study administration.

• RS exercise 2.21cf p.48 (especially for students with technical background)
• RS exercise 2.24 p.48 (especially for students with technical background)
• RS exercise 2.29 p.48 (suitable for everybody)
• RS exercise 2.51 p.64 (suitable for everybody)