Course syllabus

# Diskreta strukturer i datavetenskap

Discrete Structures in Computer Science

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

## General Information

## Aim

## Learning outcomes

## Contents

## Examination details

## Admission

Admission requirements:## Reading list

## Contact and other information

Discrete Structures in Computer Science

Valid for: 2016/17

Decided by: Education Board A

Date of Decision: 2016-04-05

Main field: Technology.

Compulsory for: D1

Language of instruction: The course will be given in English

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.

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.

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.

Grading scale: TH

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.

- Completed compulsory course items from EDAA01

The number of participants is limited to: No

The course overlaps following course/s: EDAF10

- David Makinson: Sets, Logic, and Maths for Computing, 2nd ed. Springer. The book is also available as a free PDF/eBook download within the LTH network: http://link.springer.com/book/10.1007%2F978-1-4471-2500-6.

Course coordinator: Jörn Janneck, jorn.janneck@cs.lth.se

Course homepage: http://cs.lth.se/edaa40