/Fast_Algorithms_in_Data_Structures

LA, LCA, Perfect Hash, RMQ, Segment Tree, Sparse Table, Treap, vEB Tree, x-fast Tree (Willard), Suffix Automaton (Blumer et al.), Suffix Tree (Ukkonen) etc.

Primary LanguageC++MIT LicenseMIT

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