# Foundations of Computer Science

Course
2024-2025

Not applicable.

## Description

This course provides the basic mathematical foundation that is implicitly or explicitly assumed as prior knowledge in many other computer science courses. It is a first formalization of general concepts from fundamental computer science. Some of the topics covered includes sets, functions and relations, graphs, trees, induction, and languages.

## Course objectives

Getting knowledge with discrete mathematical structures that are commonly used in computer science; learning to deal with formalizations, abstractions and proof techniques.

1. Calculate with sets (e.g., reason using Venn diagrams, set algebra, and definitions)
2. Represent relations, evaluate their properties (e.g., total, functional, surjective, injective; (ir)reflexive, (anti)symmetric, transitive), argue whether a relation is an equivalence relation or partial order, and construct relations (e.g., composition, inverse, closure)
3. Prove statements using mathematical, strong and structural induction, and apply other proof techniques (e.g., contradiction, counterexample, diagonalisation argument)
4. Represent graphs, identify closed and open paths, connected components, Euler circuits, Hamiltonian cycles, and construct special graphs (e.g., bipartite)
5. Distinguish between trees, (ordered) rooted trees and binary trees, and compute tree traversals (e.g., pre-order and post-order)
6. Solve combinatorial problems for which order matters/does not matter, with/without repetition
7. Make use of the equivalence relations: equipotence and congruence modulo m
8. Employ regular languages (e.g., perform operations on strings and languages)

## 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.

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.

• Lectures

• Workgroups

## Assessment method

There will be a mid-term written exam (M) halfway through the course and another one at the end of the course consisting of two parts P1 and P2, with P1 treating the same material as the mid-term exam and P2 the other half. The final grade will be calculated as follows:

``````   Grade = max{M,P1}+P2
``````

The mid-term exam is meant to test the knowledge gained so far, and to possibly improve the final grade without penalizing it.

In addition, there will be a retake written exam that will count for 100% of the final grade.

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

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
Starting from the 2024/2025 academic year, the Faculty of Science will use the software distribution platform Academic Software. Through this platform, you can access the software needed for specific courses in your studies. For some software, your laptop must meet certain system requirements, which will be specified with the software. It is important to install the software before the start of the course. More information about the laptop requirements can be found on the student website.