Algorithms for Engineering Informatics

Course guarantor:

Vladimír Hlaváč

Lecturer:

Vladimír Hlaváč

Tutor:

Vladimír Hlaváč

Supervisor:

Department of Instrumentation and Control Engineering

Synopsis:

Basic introduction into Java (tasks can be solved in any language; Pascal/Delphi course alternatively for who is interested). 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-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.

Requirements:

At the beginning of the course, students will receive three tasks to solve in any programming language.

Each task will represent one algorithm introduced later in the lectures.

For the exam, the student must show these programs running, explain how they work (at the level of individual words), explain why they chose this method, and be able to make modifications to the code on demand (oral part of the exam)

Syllabus of lectures:

Introduction to Java programming (all examples in Java).

Java: arrays, strings, built-in functions, input from console, the for loop.

Java: procedures and functions. Interpolation, iteration, recursion. Factorial. Loops, input from file.

Java: classes, instances of classes (objects). Static and dynamic variables. Constructor.

Sorting algorithms: bubble sort, combo sort, insertion sort, selection sort.

Divide-and-conquer algorithms: quick sort, heap sort, merge sort. Complexity of algorithms. Space complexity. Big-O notation.

Counting sort, bucket sort. Insertion sort and quicksort variants and stability.

Mathematical algorithms: multiplication of two matrices, greatest common divisor, least common multiple (LCM), Euclid's algorithm. Factorization.

Divide-and-conquer algorithms, recurrence relations, and the fast Fourier transform.

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 (directed acyclic graphs). Greedy algorithms: minimum spanning trees, Huffman encoding, Horn formulas.

Syllabus of tutorials:

Students will try to write and debug simple programs based on the content from the previous lecture. Solutions for at least 9 out of 11 tasks must be uploaded to the Moodle server within three weeks of the proposition. Programs can be written in any language, but for the final assessment, the student must be able to show any of them running. This assumes that the programming environment used for the task is installed on their own notebook or accessible through a terminal service, if a language other than Java is used.

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:

Valid from WS 2014/15

Further information:

???? katedrální stránka předmětu http://www.compileonline.com

Time-table for winter semester 2024/2025:

Time-table is not available yet

Time-table for summer semester 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Wed
Thu
Fri	roomT4:C1-308 Hlaváč V. 14:15–15:45 (lecture parallel1) Dejvice roomT4:C1-308 Hlaváč V. 16:00–17:30 (lecture parallel1 parallel nr.1) Dejvice

The course is a part of the following study plans: