Information on the course

Discrete Structures (2IT50)


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

Lectures:
The first lecture is on Wednesday, September 6, 15:45-17:30, AUD 2 and AUD 7. Starting from Wednesday, September 20, the lectures will only be in AUD 7, so no video connection any more in another room.
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 3, by dr ir J. W. Wesselink, Metaforum 6.076, tel 2734, j.w.wesselink@tue.nl. This starts on September 13.
On September 27 and October 18 there are interim tests, from 15:45 - 16:45, in AUD 2 and AUD 7, after which the solutions of the test will be presented. On these two days the lectures will be from 13:45-15:30 in AUD 3.

Instruction sessions:
These are 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
R. Aditya, Metaforum 6.111, r.aditya@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 is indicated in Canvas. The location of the instruction sessions is as follows:
Group 1, Aditya : Metaforum 7
Group 2, Den Hartog: Luna 1.240
Group 3, Van der Woude: Luna 1.056
Group 4, Verhoeff: group does not exist any more, students have been distributed over the other groups (see Canvas)
Group 5, Wesselink: Traverse Van Trierzaal

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 27 and October 18 there are interim tests. These count for 15 % each.
The material for the first interim test is Chapters 1 and 2, except for Section 2.8 on Ramsey theory.
The material for the second interim test is everything until page 127, so Chapters 1 to 5 and the first part of Chapter 6.
On the interim test you are asked to indicate your instruction group, so if you don't know, please look up in Canvas in advance.

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. Ordering a copy on paper is possible via TU/e print service .


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
Wednesday, September 6 Relations, equivalence relations Chapter 1 until Thm 1.13 (including), on page 14 1.4 (page 24-29): 1,2,3,4,5,6,7,10,12,14,16,18 (for Friday)
Friday, September 8 Equivalence relations and partitions, operations on relations Chapter 1 until Lemma 1.31 (including), on page 21 1.4 (page 24-29): 8,9,11,20,30,31,33, 34 ,27,29 (for Wednesday)
Wednesday, September 13 Closures of relations, graph theory: path, distance, connectedness, cycles Rest Chapter 1, Chapter 2 until page 42 1.4 (page 24-29): 25,32,40, 2.10 (page 52-55): 2,5,6,8 (for Friday)
Friday, September 15 Trees, spanning trees, Euler cycles Chapter 2 until Thm 2.8 (inclusive), page 43, pages 54 and 55 2.10 (page 55-58): 2,3,4,7,9,10,11,13,14,15,16,17,18 (for Wednesday)
Wednesday, September 20 Hamilton cycles, triangles, Ramsey theory Chapter 2 until page 51 2.10 (page 55-58): 21,22,23,24,25,27,28,29,30 (for Friday)
Friday, September 22 Ramsey theory, functions Rest Chapter 2, Chapter 3 until page 69 (including) 2.10 (page 55-58): 26; 3.9 (page 72-73): 1,2,3,4,8,9,11,12,13 (for next Friday)
Wednesday, September 27 Functions, posets: Hasse diagram, min/max, topological sorting (interim test) Rest Chapter 3, Chapter 4 until Theorem 4.14 (including) 4.5 (page 90-92): 1,2,3,4,5,6,14 (for Friday)
Friday, September 29 Posets: sup/inf, lattices Chapter 4 until page 85 4.5 (page 90-92): 7,8,9,11,12,13 (for Wednesday)
Wednesday, October 4 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 (for Friday)
Friday, October 6 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 (for Wednesday)
Wednesday, October 11 Counting, recurrence relations Chapter 6, until page 129 6.5 (page 135-137): 1,2,3,4,5,12,13,14,16,17 (for Friday)
Friday, October 13 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 (for next Friday)
Wednesday, October 18 Number theory: gcd, prime factorization (interim test) Chapter 7 until page 152 7.9 (page 159-161): 5,7,8,9,10,11,12,13,16,17 (for Friday)
Friday, October 20 (only instruction sessions; no lecture due to Open Day)
Wednesday, October 25 Fermat's little theorem, RSA encryption Rest Chapter 7 7.9 (page 159-161): 23
Friday, October 27 Course overview




Last change: October 18, 2017