01017 Discrete Mathematics

General Info

Teachers

David Earl Roberson, dero@dtu.dk
Carsten Thomassen, ctho@dtu.dk

Teaching Assistants

Emma Hansen
Victoria Ørsted Hougaard
Katrine Marie Pedersen
Jesper Bækholm Rom Poulsen
Caroline Tue Ravnkilde

Lectures

Thursdays 8:00-10:00.

Exercise sessions

Thursdays 10:00-12:00.

Note that most exercises are odd numbered exercises from the course textbook. The solutions to these can be found in the back of the textbook. But we highly recommend solving them on your own befre looking at the solutions.

Location and TA coverage

Lectures: Building 306 auditorium 34.
Exercise sessions: Building 306: Team areas 108a, 108b, 1 sal oest, 1 sal vest, and Team rooms 96, 98, 99. TA's will be present from 10:00 to 12:00.

Materials

Selected topics of the book "Discrete Mathematics and Its Applications" (2025 Release) by Kenneth H. Rosen, and almost all execises will be from this book. It can be purchased at the book store Polyteknisk Boghandel in Building 101, as well as from their website. Some of you may already have the Eighth Edition. That is equally good. The numbering of the exercises sometimes differs between the two editions. When this is the case, the numbering for the Eighth Edition is given in red in the weekplan below. The last lecture and exercise session are based on Chapter 6 in notes by Beelen et al. These notes are also in English and are linked to in the weekplan below.

Mandatory Homework

There will be 4 mandatory homework assignments that you will complete in pairs or triples (groups of size 3 will have to complete an additional exercise). The deadlines for these assignments may be 11:59pm on the Sunday evening following the lectures in course weeks 3, 6, 9, and 12, but this is subject to change. The assignments will be posted on DTU Learn and that is where they will be submitted as well. Due to the large number of students in the course, there will be no exceptions for accepting late assignments, so please submit them early (you can resubmit as many times as you like up to the deadline). The mandatory assignments will account for 16% of the course grade, so each one will be worth 4% of the course grade.

Exam and Grades

The exam is a 3 hour digital multiple choice exam. No internet access or AI is allowed during the exam, but all other aids are allowed (see DTU's exam aids policies for clarification). The exam is worth 84% of the final grade, and the remaining 16% comes from the four mandatory homework assignments which count 4% each (NOTE: these percentages have changed from previous years). You do not have to have completed the homeworks in order to be eligible to take the exam, but of course not doing them will hurt your final grade. YOU CANNOT USE A PREVIOUS YEAR'S ASSIGNMENTS TOWARDS YOUR GRADE, YOU MUST COMPLETE THE ASSIGNMENTS AGAIN OR YOU WILL NOT RECEIVE ANY POINTS FOR THEM. However, the points from this year's assignments may be transferred to the re-exam in the Spring.

Pensumliste

All material covered in the lectures, weekly exercises, and mandatory homeworks may appear on the exam.

Weekplan

THIS SCHEDULE IS TENTATIVE AND SUBJECT TO CHANGE

Week	Topics	Exercises (Do those in bold first)	Materials
W1 / Sep 3	Propositional and predicate logic Propositional logic Predicates and quantifiers	Section 1.1: 1, 3, 11, 37, 53 Section 1.4: 1, 31, 35, 37, 41, 55	Sections 1.1 and 1.4
W2 / Sep 10	Introduction to proofs Direct proofs Proof by contrapositive Proof by contradiction Introduction to sets Sets Subsets Power sets Cartesian products	Section 1.7: 3, 11, 37, 41 Show you are smarter than Kenneth H. Rosen by giving a direct proof for Example 3 in Section 1.7. Section 2.1: 15, 25, 31, 41 (11, 21, 27, 37 in the 8th Ed.)	Sections 1.7 and 2.1
W3 / Sep 17	Sets and Functions Set operations Cardinality of finite sets Functions	Section 2.2: 27, 29, 35, 47 (see definition above exercise 38) Section 2.3: 9g, 21, 27, 73a	Sections 2.2 and 2.3
W4 / Sep 24	Modular arithmetic Divisibility Modular arithmetic	Section 4.1: 1, 5, 9, 17, 21, 29, 41, 43, 44, 45, 47, 51	Sections 4.1 and (a bit of) 4.3
W5 / Oct 01	Primes and the Euclidean algorithm Primes Greatest common divisors Euclidean algorithm	Section 4.3: 3, 11, 15, 17, 31, 33, 41, 43, 49, 51, 55 Prove that for any integer n > 1 and non-negative integer k, the integer n-1 divides n^k - 1.	Sections 4.3
W6 / Oct 08	Chinese remainder theorem Solving congruences Mathematical Induction	Section 4.4: 5, 7, 9, 11, 19, 21, 24, 29, 35, 39, 43, 47, 53 Section 5.1: 1, 3, 5, 7	Sections 4.4 and 5.1
Holidays	Holiday week
W7 / Oct 22	Induction and recursion Mathematical induction Recursive definitions and structural induction	Section 5.1: 19, 51, 65, 75 Section 5.2: 5, 27 (3, 25 in the 8th Ed.) Section 5.3: 1, 5, 7, 13, 17, 31, 45	Sections 5.1, 5.2, and 5.3
W8 / Oct 29	Counting The basics of counting The pigeonhole principle Permutations and combinations	Section 6.1: 1, 21, 25, 47, 57, 69 (67 in the 8th Ed.) Section 6.2: 7, 13, 17, 31, 37 Section 6.3: 7, 23, 31, 43, 47	Sections 6.1, 6.2, and 6.3
W9 / Nov 05	Binomial formula Binomial coefficients and formula	Section 6.4: 7, 9, 11, 17, 21, 23, 29, 33, 35, 37, 39	Section 6.4
W10 / Nov 12	Inclusion-exclusion Inclusion-exclusion Applications of inclusion-exclusion	Section 8.5: 1, 5, 9, 11, 15, 23, 27 Section 8.6: 3, 5, 7, 13, 21, 25	Sections 8.5 and 8.6
W11 / Nov 19	Relations Equivalence relations Partial orderings	Section 9.5: 1, 7, 11, 30, 35, 45 Section 9.6: 1, 3, 15, 19, 20, 33	Sections 9.5 and 9.6
W12 / Nov 26	Graphs and the Cantor-Schröder-Bernstein theorem	Section 10.1: 11 Section 10.2: 5, 47 (43 in the 8th Ed.), 59 (55 in the 8th Ed.) Section 10.3: 7, 57 Section 10.4: 9, 11 Section 10.5: 1, 3, 13	Chapter 10, Sections 10.1-10.5, and a graph theoretic proof of the Cantor-Schröder-Bernstein Theorem (which is called the Schröder-Bernstein Theorem in Exercise 41 in Section 2.5).
W13 / Dec 03	Polynomials and the Extended Euclidean Algorithm	Beelen et al: 6.16, 6.17, 6.18, 6.19	Chapter 6 in Beelen et al Discrete Mathematics