Algorithms in Graph Theory (3 op)
Toteutuksen tunnus: TX00DU27-3001
Toteutuksen perustiedot
Ilmoittautumisaika
02.05.2019 - 04.08.2019
Ajoitus
05.08.2019 - 09.08.2019
Opintopistemäärä
3 op
Toteutustapa
Lähiopetus
Yksikkö
School of ICT
Toimipiste
Leiritie 1
Opetuskielet
- Englanti
Paikat
0 - 24
Koulutus
- Degree Programme in Information Technology
- Information and Communication Technology
Opettaja
- Antti Piironen
- Koos van Tubergen
Ryhmät
-
ICTSUMMERICT Summer School
Tavoitteet
Often we would like to travel from one place to another. If we are by car, then TomTom will help us. If we send a mail, then routers will help us. Algorithms in Graph theory will do the work.
In this course we will look at concepts of Graph Theory to understand the algorithms, so we can apply them in IT.
• Know and understand the concepts of Graph Theory.
• Know and understand the Dijkstra, Posa, Bellman-Ford, and Balanced Graph algorithms.
• Implement these algorithms in IT.
Sisältö
1 Foundations
2 Extentsions
3 Networktraversal
4 Trees
5 Social Networks
Oppimateriaalit
An Introduction to Graph Theory and Complex Networks, by Maarten van Steen 2010
Opetusmenetelmät
In each sessions theoretical concepts will be introduced. These concepts will be applied in exercises. The algorithms will be implemented in a program.
Sisällön jaksotus
Session 1: Foundations Chapter 2: not paragraph 2.1.2, 2.2.2, 2.3 ( only page 2-22 until 2-28 )
Exercises page 195 : 7, 8
LAB exercise: make a program, that can store and print a graph
Session 2: Extensions
Chapter 3: not paragraph 3.1.2 ( only page 3-9 until 3-11 )
Exercises page B-12: 3, 4, 5, 6
LAB exercise: implement the Dijkstra algorithm at page 3-14
Session 3: Network traversal
Chapter 4: not paragraph 4.2.3
Exercises page 197: 15, 17
Page 50: 1a, b
LAB exercise: implement the Posa algorithm at page 4-21
Session 4: Trees Chapter 5: not 5.4.3
Exercises page 214: 5
page 215: 9, 10, 11, 12
LAB exercise: implement the Bellman-Ford algorithm at paragraph 5.4.2
Session 5: Social Networks Chapter 9: only paragraph 9.1.1, 9.1.2, 9.2.2
Exercise 14 exam 2019
LAB exercise: implement the Balanced graphs algorithm at page 9-23
Arviointiasteikko
0-5
Arviointikriteerit, tyydyttävä (1)
All exercises will have to be made, the code must be submitted and a small report with explanation should be written and handed in. Approval for all assignments by the teacher will be necessary to obtain the 3 ECTS.
Arviointikriteerit, hyvä (3)
-
Arviointikriteerit, kiitettävä (5)
-
Arviointikriteeri, hyväksytty/hylätty
All exercises will have to be made, the code must be submitted and a small report with explanation should be written and handed in. Approval for all assignments by the teacher will be necessary to obtain the 3 ECTS.
Arviointimenetelmät ja arvioinnin perusteet
All exercises will have to be made, the code must be submitted and a small report with explanation should be written and handed in. Approval for all assignments by the teacher will be necessary to obtain the 3 ECTS.
Prerequisites
Students must have basic knowledge of programming.