Definition

The maximum sum of a contiguous subsequence problem is a problem that finds a contiguous subarray of an array that sum of it will be a maximum.

Definition

Master’s theorem is a theorem that uses for algorithm analysis.

Definition

Fibonacci sequence is a sequence that generats numbers from previous two numbers. In other world, Fibonacci sequence $a$ is a a sequence defined by 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)$. In general, it can be computed easily by computing one by one which takes $O(n)$. However, there is another algorithm that takes much less time than this.

Theorem

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

There is another data strucutre that used to store tons of data. Therefore, it has two special operations known as the insert and the pop. However, there are two types of ways to make policies for inserting and poping a data from a structure.

Before talking about algorithm itself, we need to talk about data structures that typically uses for algorithms. Some of algorithms even works based on a specific data structure that optimizes the algorithm. In this chapter, I’ll explain the most common data structures only.

To analyze performances of algorithms, we need to define some jargons.

Algorithm is a mathmatical tool to solve some problem with propal methods. For example, let’s think about a situation follows. Oneday, you’ve got a job from a city library. However, there was a tournado yesterday so all books dropped out of the shelf. Your employer calls you and asks you to clean it up in order of books’ ID. Despite of your low payment, you have no way but clean it up. Therefore, you started to think about the way to clean it up.

MAX-E3SAT is a problem that finds a truth value assignment that satisfies the maximum number of clauses for a given a set of clause which contains exactly three literals.