Admission requirements
Not applicable.
Description
This course provides the basic discrete mathematical foundation that is assumed as prior knowledge in many other computer science courses. It is a first formalization of general concepts from fundamental computer science.
Course objectives
From a bird's eye view, the main course objectives are as follows:
1. Build understanding of discrete mathematical structures common in computer science
2. Learn to deal with various formalizations, abstractions and proof techniques.
More concretely, the structures, abstractions, and techniques covered include:
1. Sets (e.g., defining sets, calculating with sets, and reasoning using Venn diagrams or set algebra).
2. Words (with prefixes, suffixes, subwords) and languages (i.e., sets of words).
3. Relations, and specifically
1. Properties of relations (e.g., total, surjective, injective; (anti)symmetric, etc.).
2. Particular kinds of relations (e.g., equivalence relations, partial orders).
3. Operators on relations (e.g., composition, inverse, closure).
4. Functions (in the relational sense).
4. Proof techniques, such as
1. Mathematical, strong and structural induction.
2. Proof by contradiction or counterexample.
3. Diagonalisation arguments.
5. Graphs; in detail, we will discuss:
1. Types of paths (closed, open, simple)
2. Euler circuits and Hamiltonian cycles
3. Special kinds of graphs (e.g., bipartite, complete)
4. Connected components
6. Trees, where we will cover:
1. Specific kinds of trees (ordered, rooted, binary)
2. Different kind of tree traversals (pre-order, in-order, post-order)
7. The concepts of countability and uncountability
8. Solutions to combinatorial problems, in which
1. order does (not) matter
2. repetition does (not) matter
3. some hybrid of the above applies
9. Modular arithmetic (i.e., congruence modulo a natural number)
Timetable
In MyTimetable, you can find all course and programme schedules, allowing you to create your personal timetable. Activities for which you have enrolled via MyStudyMap will automatically appear in your timetable.
Additionally, you can easily link MyTimetable to a calendar app on your phone, and schedule changes will be automatically updated in your calendar. You can also choose to receive email notifications about schedule changes. You can enable notifications in Settings after logging in.
Questions? Watch the video, read the instructions, or contact the ISSC helpdesk.
Note: Joint Degree students from Leiden/Delft need to combine information from both the Leiden and Delft MyTimetables to see a complete schedule. This video explains how to do it.
Mode of instruction
Lectures
Workgroups
Assessment method
The final grade is determined based on four marks, as follows:
1. A first assignment (A1) due about a quarter way through the course
2. A mid-term exam (M) halfway through the course, covering all material discussed thus far
3. A second assignment (A2) due about three quarters through the course
4. A final exam (F) at the end of the course. While this exam focuses on material discussed in the second half, it will assume prior knowledge of topics from the first half of the course, and can therefore not be prepared for in isolation.
The assignments can be made in groups of at most two students. For these assignments, use of AI assistance is strictly forbidden, and will be penalized severely.
To pass the course, the average grade of the exams (weighted equally) needs to be at least 5.5. This is true regardless of the grade attained for the assignments.
The final grade for the course is the maximum between:
A weighted average of the two assignments (each counting for 10%) and the two exams (each counting for 40%)
A weighted average of the two exams only (each counting for 50%)
Formally, this means that the final grade is computed as follows:
Grade = max { (0.1 * A1 + 0.4 * M + 0.1 * A2 + 0.4 * F), (0.5 * M + 0.5 * F) }
Thus, the grades for the assignments will never reduce the final grade.
There will also be a retake exam, which will cover all of the material discussed in the course (with the focus being distributed among both halves). The mark for this exam (R) will count for 80% of the final grade, with the remaining 20% being determined by the assignments, or for 100% - whichever gives the highest grade. As always, if the retake grade is lower than the original grade (G), then the grade on the transcript will not change.
Formally, this means that the final grade in case of a retake is computed as follows:
Retake grade = max { (0.8 * R + 0.1 * A1 + 0.1 * A2), R, G }
Reading list
Schaum’s Outline of Discrete Mathematics (4th edition), by Seymour Lipschutz, Marc Lipson. ISBN 9781264258802.
Additional material, slides, and exercises will be provided through the Brightspace page of the course.
Registration
As a student, you are responsible for enrolling on time through MyStudyMap.
In this short video, you can see step-by-step how to enrol for courses in MyStudyMap.
Extensive information about the operation of MyStudyMap can be found here.
There are two enrolment periods per year:
Enrolment for the fall opens in July
Enrolment for the spring opens in December
See this page for more information about deadlines and enrolling for courses and exams.
Note:
It is mandatory to enrol for all activities of a course that you are going to follow.
Your enrolment is only complete when you submit your course planning in the ‘Ready for enrolment’ tab by clicking ‘Send’.
Not being enrolled for an exam/resit means that you are not allowed to participate in the exam/resit.
Contact
Education coordinator LIACS bachelors
Remarks
Software
No specific software is required for this course.