Course syllabus

# Diskreta strukturer i datavetenskap Discrete Structures in Computer Science

## EDAA40, 5 credits, G1 (First Cycle)

Valid for: 2016/17
Decided by: Education Board A
Date of Decision: 2016-04-05

## General Information

Main field: Technology.
Compulsory for: D1
Language of instruction: The course will be given in English

## Aim

The course is intended to introduce some of the basic formal concepts and terminology pervading all areas of computer science, and to establish a common lexicon, including notational conventions and nomenclature, that subsequent courses can build upon. This includes an introduction to abstract set theory, relations, functions, and ordered sets, Boolean algebra, logic and proof techniques, as well as structures such as graphs and trees.

## Learning outcomes

Knowledge and understanding
For a passing grade the student must

- demonstrate an understanding of basic notions of set theory, such as equivalence, cardinality, countability, infinite sets,

- be able to characterize functions, injective/surjective/bijective functions, relations, partial and total orders and their properties, complete partial orders,

- understand basic proof techniques such as induction,

- be familiar with Boolean algebra and first­ order logic,

- understand fundamental structures such as trees and graphs.

Competences and skills
For a passing grade the student must

- be able to use notation associated with sets, relations, functions, and orders to define structures and discuss their properties,

- be able to use induction to prove properties of infinite sets of objects,

- be able to manipulate, transform and simplify Boolean terms according to the laws of Boolean algebra,

- be able to work with trees and graphs, such as devising proofs of properties,

- be able to implement simple algorithms and tests for properties on discrete structures.

Judgement and approach
For a passing grade the student must

- be able to apply sets, graphs, and trees to represent aspects of real-world problems,

- show the ability to devise an appropriate proof strategy for a given problem.

## Contents

Sets, set equivalence, infinite sets, countability, functions, properties of functions (injective, surjective, bijective functions), relations, orders (total and partial), transitivity, (anti­) symmetry, reflexivity, equivalence relations and classes, complete partial orders, Boolean algebra, predicate logic, proofs, induction, graphs, trees.

## Examination details

Assessment: Written exam. The final grade of the course is based on the result of the written exam. For a passing grade of the course the compulsory course items must be completed.

Parts
Code: 0116. Name: Written Examination.
Credits: 3. Grading scale: TH. Assessment: The final grade of the course is based on the result of the written examination. In order to pass, the compulsory course items must also be completed. Contents: Written examination.
Code: 0216. Name: Compulsory Course Items.
Credits: 2. Grading scale: UG. Assessment: For a final grade the compulsory course items must be completed.