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

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.

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

Examination February 2018

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: August 16, 2018