SubjectsSubjects(version: 845)
Course, academic year 2019/2020
   Login via CAS
Sorting - NTIN058
Title in English: Třídění
Guaranteed by: Department of Distributed and Dependable Systems (32-KDSS)
Faculty: Faculty of Mathematics and Physics
Actual: from 2014
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech
Teaching methods: full-time
Additional information: http://d3s.mff.cuni.cz/teaching/ntin058
Guarantor: RNDr. Alena Koubková, CSc.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: RNDr. Filip Zavoral, Ph.D. (03.04.2001)
A survey on sorting algorithms and their analysis. Sequential and parallel sorting algorithms, internal and external sorting.
Literature - Czech
Last update: RNDr. Alena Koubková, CSc. (27.04.2005)

Akl, S. G.: Parallel sorting algorithms. Academic Press, 1985.

Knuth, D. E.: The art of computer programming. Sorting and searching. Addison-Wesley, 1973.

Sedgewick, R.: Algorithms in C. Addison-Wesley, 1998 (česky SoftPress, 2003).

Requirements to the exam - Czech
Last update: RNDr. Alena Koubková, CSc. (10.10.2017)

Zkouška má pouze ústní část. Požadavky odpovídají sylabu přednášky.

Syllabus -
Last update: RNDr. Alena Koubková, CSc. (28.04.2005)

Sequential algorithms for internal sorting. Algorithms based on comparisons, bucket sorting, estimates of their complexity. A survey on well-known sorting algorithms (Bubblesort, Insertionsort, Quicksort, Mergesort,...) and their modifications. Some little-known sorting algorithms.

Parallel sorting. Parallel models of computation, measures of complexity of parallel algorithms. Special parallel architectures for sorting (sorting networks). Sorting on multi-purpose parallel machines with various types of processor interconnection ( linear, tree, ...), shared memory computers. Synchronous and asynchronous sorting.

Sorting of external files on tapes and discs. Complexity measures for external sorting.

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