Performance and Test, Spring 2007: Episode 1.1

Lecture Wednesday, January 31, 13:30—15:30, Room 2A14

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].

Download: Introduction slides for the first lecture. Lecture notes.

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.

Exercises, Friday, February 2, 10:00—12:00 (!), Room 2A14

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. Assume we run the improved version of sequential search algorithm from lecture 2.1 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 iteration has been benchmarked to be a=10^-7 if run on a machine performing a single task at a time. What is the expected running time for a single search on this machine? Is that satisfactory? Consider that such searches normally happen concurrently for multiple threads at the same time (think efficiency/throughput/latency).

7. Repeat the above exercise for binary search.

The solutions to any two of the following four exercises should be handed in to the course pigeon hole, before Wednesday, February 7, 13:00 [expected time 2—3h]

• 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)