Selected graph algorithms Field of study: Computer Science
Programme code: W4-S2INA19.2020

Module name: Selected graph algorithms
Module code: W4-INA-S2-20-F-WAG
Programme code: W4-S2INA19.2020
Semester:
  • summer semester 2021/2022
  • winter semester 2021/2022
  • summer semester 2020/2021
Language of instruction: English
Form of verification: course work
ECTS credits: 4
Description:
The course aims at acquainting the students with the basic knowledge of graph theory and selected graph algorithms. The students solve practical problems such as for which graph it is possible to apply representation, which can be solved using appropriate graph algorithms.
Prerequisites:
(no information given)
Key reading:
1. R.J.Wilson: Introduction to Graph Theory, Longman 1998 2. T.H.Cormen, C.E.Leiserson, R.L.Rivest: Introduction to Algorithms, Mit Press 3. R.Diestel: Graph theory, Springer, 2000
Learning outcome of the module Codes of the learning outcomes of the programme to which the learning outcome of the module is related [level of competence: scale 1-5]
The student is familiar with the concept of graphs, including trees, along with their features and types. [M_001]
 K_W01 [1/5] K_W04 [1/5] K_W09 [1/5]
The student understands the functioning of graph algorithms and trees used to solve selected practical problems. [M_002]
 K_W02 [1/5] K_W04 [1/5] K_W09 [1/5]
The student can apply an appropriate algorithm to solve a problem. [M_003]
 K_U01 [1/5] K_U08 [1/5]
The student can construct a solution to a problem according to a specific algorithm and program it in the chosen programming language. [M_004]
 K_U01 [1/5] K_U02 [1/5] K_U03 [1/5]
The student can work in a project-programming team. [M_005]
 K_K01 [1/5] K_K03 [1/5] K_K05 [1/5]
The student knows how to implement graphs, including trees, using tables and pointers. [M_006]
 K_W01 [1/5] K_W09 [1/5]
The student can implement graphs and trees using data structures available in particular programming languages. [M_007]
 K_U01 [1/5] K_U03 [1/5] K_U04 [1/5] K_U09 [1/5]
Type Description Codes of the learning outcomes of the module to which assessment is related
Evaluation of presentation and computer implementation [W_001]
The students develop their own software, the specification of which is given by the teacher, and make presentations on a chosen topic from the given list.
 M_001 M_002 M_003 M_004 M_005 M_006 M_007
Evaluation work [W_002]
The evaluation has a form of a written mid-term test (including a test performed on a computer during classes).
 M_001 M_002 M_003 M_006 M_007
End-term test [W_003]
The students answer test questions and describe problems by answering open-ended questions.
 M_001 M_002 M_003 M_004 M_006 M_007
Form of teaching Student's own work Assessment of the learning outcomes
Type Description (including teaching methods) Number of hours Description Number of hours
lecture [Z_001]
The lectures have a verbal form with the use of content visualisation. They primarily focus on conceptually demanding material, address some external sources and illustrate the content with some examples.
 15
The students study the lecture's topic using the existing packages of methods: manuals, scripts, websites, etc.
 30 End-term test [W_003]
laboratory classes [Z_002]
The classes thoroughly train the students to solve tasks concerning the proceeding method and the sequence of operations. The students design solutions and their computer implementation and present them in front of the class.
 30
The students complete tasks from particular topics and analyse existing solutions, available in the recommended materials and websites, and prepare for discussions or catching up.
 45 Evaluation of presentation and computer implementation [W_001] Evaluation work [W_002]
Attachments
Module description (PDF)
Information concerning module syllabuses might be changed during studies.
Syllabuses (USOSweb)
Semester Module Language of instruction
(no information given)