 CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2019/2020

# Data a Data Structures

The course is not on the list Without time-table
Code Completion Credits Range Language
17KBIDDS Z,ZK 5 12P+8C Czech
Lecturer:
Tutor:
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.

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:

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

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

Note:
Further information:
No time-table has been prepared for this course
The course is a part of the following study plans:
Data valid to 2019-10-18
For updated information see http://bilakniha.cvut.cz/en/predmet2797406.html