Data and Data Structures
Code  Completion  Credits  Range  Language 

17PBIDDS  Z,ZK  5  2P+2L  Czech 
 Garant předmětu:
 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, lookup 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 025 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, and successful completion of credit tasks. The first part consists of a test in the middle of the semester containing the theoretical part of the exercise. The second compulsory component of the credit is the successful elaboration of the practical part on the given issue (programming task), the student then presents the elaborated task to verify the knowledge, authorship and understanding of the issue.
 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. Depthfirst and breadthfirst search on undirected graphs, detection of connected component, depthfirst 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, redblack trees, operation with the trees (MEMBER, INSERT, DELETE, JOIN, SPLIT)
7. Btrees, heaps, Fibonacci Heap, B*trees, (a,b)  trees. Comparation of usage of Btrees 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. Selfhealing data.
12.Cryptography  symmetric and asymmetric cipher  encryption with publickey (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 9783540779773.
[2] Manoocher, A.:Abstract Data Types and Algorithms, London, MacMillan Education Ltd. 1990
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans:

 Biomedical Informatics  fulltime study (compulsory course)