T÷lvunarfrŠ­i 2

Weekly notes 4


This week (i.e. Jan. 31st - Feb. 4th) Anna Ingˇlfsdˇttir will take over the lectures. They will cover material from chapters 1 and 2 in the main textbook of the course, Algorithms in C++ by Robert Sedgewick. In chapter 1 we will skip sections 1.2 and 1.3. The remainder of the chapter is an easy introduction and can be read quickly. Chapter 2 on the other hand will be the main topic of this week. It deals with algorithms and their analysis.

Next week we will continue with the Algorithms book and cover linked lists.

Sections this week (Feb. 1st - 2nd) will be in the classrooms that are one your schedules (Tfr. 2: H1: V-258, H2: V-155, Tfr.2a: H1: V-138, H2: V-138).

Problem set 4

Solve the following problems and put the solutions into your section teacher's box before noon monday Feb. 7th. They will not accept solutions that arrive later.

  1. Compare the time required to call virtual methods to the time needed to call static methods (i.e. the usual methods). Build two classes that have one virtual method and one static one. If you have the methods do something simple, e.g. increment a counter, then you will get a more realistic measurement of the difference between these two kinds of methods. To measure the time you can use the function clock(), defined in the library time.h. Here is an example of its use. It is likely that you will need at least 10 million calls to the methods to get a measurable difference, but that depends on computer types, how the methods are constructed and other things.

  2. The few operators that are worth overloading in normal classes are the relational operators ( <, <=, >, >=, ==, != ). Overload these operators in the Cat class (e.g. use program 6.4 as a base) and have the age of the cats determine the result of the comparison. Below is the header of one of the relational operators:
          bool operator< ( Cat &rhs );
      
    In this case the return value should be the truth value of the age of "our" cat being less than the cat rhs. Implement all six relational operators in the Cat class.

  3. Exercise 2.10 on page 43 of the Algorithms book.

  4. Exercise 2.20 on page 47 of the Algorithms book.

  5. Show that log10(n) is O(log2(n)).

Those that want more practice should try solving the following problems. Their solutions are all available, either on an old homepage of the course or at the back of the C++ textbook. If you want an explanation of the solutions you can ask about them in your section.
hh (hja) hi.is, January 31st, 2005.