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.
- 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.
- 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
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.
- Exercise 2.10 on page 43 of the Algorithms book.
- Exercise 2.20 on page 47 of the Algorithms book.
- 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.