FP8-11 Graph Theory

Short Description
Enable the students to apply graph theory and graph algorithms to solve … applications are used as a tool to introduce algorithms from graph theory. …

Website: esn.aau.dk | Filesize: 77kb

Content
http://esn.auc.dk/empty_seat.pdf (spring)
FP8-11: Graph Theory
Course Description
Purpose:
?Introduce techniques and concepts from graph theory, so that the students will acquire an
understanding of graphs as representation of e.g. abstract data, or as models of relationships
between actions and sequences of actions
?Enable the students to understand the advantages and disadvantages of different graph
algorithms
?Enable the students to apply graph theory and graph algorithms to solve specific problems
Content:
The course takes application as its starting point exemplified by dialog modelling, circuit theory,
robot navigation, games, structural pattern recognition, parallelization of programs etc. These
applications are used as a tool to introduce algorithms from graph theory. The course focuses on the
tight relationship between data structures and algorithms. The following topics are covered by the
course:
?Representation of graphs
?Basic algorithmic aspects: introduction to complexity analysis, verification of algorithms
?Classic graph problems and algorithms: shortest path, spanning trees, detection of cycles,
travelling salesman
?Search (”game theory”): depth first and breadth first, game trees, optimal solution versus
efficiency, problem modelling, non-explicit representation
?Search optimization: cost directed search, the A* search algorithm,…