Code: E371526 Algorithms for Engineering Informatics
Lecturer: doc. Ing. Josef Kokeš CSc. Weekly load: 2+1 Assessment: Z,ZK
Department: 12110 Credits: 4 Semester: S
Description:
Big-O notation. Algorithms with numbers - cryptography, universal hashing, divide-and-conquer algorithms, recurrence relations, the fast Fourier transform. Sorting algorithms - mergesort, insert sort, selection sort, heap sort, quick sort. Graphs - depth-first search in undirected graph, depth-first search in directed graphs, strongly connected components. Paths in graphs - distances, breadth-first 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.


Contents:
Introduction into Java programming (all examples in Java).
Theory of algorithms. Complexity of algorithms. Big-O notation.
Mathematical algorithms - multiplication of two matrices, the greatest common divisor, the least common multiple ( LCM ) , Euclid's algorithm.
Factorial, recursion, factorization.
Divide-and-conquer 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, breadth-first search , BFS, depth-first search , DFS, minimum spanning tree.
Paths in graphs - distances, breadth-first 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.
Recommended literature:
Study materials including lecture slides and preparations are provided by lecturer.
Keywords:
Algorithms, BFS, DFS, graphs, KMP