460-4039/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 introduction2010/2011Year of cancellation2010/2011
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
Combined 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

Další požadavky na studenta

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

Full-time form (validity from: 2010/2011 Winter semester)
Task nameType of taskMax. number of points
(act. for subtasks)
Min. number of points
Exercises evaluation and Examination Credit and Examination 100 (100) 51
        Exercises evaluation Credit 45  23
        Examination Examination 55  20
Mandatory attendence parzicipation:

Show history

Occurrence in study plans

Academic yearProgrammeField of studySpec.FormStudy language Tut. centreYearWSType of duty
2010/2011 (N2647) Information and Communication Technology (1103T031) Computational Mathematics P Czech Ostrava 2 Optional study plan
2010/2011 (N2647) Information and Communication Technology (1103T031) Computational Mathematics K Czech Ostrava 2 Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology P Czech Ostrava 2 Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology K Czech Ostrava 2 Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T059) Mobile Technology P Czech Ostrava 2 Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T059) Mobile Technology K Czech Ostrava 2 Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T025) Computer Science and Technology (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (B2649) Electrical Engineering (2601R004) Measurement and Control Engineering (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (B2649) Electrical Engineering (2602R014) Applied and Commercial Electronics (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (B2649) Electrical Engineering (3901R039) Biomedical Technician (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (B2649) Electrical Engineering (3907R001) Electrical Power Engineering (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (B2647) Information and Communication Technology (1103R031) Computational Mathematics (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (B2647) Information and Communication Technology (2601R013) Telecommunication Technology (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (B2647) Information and Communication Technology (2612R025) Computer Science and Technology (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (B2647) Information and Communication Technology (2612R059) Mobile Technology (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (N2647) Information and Communication Technology (1103T031) Computational Mathematics (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (N2647) Information and Communication Technology (2601T013) Telecommunication Technology (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (N2647) Information and Communication Technology (2612T059) Mobile Technology (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (N2649) Electrical Engineering (2601T004) Measurement and Control Engineering (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (N2649) Electrical Engineering (2612T015) Electronics (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (N2649) Electrical Engineering (3901T009) Biomedical Engineering (01) Exchange Students P Czech Ostrava Optional study plan
2010/2011 (N2649) Electrical Engineering (3907T001) Electrical Power Engineering (01) Exchange Students P Czech Ostrava Optional study plan

Occurrence in special blocks

Block nameAcademic yearForm of studyStudy language YearWSType of blockBlock owner