Data and Data Structures

Lecturer:

Radim Krupička, Marcel Jiřina (gar.), Jan Kauler

Tutor:

Radim Krupička

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 2011/2012:

Time-table is not available yet

Time-table for summer semester 2011/2012:

	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
Tue
Fri	roomKL:B-505 Krupička R. 10:00–11:50 (lecture parallel1 parallel nr.1) Kladno FBMI Počítačová učebnaroomKL:B-505 Krupička R. 12:00–13:50 (lecture parallel1 parallel nr.2) Kladno FBMI Počítačová učebnaroomKL:B-415 Jiřina M. Kauler J. 14:00–15:50 (lecture parallel1) Kladno FBMI Počítačová učebna
Thu
Fri

The course is a part of the following study plans:

• Bakalářský studijní obor Biomedicínská informatika - prezenční (compulsory course)
• Bakalářský studijní obor Biomedicínská informatika - prezenční (compulsory course)