Diskret Matematik E3 (TMA 055) - HT04

Kursutvärederingen kan fyllas i här

Home page for last year's course with links to previous courses  

PS    PDF      Schema (OBS! Fr.o.m. Vecka 3 blir det bara tva ovningsgrupper i stallet for tre !!!)

PS    PDF      Kursplan

PS    PDF      Supplementära föreläsningsanteckningar

PS    PDF      Short course summary

PS    PDF      Extra exercises and solutions

Click here      for a useful website

   Detailed schedule (subject to modification during course !)

Vecka 1:   Basic enumerative techniques. The pigeonhole principle. Counting pairs. The multiplication principle. Permutations and combinations. Choice with repitition allowed. Combinatorial arguments and identities. The inclusion-exclusion principle.

Biggs : Chapters 9,10,11 (excluding 11.6, 11.7)

Vecka 2:   Recurrence relations. Deerangements, Stirling and Catalan numbers. Solution of linear recurrence relations with constant coefficients. Time permitting, we'll also discuss generating functions.

Biggs : Chapters 12,19. Generating functions are covered in Chapter 25.

Vecka 3:   Introduction to arithmeic. Euclid's algorithm and the fundamental theorem of arithmetic. Linear Diophantine equations. Relations. Arithmetic modulo n. Non-liner Diophantine equations.

Biggs : Chapter 8 and part of 13.

Vecka 4:   The theorems of Fermat and Euler. RSA encryption.

Biggs : Chapter 13. RSA encryption is not covered in the text.

Vecka 5:   Introduction to graph theory. Paths and cycles. Graph colouring. Planar graphs.

Biggs : Most of the material (though not all) is in Chapters 15 and 16.

Vecka 6:   Trees. Decision problems and search algorithms. Matchings and network flows.

Biggs : Chapters 17 and 18.

Vecka 7:   Wrapping up of loose ends and revision.


OBS! The miscellaneous exercises at the end of each chapter in Biggs are often considerably more difficult than those after each section. Hence, when studying, you should first work on the exercises after each section. These represent the basic standard expected of you.

Vecka 1:   The following exercises from Biggs will be demonstrated

6.4.2, 10.2.1, 10.4.1, 10.5.4, 10.7.4, 11.1.7, 11.2.2, 11.3.2(iv), 11.4.2.

(In 1989 edition : 2.3.4, 3.2.1, 3.4.1, 3.5.4, 3.7.4, 4.1.7, 4.2.2, 4.3.2(iv), 4.4.2)

Suggestions for self-study : Further exercises from the same sections of the book, plus the practice probelms for Week 1 from last year's course (download from homepage for last year).

Vecka 2:   The following exercises from Biggs will be demonstrated

11.5.1, 11.5.4, 19.1.3, 19.2.3.

(In 1989 edition : 4.5.1, 4.5.4, 12.1.3, 12.2.3)

Vecka 3:   Thursday : 19.2.1 (12.2.1). The exercise will be repeated, but with something non-zero on the right-hand side (an exponential function or a polynomial in n), and then repeated yet again using exponential generating functions (EGF).

For a definition of EGF, and further exercises, see ps pdf

Friday : 12.1.1, 12.1.2 (5.1.1, 5.1.2) and the following exercises ps pdf

Vecka 4:   Tuesday : 4.3.1 and 4.3.2 (1.6.4), plus the following exercises ps pdf

OBS! Here are a couple of facts which follow from the fundamental theorem of arithmetic which are useful in solving many problems ps pdf

For self-study, I recommend the exercises in sections 8.4 - 8.7 of Biggs (1.6 - 1.9 in the old edition). In fact, most of the exercises in 8.7 (1.9) you should be able to solve without too much difficulty. I will also put a few of them on the homework.

Thursday : Exercises 13.1.1, 13.1.2, 13.3.1, 13.4.1(ii) (6.1.1, 6.1.2, 6.3.1, 6.4.1(ii)) and the following exercises ps pdf

Vecka 5:   Tuesday : 13.2.2 (6.2.2) plus the following exercises ps pdf

Thursday : the following exercises ps pdf followed by revision exercises, chosen in consultation with the participants.

Vecka 6:   Tuesday : 15.1.2, 15.2.1, 15.3.1, 15.4.3, 15.8.5, 15.8.6.

Thursday : 15.5.1, 15.5.2, 15.6.2(i)(ii), 15.7.1, 15.8.7

Vecka 7:   Tuesday : 16.3.3, 16.4.3, 16.6.1 plus the Ford-Fulkerson algorithm for the network drawn on the board in Monday's lecture.

Thursday :


1:   PS    PDF    Solutions:   PS    PDF 2:   PS    PDF    Solutions:   PS    PDF 3:   PS    PDF    Solutions:   PS    PDF

   Study tips

Here is a document which should help you when planning your strategy for how to study for the exam ps pdf

   Övningstentor (the first one is probably too hard)

1:   PS    PDF Solutions:   PS    PDF 2:   PS    PDF Solutions:   PS    PDF 3:   PS    PDF Solutions:   PS    PDF 4:   PS    PDF

   Riktiga Tentor

Tenta 20/10/04   PS    PDF och lösningar   PS    PDF Tenta 15/01/05   PS    PDF och lösningar   PS    PDF Tenta ??/04/05   PS    PDF och lösningar   PS    PDF

   Något om LaTeX

Anvisningar En svensk manual (LTH) Manualer LaTeX för Windows LaTeX hemsida

   Andra länkar

Intressant länk om bevisteknik (PDF) Att skriva matematik Sloane's On-Line Encyclopedia of Integer Sequences

Om du har kommentarer, påpekanden eller annat att säga om kursen, tryck   här

Peter Hegarty <hegarty@math.chalmers.se>
Last modified: Tue Oct 7 18:24:07 MET DST 2003