Introduction

This module (MAT3) supports the modules FND1 (Algorithms and Data Structures) and FND3 (Compiler construction). We focus on the needs of mathematical structures in Computer Science.

The current module desciption is given by the following link (in German).

Exams

An exam will take place at the end of the first quarter.
(This time this course will only runs a quarter.)

Study Materials

Outline by Chapters of Schaum's Outline Discrete Mathematics (third edition)

CHAPTER 1 Set Theory

1.2 Sets and Elements, Subsets
1.3 Venn Diagrams
1.4 Set Operations
1.5 Algebra od sets, duality
1.6 Finite Sets, Counting Principle
1.7 Classes of sets, power sets, partitions
1.8 Mathematical induction

CHAPTER 2 Relations

2.1 Introduction
2.2 Product Sets
2.3 Relations
2.4 Pictoral Representations of Relations
2.5 Composition of Relations
2.6 Types of Relations
2.8 Equivalence Relations

CHAPTER 3 Functions and Algorithms

3.2 Functions
3.3 One-to-one, onto, and invertible functions
3.6 Recursively Defined Functions, especially Ackermann Function
3.9 Complexity of algorithms

CHAPTER 8 Graph Theory - Undirected Graphs

8.2 Graphs and Multigraphs
8.3 Subgraphs, isomorphic and homeomorphic graphs
8.4 Path, Connectivity
8.6 Labelled and Weighted Graphs

CHAPTER 9 Graph Theory - Directed Graphs

9.1 Introduction
9.2 Directed Graphs
9.3 Basic Definitions
9.4 Rooted trees
9.5 Sequential representation of directed graphs

CHAPTER 12 Languages, Automata, Grammars

12.1 Introduction
12.2 Alphabet, Words (and Semigroups)
12.3 Languages
12.4 Regular Expressions, Regular Languages
12.5 Finite State Automata
12.6 Grammars

Realization First Quarter 2009
Numbers between () refer to edition 2

Week 1:

Lessons 1,2:

• Theory: 1.2 - 1.6
• Solved problems: 1.9, 1.13, 1.14
• 1.27, 1.29, 1.30, 1.35

Lessons 3,4:

• Discussion homework previous lessons.
• Solved problems:
• Homework: 1.36, 1.39, 1.41

• Discussion homework previous lessons.
• Theory: 2.1 - 2.5
• Homework solved problems: 2.1 (2.2), 2.4 (2.7), 2.5 (2.9)
• Homework supplementary problems: 2.20 (2.26), 2.23 (2.29)

Week 2

Lesson 7,8: Discussion homework previous week.

• Theory: 2.6
• Homework solved problems: 2.7 (2.10), 2.9 (2.12), 2.10 (2.14)
• Homework supplementary problems: 2.26 (2.31)

Lesson 9,10: Discussion homework previous week.

• Theory: 2.8
• Homework solved problems: 2.15 (2.19), 2.16 (2.20)

Lesson 11,12: Discussion homework previous week.

• Theory: 2.8
• Homework supplementary problems: 2.32 (2.36), 2.33 (2.37)

Week 3

Lesson 13,14: Discussion homework previous week.

• Theory: 3.1-3.3
• Homework solved problems:3.1 (3.2), 3.3 (3.8a), 3.5 (3.5)
• Homework supplementary problems: 3.28 (3.33), 3.31 (-)

Lesson 15,16: Discussion homework previous week.

• Theory: 3.3 Permutations, 3.6
• Homework solved problems: 3.6 (-), 3.20 (3.22), 3.21 (3.24)
• Homework supplementary problems: 3.35 (-)

Lesson 17,18: Discussion homework previous week.

• Theory: 8.2, except proof of theorem 8.1
• Homework solved problems: 8.1, 8.2

Week 4

The Tuesday lessons have been canceled

Lesson 19,20: Discussion homework previous week.

• Theory: 8.2 (proof of theorem 8.1), 8.3, 8.4
• Homework solved problems: 8.3, 8.4, 8.5, 8.6

Lesson 21,22: Discussion homework previous week.

• Theory: 8.6, 3.9
• Homework supplementary problems: 8.34, 8.35, 8.36

Week 5

Lesson 23,24: Discussion homework previous week.

• Theory: 9.1, 9.2, 9.3
• Homework solved problems: 8.38, 8.39, 8.40, 9.1, 9.2

Lesson 25,26: Discussion homework previous week.

• Theory: 9.4, 9.5 up to example 9.6
• Homework solved problems: 9.19, 9.23

Week 6

Lesson 27,28: Discussion homework previous week.

• Theory: 9.5, 12.1-12.4 up to example 12.2
• Homework solved problems: 9.5, 9.6, 9.7, 9.12, 12.1, 12.6, 12.11
• Homework supplementary problems: 9.26

Lesson 29,30: Discussion homework previous week.

• Theory: 12.4 (example 12.3), 12.5
• Homework solved problems: 12.14, 12.15
• Homework supplementary problems: 12.43, 12.44

Lesson 31,32: Discussion homework previous week.

• Theory: 12.6 up to "Types of grammars"
• Homework solved problems:12.22, 12.23, 12.24, 12.25
• Homework supplementary problems: 12.47

Week 7

Lesson 33,34: Discussion homework previous week.

• Homework supplementary problems: 12.34, 12.35, 12.36, 12.39, 12.40, 12.41, 12.46, 12.48, 12.49, 12.53, 12.57

Lesson 35,36: Discussion homework previous week.

• Homework supplementary problems: Testexam (DE), Testexam (NL)

Lesson 37,38: Discussion homework previous week.

• Exam training

Formelsammlung (DE)

Testexam