Information on the course

Discrete Structures (2IT50)

This is the information about the 5ects course Discrete Structures 2IT50. It was given for the last time in the first quartile of 2017/2018.
The very last examination will be on November 1, 2018. This is just a single examination of which the result is the final grade for the course, without interim tests.

The lecturer is prof dr H. Zantema, Metaforum 6.078, tel 2749, h.zantema@tue.nl

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.

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
Examination November 2017
Examination February 2018


Lectures and topics: (refers to the last instance of 2017).
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: August 16, 2018