Discrete Mathematics, 7.5 credits

Main field of study with advanced study

Programming 7.5 credits. English 6.

The course is given in Applied Artificial Intelligence (AI) 180 credits and is also given as a single subject course.

The goals of the course are that the student develops an understanding and knowledge related to basic combinatorics, probability and graph theory as well as frequently encountered graph algorithms that have significance within computer science. The student acquires a scientific approach to probability theory and graph theory and consolidate and develop their prior knowledge in the subject.

Following successful completion of the course the student should be able to:

Knowledge and understanding

• define and explain the basic concepts within combinatorics, probability theory and graph theory
• discuss the theoretical and practical aspects of graph algorithms

Skills and ability

• solve simple combinatorial problems using permutations, combinations and variations
• apply solving methods for calculating probabilities
• identify basic types of graphs like Eulerian, Hamiltonian, planar, tree etc
• describe real concrete problems and translate these into mathematical models

Judgement and approach

• propose and evaluate appropriate mathematical models for applied problems
• critically review model selection and calculation results.

Combinatorics and Probability theory:
Basic combinatorics: permutations, combinations, variations. Inclusion/exclusion principle.The aspects of probability theory: random variable, conditional probability, independent events, Bayes’ theorem, expected value.

Graph theory and Graph algorithms:
Definitions and properties of different types of graphs: simple, undirected/directed, tree, planar, eulerian and hamiltonian graph, spanning tree, TSP (Travelling salesman problem) etc. DFS (Depth First Search) and BFS (Breadth First Search), Dijkstra’s, Prim’s and Kruskal’s algorithms.

Modeling:

Project where the student implements and tests simple graph algorithms in a programming language of their choice, e.g. Python.

The course consists of a series of lectures, exercises and individual project work. Supervision and consultation are provided for the project work.

Teaching is in English.

The course is examined through individual written exam and both written and oral presentation of the project work.

If there are special reasons, the examiner may make exceptions from the specified examination format and allow a student to be examined in another way. Special reasons can e.g. be study support for students with disabilities.

Course evaluation is part of the course. This evaluation offers guidance in the future development and planning of the course. Course evaluation is documented and made available to the students.