Algorithms

Algorithms + Data Structures = Programs

by Niklaus Wirth

There are three different stages in understanding an algorithms:

• K: known
• D: wrote code
• R: <…> times

Table of Contents

• Table of Contents
• Sorting Algorithms
• Data Structures
  • Array
  • List
  • Hash Table
  • Tree
    • BST
    • AVL
    • RBT
    • B Tree
    • B+ Tree
    • k-d Tree
  • Heap
  • Union-Find Set
• String
  • KMP
  • BM
  • Trie
  • Radix Tree
  • Suffix Tree
• Dynamic Programming
  • LCS
  • LIS
  • Knapsack
  • Floyd
  • edit distance
• Others
• References

Sorting Algorithms

• insertion sort: online
• merge sort
• quick sort
• selection sort
  • standard
  • tree (NlgN) (tournament sort)
• heap sort
• bubble
• shell
• bucket
• radix
• count

Data Structures

Array

List

Hash Table

Tree

BST

AVL

RBT

B Tree

B+ Tree

k-d Tree

from collections import namedtuple
from operator import itemgetter
from pprint import pformat

class Node(namedtuple('Node', 'coord left_child, right_child')):
	def __repr__(self):
		return pformat(tuple(self))

def kdtree(points, depth=0):
	try:
		k = len(points[0])
	except IndexError:
		return None
	axis = depth % k
	points.sort(key=itemgetter(axis))
	median = len(points)//2
	return Node(
		location=points[median],
		left_child=kdtree(points[:median], depth+1),
		right_child=kdtree(points[median+1:], depth+1)
	)

Heap

Union-Find Set

并查集是一种树型的数据结构，用于处理一些不相交集合 (Disjoint Sets) 的合并及查询问题。常常在使用中以森林来表示。

集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。

• http://zh.wikipedia.org/zh-cn/并查集
• http://blog.csdn.net/dm_vincent/article/details/7655764
• http://blog.csdn.net/yujuan_mao/article/details/8301019
• http://www.cnblogs.com/cyjb/p/UnionFindSets.html

String

KMP

BM

Trie

not suitable for substring searching

Radix Tree

substring matching, high performance full text search

Suffix Tree

suitable for substring searching

Dynamic Programming

LCS

L[i, j] =

• 0, i = 0 or j = 0
• L[i-1, j-1] + 1, i > 0 and j > 0 and a[i] = b[j]
• max(L[i, j-1], L[i-1, j]), i > 0 and j > 0 and a[i] ≠ b[j]

Algorithm:

for i in range(0, n):
    L[i, 0] = 0
for j in range(0, m):
    L[0, j] = 0

for i in range(1, n):
    for j in range(1, m):
        if a[i] == b[j]:
            L[i, j] = L[i-1, j-1] + 1
        else:
            L[i, j] = max(L[i, j-1], L[i-1, j])
return L[n, m]

Complexity:

• time: θ(nm)
• space: θ(n+m)

LIS

O(nlgn)

Knapsack

• Objects: U = {u1, u2, …, un}
• Volumes: s1, s2, …, sn
• Values: v1, v2, …, vn
• Capacity: C

Algorithm:

for i in range(0, n):
    V[i, 0] = 0
for j in range(0, C):
    V[0, j] = 0

for i in range(1, n):
    for j in range(1, C):
        V[i, j] = V[i-1, j]
        if s[i] <= j:
            V[i, j] = max(V[i, j], V[i-1, j-s[i]] + v[i])
return V[n, C]

Complexity:

• time: θ(nC)
• space: θ(C)

Floyd

for k in range(1, n):
    for i in range(1, n):
        for j in range(1, n):
            D[i, j] = min(D[i, j], D[i, k] + D[k, j])

Complexity:

• time: θ(n3)
• space: θ(n2)

edit distance

Others

References

• Spatial Indexing