čs en |

Algorithms for Engineering Informatics (E371014)

Departments: | ústav přístrojové a řídící techniky (12110) | ||

Abbreviation: | Approved: | 24.02.2009 | |

Valid until: | ?? | Range: | 2P+2C |

Semestr: | L,Z | Credits: | 5 |

Completion: | Z,ZK | Language: | EN |

Annotation

Basic introduction into Java (tasks can be solved in any language). Algorithms with numbers - Divide-and-conquer algorithms, Recurrence relations, the fast Fourier transform. Big-O notation. Sorting algorithms - Bubble sort, Insert sort, Selection sort, Heap sort, Quick sort, Mergesort. Graphs - Depth-fit search in undirected graph, Depth-fit 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.

Teacher's

Ing. Vladimír Hlaváč Ph.D.

Letní 2018/2019

Ing. Vladimír Hlaváč Ph.D.

Letní 2017/2018

Ing. Vladimír Hlaváč Ph.D.

Letní 2016/2017

Structure

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 - bubble sort, combo sort, insert sort, selection sort, heap sort, quick sort, mergesort. Counting sort.

Data structures, linked lists (stack, circular queue), trees (binary, AVL, red-black; B-trees).

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.

Cryptography - historical ciphers, search primes, factorization, symmetric ciphers.

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 - bubble sort, combo sort, insert sort, selection sort, heap sort, quick sort, mergesort. Counting sort.

Data structures, linked lists (stack, circular queue), trees (binary, AVL, red-black; B-trees).

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.

Cryptography - historical ciphers, search primes, factorization, symmetric ciphers.

Structure of tutorial

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.

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.

Literarture

Study materials including lecture slides and preparations are provided by lecturer.

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.

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.

Keywords

algorithms, searching, sorting, linked list, tree, recurrence, graphs

data online/KOS/FS :: [Helpdesk] (hlášení problémů) :: [Reload] [Print] [Print wide] © 2011-2017 [CPS] v3.7 (master/180e4e5a/2019-10-09/02:51)