Logo ČVUT
CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2018/2019

Data and Data Structures

Login to KOS for course enrollment Display time-table
Code Completion Credits Range Language
17PBIDDS Z,ZK 5 2P+2C Czech
Lecturer:
Jan Kauler (guarantor), Radim Krupička (guarantor)
Tutor:
Jan Kauler (guarantor), Radim Krupička (guarantor), Jan Tesař
Supervisor:
Department of Biomedical Informatics
Synopsis:

A survey of basic data structures and their application. A specification of abstract data types (ADT). Specification and implementation of ADT: list, stack, queue, set, array, look-up table, graph, binary tree. Dynamic data structures and operations with them (effective searching, sorting, storing of data structures etc.). Representation of the data structures, strategies for choice of proper data structure.

Requirements:

For tests to be 4 examples. 2 examples of substances lectured by Doc. Jiřina, 1 example of substances lectured by Mgr. Krupička and 1 example of substances lectured by Dr. Kauler. Each example will be rated by 0-25 points. Total evaluation according to the ECTS scale. Examples are numerous, or „drawing“, but not theoretical. The test is 1 hour (60 minutes). For the test are allowed, papers, pen/pencil, or a simple calculator.

More information about examination you can find below on the subject web page.

Prerequisites are passing all the exercises (max 3 leaves of absence), and the successful handling of the two tests (in the middle and at the end of the semester) each to at least 50%.

Syllabus of lectures:

1. Fundamental terms and significations (prime numbers, sets, mathematical induction, relation, relation of equivalence, functions and organized sets)

2. Computational complexity theory. Techniques for algorithms complexity description and operations with data structures. Problems complexity.

3. Introduction to graph theory. Depth-first and breadth-first search on undirected graphs, detection of connected component, depth-first search on directed graph, transitive closure.

4. Graph drawing in a plane. Number of spanning trees in a complete graph. Graph independence.

5. Trees - definition, characteristic (isomorphism, spanning tree, problem of searching of minimal spanning tree)

6. Tree data structures: heaps, binary searching tree, AVL trees, red-black trees, operation with the trees (MEMBER, INSERT, DELETE, JOIN, SPLIT)

7. B-trees, heaps, Fibonacci Heap, B*-trees, (a,b) - trees. Comparation of usage of B-trees and (a,b)-trees. Trees and hardware.

8. Arrays sorting - bubble sort, heapsort, quicksort, merge sort. Searching in sorted array.

9. Divide et impera algorithms (binary searching and merge sort, searching of median in linear time)

10. Hash functions - definition and application. Universal hashing, its properties and application. Design of perfect hashing.

11.Data coding, compression. Self-healing data.

12.Cryptography - symmetric and asymmetric cipher - encryption with public-key (RSA, DES, etc.)

13.Logical and physical file scheme, logical and physical record. Coding and compression of data. Hardware description.

14. Fundamental database operations. SQL.

Syllabus of tutorials:

1. Fundamental definition, combinatory enumeration.

2. Computational complexity theory. Examples and computation of algorithm complexity.

3. Graph algorithms examples.

4. Graph drawing in a plane. Number of spanning trees in a complete graph. Graph independence.

5. 1.Test

6. Arrays structures, pointers in C language.

7. Implementation of data tree structure.

8. Trees operation - Insert, member, delete, join

9. Sorting algorithm implementation.

10. Searching in data structure.

11. Searching in file.

12. Example and implementation of hashing

13. 2. test

14. Credit acknowledgement

Study Objective:
Study materials:

[1] K. Mehlhorn, P. Sanders: Data Structures and Algorithms: The Basic Toolbox, Springer, 2008, ISBN 978-3-540-77977-3.

[2] Manoocher, A.:Abstract Data Types and Algorithms, London, MacMillan Education Ltd. 1990

Note:
Time-table for winter semester 2018/2019:
Time-table is not available yet
Time-table for summer semester 2018/2019:
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
roomKL:B-534
Krupička R.
Kauler J.

10:00–11:50
(lecture parallel1)
Kladno FBMI
Počítačová učebna
Tue
roomKL:B-520
Krupička R.
12:00–13:50
(lecture parallel1
parallel nr.2)

Kladno FBMI
Počítačová učebna
Fri
Thu
Fri
The course is a part of the following study plans:
Data valid to 2019-08-21
For updated information see http://bilakniha.cvut.cz/en/predmet2789206.html