Topics

1. Algorithms, properties of algorithms, time complexity and space complexity, asymptotic behaviour of functions, analysis of algorithms, main complexity classes. NB! Definitions of relations: "big-O", "small-o", "Theta", big-Omega", "small-omega".
   
2. Searching and sorting. Linear search, binary search, hashing. Insertion sort, binary insertion sort, quicksort, merge sort, counting sort, radix sort, bucket sort. Complexity of different methods (for all methods time complexity: average and worst case, space complexity).
   
3. Abstract data types. Stacks and queues. Reverse Polish Notation (RPN). Linked lists and other pointer structures.
4. Trees. Examples of trees - arithmetic expression tree. Traversal of trees - preorder, postorder, in-order. Forms of expression for trees - parenthetic expressions, pointer structures, textual representation. Examples of "top-down" and "bottom-up" traversal.
5. Graphs. Directed and undirected graphs, multigraphs. Cyclic and acyclic graphs. Connected components. Strongly connected  and weakly connected graphs. Paths and cycles. Simple graphs. Matrices related to graphs: adjacency matrix, matrix of shortest pathlengths. Operations on graphs: sum, multiplication, transitive closure. Representation and implementation of graphs. Algorithms on graphs: Floyd-Warshall (lengths of shortest paths), topological sort of vertices, depth-first and breadth-first traversal, Dijkstra (shortest path), finding connected components, minimal spanning tree. Complexities for all algorithms.
   
6. Recursion: Hanoi tower, elimination of recursion, tail recursion. Exhaustive search: 8 queens problem, knapsack problem.
7. Binary search trees, AVL trees, red-black trees, binomial trees. B-trees. Heaps, heapsort. BST property and heap property.
   
8. String algorithms: exact matching (linear, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp).
9. Coding and compressing, coding schemes: Huffman, Shannon-Fano. Greedy algoritms: Huffman encoding.
10. Dynamic programming: longest common subsequence problem.
11. Correctness of algorithms: preconditions, postconditions, loop invariants, weakest precondition, structural rules, total correctness and partial correctness, halting problem.
12. Practical programming task: trees, recursion.