Diskret Matematik E3 (TMA 055) - HT05

Kursutvärederingen kan fyllas i här

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

PS    PDF      Schema (OBS! Vi börjar med två övningsgrupper. Antalet kan utökas om det visar sig att behovet finns.)

PS    PDF      Kursplan (OBS! Viktig notis angående kursboken. Annars är det samma kursplan som i fjol.)

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.

Biggs : Chapters 6.4, 10 (except 10.3), 11.1 - 11.3 (see also Ch.19, though we won't go into this chapter any deeper).

Grimaldi : Chapters 1.1 - 1.4, 5.5.

Vecka 2:   The inclusion-exclusion principle. Recurrence relations. Derangements. Solution of linear recurrence relations with constant coefficients.

Biggs : Chapters 11.4, 11.5, 19.1, 19.2.

Grimaldi : 8.1, 8.2, 8.3, 10.1, 10.2.

Vecka 3:   Linear recurrence relations with constant coefficients (continued). Stirling and Catalan numbers. Introduction to arithmeic. Euclid's algorithm and the fundamental theorem of arithmetic. Linear Diophantine equations.

Biggs : Chapters 25.4-25.6, 8.

Grimaldi : 10.3, 1.5, 5.3, 4.

Vecka 4:   Relations. Modular arithmetic. Non-linear Diophantine equations.

Biggs : 13.1, 13.2.

Grimaldi : 14.1, 14.2, 14.3 (see also 5.1).

Vecka 5:   Invertible elements in Z_n. The theorems of Fermat and Euler. The Chinese Remainder Theorem. Introduction to public-key cryptography.

Biggs : 13.3. CRT is an exercise in 13.6. RSA is not covered in this book.

Grimaldi : 14.3, 14.4, 16.2, 16.3, 16.4 (OBS!!! Grimaldi's treatment of these subjects is far more abstract algebraic than mine will be. Hence, I actually recommend that you not use the book, unless you want to get a deeper insight into the subject for your own benefit. I will post lists of recommended exercises).

Vecka 6:   RSA encryption. Introduction to graphs - Paths and cycles, Euler/Hamilton paths and cycles, Planar graphs, Graph coloring.

Biggs : Chapters 15,16.

Grimaldi : 16.4,11,12.

Vecka 7:   Monday : More on planar graphs and graph coloring. Trees and search algorithms (Euler cycles, path, minimal spanning tree, Dijkstra's algorithm for shortest paths).

Wednesday : 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 will be demonstrated (download ps pdf)

6.4.2(B), 10.2.1(B), 10.5.2(B), 10.7.4(B), 10.7.5(B), 1.3.7(G), 11.1.7(B), 11.2.2(B), 11.3.2(iv)(B).

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

Vecka 2:   The following exercises will be demonstrated (download ps pdf)

11.5.1(B), 11.5.4(B), 11.4.2(B), 8.1.8(G), 8.2.7(G), 19.1.3(B), 10.1.2c(G), 10.2.1e(G), 19.2.3(B) or 10.2.11(G).

Suggestions for self-study : Handouts from Grimaldi.

Vecka 3:   The week's exercises can be downloaded here ps pdf

Vecka 4:   Tuesday : No exercises will be demonstrated today ; you may study on your own. Here are some recommended exercises on arithmetic from the sections of Grimaldi recently handed out :

Section 4.3 : 2,7,10,11,13.

Section 4.4 : 1(b),6,8,10,13,17,19.

Section 4.5 : 1(b),6,8,13,14,18,19,21,26,27.

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

Thursday : The following exercises will be demonstrated ps pdf

Vecka 5:   Tisdag : Följande uppgifter kommer att demonstreras ps pdf

Torsdag : Följande uppgifter kommer att demonstreras ps pdf

Vecka 6:   Tisdag : Följande uppgifter kommer att demonstreras ps pdf

Torsdag : Följande uppgifter kommer att demonstreras ps pdf

Vecka 7:   Tisdag : Följande uppgifter ska demonstreras (de flesta har bilder med sig så jag avstår från att skriva ut dem) :

15.5.1(B), 15.5.2(B), 16.3.3(B), 16.4.3(B), 16.6.1(B), 11.4.14(a)(b) (G).

Torsdag : Repitition.

Följande är lösningar till demonstrationsuppgifter som vi (jag eller David) inte hann fram till under lektionerna ps pdf


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

   Study tips

Here is an updated version of the 2004 document which should help you when planning your strategy for how to study for the exam ps pdf

   Kommentarer på gamla tentor

On the homepages for the last two years you will find five exams plus three "practice exams". The exam ??/04/05 has mysteriously disappeared (I will see if the secretary has a copy) and "Övningstenta 4" probably never existed.

Otherwise, basically all the questions on these exams are examinable material. The only exceptions are question 4(ii) on each of 20/10/04 and 15/01/05. These two exams are at the same level as you can expect this time. The exams from 2003 and the practice exams are generally at a higher level. In the language of "Level 1,2,3" in the study document above, we can make the following summary :

Övningstenta 1 : #5 is the only Level 1 question. All others are essentially Level 3.

Övningstenta 2 : #1,6 are Level 3. Rest are Level 1.

Övningstenta 3 : #3 is Level 2, #4,5(ii),6 are Level 3.

20/10/03 : #4,6 are Level 3. Rest are Level 1.

10/01/04 : #4 is Level 2, #5(i),6 are Level 3.

22/04/04 : #4,5(iii) are Level 2, #6 is Level 3.

OBS! The solutions to some of the questions concerning recurrence relations on the old exams use the method of generating functions, which was not introduced this year. Here are corresponding solutions which do not use this method ps pdf


Tenta 17/10/05   PS    PDF och lösningar   PS    PDF Tenta 14/01/06   PS    PDF och lösningar   PS    PDF Tenta 29/08/06   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