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

    Most topics will be based on the book "Discrete Mathematics and Its Applications" (Eighth Edition) 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.

    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. Please note that if you are enrolled in 01019, then you must submit your assignments in English. If you are enrolled in 01017, then you may submit your assignments in Danish or English (which may be easier since the exercises are written in English).

    Weekplan

    THIS SCHEDULE IS TENTATIVE AND SUBJECT TO CHANGE

    Week Topics Exercises
    (Do those in bold first)    		 Materials
    W1 / Sep 5 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 12 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: 11, 21, 27, 37
    		•  Sections 1.7 and 2.1
    W3 / Sep 19 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 26 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 03 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 10 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 24 Induction and recursion
  • Mathematical induction
  • Recursive definitions and structural induction
    		•
  • Section 5.1: 19, 51, 65, 75
  • Section 5.2: 3, 25
  • Section 5.3: 1, 5, 7, 13, 17, 31, 45
    		•  Sections 5.1, 5.2, and 5.3
    W8 / Oct 31 Counting
  • The basics of counting
  • The pigeonhole principle
  • Permutations and combinations
    		•
  • Section 6.1: 1, 21, 25, 47, 57, 67
  • 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 07 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 014 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 21 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 28 Graphs and the Cantor-Schröder-Bernstein theorem
  • Section 10.1: 11
  • Section 10.2: 5, 43, 55
  • 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 05 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