Foundations of Computing - Discrete Mathematics BSc (Autumn 2018)

Abstract

Description

The course introduces the foundations of computational thinking and logic reasoning which are essential skills for a software developer. Building upon these skills, the course covers a range of mathematical concepts that are the foundations of many areas of computer science: just to name a few, databases rely heavily on set theory and relational algebra; advanced algorithms and data structure require notions such as graphs and trees, regular grammars and automata, solving recurrence relations to talk about asymptotic complexity, familiarity with the induction principle to prove the correctness of iterative and recursive algorithms; probability theory enables the study of machine learning and cryptography, which also benefits a lot from number theory.

The student will obtain the fundamental skill of computational thinking and will be better equipped to tackle technical subjects throughout the curriculum.

The course is an introduction to discrete mathematics as a foundation to work within the fields of computer science, information technologies, and software development.
The course develops the necessary terminology and conceptual tools needed for later courses. This includes:

• formal reasoning, proofs, logic, set theory, sequences and sums
• number theory, combinatorics and (discrete) probability theory
• induction, recursion and counting
• relations and functions
• basic graph theory, language theory
• theory and models of computation, such as finite state machines, regular expressions and grammars

The course aims at providing a basic understanding of the mathematical foundations of computer science.

Formal prerequisites

Basic arithmetics.

Intended learning outcomes

After the course, the student should be able to:

• Describe and apply formal definitions
• Conduct and explain basic formal proofs
• Work with regular languages and finite and infinite state machines
• Use models of computation and specification
• Use combinatorial reasoning
• Assess probabilities of events
• Use basic modular arithmetic

Ordinary exam

Exam type:
X: Special exam type, external (7-trinsskala)
Exam description:
4 hours written exam with no aids. There is no access to advanced electronic tools such as computers, e-Readers or tablets. Only old-fashioned pocket calculators and standard tools for writing on paper are allowed (pen, pencil, eraser, etc.). Only use of pen is allowed for the final exam hand-in. Form of re-exam is the same as the ordinairy exam.