General Info

Teachers

Teaching Assistants

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

    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 will be uploaded on DTU-Learn.

    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 20% of the course grade, so each one will be worth 5% 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 80% of the final grade, and the remaining 20% comes from the four mandatory homework assignments (5% each). 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.

    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 4 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 11 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 18 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 25 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 02 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 09 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 23 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 30 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 06 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 013 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 20 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 27 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 04 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