Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

Algorithms and Data Structures I - NTIN060

Czech title:	Algoritmy a datové struktury I
Guaranteed by:	Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty:	Faculty of Mathematics and Physics
Actual:	from 2017 to 2017
Semester:	summer
E-Credits:	5
Hours per week, examination:	summer s.:2/2 C+Ex [hours/week]
Capacity:	unlimited
Min. number of students:	unlimited
State of the course:	taught
Language:	Czech, English
Teaching methods:	full-time

Guarantor:	Mgr. Martin Mareš, Ph.D. doc. RNDr. Ondřej Čepek, Ph.D. Mgr. Jan Hubička, Ph.D.
Class:	Informatika Bc.
Classification:	Informatics > Theoretical Computer Science

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

A course about basic types of algorithms and data structures needed for their implementation.

Aim of the course - Czech

Last update: T_KTI (23.05.2008)

Naučit základní datové struktury, algoritmy a metody teoretické informatiky

Course completion requirements -

Last update: Mgr. Martin Mareš, Ph.D. (04.03.2018)

It is necessary to get course credit and pass the examination (in arbitrary order). Credit is given for solving homeworks, including potential additional homeworks at the end of the semester. The nature of this requirement excludes the possibility of repeated attempts to get credit, which means that if you do not obtain enough points for homeworks, there is no other way how to get credit.

The examination consists of a written and oral part. The written part precedes the oral part, a failure in the written part implies failing the whole exam, so the oral part is skipped in such cases.

Literature - Czech

Last update: RNDr. Jan Hric (03.10.2017)

Cormen, Leiserson, Rivest, Stein : Introduction to algorithms (2nd Edition), Mc Graw Hill 2001
M.Mareš, T.Valla : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, 978-80-88168-19-5, http://pruvodce.ucw.cz/
Videozáznamy přednášek

Requirements to the exam -

Last update: Mgr. Martin Mareš, Ph.D. (02.03.2018)

It is necessary to understand the theory presented at the lectures and to be able to apply it to solving of algorithmic problems.

Syllabus -

Last update: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)

Asymptotic notation.

Tree structures, binary search trees, AVL trees, Red-black trees.

Hashing, solving of collisions, analysis of average case.

Sorting. Analysis of average case for quicksort, randomization. Lower bound for sorting (decision trees), linear-time sorting based on indexing by keys.

Graph algorithms, depth-first search, breadth-first search, strongly connected components, transitive closure, topological sorting.

Extreme paths in graphs. Method of critical path - PERT. Dijkstra alg., Bellman-Ford alg. (searching of negative cycles), Floyd-Warshall alg. for all paths.

Minimal spanning tree. Kruskal alg., Prim-Jarnik alg.

Method Divide and conquer. General schema, solving of recurrent equations. Master theorem. Applications: binary searching, mergesort, Strassen alg.

Eucleid alg., LUP decomposition.