Subjects

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

Algorithms and Data Structures 1 - NTIN060

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

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

Opinion survey results Examination dates SS schedule Noticeboard

Annotation -

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

Introductory lecture on the basic types of algorithms and data structures necessary for their implementation. It follows the lecture NPRG062 Algorithmization in the previous semester.

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)

Optional topics in square brackets, the rest is mandatory.

1. Means for describing the complexity of algorithms and operations with data structures

measurement of data size, number of algorithm steps as a function of data size

RAM computational model

asymptotic notation

2. Tree data structures

binary search trees

AVL trees

(a,b)-trees

[red-black trees]

3. Hashing

a description of simple collision resolution strategies

analysis of the average time complexity of the search

universal hashing

4. Sorting

average case analysis for Quicksort, Randomized Quicksort

lower bound on the complexity of comparison sorting algorithms (decision trees)

5. Basic graph algorithms

depth-first search on an undirected graph, detection of bridges and articulations

depth-first search on a directed graph, transitive closure, topological numbering

[detection of components of strong connectivity in linear time]

6. Extreme paths in graphs

extreme paths in a directed acyclic graph, the critical path method

Dijkstra's algorithm (refresher of binary heaps, comparison of implementation using an array and a binary heap)

Bellman-Ford's algorithm (looking for negative cycles)

[Floyd-Warshall's algorithm]

7. Minimum spanning tree

Jarník's and Borůvka's algorithm

[Kruskal's algorithm and data structure for Union-Find]

8. Divide and conquer method

general schema of divide and conquer algorithms, describing their complexity by recurrent equations

substitution method for recurrent equations and "master theorem (cook-book)"

simple applications: binary search, Merge sort, multiplication of numbers (Karatsuba-Ofman)

more complex applications: Strassen's multiplication of matrices, [median search in linear time in the worst case]

9. Dynamic programming

general principle of dynamic programming

edit-distance of strings

[optimal search trees]