DIT008 H24 Diskret matematik
On this page you can find details about the discrete mathematics course DIT008 in the N1SOF Software Engineering and Management bachelor's programme.
The course plan is available here.
Literature
The course will be based on the book
Epp, S. S. (2020). Discrete Mathematics with Applications (Fifth edition, metric version). Cengage Learning
It is highly recommended that you buy this book if you are taking this course.
Schedule
The schedule for all lectures, exercise sessions and exams is available on TimeEdit.
Usually, there are three lectures and two exercise sessions a week. The lectures introduce new material, the exercise sessions provide opportunities to practice. Lectures happen in Babord and Styrbord.
Two exercise sessions are run in parallel, one led by Jan, the other one by Emil. Each group for the homework assignments will alternate between exercise leaders and should come to the corresponding session, see table below for details. Exercises happen in various rooms in Svea. The following table lists who will be in which room.
| Date | Emil | Jan |
|---|---|---|
| 2024-09-03 | Svea 219 | Svea 213 |
| 2024-09-05 | Svea 213 | Svea 130 |
| 2024-09-10 | Svea 219 | Svea 239 |
| 2024-09-12 | Svea 213 | Svea 130 |
| 2024-09-17 | Svea 219 | Svea 239 |
| 2024-09-19 | Svea 219 | Svea 239 |
| 2024-09-24 | Svea 219 (odd group numbers) | Svea 239 (even group numbers) |
| 2024-09-26 | Svea 219 (even group numbers) | Svea 239 (odd group numbers) |
| 2024-10-01 | Svea 213 (odd group numbers) | Svea 215 (even group numbers) |
| 2024-10-03 | Svea 219 (even group numbers) | Svea 239 (odd group numbers) |
| 2024-10-08 | Svea 213 (odd group numbers) | Svea 239 (even group numbers) |
| 2024-10-10 | Svea 219 (even group numbers) | Svea 213 (odd group numbers) |
| 2024-10-15 | Svea 219 (odd group numbers) | Svea 239 (even group numbers) |
| 2024-10-17 | Svea 219 (even group numbers) | Svea 213 (odd group numbers) |
| 2024-10-22 | Svea 213 (everyone) | |
| 2024-10-24 | Svea 219 (everyone) |
There are many irregularities in the schedule, so please check TimeEdit for exact times and places each week.
Assessment
The course is graded based on two parts:
Written Hall Exam
One of the grades distinction (5), pass with credit (4), pass (3) or fail (U) will be awarded.
All material from the lectures is examinable, excluding Turing machines and the halting problem. You will not be required to reproduce theorems or proofs of theorems which appeared in the lecture (e.g. the proof for the pigeonhole principle). But you will be required to be able to apply the theorems appropriately and to write proofs of simple statements as they appeared in the exercises.
The exam will contain problems which go beyond the difficulty level of the homework assignments. Take the exercises in the book as a reference for the difficulty level of the problems in the exam.
No calculators and no additional material like cheat sheets will be allowed.
There will be 12 problems on the exam with a total of 40 points. The grade boundaries will be
- pass (3): at least 20 points (50%)
- pass with credit (4): at least 28 points (70%)
- distinction (5): at least 36 points (90%).
Previous Exams
Homework assignments
There will be two homework assignments to be completed in groups of three and handed in within one week. All assignments will be graded with either pass or fail and you have to pass both assignments to pass this part of the course.
The groups will be self-assigned via Canvas, there will be an announcement when the group assignment opens.
The first assignment will be published on 2024-09-19 and is due on 2024-09-26.
The second assignment will be published on 2024-10-10 and is due on 2024-10-17.
Content
The course is designed to teach basic mathematical arguing and mathematical concepts relevant for software development. Specifically, it will cover
- Introduction: variables, sets, relations, functions
- Logical statements and logical equivalence
- Conditional statements
- Predicates and quantified statements
- Direct proofs and counterexamples
- Proof by contradiction
- Sequences
- Proof by induction
- Recursion and iteration
- Basics of set theory
- Basic properties of functions
- Basic probability theory and combinatorics
- Basic properties of graphs
- Trees
- Growth behavior of functions and algorithm efficiency
Detailed course plan
| Date | Content | |
|---|---|---|
| Lecture 1 | Tue 03/09 | Introduction, Sections 1.1, 1.2 |
| Exercise Session 1 | Tue 03/09 | Sections 1.1, 1.2, Exercises 1.1.2, 1.1.6, 1.1.11, 1.2.1, 1.2.4, 1.2.5, 1.2.7, 1.2.9, 1.2.12, 1.2.14 |
| Lecture 2 | Tue 03/09 | Sections 1.3, 2.1 |
| Lecture 3 | Thu 05/09 | Sections 2.2, 2.3 |
| Exercise Session 2 | Thu 05/09 | Sections 1.3, 2.1, 2.2, Exercises 1.3.2, 1.3.8, 1.3.20, 2.1.8, 2.1.22, 2.1.29, 2.1.45, 2.2.13, 2.2.18, 2.2.46, 2.2.48 |
| Lecture 4 | Tue 10/09 | Sections 3.1, 3.2 |
| Exercise Session 3 | Tue 10/09 | Sections 2.3, 3.1, 3.2, Exercises 2.3.9, 2.3.30, 2.3.40, 2.3.42, 3.1.3, 3.1.5, 3.1.12, 3.1.33, 3.2.1, 3.2.18, 3.2.38, 3.2.40, 3.2.41 |
| Lecture 5 | Tue 10/09 | Sections 3.3, 3.4 |
| Lecture 6 | Thu 12/09 | Sections 4.1, 4.2 |
| Exercise Session 4 | Thu 12/09 | Sections 3.3, 3.4, 4.1, Exercises 3.3.11, 3.3.12, 3.3.55, 3.3.56, 3.3.57, 3.3.58, 3.4.2, 3.4.5, 3.4.5, 3.4.7, 3.4.8, 3.4.17, 3.4.18, 3.4.25, 3.4.35, 4.1.8, 4.1.14, 4.1.28 |
| Lecture 7 | Tue 17/09 | Sections 4.3, 4.4 |
| Exercise Session 5 | Tue 17/09 | Sections 4.2, 4.3, 4,4, Exercises 4.2.6, 4.2.7, 4.2.8, 4.2.16, 4.2.22, 4.2.29, 4.2.31, 4.2.41, 4.3.6, 4.3.13, 4.3.19, 4.3.21, 4.3.28, 4.3.35, 4.3.36, 4.3.37, 4.3.38, 4.4.14, 4.4.17, 4.4.20, 4.4.39 |
| Lecture 8 | Tue 17/09 | Sections 4.5, 4.6 |
| Lecture 9 | Thu 19/09 | Sections 4.6, 4.7 |
| Exercise Session 6 | Thu 19/09 | Sections 4.5, 4.6, 4.7, Exercises 4.5.16, 4.5.20, 4.5.44, 4.6.1, 4.6.2, 4.6.3, 4.6.4, 4.6.8, 4.6.9, 4.6.18, 4.6.19, 4.6.28, 4.7.1, 4.7.5, 4.7.10, 4.7.16, 4.7.31 |
| Lecture 10 | Tue 24/09 | Sections 5.1, 5.2 |
| Exercise Session 7 | Tue 24/09 | Sections 5.1, 5.2, Exercises 5.1.19, 5.1.20, 5.1.27, 5.1.53, 5.1.54, 5.1.59, 5.1.65, 5.1.66, 5.1.68, 5.1.69, 5.2.5, 5.2.10, 5.2.13, 5.2.15, 5.2.28, 5.2.30 |
| Lecture 11 | Tue 24/09 | Sections 5.6, 5.7 |
| Lecture 12 | Thu 26/09 | Section 6.1, Halting Problem |
| Exercise Session 8 | Thu 26/09 | Sections 5.6, 5.7, 6.1, Exercises 5.6.3, 5.6.5, 5.6.13, 5.6.27, 5.6.39, 5.6.44, 5.7.2, 5.7.3, 5.7.10, 5.7.12, 5.7.24, 5.7.43, 5.7.50, 6.1.5, 6.1.11, 6.1.15, 6.1.28, 6.1.31, 6.1.35 |
| Lecture 13 | Tue 01/10 | Sections 7.1, 7.2 |
| Exercise Session 9 | Tue 01/10 | Assignment 1 |
| Lecture 14 | Tue 01/10 | Sections 9.1, 9.2 |
| Lecture 15 | Thu 03/10 | Sections 9.3, 9.4 |
| Exercise Session 10 | Thu 03/10 | Sections 7.1, 7.2, 9.1, Exercises 7.1.1, 7.1.4, 7.1.11, 7.1.19, 7.1.21, 7.1.35, 7.1.38, 7.2.1, 7.2.4, 7.2.6, 7.2.10, 7.2.15, 7.2.16, 7.2.26, 7.2.28, 7.2.36, 9.1.9, 9.1.16, 9.1.23, 9.1.28 |
| Lecture 16 | Tue 08/10 | Sections 9.5, 9.6 |
| Exercise Session 11 | Tue 08/10 | Sections 9.2, 9.3, 9.4, Exercises 9.2.6, 9.2.11, 9.2.19, 9.2.39, 9.2.41, 9.3.3, 9.3.6, 9.3.9, 9.3.32, 9.3.33, 9.4.3, 9.4.7, 9.4.20, 9.4.22, 9.4.22, 9.4.25, 9.4.26, 9.4.29 |
| Lecture 17 | Tue 08/10 | Sections 1.4 (definitions only), 10.1 (excluding Hamiltonian circuits) |
| Lecture 18 | Thu 10/10 | Sections 10.2, 10.4 |
| Exercise Session 12 | Thu 10/10 | Sections 9.5, 9.6, 10.1, Exercises 9.5.1, 9.5.6, 9.5.19, 9.5.23, 9.5.25, 9.6.1, 9.6.3, 9.6.5, 9.6.8, 9.6.16, 10.1.1, 10.1.4, 10.1.8, 10.1.12, 10.1.14, 10.1.23 |
| Lecture 19 | Tue 15/10 | Sections 10.4, 10.5, Lecture Notes |
| Exercise Session 13 | Tue 15/10 | Sections 10.2, 10.4, 10.5, Exercises 10.2.2, 10.2.3, 10.2.10, 10.2.15, 10.2.17, 10.2.20, 10.4.8-10, 10.4.12-14, 10.4.22, 10.4.25, 10.5.1, 10.5.4-11, 10.5.20 |
| Lecture 20 | Tue 15/10 | Sections 10.5, 10.6, Lecture Notes |
| Lecture 21 | Thu 17/10 | Sections 11.1, 11.2, 11.3 |
| Exercise Session 14 | Thu 17/10 | Sections 10.6, 11.1, 11.2, Exercises 10.6.1, 10.6.2, 10.6.7, 10.6.8, 10.6.12, 10.6.13, 10.6.20, 10.6.24, 11.1.3, 11.1.5, 11.1.15, 11.1.19, 11.1.24, 11.1.27 |
| Lecture 22 | Fri 18/10 | Section 11.3, 11.4 |
| Lecture 23 | Mon 21/10 | Summary |
| Exercise Session 15 | Tue 22/10 | Sections 11.3, 11.4, Exercises 11.3.4, 11.3.6, 11.3.11, 11.3.17, 11.3.40, 11.3.42, 11.3.43, 11.4.9, 11.4.13, 11.4.21(a), 11.4.32, 11.4.33, 11.4.41, 11.4.45, 11.4.47 |
| Exercise Session 16 | Thu 24/10 | Assignment 2 |
| Lecture 24 | Fri 25/10 | Q & A, Exercises |
Math Support
For additional support with the lecture material and the homework assignments, you can go to Math Support. There, you can ask senior students in mathematics any math-related questions you have, several times a week.
Student representatives
The student representatives for this course are:
- Abdullah Arif (gusarifab@student.gu.se)
- Leon Ljungström (gusleolj@student.gu.se)
- Omar Moussa (gusmouom@student.gu.se)
- Sheikh Muhammad Shoaib (gusshoash@student.gu.se)
- Ville Vikingsson (gusvikivi@student.gu.se)
If you have any issues that you don’t want to raise with the teachers directly, you can contact one of the representatives and they’ll relay your concern.
Teachers
Examiner: Jan Gerken
Lecturer: Jan Gerken
Teaching Assistant: Emil Nyström