Description: The course provides students with the introduction to mathematical computer science. Formal languages and grammars and word processing tools in these languages are discussed.
Canadian Traveller Problem (CTP) is an optimization problem in which the graph is partially observed. That means that the path from node i to node j may be blocked. Whether the path is blocked or not is discovered, when the traveller reaches the node i. Traveller then chooses to find another road or pays the penalty for using blocked path (for example he waits until path is not blocked anymore).
Semestral Project. Application creates random graph with blocked paths. The user chooses start and end node end node and algorithm to solve the problem. Several non-heuristic methods were programmed: Greedy, Reposition, Comparison, Waiting and Recovery-Greedy.
The main goal of the project is to use or implement non-trivial data structure. The idea is to implement own Binary Heap data structure in Dijkstra algorithm.