Ämnesdisposition
-
Instructor: Sofia Tirabassi (tirabassi@math.su.se)
Teaching assistant: Séverin Philip
The course will be given in English
Textbook: R.P. Grimaldi, Discrete and combinatorial mathematics. An applied introduction, Pearson, fifth edition, ISBN 0-321-21103-0. (Note that the version with ISBN 1-292-02279-5 is of very bad quality and does not include chapter 17.)
There are also some typed lecture notes that should help you put order in the theory. This is the first version, so it is going typos... please help me improve it by using the forum below.
Old video resources: https://www.youtube.com/playlist?list=PLO7HV4vzLIgYvtAfGjNAKKX96-v4f3KGq
Newer video resources: https://www.youtube.com/playlist?list=PLW-AP6BXNiBOwSSaSDgPVdYyItr6Zu-s4,
This is a distance course, that is students are assumed to read by themselves, viewing the video material, reading the book(which is most important) and solving exercises. We will also have regular zoom lectures where I will explain the material and answer questions. I will follow the schedule below:
Lectures: Mondays Thursdays 9:00-10:45 Zoom Meeting: 65640306492
Exercise Sessions: Mondays Thursdays 11:00-12:00 starting from the second lecture of the course (Nov. 7th). Zoom meeting : 425627
Examiner: Sofia Tirabassi
Examination form: Written
Examination dates: January 14th 14-19
Re-exam:TBA
Examination Rules at the Department of Mathematics.
Bonus system:
To help you stay on track, there will be some exercise sheets. You will receive bonus points according to the proportion of exercises you solved correctly, with a maximum of 3 bonus point that will be added to your written exam once it is graded. You can use bonus points both for the exam and the re-exam.
Deadline for submitting: There will be one or two deadline every week, on Sundays kl 23:59 and on Wednesdays kl 23:59. As the bonus points can only improve the grade of your exam, no extension will be granted.
Recordings from older courses:
Lecture 1, part 1
https://www.youtube.com/watch?v=V_EKLXZaolo
Lecture 1, part 2
https://youtu.be/6wjde6WQBcM
Lecture 2
Lecture 3, part 2. (Part1 got corrupted)
Lecture 4
Lecture 5Lecture 6Lecture 7Lecture 8https://youtu.be/ZY75Fd38GAw
Lecture 9
https://www.youtube.com/watch?v=FYcaQ-3rFTU&t=2148s
Lecture 10https://www.youtube.com/watch?v=OL4ozRr5W4A&t=9sLecture 11https://www.youtube.com/watch?v=JFdMBJwXIfk&t=52sLecture 12Lecture 13Lecture 14https://www.youtube.com/watch?v=IjlpW4ueZEQ&feature=youtu.be-
Here you can ask for help in understanding the video and the book. I will go over the questions during the lecture time. If you want me to address the problem on Monday you have to ask before Friday at 12.
-
Here you can ask for help in solving exercises. If you have a question post it here, it is the only way you will get an answer :)
-
This lecture notes help put order in the theory of this course giving it the definition-statement-proof structure. No example are provided because they are covered in the book.
I fixed the typo signaled during the lecture! Thanks!
-
Basic counting principles; Functions and the pigeon-hole principle
Reading:
Counting: 1.1 - 1.4,
Basic set theory: 3.1 - 3.2,
Relations and functions: 5.1 - 5.3, 5.5
Videos: “Basic Principles of Counting” & “Functions and the Pidgeonhole Principle”
Lecture recording part 1 (HT22)
Lecture Recording part 1 (HT23)
Lecture recording part 2 (HT23)
Lecture recording H24
Exercises:
1.1+1.2: 10,16,20,22
1.3: 10,12,16,18
1.4: 2,4,8,103.1: 2,9,15
3.2: 4,13,175.3: 8,10,13
5.5: 4,8,10,12,13,20 -
Inclusion-exclusion formulae
Text: 8.1-8.3
Video: "Inclusion Exclusion Principle"
Exercises:
8.1: 4,16,20
8.2: 2,4
8.3: 4,6,10Recordig of lecture (HT23)- just second half
Recording of the lecture (H24)
-
Rook polynomials
Text: 8.4-8.5
Video: "Rook polynomials"
Exercises:
8.4 + 8.5: 4,6,9,10,12 -
Generating functions I and partitions
Text: 9.1-9.3
Video: "Generating functions"
Exercises:
9.2: 8,10,16,30
9.3: 2,3,4,5,10 -
Generating functions II
Text: 9.4-9.5
Video: "Exponential generating functions"
Exercises:
9.4: 2,4,6,7
9.5: 2,4 -
Recursions I
Text: 10.1-10.2
Video: "Homogeneous recurrence relations"
Exercises:
10.1: 2
10.2: 4,9,11,12,13,14,24, 26, 28 -
Recursions II
Text: 10.3-10.4
Video: "Non-homogeneous recurrence relations"
Lecture video(I forgot to stop the recording, so there will be a 15 minutes break in the middle)
Exercises:
10.3: 2,8,12
10.4: 1 -
Graphs I
Text: 11.1-11.2
Video: "Basics of graph theory"
Exercises:
11.1: 2,4,6,10,14
11.2: 2,6,8,10,12 -
Lecture Part 1 - unfortunately I completely forgot to press the "record button" the good news is that all the material in the first part of the lecture was more or less straightforward from the book and without any proof. I apologize for the mistake
Lecture Part 2 -
Graphs II
Text: 11.3-11.4
Video: "Planar graphs"
Lecture video (I forgot to stop the recording midways)
Exercises:
11.3: 1,2,4,6,8,10,20,22,24
11.4: 2,6,8,10,12,14,18,19,21,22 -
Graphs III
Text: 11.5 - 11.6
Video: "Hamilton paths"
Exercises:
11.5: 2,6,8,10,12,18
11.6: 2,4,6,8,9,10,14,15,16 -
Trees
Text: 12.1-12.2
Video: unfortunately no video is available from SU. Here is another link to YouTube.
Exercises:
12.1: 2,3,4,5,6,7,8,10,12,16,18
12.2: 1,7,8,10,16,17 -
Combinatorial optimization
Text: 13.1-13.2
Exercises:
13.1: 2,3
13.2: 1,2,4 -
Video part 1 https://youtu.be/gUJuc1d594E
Video part 2 https://youtu.be/WbOSJ8IlWgQ
-
Online lesson starts at 9:30 and we go forward without pause. Sorry for that.
Combinatorial optimisation II
Text: 13.3
Exercises:
13.3: 1,4,6,7 (find in 4 also the corresponding minimal cut), you can try to start with a flow with large flow value -
Finite geometry
Text: Lecture notes
Alternative text: Course book chapters 17.3–17.4
Exercises:
17.3: 1, 4, 5
17.4: 3, 5, 6Due to some issues, exercise session will be at 6 pm.
-
Review! No new material
Lecture video part 1
Lecture video part 2
Hello!
Thanks to all thos who have connected today. It was impossible to record due to way to many technical problems that occurred.
Thank you for a great )half) semester. Get rested!!! And see you at the exam -
Grade scale
<15 F
15-17.99 E
18-20.99 D
21-23.99 C
24-26.99 B
27+ A