sequence.md

Sequence data structures and algorithms

Table of contents

• Arrays and vectors
• Rotation (cyclic shift)
  • Three reverses rotation algorithm
  • Gries–Mills algorithm
  • Dolphin (juggling) algoirithm
• Circular buffer
• Longest increasing subsequence
• Maximum subsequence
  • Kadane’s algorithm
• Majority element
  • Boyer–Moore majority vote algorithm
• Sqrt decomposition

---

Arrays and vectors

See also Sequence containers – The standard library, Boost, and proposals.

🎥

• D.Stone. Faster, easier, simpler vectors – CppCon (2021)
• D.Stone. Implementing static_vector: How hard could it be? – CppCon (2021)

Rotation (cyclic shift)

A K-rotation (or a K-cyclic shift) of a sequence {a0a2...aN-1} is a sequence {aP(1)aP(2)...aP(N-1)}, where the index permutation is P(i) = (i + K) % N. Any non-zero rotation has no trivial cycles. The number of (non-trivial) cycles is gcd(K, N).

🔗

• Benchmarking block-swapping algorithms – Dr. Dobb’s Journal

📖

• Sec. 11.3: Rotation – A.A.Stepanov, D.E.Rose. From mathematics to generic programming (2014)
• Sec. 10.4: Rotate algorithms – A.A.Stepanov, P.McJones. Elements of programming (2009)
• Sec. 2.3: The power of primitives – J.Bentley. Programming pearls (1999)

📄

• C.A.Furia. Rotation of sequences: Algorithms and proofs – Preprint (2014)
• D.Gries, H.Mills. Swapping sections – Technical report 81-452, Department of computer science, Cornell University (1981)

Three reverses rotation algorithm

Gist of the algorithm: reverse the subsequences {a0...aK-1} and {aK...aN-1}, then reverse the whole sequence {aK-1...a0aN-1...aK}. The total number of swaps is ⌊N/2⌋ + ⌊K/2⌋ + ⌊(N-K)/2⌋ ∼ N. With 3 assignments per swap, the total number of assignments is ∼ 3N. This algorithm is typically used to implement std::rotate for bidirectional iterators.

Gries–Mills algorithm

Gist of the algorithm: if K = N - K, swap the subsequences {a0...aK-1} and {aK...aN-1}; if K < N - K, swap the subsequences {a0...aK-1} and {aK...a2K-1}, then proceed recursively for the suffix subsequence {a0...aK-1a2K...aN-1} with K' = K; if K > N - K, swap the subsequences {a0...aN-K-1} and {ak...aN-1}, then proceed recursively for the suffix subsequence {aN-K...aK-1a0...aN-K-1} with K' = 2K - N. The section sizes (K, N - K) form the same sequence as that obtained if the subtraction-based Euclidean algorithm is employed to calculate gcd(K, N). The total number of swaps is N - gcd(K, N). With 3 assignments per swap, the total number of assignments is 3[N - gcd(K, N)]. The Gries–Mills algorithm can be implemented such that it only requires to move one step forward, so this algorithm is typically used to implement std::rotate for forward and random access iterators.

Dolphin (juggling) algoirithm

Gist of the algorithm: compute the number of cycles, Nc = gcd(K, N - K); for each cycle {aCi(0)aCi(1)aCi(2)...} with Ci(j) = (i + jK) % N, i = 0, ..., Nc - 1, make a cyclic shift of all the elements by one position to obtain {aCi(1)aCi(2)...aCi(0)}. The total number of assignments is N + gcd(K, N). However, this algorithm is not cache-friendly and can have poor performance in practice, although it makes much fewer (~2-3 times) memory accesses. This algorithm is sometimes used to implement std::rotate for random access iterators.

📄

• W.Fletcher, R.Silver. Algorithm 284: Interchange of two blocks of data – Communications of the ACM 9, 326 (1966)

---

Circular buffer

A circular buffer (cyclic buffer, ring buffer) is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. When the buffer is filled, new data is written starting at the beginning of the buffer and overwriting the old.

🔗

• Circular buffer – Wikipedia
• B.Stout. “Olympic” filtering for noisy data – C/C++ Users Journal 13 (1995)

⚓

• Boost.Circular Buffer: The circular buffer library

---

Longest increasing subsequence

Problem: find the longest monotonically increasing subsequence (not necessarily contiguous) within a given sequence. The dynamic programming solution (without additional tricks) has running time O(N2), and is not the most efficient one. The problem can be solved in O(N log N) time using an algorithm based on binary search. This algorithm is output-sensitive: if the size of the output, the length K of a subsequence, is taken into account, it requires O(N log K) time. Any comparison-based algorithm requires at least N log2 N - N log2 log2 N + O(N) comparisons in the worst case.

🔗

• Longest increasing subsequence – Wikipedia
• Longest increasing subsequence – CP-Algorithms

🎥

• Dynamic programming – MIT OCW 6.006: Introduction to algorithms (2011)

📖

• Sec. 8.3: Longest increasing sequence – S.S.Skiena. The algorithm design manual (2008)
• Sec. 3.5.2 Classical examples – S.Halim, F.Halim. Competitive programming (2013)
• Sec. 6.5.2: Finding the k^th smallest element, Sec. 6.11.1: Longest increasing subsequence – U.Manber. Introduction to algorithms: A creative approach (1989)

📄

• M.L.Fredman. On computing the length of longest increasing subsequences – Discrete Mathematics 11, 29 (1975)

---

Maximum subsequence

Problem: find a contiguous subsequence with the largest sum within a given one-dimensional sequence.

📖

• Col. 8: Searching – J.Bentley. Algorithm design techniques (1999)

📄

• J.Bentley. Programming pearls: Algorithm design techniques – Communications of the ACM 27, 865 (1984)

Kadane’s algorithm

📄

• D.Gries. A note on a standard strategy for developing loop invariants and loops – Science of computer programming 2, 207 (1982)

---

Majority element

Boyer–Moore majority vote algorithm

🔗

• Boyer–Moore majority vote algorithm – Wikipedia

---

Sqrt decomposition

🔗

• Sqrt decomposition – CP-Algorithms
• S.Kopeliovich. Sqrt decomposition – MIPT (2016)