Algorithms for Engineering Informatics (E371526)
Katedra:ústav přístrojové a řídící techniky (12110)
Zkratka:Schválen:09.01.2012
Platí do: ??Rozsah:2P+1C
Semestr:*Kredity:4
Zakončení:Z,ZKJazyk výuky:EN
Anotace
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.


Osnova
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.
Osnova cvičení
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, B-tree.
Literatura
Study materials including lecture slides and preparations are provided by lecturer.
Požadavky
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.
Klíčová slova
Algorithms, BFS, DFS, graphs, KMP
data online/KOS/FS :: [Helpdesk] (hlášení problémů) :: - datum tisku: 5.12.2024, 8:46 © 2011-2022 [CPS] v3.8 (master/ade9e2c3/2024-10-11/07:15)