MS-A0402 - Foundations of Discrete Mathematics, Lecture, 28.2.2022-14.4.2022
This course space end date is set to 14.04.2022 Search Courses: MS-A0402
Topic outline
-
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.
-
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.
-
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)
-
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