Information on the course

Discrete Structures (2IT50)


This is the information about the 5ects course Discrete Structures 2IT50 given in the first quartile of 2016/2017.

Lectures:
The first lecture is on Friday, September 9, 8:45-10:30. Next all lectures are on Wednesday, 15:45-17:30 in PAV B1, and Friday, 10:45-12:30 in AUD 4.
The lecturer is prof dr H. Zantema, Metaforum 6.078, tel 2749, h.zantema@tue.nl

Exercise lectures:
Wednesday, 13:45-15:30, in AUD 1, by dr ir J. W. Wesselink, Metaforum 6.076, tel 2734, j.w.wesselink@tue.nl. This started on September 14.
On September 21, October 5 and October 19 there are interim tests, from 13:45 - 14:45, in AUD 1, after which the solutions of the test will be presented.

Instruction sessions:
The first week (September 9) they are on Friday 10:45-12:30, next on Friday 8:45-10:30.
Instructors:
dr J.I. den Hartog, Metaforum 6.063, tel 2800, j.d.hartog@tue.nl
dr ir T. Verhoeff, Metaforum 6.093, tel 4125, t.verhoeff@tue.nl
dr E. P. de Vink, Metaforum 6.075, tel 3146, e.p.d.vink@tue.nl
dr ir J. W. Wesselink, Metaforum 6.076, tel 2734, j.w.wesselink@tue.nl
dr. J.C.S.P. van der Woude, Metaforum 5.106, tel 5146, j.c.s.p.v.d.woude@tue.nl

The distribution of the students over the groups can be found in OASE. The location of the instruction sessions is as follows:
Group De Vink : September 9 in AUD 7, September 16 and later in AUD 9
Group Den Hartog: AUD 10
Group Van der Woude: AUD 11
Group Verhoeff: September 9 in AUD 13, September 16 and later in AUD 14
Group Wesselink: September 9 in AUD 16, September 16 and later in AUD 15

Results of interim tests:
Group De Vink
Group Den Hartog
Group Van der Woude
Group Verhoeff (only results of last test)
Group Wesselink

Goals:
Achieving knowledge of discrete structures in computer science
Further developing skills giving formal proofs


Contents:
Relations: closures, equivalence relations and partitions
Graph theory: trees, Euler/Hamilton cycles, Ramsey theory
Functions: composition, injective/surjective, functions on finite sets
Posets and lattices
Monoids and (semi)groups
Combinatorics: counting and recurrence relations
Number theory


Required background for this course is Logic and Set Theory, of which a summary of basic rules can be found here.

Examination:
The course is concluded by a written examination. It is a 'closed book' examination: on this examination using books and/or notes is not allowed. This written examination counts for 70 %.
On September 21, October 5 and October 19 there are interim tests. The two best results of these three tests count for 15 % each.
The material of the first interim test on September 21 consists of Chapter 1 until Lemma 1.31 (including), on page 21, plus the notions R^+ and R^* as defined on page 23.
The material of the second interim test on October 5 consists of Chapters 1, 2 and 3, with the emphasis on Chapters 2 and 3.
The material of the third interim test on October 19 consists of Chapters 1-5, excluding pages 109-111, with the emphasis on Chapters 4 and 5.
The material for the examination consists of the lecture notes until page 152, excluding pages 109-111.

To download:

The lecture notes in PDF (version August 2016). This text includes all course material and all exercises.


Some earlier examinations and interim tests.
Examination November 2012
Examination January 2013
Interim test September 24, 2014, with solutions
Interim test October 8, 2014, with solutions
Interim test October 22, 2014, with solutions
Examination November 2013, with solutions
Examination January 2014
Examination November 2014
Examination January 2015
Examination November 2015
Solutions of examination November 2015
Examination January 2016
Interim test September 23, 2015
Interim test October 7, 2015
Interim test October 21, 2015
Interim test September 21, 2016
Interim test October 5, 2016
Interim test October 19, 2016
Examination November 2016
Examination February 2017


Lectures and topics: (to be updated every lecture).
The given exercises correspond to the lecture on the given date, and will be considered at the next instruction session or exercise lecture. Exercises indicated in bold are recommended to be considered before this next instruction session or exercise lecture.


date topic material exercises
Friday, September 9 Relations, equivalence relations Chapter 1 until Thm 1.13 (including), on page 14 1.4 (page 24-29): 1-6, 10, 12, 18
Wednesday, September 14 (Exercise lecture) 1.4 (page 24-29): 7,13,14,15,16,11,19
Wednesday, September 14 Equivalence relations and partitions, operations on relations Chapter 1 until Lemma 1.31 (including), on page 21 1.4 (page 24-29): 8,9,20,30,31,33, 34 ,27,29
Friday, September 16 Closures of relations, graph theory: path, distance Rest Chapter 1, Chapter 2 until page 40 1.4 (page 24-29): 34(b),25,32,40, 2.10 (page 52-55): 5,6,8
Wednesday, September 21 (interim test) Connectedness, cycles, trees, Euler cycles Chapter 2 until Thm 2.8 (exclusive), page 42, pages 54 and 55 2.10 (page 55-58): 2,3,4,7,9,10,11,13,14,15,16,17,18
Friday September 23 Euler and Hamilton cycles, triangles Chapter 2 until page 49 2.10 (page 55-58): 21,22,23,24,25,27,28,29,30
Wednesday, September 28 Ramsey theory, functions Rest Chapter 2, Chapter 3 2.10 (page 55-58): 26; 3.9 (page 72-73): 1,2,3,4,8,9,11,12,13
Friday, September 30 Posets: Hasse diagram, min/max, topological sorting Chapter 4 until Theorem 4.14 (including), on page 79 4.5 (page 90-92): 1,2,3,4,5,6,14
Wednesday, October 5 (interim test) Posets: sup/inf, lattices Chapter 4 until page 85 4.5 (page 90-92): 7,8,9,11,12,13
Friday, October 7 Lattices, complete lattices, distributive lattices, monoids and groups Rest Chapter 4, Chapter 5 until Def 5.17, page 98 (including) 4.5 (page 90-92): 10,16,18,19, 5.7 (page 111-113): 1,3,4,5,13
Wednesday, October 12 Monoids and groups, permutations Rest Chapter 5, excluding page 109-111 5.7 (page 111-113): 7,8,9,14,16,18,20,21,22
Friday, October 14 Counting, recurrence relations Chapter 6, until page 129 6.5 (page 135-137): 1,2,3,4,5,12,13,14,16,17
Wednesday, October 19 (interim test) Counting, binomial coefficients, number theory: div, mod, gcd Rest Chapter 6, Chapter 7 until page 142 (including) 6.5 (page 135-137): 18,19,21,23, 7.9 (page 159-161): 1,2,3,4
Friday, October 21 No exercise lecture, no lecture
Wednesday, October 26 Number theory: gcd, prime factorization Chapter 7 until page 152 7.9 (page 159-161): 5,7,8,9,10,11,12,13,16,17
Friday, October 28 Fermat's little theorem, RSA encryption, course overview Rest Chapter 7 7.9 (page 159-161): 23




Last change: February 15, 2017