Terminated in academic year 2008/2009

Introduction to Algorithms

Type of study	Bachelor
Language of instruction	Czech
Code	456-0521/01
Abbreviation	ZAL
Course title	Introduction to Algorithms
Credits	6
Coordinating department	Department of Computer Science
Course coordinator	doc. Mgr. Jiří Dvorský, Ph.D.

Subject syllabus

Lectures:
Introductory lesson
Concept of algorithm, complexity of algorithm
Linear data structures - stack, queue, list
Sorting I.
Sorting II.

Binary search trees I.
Binary search trees II.
Balanced binary search trees - Red-black trees, B-trees.
Hashing
Pattern matching I.
Pattern matching II.
Advanced data structures - skip-list, splay trees (optionally)

Exercises:
Implementation of examples corresponding to lessons.

Projects:
Each student will implement one project during the term.

Computer labs:
Students work on thier project and on examples corresponding to current lesson.
Java programming revision
Searching in array - linear search, binary search
Implementation of stack (queue, list), Bracket parity checking
Implementation of O(n2) sorting algorithm
Implementation of O(nlogn) sorting algorithm, implementation using Comparable interface
Binary search trees - implementation of operations Insert and Search

Binary search trees - tree traversal algorithms, counting of nodes etc.
Complex example of usage of binary search trees
Implementation of hash table, hash function design and tests
Pattern matching algorithms
Work on term project

Literature

Studijní opora (skripta) pro ZAL
Wirth, N.: Algoritmy a štruktúry údajov, Alfa, Bratislava 1989.
Sedgewick R.: Algoritmy v C, části 1-4, SoftPress, Praha, 2003 Existuje i v anglické verzi, náročná, ale vynikající kniha.
Wróblewski P.: Algoritmy. Datové struktury a programovací techniky, Computer Press, Praha 2003

Advised literature

Topfer, P.: Algoritmy a programovací techniky, Prometheus, Praha 1995.
Virius, M.: Základy algoritmizace, ČVUT Praha, 1997, skripta.
Honzík, J. a kolektiv: Programovací techniky, VUT Brno, 1987, skripta.
Harel, D.: Algorithmics, The Spirits of Computing, Addison-Wesley Publishing Company, 1993.
Sedgewick, R.: Algorithms in C++, Addison-Wesley Publishing Company, 1992.
Wood, D.: Data Structures, Algorithms and Performance, Addison-Wesley Publishing Company, 1993.
Cormen, Leiserson, Rievest: Introduction to Algorithms, MIT Press, 2001.
Obecně jakákoliv učebnice jazyka Java.

back to search page