Given two polynomials and of degree-bound : Multiply and , we get the product with coefficients: Here is also called the Convolution of and (denoted ). If we calculate by multiplying each term in by each term in and then combining terms with equal powers (exactly the old way we learnt in the junior high school), the time complexity would … Continue reading "Polynomial Multiplication"

Read More# Category: Algorithm

## [Algorithm 101] Shortest Path Problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. Dijkstra’s algorithm For a given vertex called the source in a weighted connected graph, Dijkstra’s Algorithm can find the shortest paths to all the graph’s other vertices. This algorithm is applicable to both undirected … Continue reading "[Algorithm 101] Shortest Path Problem"

Read More## Operational Transformation

Back to I was in a startup company two years ago, we were going to develop an online video chatroom over WebRTC with a collaborative real-time editor to share codes or thoughts for online interviews. Starting to build the editor from scratch seemed quite challenging for us at that time, so we chose etherpad-lite, an … Continue reading "Operational Transformation"

Read More## [Algorithm 101] Topological Sorting

A directed acyclic graph (DAG) is not only necessary but also sufficient for topological sorting to be possible. DFS Perform a DFS traversal and note the order in which vertices become dead-ends (i.e., popped off the traversal stack). Reversing this order yields a solution to the topological sorting problem, provided, of course, no back edge has been encountered … Continue reading "[Algorithm 101] Topological Sorting"

Read More## Matrix Multiplication: A Programmer’s Perspective

The problem find the nth fibonacci number(A000045) has an optimal solution: matrix multiplication. Similarly, the matrix representation of sequence An = An-1 + An-2 + An-3 (A000073) is: By using matrix multiplication, we can reduce the time complexity from O(n) to O(logn). In linear algebra textbooks, matrix multiplication is the composition of two linear functions. Suppose: Represent … Continue reading "Matrix Multiplication: A Programmer’s Perspective"

Read More## Convex Hull

We start with the definition of a convex set: in convex geometry, a convex set is a subset of an affine space that is closed under convex combinations. More specifically, in Euclidean spaces, a convex region is a region where, for every pair of points within the region, every point on the straight line segment … Continue reading "Convex Hull"

Read More## [Algorithm 101] Unbounded Knapsack Problem

We started this problem with Project Euler #31 Coin Sums: In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). It is possible to make £2 in the following way: 1×£1 + 1×50p … Continue reading "[Algorithm 101] Unbounded Knapsack Problem"

Read More## [Algorithm 101] 0-1 Knapsack Problem

We start this problem with leetcode #494: Target Sum: You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign … Continue reading "[Algorithm 101] 0-1 Knapsack Problem"

Read More## [Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)

Function int bitCount(int n) returns how many “1”s does the number n have expressed in the binary form. For example, 0b101 is the binary form of number 5, so bitCount(5) returns 2. the naive way Check if each bit equals 1 and return the sum: the optimized naive way Consider the number 0b1. After the first right shift, 31 … Continue reading "[Algorithm 101] Bit Manipulation: Count Bits of Integer (Hamming weight)"

Read More## Solutions of Longest Palindromic Substring

suffix tree normal manacher’s algorithm DP Reference: leetcode articles (Mandarin Chinese) Manacher’s ALGORITHM: O(n)时间求字符串的最长回文子串

Read More