Discrete Mathematics

Volume: 13 weeks × 5 lecture periods/week

Textbook: Kenneth Rosen, Discrete mathematics and its Applications, 6th Edition, McGraw-Hill,
Link to publisher's description

Prerequisites: None, but Vv156 or Vv186 is recommended.

Last Taught: Summer Term 2011

Background and Goals: This course is of natural interest for students majoring in ECE, as much of the mathematical background is required in other courses, such as “Ve281 Data Structures and Algorithms” or “Ve478 Logic Circuit Synthesis and Optimization”. However, the present course is also of interest for any student wishing to gain a broader general knowledge of mathematics. Many of the concepts covered here, such as number theory, graph theory or combinatorics, are not introduced in any other course.

There is no formal prerequisite for this course. However, we will occasionally use knowledge borrowed from the calculus of single-variable functions, such as is taught in Vv156 or Vv186.

Key Words: Logic; set theory; construction of the natural, negative and rational numbers; induction; algorithms; number theory; combinatorics; elementary probability; advanced counting techniques; recursion equations; relations; graphs, trees.

Detailed Content: The present course is different from many other math courses at the JI in that it does not give an in-depth look at any one topic. Instead, we visit several different mathematical fields that are loosely grouped together under the heading “discrete mathematics”. These fields have in common that they deal with problems related to integers as opposed to the real numbers. Hence the problems can often be formulated in quite elementary terms. Many of these problems are classical, having been analyzed by natural philosophers and scientists for centuries or (in some cases) millennia.

That said, the various topics in this course are not just of abstract interest; with the advent of computers, it has been found that fields such as logic, number theory and computability have important applications in the real world. Many things we take for granted (such as secure online banking) would not be possible without the developments in these fields.

The course mainly follows Rosen's book, with some small additions (e.g., regarding the construction of the various number fields) and change in the order of presentation. The course aims to cover logic, set theory, number fields, algorithms, graph theory and trees, various generalizations of mathematical induction, elementary combinatorics, elementary probability, number theory and (if time permits) Boolean algebra.

Overview:

Week	Lecture Subject	Textbook Sections	Date
1	Elements of Logic	1.1 - 1.5	16-5-2011 17-5-2011 19-5-2011
2	Set Theory and Numbers Mathematical Induction	2.1 - 2.4, 8.5 4.1-4.3	23-5-2011 24-5-2011 26-5-2011
3	Mathematical Induction The Real Numbers	4.1 - 4.3, A-1	30-5-2011 31-5-2011 2-6-2011
4	Functions, Sequences, Algorithms	3.1 - 3.3, 4.4 - 4.5	7-6-2011 9-6-2011
5	Introduction to Number Theory First Midterm Exam	3.4 - 3.8 1, 2, 3.1-3.3, 4	13-6-2011 14-6-2011 16-6-2011
6	Introduction to Number Theory Counting	3.4 - 3.8 5.1 - 5.5	20-6-2011 21-6-2011 23-6-2011
7	Elementary Probability	6.1 - 6.4	27-6-2011 28-6-2011 30-6-2011
8	More Counting	7.1 - 7.6	4-7-2011 5-7-2011 7-7-2011
9	Relations Second Midterm Exam	8.1 - 8.4, 8.6 5, 6, 7	11-7-2011 12-7-2011 14-7-2011
10	Relations	9.1 - 9.8	18-7-2011 19-7-2011 21-7-2011
11	Graphs	10.1 - 10.5	25-7-2011 26-7-2011 28-7-2011
12	Trees	11.1 - 11.4	1-8-2011 2-8-2011 4-8-2011
13	Final Exam Mathematical Movie	8, 9, 10, 11	8-8-2011 10-8-2011 11-8-2011

Lecture Slides (2011 version; PDF):

Summer 2011

(There will always be minor modifications from one iteration of the course to the next; if you are presently taking the course, it is not advisable to print out all these slides at the beginning of the term.)

Assignments (2011 version; PDF files):

(There will always be minor modifications from one iteration of the course to the next; if you are presently taking the course, your assignments may differ from these.)