Timetable at FEE
Students of ePAL
Upload system BRUTE
Discussion board
Practices
Upload system
Repetitions
The following topics are considered fundamental and known to the students from their previous years of study.
Everybody is invited to check themselves the related problems listed below. In need of assistance or explanation talk to your labs or lectures teacher(s). Asymptotic complexity and graphs representation will not appear as as an explicit training topic in PAL practices.
Asymptotic complexity recap. Training problems
are here.
For more thorough or necessary basic acquaintance with the related topics consult the book
Problems on Algorithms. Student are expected to be able to solve any problem marked by one cap in chapters 2. and 3. both during the semester and at the exam. We recommend problems 64. - 66., 144. - 148., 163. - 170. as an easy start.
Semester
The list of exam topics related to particular weeks in practices is at the bottom of this page.
1st and 2nd week (25.9., 2.10.) -- Asymptotic complexity recapitulation. Graph representation. MST problem. Union-Find problem.
Asymptotic complexity repetitions:
example problems, concentrate on problems 14-23.
3rd week (9.10.) -- Euler Trail. Directed graphs. Strongly Connected Components.
Problems for personal training: Directed graphs, strongly connected components, Eulerian graphs:
set 1,
set 2.
4th week (16.10.) -- Heaps: Binary, d-ary, binomial, Fibonacci. Heaps comparison.
Additional problems for training
here
5th week (23.10.) -- Isomorphism of graphs and of trees.
Additional problems for training
here
6th week (30.10.) -- Generation and enumeration of combinatorial objects (subsets, k-element subsets, permutations). Gray codes.
Combinatorial generation of subsets, permutations and their ranks.
Example problems.
Additional problems for training
here
Kreher, Stinson: Combinatorial Algorithms, notes: page 30, 31, page 32, 33, page 34, 35, page 36, 37, page 38, 39, page 40, 41, page 42, 43, page 44, 45, page 52, 53, page 54, 55, page 56, 67.
7th week (6.11.) -- Finite automata, indeterminism, regular expressions, exact pattern matching.
Additional problems for training
here
8th week (13.11.) -- Language operations, Approximate pattern matching with finite automata.
Text Searching. Additional problems for training
here
9th week (20.11.) -- Dictionary automata. Implementations of automata.
Additional problems for training
here.
10th week (27.11.) -- Random numbers properties and generators. Prime number generators. Primality tests - randomized and exact. Fast powers. Prime factoring.
11th week (4.12.) -- Skip list, search trees: B, B+.
12th week (11.12.) -- Search trees: 2-3-4, R-B, splay.
2-3-4 trees and B+ trees, splay trees. Additional problems for training
here
13th week (18.12.) -- Searching in higher dimensions, K-D trees.
14th week (8.1.)-- Binary trie, Patricia trie
15th week -- will not happen this year :-)
In preparation
* Radix trie, suffix trie, segment tree.
Search Trees Interactive Animations
Exam topics, week by week
1st week
Asymptotic notations, asymptotic complexity, graph representations.
Boruvka's, Kruskal's, Prim's algorithms. Their implementation and data structures, ie. priority queues and Union-Find.
Prim's algorithm without a queue.
Union-Find implementations.
2nd week
Eulerian graph (directed and undirected), Eulerian path/cycle, method of finding them.
Strong and weak connectivity, strong and weak components, graph condensation. Algorithms which find strong components or produce a condensation.
Topological ordering of a graph using DFS or using gradual roots/leaves removal.
3rd week
The heap rule. Standard operations on heaps. Binary, d-ary and binomial heap.
Binary and d-ary heap implemented in an array.
Fibonacci heap, amortized complexity of its operations.
4th week
Graph isomorphism, definition, invariants, algorithm for finding all isomorphisms.
Isomorphism and certificates of undirected trees, computing the certificate for a tree and reconstructing a tree from a certificate.
5th week
Combinations, variations, permutations with or without repetition, definitions, formulas. Binomial coefficients, their basic relations, Pascal triangle.
Operations(functions) Rank and UnRank for ordered permutations and k-element subsets of given set.
Gray code - definition, properties, operations Rank and UnRank.
6th week
Deterministic and non-deterministic finite automaton (DFA and NFA), definition. Languages accepted by finite automata.
Algorithm for transforming NFA to DFA, simulation of NFA work without transformation to DFA. Epsilon-transitions and their removal from an automaton.
Regular expressions. Definition, algorithm for transformation of regular expression to NFA.
7th week
Construction of NFA for pattern matching. Impelementation of NFA/DFA by a table or by code.
Hamming and Levenshtein distance. NFA/DFA for search of substrings which have nonzero distance from a given pattern.
8th week
Finding dictionary entries in a text with the help of dictionary automaton.
Number of states of dictionary NFA, DFA.
Approximate text search based on previous methods.
9th week
Canceled, holidays.
10th week
11th week
12th week
2-3-4 trees and B+ trees. Asymptotic complexity of particular search tree operations.
13th week
KD trees, search for Nearest Neighbour in 2D.
14th week