You are here

17ABBALP - Algorithmic and Programming Theory

Code Completion Credits Range Language
17ABBALP KZ 4 2+2
Lecturer:
Pavel Smrčka (guarantor), David Gillar, Martin Vítězník
Tutor:
Pavel Smrčka (guarantor), David Gillar, Lenka Hanáková, Martin Vítězník
Supervisor:
Department of Information and Communication Technology in Medicine
Synopsis:

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.

Requirements:

Compulsory attendance at seminars, implementation of individual tasks with a minimum gain of 30 points (maximum 60), passing examination with a total minimum profit of 20 points (maximum 40). Total score: 50-59 points = E (3), 60-69 points = D (2.5) 70-79 points = C (2), 80-89 points = B (1.5), A = 90-100 points ( 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:

Basic abitity to design simple microprocessor systems for biomedical embedded devices. Practical approcah to digitisation, transmission and data-processing of biological signals. Orientation in modern microporcessor families and wireless connectivity technologies.

Study materials:

All stud. materials (incl. syllabus, practical tasks etc.) are available on e-learning server <a href="https://skolicka.fbmi.cvut.cz">https://skolicka.fbmi.cvut.cz</a>

[1] Lipovski, G:Introduction to Microcontrollers Book,2nd edition,A.P.PROFESSIONAL,2004, 2. ARM7TDMI-Technical ReferenceManual,ArmLimited,2004, 3.AXIS ETRAX 100LX-Technical Reference,Axis Communications,2006

Note:
The course is a part of the following study plans:
Downloads:

Lectures: 
AttachmentSize
PDF icon Presentations245.9 KB

Exercises: 
AttachmentSize
PDF icon Tutorials245.25 KB

Others: 
AttachmentSize
PDF icon Course schedule19.19 KB