Algoritmic and Programming Theory
- Garant předmětu:
- Department of Biomedical Informatics
Algorithm, data structures. Identifiers, data types. assignment statement, conditional statement, cycles. Arithmetical and logical operations. Digital representation of numbers, numeration systems. Introduction to structured programming in C language - building and structure of simple programs, creating of the user functions, user input and output, file management, memory management. Practical overview of programming techniques and basic algorithms in C language. Recursive and iterative methods, measuring algorithm quality. Abstract data- types, data sorting and searching, implementation of basic numerical algorithms. Introduction to biomedical data processing - programmers view. Introduction to software engineering.
Realization of seminary tasks with minimal score of 20 points (max. 40), realization of tests (control points) with minimal score of 30 points (max. 60). Resulting classification: 50-59 pts = E (3), 60-69 pts = D (2.5), 70-79 pts = C (2), 80-89 pts = B (1.5), 90-100 pts = A (1)
- Syllabus of lectures:
1. Algorithm - introduction, properties, principles of algoritmization - motivation examples. Graphical representation of the algorithms, basic data a control structures - variables, data types, input and output operations, operators and operands, sequention and selection-
2. 1D and 2D arrays, logical variables, string variables. Cycles - general and normalized, inductive and iterative. Trace table.
3. Introduction to bits and bytes - internal representation of numbers in computer. Programmer's model of the modern computer. Low-level and high-lever programming languages. Quick introduction to C language structure, elementary examples.
4. Programming environments for C language - Integrated development environment, editor, compiler, linker, debugger. Syntactic and semantic errors. Statements, operators, assignments. Data-types, declaration and initialization of the variable. Command block, if-command. Switch-case command, cycles while, do-while and for, goto and break commands.
5. Derived and structured data-types - structure, union, array, user defined types. Subroutines, decomposition of the code. Standard library functions, user-defined functions.
6. C language preprocessor - basic directives of the preprocessor. Usage of the debugger. Files and streams - types. Creating, reading, writing and appending data from/to the stream.
7. Dynamical memory management, pointers to structured data-types, pointers used as parameters in user functions. Project in several modules - function prototypes, user-defined header files. Build dependencies. Creation of multiplatform libraries of user-functions in C.
8. Recursion and iteration. Task decomposition, top-down and bottom-up methods. Methods of quantification of algorithm quality. System, speed and memory requirements. Asymptotic measures of quality of algorithms.
9. Structured dynamical data-type: stack, queue, linked list, set, tree. Sorting algorithms - comparison of properties: Selection sort, Insertion sort, Bubble sort, Shaker sort, Quick sort, Shell sort a Heap sort.
10. Searching algorithms - address and associative algorithms. Numerical algorithms I.
11. Numerical algorithms II and III.
12. Introduction to biomedical data processing from the programmers poit of view. Application and system programs, functions of the operating system, overview of system calls in MS Windows and GNU Linux.
13. Introduction to object oriented programming in C++.
14. Graphical user interface (GUI), event-driven programming. Overview of selected multiplatform GUI toolkits.
- Syllabus of tutorials:
1. Algorithms - elementary motivation examples. Variables, data-structures, expressions, assignment, input and output commands.2. Logical statements, if-command. Practical usage of the trace-table.
2. Normalized cycles - condition before the body, after the body, for-cycle. 4. Conversion of the general cycle to the normalized forms. One-dimensional and two-dimensional arrays.
3. Basic practical usage of the Integrated Development Environment, editing of the code, compilation, execution. Examples of the syntactic and semantic errors. Examples of implementation of the elementary algorithms in C - input from the keyboard, output to the monitor, calculation of the simple formulas etc.
4. Examples to if-command, usage of cycles in C-language: while, do-while, for cycle.. Usage of pointers, structured data-types and user-defined types. Dynamical memory management (malloc, free etc).
5. Definition of user functions in C. Usage of basic preprocessor directives (#include, #define, #ifdef, etc.)
6. Practical examples of file-operations: creating, structured writing and reading, appending..
Subroutines in C - creation and usage of libraries of user-defined functions.
7. Practical using of standard and user-defined libraries of functions in C. Example of recursion, comparison of recursive and iterative algorithm.
8. Test 1 - 1st control point with evaluation.
9. Example of the usage of the library with implemented basic sorting algorithms - modifications and comparison of implemented methods. Sequential, binary and interpolative searching algorithms - example. Estimation of time-complexity of the algorithm, experimental comparison of several algorithms.
10. Usage of the binary tree. Examples of selected numerical algorithms - numerical derivation and integration, interpolation and approximation.
11. Iterative methods for root-finding of nonlinear equations. Implementation of basic statistical algorithms. Usage of the FFT library.
12. Example of the system program - usage of the operation system services. Example of the basic OOP program, class definition, encapsulation, inheritance, polymorphism.
13. Example of the simple event-driven program with Graphical User Interface using multiplatform GTK library.
14. Test 2 - 2nd control point with evaluation.
- Study Objective:
Active knowledge of basic programmer techniques and resources with special emphasis to the application in biomedical engineering area. Understanding internal function ot the complex software systems ability to formulate and analyze the complex programming task and participate on the software solution of the complex costumer-oriented biomedical software. Basic knowledge in algorithms and principles of modern software systems.
- Study materials:
All stud. materials (incl. syllabus, practical tasks etc.) are available on e-learning server <a href="http://skolicka.fbmi.cvut.cz">http://skolicka.fbmi.cvut.cz</a>
 Corman et al.: Introduction to Algorithms, The MIT Press, 2nd edition 2001
 Goodrich et al: Algorithm Design - Foundations, Analysis, and Internet Examples, John Wiley & Sons, New York 2002
- Further information:
- No time-table has been prepared for this course
- The course is a part of the following study plans:
- Biomedical Informatics - full-time study (compulsory course)