Algorithms

Algorithm is the soul of programming, and the only way to learn it well is to practice it well. The chart below shows my LeetCode Contest Rating History. Fine me on LeetCode and LeetCode-CN!

Loading...

Fundamental Algorithms

This section includes an introduction to some commonly used data structures. Algorithms such as sorting and searching are presented in the form of the best practices.

NP-Hard Problems and Advanced Algorithms

This part contains an introduction to the NP-hard problems and some advanced algorithms, including approximation algorithms, online algorithms and other heuristic algorithms. Part of the content here is derived from the courses given by Dr. Vorapong Suppakitpaisarn

Linear Programming

Linear programming (LP, also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships.

• Input: Matrix $\mathbf{A}$, vectors $\overrightarrow{b}$, $\overrightarrow{c}$

• Output: vector $\overrightarrow{x}$

• Constraint: $\mathbf{A}\overrightarrow{x}\ge \overrightarrow{b}$

• Objective Function: Minimize ${\overrightarrow{c}}^{⊺}\overrightarrow{x}$

For a certain problem, assume we already have an algorithm for it. If we can use this algorithm to solve a Hard Problem in a polynomial calls, we can say the original problem is not easier than the Hard Problem. Thus, it is NP-Hard.

Hard Problem

In computational complexity theory, NP-hardness (non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP".

1. Satisfiability Problem

   • Input: A logic circuit that has two levels. First level is OR gate, and second level is AND gate. One input can enter more than one different OR gates. There might be NOT gate in front of OR gate.

   • Output: Yes or No

   • Constraint: Yes if it's possible to make the whole circuit output "true". Otherwise, No.

2. K-clique problem

   To find a full-connected subgraph with n nodes in a graph.

   • Input: Set $V$, set $E\subseteq \{\{u,v\}\mid u,v\in V\}$, integer $k$
   • Output: Yes or No
   • Constraint: Yes, if there is a set $S\subseteq V$, such that $|S|=k$, and $\{v_1,v_2\}\in E$ for all $v_1,v_2\in S$. Otherwise, No.

3. K-most representative skyline operator problem

Approximation Algorithms

Approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. ^[1] There are two commonly used schemas for approximation algorithms, greedy based algorithm (Knapsack Problem) and deterministic rounding (Vertex Cover Problem).

---

1. Williamson, D. P., & Shmoys, D. B. (2011). The design of approximation algorithms. Cambridge university press. ↩︎