Gurantor department | Department of Computer Science | Credits | 4 |

Subject guarantor | RNDr. Eliška Ochodková, Ph.D. | Subject version guarantor | RNDr. Eliška Ochodková, Ph.D. |

Study level | undergraduate or graduate | Requirement | Optional |

Year | 2 | Semester | winter |

Study language | Czech | ||

Year of introduction | 2010/2011 | Year of cancellation | 2010/2011 |

Intended for the faculties | FEI | Intended for study types | Follow-up Master |

Instruction secured by | |||
---|---|---|---|

Login | Name | Tuitor | Teacher giving lectures |

OH140 | RNDr. Eliška Ochodková, Ph.D. |

Extent of instruction for forms of study | ||
---|---|---|

Form of study | Way of compl. | Extent |

Full-time | Credit and Examination | 2+1 |

Combined | Credit and Examination | 10+5 |

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.

Lectures

Tutorials

Project work

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.

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

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/

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.

Subject has no prerequisities.

Subject has no co-requisities.

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.

Task name | Type of task | Max. 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 |

Show history

Academic year | Programme | Field of study | Spec. | Form | Study language | Tut. centre | Year | W | S | Type 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 |

Block name | Academic year | Form of study | Study language | Year | W | S | Type of block | Block owner |
---|