DM22, Spring 2005 - Weekly Note 8

To give you time to work on Project 1, one set of lectures and eksaminatorie classes were canceled: there were no lectures Monday, March 21, and no eksaminatorie classes Thursday March 31 and Friday April 1.

Lecture April 4

Proofs of correctness. Time complexity.

Reading

Chapter 8, and Sections 10.9, 14.7, and 17.9 in Thompson. Sections 19.1-3 in Thompson.

Comments

Since the book assumes no previous knowledge about algorithm analysis, there is much repetition in Chapter 19 from DM01 and DM02. The only really relevant parts are 19.2 and 19.4. The rest you can read lightly.

Lecture April 11 (Expected Contents)

Space complexity. I/O in Haskell. Start on Prolog.

Reading

Sections 19.4-5 and 18.1-7 in Thompson. Chapters 1 and 2 in Clocksin and Mellish.

Comments

The I/O part of Haskell is an example of a monad. A monad is a mathematical concept from category theory, which has found use as a model of programming in advanced functional programming. The book discusses monads briefly in Sections 18.7-9, but the exposition is too short and poorly written to make sense to cover. These sections will not be part of the curriculum (although the official curriculum mentions the entire Chapter 18).

Exercises April 7/8

Exercises 16.11, 16.12, 17.2, 17.22, 17.23, 17.28, 17.29 in Thompson. Exam of summer 2003 (pdf), exercise 3. Exam of summer 2002 (pdf), exercise 4, Exam of winter 2001 (pdf), exercise 3.

Unfortunately, previous exam sets are all in Danish. The exam set this summer will be in English.

Exercises April 14/15

Remaining exercises from previous eksaminatorier (namely, all non-exam exercises from April 7/8).

Exam of summer 2002 (pdf), exercise 3.