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# Tag: algorithm101

## 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