SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Extension seminar Algorithms and Data Structures I - NTIN107
Title in English: Rozšiřující seminář Algoritmy a datové struktury I
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2019
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:0/2 C [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. RNDr. Luděk Kučera, DrSc.
Class: Informatika Bc.
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: Mgr. Jan Kynčl, Ph.D. (21.05.2018)
The course is a continuation of NTIN060 Algorithms and Data Structures I; algorithms taught in ADS I are shown under a different point of view and other and more advanced methods are introduced. Algorithms are presented using visualizations that are created so that illustrate basic ideas on which the algorithms are based. The goal is to present algorithms as a creative part of the computer science and to teach students to think about the behavior and properties of algorithms in an exact way.
Literature -
Last update: Mgr. Jan Kynčl, Ph.D. (21.05.2018)

1. Visualizations are available at www.algovision.org, a web browser (Chrome, Mozilla) and pdf reader (e.g., Adobe Acrobat) suffice

2. Cormen, Leiserson, Rivest, Stein : Introduction to algorithms (2nd Edition), Mc Graw Hill 2001

3. 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/

Syllabus -
Last update: Mgr. Jan Kynčl, Ph.D. (21.05.2018)

Tree data structures with the search operation: binary search trees (BST), balanced BST (AVL-trees and red-black trees), B-trees

Heaps: The standard heap, binomial (mergeable) heap, Fibonacci heap.

Standard sorting algorithms: bubblesort, mergesort, quicksort, heapsort.

Algorithms connected to sorting: median (and k-th element) search; sorting and switching networks: bitonic sorter.

Basic graph algorithms: graph and tree searching (depth and breadth search), shortest and extremal paths (CPM, Dijkstra, Bellman-Ford), minimum spanning tree (general scheme, Jarnik-Prim and Kruskal implementations), spectral heuristics for min-cut.

Detailed syllabus:

1. Binary search trees.

2. AVL-trees.

3. Red-black trees.

4. B-stromy.

5. Standard heap, binomial (mergeable) heap.

6. Fibonacci heap.

7. Bubblesort, mergesort, quicksort, median (and k-th element) search.

8. Bitonic sorter.

9. Graph and tree searching.

10. Shortest and extremal paths - CPM, Dijkstra.

11. Shortest and extremal paths - Bellman-Ford.

12. Minimum spanning tree (general scheme, Jarnik-Prim and Kruskal implementations).

13. Spectral heuristics for min-cut.

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html