Discrete Structures (2IT50)

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

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

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.

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

Achieving knowledge of discrete structures in computer science

Further developing skills giving formal proofs

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.

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.

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

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

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: November 27, 2017