Algorithms for Engineering Informatics
Code  Completion  Credits  Range  Language 

E371526  Z,ZK  4  2P+1C  English 
 Garant předmětu:
 Lecturer:
 Tutor:
 Supervisor:
 Department of Instrumentation and Control Engineering
 Synopsis:

BigO notation. Algorithms with numbers  cryptography, universal hashing, divideandconquer algorithms, recurrence relations, the fast Fourier transform. Sorting algorithms  mergesort, insert sort, selection sort, heap sort, quick sort. Graphs  depthfirst search in undirected graph, depthfirst search in directed graphs, strongly connected components. Paths in graphs  distances, breadthfirst search, lengths on edges, Dijkstra's algorithm, Priority queue implementations, Shortest paths in the presence of negative edges, shortest paths in dags. Greedy algorithms  minimum spanning trees, Huffman encoding, Horn formulas.
 Requirements:

The course strongly assumes prior knowledge on level of course Algorithms 1.
For the Exams: knowledge prescribed in lectures. The exam has a practical and oral parts. The practical part of the exam  write and debug a simple program on given task.
For Assessment, the student receies three tasks to program.
 Syllabus of lectures:

Theory of algorithms. Complexity of algorithms. BigO notation.
Mathematical algorithms  multiplication of two matrices, the greatest common divisor, the least common multiple ( LCM ) , Euclid's algorithm.
Factorial, recursion, factorization.
Divideandconquer algorithms, recurrence relations, the fast Fourier transform.
Sorting algorithms  mergesort, insert sort, selection sort, heap sort, quick sort.
Graphs and graph algorithms  terminology, notation , theory, breadthfirst search , BFS, depthfirst search , DFS, minimum spanning tree.
Paths in graphs  distances, breadthfirst search, lengths on edges, Dijkstra's algorithm, priority queue implementations, shortest paths in the presence of negative edges, shortest paths in dags. Greedy algorithms  minimum spanning trees, Huffman encoding, Horn formulas.
Search in text  terminology, Hamming distance, trivial algorithm, KMP.
Cryptography  historical ciphers, search primes, factorization, symmetric ciphers.
 Syllabus of tutorials:

Introduction into running applications in 308 laboratory, students' accounts, students will be submitted 3 practical excercises to solve.
Simple application. Constants. Simple types, structured types incl. arrays, records, sets, files. Variables. Basics of programming language.
Sorting. Handling events and exceptions.
Printing from Java applications, I/O operations.
Dynamic data structures: stack, queue, linked list, tree.
Binary tree, AVL tree, Btree.
 Study Objective:

This subject introduces advanced programming skills and algorithms.
Teaching is focused more practically, on the application of algorithms in solving engineering problems. Examples are presented in the language Java.
 Study materials:

Study materials including lecture slides and preparations are provided by lecturer.
 Note:
 Further information:
 ???? katedrální stránka předmětu http://www.compileonline.com
 No timetable has been prepared for this course
 The course is a part of the following study plans: