Skip to content

sequence.md

Latest commit

 

History

History
139 lines (82 loc) · 7.68 KB

sequence.md

File metadata and controls

139 lines (82 loc) · 7.68 KB
Raw

Sequence algorithms

Table of contents

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).

🔗

📖

📄

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

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 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)}.

📝

  • This algorithm is also known as the juggling algorithm.
  • 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)

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.

🔗

🎥

📖

  • 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 kth smallest element, Sec. 6.11.1: Longest increasing subsequence – U.Manber. Introduction to algorithms: A creative approach (1989)

📄

Maximum subsequence

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

📄

Kadane’s algorithm

Majority element

Boyer–Moore majority vote algorithm

🔗

Sqrt decomposition

🔗