Code: ITX 8015
Amount of credits: 5 c
Amount of hours: 2 h lectures, 2 h tutorials per week
Schedule: Mondays 10-13.30, hall B101 of Cybernetica Bldg (Akadeemia tee 21)
[First lecture 24 Jan. 2005.]
[24 Jan. 2005: The start of this course has been postponed until further notice. Reason: The students of the international masters programme in IT have not arrived.]
[7 Feb. 2005: This course will start 14 Feb. 2005.]
Form of examination: written exam
Consultation: Wednesday 18 May 14-15.50, hall B101 of Cybernetica Bldg
Exam (1): Friday 20 May 10-13, hall B101 of Cybernetica Bldg
Exam (2): Friday 27 May 10-13, hall B101 of Cybernetica Bldg
Teacher: prof Tarmo Uustalu, firstname(at)cs.ioc.ee, 620 4250
Annotation: Counting. Combinatorial tools. Binomial coefficients. Fibonacci numbers. Combinatorial probability. Integers, divisors and primes. Graphs. Trees. Optimization. Matchings in graphs. Combinatorics in geometry. Finite geometries. Euler's formula. Coloring maps and graphs. A glimpse of complexity and cryptography.
Course book: L Lovász, J Pelikán, K Vesztergombi. Discrete mathematics: elementary and beyond. Springer-Verlag, 2003.
The TUT library has 10 hardcopies of the book. A 1999 version of the text is electronically available here.
| Date | Topic | Reading | Homework |
|---|---|---|---|
| Mon 14 Feb | Counting orderings, ordered subsets, subsets etc | Ch 1 | Ex 1.8.12,16,25,26,29 |
| Mon 21 Feb | Induction, inclusion-exclusion, pigeonhole principle | Ch 2 | Ex 2.5.1,2,6,7,8 |
| Mon 7 Mar | Binomial coefficients | Ch 3 | Ex 3.8.6,9,10,12,13 |
| Mon 14 Mar | Fibonacci numbers | Sec 4.1-2 | Ex 4.3.5,7,8,12,15 |
| Fri 18 Mar | Fibonacci numbers cont'd | Sec 4.3 | - |
| Mon 28 Mar | Combinatorial probability; Divisors, primes, Fermat's little thm | Ch 5, Sec 6.1-5 | Ex 6.10.3,4,5,9,12 |
| Mon 4 Apr | Euclid's algorithm, congruences, modular arithmetic | Sec 6.6-8 | Ex 6.10.13,16,17,18,19 |
| Mon 11 Apr | Number theory and combinatorics, primality testing; Graphs | Sec 6.9-10, 7.1-2 | Ex 6.10.22,23, 7.3.4,5,7 |
| Mon 18 Apr | Graphs (ctd); Trees | Ch 7.3, Ch 8 | Ex 8.5.2,3,4 |
| Mon 25 Apr | Minimum cost spanning trees, Traveling salesman problem | Ch 9 | Ex 9.2.4,7,8 |
| Fri 29 Apr | Perfect mathcings | Ch 10 | Ex 10.4.5,6,10 |
| Mon 2 May | Combinatorics in geometry, Euler's formula | Ch 11, 12 | Ex 12.2.2, 3.2,4 |
| Mon 9 May | Map and graph coloring | Ch 13 | - |