Discrete Structures (2IT50)

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

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

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.

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

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 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.

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

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 |
---|---|---|---|

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