Topic outline

  • General

    • Welcome to Foundations of Discrete Mathematics

      This is the course website for Foundations of Discrete Mathematics (MS-A0402) is given in Period IV on Spring 2022. Discrete Mathematics is the mathematics of finite and countable structures, or loosely speaking the mathematics of sets where there is no notion of "convergence". Methods from discrete mathematics play a large role in many other subjects, in particular in computer engineering and data science. In this course we cover the foundations of discrete mathematics (graphs, enumeration, modular arithmetic) as well as as the foundations of all mathematics on university level (set logic and proof techniques). We also study some modern applications of the theory, in cryptography and networks theory.


      For whom? The course is suitable for all Aalto students; no other prerequisites than high school mathematics are necessary. 

      Lecturer: Tuomas Sahlsten

      Course assistants: 

      • H01 Online Zoom group(meeting ID :625 6727 0245)- Rahinatou Njah (rahinatou.njah@aalto.fi) - Head Assistant
      • H02 - Teemu Tasanen (teemu.tasanen@aalto.fi), Tuesdays classroom R001/M240, Undergraduate Centre and Fridays classroom R001/M240, Undergraduate Centre
      • H03 - Noora Puputti (noora.puputti@aalto.fi), Mondays classroom R001/Y228b, Undergraduate Centre, and Wednesdays classroom R001/U358 AMER SPORTS, Undergraduate Centre (we had to change the Wednesday class to another class as the size of the class was increased)

      Registration: Sisu. When you register for the course on Sisu, remember to also register for one (and only one) exercise group.

      Resources: Please see the Materials

      Laskutupa: Free math tutoring center. Follow the link for a schedule and other details. 

      Assignments: See Assignments

      Grading policy: The grade for the course will be determined by

      Max{H*60 + F*40  ,  F*100%}

      where

      H = Homework, F = Final exam

      Final exam and re-take exams: The final exam on April is only organised on campus, we cannot organise both virtual and on-campus examinations for a course. For the re-take exams later in the year, the exercise points will not count towards to the final grade. However, if you cannot attend the first exam on April (please contact me if you cannot and you plan to come to exercise classes), you can take a re-take exam later in the year when you are in Finland, which will also be on campus, there will not be separate virtual exams. In this case, if you had not attended the first exam on April, the exercise points will count towards the final grade (so you can also pass the course also with the 60% assignments, 40% final exam rule in addition to the 100% final exam grade), but you need to first contact me that you are planning to do this as a priori I will the re-take exams will be marked with 100% grade from the final exam. If you already attended the April exam, then the exercise points will not count towards to the final grade you would get in the re-take exam.




    • Structure of the teaching


      How is the course taught? 

      • This course will be delivered in the traditional style with in-person scheduled lectures on campus (8:15 - 10 am on Wednesdays and Thursdays). These lectures will follow lecture notes I have put to Materials section. Into the Lecture journal section I will gather what pages of the lecture notes we have covered in each lecture. For students who cannot attend, I have put out also last year's online videos and lecture slides into the Further materials section. 
      • We will also have two weekly exercise classes for each group, the group H01 will be online. Attendance to the classes is not mandatory but highly recommended. Here you can also work on some of the exercises, get advise and feedback.
      • Assignments that will weight 60% of the final mark, and a final exam that weights 40%, see Assignments section for more info about homework.



    • Contacting lecturer and assistants: Zulip Chat


      • This forum will be used in an essential way during the course: you should aim to use it for all contact with the lecturer and the assistants for questions. It is possible to send a private message or put a public questions which could be helpful for other students of the course
      • https://ms-a0402.zulip.aalto.fi (log in with your Aalto credentials)


      Laskutupa (math help center)


      Lasutupa is Aalto's math tutoring center that is run by the Department of Mathematics and Systems Analysis. 
      Feel free to ask the tutors there for help any time. Since it's online you can post your questions any time. 


    • forum icon
      Announcements Forum

  • Materials

    In this section you will find all the material for the course. As the lectures will be on campus, we will follow the attached lecture notes below (which are updated during the course). See the Lecture journal section for what was covered in each lecture. However, I understand there may be some students who are unable to attend physically to the lectures. For this purpose, you can also find in this page last year's Zoom videos and lecture slides from Further materials section. The lecture material for this year is very similar to last year's. Nevertheless, if you can, I recommend to come to the on campus lectures as they can be more interactive and you can ask questions.

  • Lecture journal

    This journal will follow the lectures, and what we covered. We will mention which page numbers were covered from the lecture notes in the Materials section.


  • Further materials


    All the lectures for this year's course will be on campus. However, I understand there may be some students who are unable to attend. For this purpose, you can find in this page last year's Zoom videos by Ragnar Freij-Hollanti, and his lecture slides (disc_slides.pdf below). In this year we will follow very closely same structure as Ragnar and we do not deviate from the material. The main addition to this year are the new lecture notes (see Materials), which are basically a modification of the slides below.

    Videos from last year. The videos follow roughly the following schedule (including references to Kenneth H. Rosen: Discrete mathematics and its applications):
    1: Sets (2.1-3,5 ; Slides 1-31)
    2: Formal logic (1.1-6 ; Slides 32-51)
    3: Proof methods (1.7-8, 5.1 ; Slides 52-67)
    4: Equivalence relations, partitions, partial orders (9.1,3,5,6 ; Slides 68-86)
    5. Functions and cardinalities (2.3,5 ; Slides 87-116)
    6: Enumerative combinatorics: multiplication rule, binomial coefficients (6.1-4 ; Slides 117-135)
    7: Enumerative combinatorics: inclusion-exclusion principle (8.5-6 ; Slides 136-155)
    8: Permutations and groups (Bogart 6.1 ; Slides 156-179)
    9: Graph theory: concepts (10.1-3, 11.1 ; Slides 180-205)
    10: Graph theory: algorithms (10.6,8, 11.4-5 ; Slides 206-225)
    11: Number theory: Divisibility and Diophantine equations (4.1-3 ; Slides 226-256)
    12: Number theory: Modular arithmetics and Fermat's little theorem (4.4-6 ; Slides 257-273)
    Bonus lecture: RSA cryptography (Slides 274-285)

  • Results

    Dear all,

    The grading for the final exam is now complete. Here are the results of the final exam. 

    General comments and feedback:

    The exam seemed to have been more difficult for most students compared to earlier online exams I have given in Aalto. Thus I lowered the grade thresholds and they are now:

    1 - 0,4

    2 - 0,55

    3 - 0,68

    4 - 0,78

    5 - 0,88

    In total the average grade was: 2,855. Remember the grading mentioned in the final exam:

    ”Answers must always be justified with calculations, explanations and clear logic so the person marking can follow your argument. For example, it can be helpful to use implication arrows ⇒, words "Thus", "Therefore", "Hence" etc., or short sentences that make it clear what the logic in the answer is, especially in the proofs.

    On the grading:

    1. If you have not done any assignments, then 100% of your final grade comes from the marks you get from this exam (from all 5 questions)

    2. If you have assignment/exercise marks (like most students taking this exam), there are two ways your final grade is determined:

    (a) Firstly, we will look at 4 of your answers that earn the most points out of all 5 and this will determine 40% of your grade. The rest 60% will come from the assignment/exercise marks done during the course.

    (b) Secondly, we will grade you as we would in case 1, that is, we will also look at what your mark would be if all 5 (including the answer with the lowest mark) are graded and what mark you would get if we do not take assignment/exercise marks into account.

    Then the better (max) of these two performances in (a) and (b) will determine your final grade.”

    Grading was done Q1 and Q2 by Teemu, Q3 and Q4 by Rahinatou and Q5 by Noora. If you have some complaints on the marking, you can come to see you exam script to 

    M145b Masto at Friday 29.4.2022, at 14:00, 

    or alternatively email the person who graded the particular question by Friday 29.4.2022, at 16:00. After this, the marking cannot be altered and the grades will go officially to Sisu.

    Some comments on the final exam, generally, most solutions were done well, but maybe some more clarity in the proofs would have been useful. Some of the problems done during the exercise sessions weren't answered very well, given that they already had the solutions to them. Overall some of the exams were quite hard to follow. If would be useful to use in the future a pencil instead of pen and also to take some effort to make the questions readable (for example take a new paper instead of trying to force fit everything into the same page). Also, sometimes explaining the thought process a bit more would be beneficial.

    Further comments on some of the questions:

    -Surprisingly many struggled with defining/explaining the power set and cartesian product precisely. Somewhat common mistake for the power set was to think that P(A) = AxA. For the cartesian product there was he right idea but many students used notation/explanations which disincluded the possibility of infinite sets or the idea of ordering with the pair.

    -If the definitions were correct also part 1c) was correct

    -1d) Many people simply tried to use distributivity directly as an argument whereas this was precisely what was to be proven. Also some incorrect arguments including reference to the cardinality of the sets were present. Many though people argued in a very nice way using an arbitrary element belonging to the set on the left. Here too there very some implicit incorrect assumptions that the sets have to be finite.

    Exercise 2 went very well in general and I think almost everyone got full points for the direct proof. Only points I took away with the induction were usually from unclear presentation or structure. For example the induction assumption is not written out etc.

    For question 5:

    a) many students showed the right colouring but did not explain why the chromatic number cannot be lower with other colourings

    b) nothing special here, if the student just remembered how to do it

    I hope you enjoyed the course and good luck with your future courses!

    Best wishes,

    Tuomas