When implementing arbitrary-precision integers in C++, the key challenge is how fast you can perform multiplication. This post introduces a two-stage hybrid approach combining NTT and Karatsuba.

Definition

The maximum subarray problem asks for the contiguous subarray of an array whose sum is the largest.

Definition

The Master’s Theorem is a tool for analyzing the time complexity of divide-and-conquer algorithms.

Definition

The Fibonacci sequence is defined by each number being the sum of the two preceding ones. Formally, the Fibonacci sequence $a$ is defined as follows.

Problem

Let’s think about the sequence of $[\alpha k]$ for $k \in \mathcal{Z}^+$ and $\alpha \in \mathcal{R}^+/\mathcal{Q}^+$ and $\alpha > 1$. For example, $[\sqrt{2}] \approxeq 1.414 = 1, [2 \sqrt{2}] \approxeq 2.828 = 2, [3 \sqrt{2}] \approxeq 4.242 = 4, [4 \sqrt{2}] \approxeq 5.656 = 5, [5 \sqrt{2}] \approxeq 7.071 = 7$ for $\alpha = \sqrt{2}$. Let’s define $S(\alpha, n) = \sum\limits_{k = 1}^{n}[\alpha k]$. Then, problem is that compute $S(\alpha, n)$. The naive approach of computing term by term takes $O(n)$. However, there is a faster algorithm.

Theorem

Consider the sequence $\lfloor \alpha k \rfloor$ for $k \in \mathbb{Z}^+$, where $\alpha \in \mathbb{R}^+ \setminus \mathbb{Q}^+$ and $\alpha > 1$. For example, $[\sqrt{2}] \approxeq 1.414 = 1, [2 \sqrt{2}] \approxeq 2.828 = 2, [3 \sqrt{2}] \approxeq 4.242 = 4, [4 \sqrt{2}] \approxeq 5.656 = 5, [5 \sqrt{2}] \approxeq 7.071 = 7$ for $\alpha = \sqrt{2}$. Then, $[\alpha k]$ and $[\beta k]$ partitions an integer sequence if $\alpha^{-1} + \beta^{-1} = 1$. For example, $\frac{1}{\sqrt{2}} + \frac{1}{\sqrt{2}/(\sqrt{2} - 1)} = \frac{1}{\sqrt{2}} + \frac{\sqrt{2} - 1}{\sqrt{2}} = 1$. Which means $[\sqrt{2}/(\sqrt{2} - 1)] \approxeq 3.414 = 3, [2\sqrt{2}/(\sqrt{2} - 1)] \approxeq 6.828 = 6$.

Stack and queue are fundamental data structures with two core operations: push (insert) and pop (remove). They differ in the order in which elements are removed.

Before discussing algorithms, we need to cover the data structures they commonly rely on. Some algorithms are only efficient because of a specific underlying data structure. This post covers the most fundamental ones.

To analyze the performance of algorithms, we need a few key definitions.

An algorithm is a well-defined procedure for solving a problem. For example, imagine you just started a job at a city library. A tornado hit yesterday, and all the books fell off the shelves. Your employer asks you to put them back in order by book ID. Despite your meager pay, you have no choice but to sort them out. So you start thinking about the best way to do it.