Transformer-based Algorithmics

Content (tentative)

• Algorithms, summation, design patterns: step-by-step processing (linear effort), calculation with constant effort, reduction principle: sorting by insertion, sorting by selection, problem complexity, algorithm analysis: asymptotic complexity of an algorithm (O-notation)
• Sorting by divide-and-conquer, algorithm analysis, design pattern divide-and-conquer: mergesort, quicksort, omega and theta notation, heaps as data structures, heapsort, other sorting approaches
• Priority queues, implementation with binary heaps
• Association of objects, hash tables, probing
• Graphs, operations on graphs, graph representations, breadth-first and depth-first search, context components, shortest paths, single-source shortest test paths (Dijkstra's algorithm, A* algorithm)
• Graph reachability and superposition-based search with transformers, reasoning with transformers
• Search graphs for games, minimax search, search space construction, alpha-beta cuts and subgraph isomorphism for search space pruning
• Dynamic programming, decision transformer with dynamic programming