Fast Algorithms in Data Structures

Lecture	Topic	Solution
2020-10-02 LAQ (Level Ancestor Query) pt.1 2020-10-09 (Level Ancestor Query) pt.2 2020-10-02 LAQ (Level Ancestor Query) pt.3 LA-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: Analysis Binary 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.1 2020-10-23 LCA, RMQ pt.2 2020-10-30 Solving RMQ by finding LCA)	LCA-RMQ Problem	LCA Query LCA, Sparse Table: O(nlog(n),1) Distance Query Solution 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 intuition 2020-11-20 van Emde Boas Trees vEB Additional Analysis	van Emde Boas trees	vanEmdeBoasTree.cpp O(n,log(log(n))) vEB MIT (Overview)
2020-11-27 Suffix Automaton pt.1, 2 & 3 Project 2021-01-10 Test Case 01 Test Case 02 Записки по „Езици, автомати, изчислимост“ (Стефан Вътев)	Blumer et. al. Algorithm	SuffixAutomaton.cpp General Suffix Automaton Construction Algorithmand Space Bounds (Mehryar Mohri, Pedro Moreno, Eugene Weinstein) THE SMALLEST AUTOMATON RECOGNIZING THE SUBWORDS OF A TEXT* (A.BLUMER, J.BLUMER and D.HAUSSLER)
2020-12-11 Ukkonen's Algorithm pt. 1 2020-12-18 Ukkonen's Algorithm pt. 2	Suffix Tree
2021-01-08 Lempel-Ziv, Suffix Arrays pt.1 2021-01-08 Lempel-Ziv, Suffix Arrays pt.2	Lempel-Ziv Algorithm Information Theory Suffix Arrays
2021-01-15 Dynamization of Static Data Structures pt.1 2021-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 Aphids I/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).cpp 847D (priority queue).cpp
Codeforces - Yet Another Array Queries Problem	863D (Implicit).cpp 863D (reverse queries).cpp
SPOJ - MEANARR - Mean of array	MEANARR.cpp
SPOJ - Twist and whirl - want to cheat	TWIST (insert via split & merge).cpp TWIST (insert via merge).cpp
SPOJ - KOILINE - Line up	KOILINE.cpp
CodeChef - The Prestige	PRESTIGE.cpp
Codeforces F. T-Shirts	702F (breaking into intervals).cpp 702F (Algorithms using Treap).pdf 702F (Treap).cpp
Codeforces - Wizards and Roads	167D.cpp
Codeforces - Yaroslav and Points	295E.cpp
Codeforces - Letters Removing	899F.cpp
Codeforces – Irrigation	1181D.pdf 1181D.cpp
Hackerrank – Running median	RunningMedian (Split by count – implicit key).cpp RunningMedian (kthSmallest).cpp Running Median (Probabilistic Heaps).cpp Running 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).cpp DISQUERY – Distance Query–2.cpp