Description:

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.

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 - 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 (directed acyclic graphs). Greedy algorithms - minimum spanning trees, Huffman encoding, Horn formulas.
Cryptography - historical ciphers, search primes, factorization, symmetric ciphers.

Seminar contents:

Introduction into running applications in 308 laboratory, students' accounts.
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.
Graph algorithms.
Each student will be submitted 3 practical excercises to solve, in the range of lectures. Their solutions will create part of the final classification.

Recommended literature:

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

Keywords:

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

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar