Fast Algorithms in Data Structures Lecture Topic Solution 2020-10-02 LAQ (Level Ancestor Query) pt.12020-10-09 (Level Ancestor Query) pt.22020-10-02 LAQ (Level Ancestor Query) pt.3LA-Problem (Cai Qi)LA-Problem (Bender, Farach-Colton) LA Problem Table:O(n^2,1)Long-Paths:O(n,sqrt(n))Jump pointers:O(nlog(n),log(n))Ladders:O(n,log(n))Preorder traversal: AnalysisBinary search:O(n,log(n))Ladders & Jump pointers:O(nlog(n),1))Input(tree & file) 2020-10-16 LCA (Lowest Common Ancestor),RMQ (Range Minimum Quert) pt.12020-10-23 LCA, RMQ pt.22020-10-30 Solving RMQ by finding LCA) LCA-RMQ Problem LCA QueryLCA, Sparse Table: O(nlog(n),1)Distance QuerySolution 1.cpp O(n.log(n),log(n))Solution 2.cpp O(n.log(n),log(n)) 2020-11-06 Perfect Hash Perfect Hash 2020-11-13 Willard Algorithm x-fast, y-fast trees van Emde Boas Tree, idea and intuition2020-11-20 van Emde Boas TreesvEB Additional Analysis van Emde Boas trees vanEmdeBoasTree.cpp O(n,log(log(n)))vEB MIT (Overview) 2020-11-27 Suffix Automaton pt.1, 2 & 3Project 2021-01-10Test Case 01Test Case 02Записки по „Езици, автомати, изчислимост“(Стефан Вътев) Blumer et. al. Algorithm SuffixAutomaton.cppGeneral Suffix Automaton ConstructionAlgorithmand Space Bounds(Mehryar Mohri, Pedro Moreno, Eugene Weinstein)THE SMALLEST AUTOMATON RECOGNIZINGTHE SUBWORDS OF A TEXT*(A.BLUMER, J.BLUMER and D.HAUSSLER) 2020-12-11 Ukkonen's Algorithm pt. 12020-12-18 Ukkonen's Algorithm pt. 2 Suffix Tree 2021-01-08 Lempel-Ziv, Suffix Arrays pt.12021-01-08 Lempel-Ziv, Suffix Arrays pt.2 Lempel-Ziv AlgorithmInformation TheorySuffix Arrays 2021-01-15 Dynamization of Static Data Structures pt.12021-01-22 Dynamization of Static Data Structures pt.2 Dynamization of Static Data Structures Treap Treaps Fast Set Operations Using Treaps Problems Solutions SPOJ - ADAAPHID - Ada and AphidsI/O Explanation ADAAPHID.cpp SPOJ - ADACROP - Ada and Harvest ADACROP.cpp Codeforces - E. Radio stations 762E.cpp SPOJ - COUNT1IT - Ghost Town COUNT1IT.cpp SPOJ - IITWPC4D - Arrangement Validity IITWPC4D.cpp SPOJ - All in One ALLIN1.cpp Codeforces - D. Dog Show 847D (Treap).cpp847D (priority queue).cpp Codeforces - Yet Another Array Queries Problem 863D (Implicit).cpp863D (reverse queries).cpp SPOJ - MEANARR - Mean of array MEANARR.cpp SPOJ - Twist and whirl - want to cheat TWIST (insert via split & merge).cppTWIST (insert via merge).cpp SPOJ - KOILINE - Line up KOILINE.cpp CodeChef - The Prestige PRESTIGE.cpp Codeforces F. T-Shirts 702F (breaking into intervals).cpp702F (Algorithms using Treap).pdf702F (Treap).cpp Codeforces - Wizards and Roads 167D.cpp Codeforces - Yaroslav and Points 295E.cpp Codeforces - Letters Removing 899F.cpp Codeforces – Irrigation 1181D.pdf1181D.cpp Hackerrank – Running median RunningMedian (Split by count – implicit key).cppRunningMedian (kthSmallest).cppRunning Median (Probabilistic Heaps).cppRunning Median (Ordinary Heaps).cpp USP2019-W8-A USP2019-W8-A (Range sum and reverse).cpp Lowest Common Ancestor Problems Solutions LCA – Lowest Common Ancestor LCA – Lowest Common Ancestor–1 (euler tour and sparse table).cpp DISQUERY– Distance Query DISQUERY – Distance Query–1 (jump pointers).cppDISQUERY – Distance Query–2.cpp