456-0313/01 – Graph Algorithms (GAL)

Gurantor departmentDepartment of Computer ScienceCredits4
Subject guarantorRNDr. Eliška Ochodková, Ph.D.Subject version guarantorRNDr. Eliška Ochodková, Ph.D.
Study levelundergraduate or graduateRequirementOptional
Year2Semesterwinter
Study languageCzech
Year of introduction2003/2004Year of cancellation2009/2010
Intended for the facultiesFEIIntended for study typesFollow-up Master
Instruction secured by
LoginNameTuitorTeacher giving lectures
OH140 RNDr. Eliška Ochodková, Ph.D.
Extent of instruction for forms of study
Form of studyWay of compl.Extent
Full-time Credit and Examination 2+1
Part-time Credit and Examination 10+5

Subject aims expressed by acquired skills and competences

After graduation student will be able to: 1. For solving given problems choose proper graph algorithms and implemnt it. 2. Experiment with chosen datasets and analyze achieved results. 3. Interpret experiments results and design possible modifications of used algorithms. 4. Summarize properties of real networks represented by used dataset. 5. Cooperate on project.

Teaching methods

Lectures
Tutorials
Project work

Summary

This course will be concentrating on the basic graph algorithms. Learning and designing efficient algorithms for basic graph theoretic problems that are used as building blocks elsewhere (shortest paths, minimum spanning trees, matching, flows, ...). This course is concerned in models and algorithms for complex networks such as the Web, the internet, social networks and biological networks, too. The goal is to see the common structure and properties that underlie these networks.

Compulsory literature:

1. M. E. J. Newman: The structure and function of complex networks, SIAM Reviews, 45(2): 167-256, 2003 2. A.L. Barabasi: Scale Free Networks 3. S. H. Strogatz: Exploring Complex Networks 4. R. Albert and L.A. Barabasi: Statistical Mechanics of Complex Networks, Rev. Mod. Phys. 74, 47-97 (2002). 7. McHugh J. A.: Algorithmic graph theory, PRENTICE HALL, 1990. 8. Cormen T.H., Leiserson Ch.E., Rivest R.L.: Introduction to algorithms, The MIT Press, 1990. 9. Bang-Jensen J., Guitn G.: Digraphs, Theory, Algorithms and Applications, Springer 2002 10. Jungnickel D.: Graphs, Networks and Algorithms, Springer 2005

Recommended literature:

1. The Stony Brook Algorithm Repository, http://www.cs.sunysb.edu/~algorith/ 2. Journal of Graph Algorithms and Applications, ISSN: 1526-1719, http://www.cs.brown.edu/publications/jgaa/

Way of continuous check of knowledge in the course of semester

Conditions for credit - Encompassing chosen project: problem understanding, algorithm selection, implementation, functionality of application, experiments and their results, project presentation. It is necessary to obtain at least (>=) 23 points from 45 possible.

E-learning

Other requirements

Prerequisities

Subject has no prerequisities.

Co-requisities

Subject has no co-requisities.

Subject syllabus:

Lectures: Representation of graphs - graphic, adjacency matrix, the edge list, the edge incidence matrix, and the adjacency list. Graph traversal - basic algorithm, depth-first search, breadth-first search. Shortest path - basic algorithm and its modifications, Dijkstra's algorithm, Bellman-Ford's algorithm. Floyd's algorithm and negative cycle testing. Topological ordering of vertices and edges - algorithm of topological ordering and its modifications of searching shortest path. Cycle testing. (Strong) components algorithm - apply Floyd's algorithm. Graph connectivity. Minimum spanning tree. Transitive closure and reduction Matching on a bipartite graphs - maximum matching algorithm on a bipartite graphs, cheapest maximum matching algorithm on a complete bipartite graphs. Maximum matching - maximum matching algorithm of Edmonds. Euler trail - conditions of existence open (closed) euler trail on directed (undirected) connected graphs. Euler trail algorithms. Graph coloring - verticies coloring algorithm, edges coloring algorithm. Algorithm of independent sets. Planar graphs. Network flows - maximum flow algorithm (Ford-Fulkerson algorithm), cheapest maximum flow algorithm. Heuristic algorithms - Hamiltonian paths, isomorphic graphs, independent sets. Complex networks. Common structure of complex networks. Their properties. Exercises: Demonsrarton of particular algorithms. Projects: The goal of project is to demonstrate knowledge of graph algorithms through their implemetatation.

Conditions for subject completion

Conditions for completion are defined only for particular subject version and form of study

Occurrence in study plans

Academic yearProgrammeBranch/spec.Spec.ZaměřeníFormStudy language Tut. centreYearWSType of duty
2009/2010 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2009/2010 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2009/2010 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2009/2010 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2009/2010 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2009/2010 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2009/2010 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2008/2009 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2008/2009 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2008/2009 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2008/2009 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2008/2009 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2008/2009 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2008/2009 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2008/2009 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Optional study plan
2007/2008 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2007/2008 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Optional study plan
2007/2008 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2007/2008 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2007/2008 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2007/2008 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2007/2008 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2007/2008 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2006/2007 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2006/2007 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Optional study plan
2006/2007 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2006/2007 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2006/2007 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2006/2007 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2006/2007 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2006/2007 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Optional study plan
2005/2006 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 3 Choice-compulsory study plan
2005/2006 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Optional study plan
2005/2006 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 3 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 3 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan
2004/2005 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology P Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (1103T021) Computational Mathematics P Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (2612T025) Computer Science and Technology K Czech Ostrava 3 Choice-compulsory study plan
2003/2004 (N2646) Information Technology (1103T021) Computational Mathematics K Czech Ostrava 3 Choice-compulsory study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner

Assessment of instruction



2009/2010 Winter