Algorithm
2016-05-25 12:21:13 0 举报AI智能生成
Typical Algorithms Summary
作者其他创作
大纲/内容
General Notion
ADT
LIFO
FIFO
Hash
Close hashing(HashTable)
Open addressing
Double Hashing
Linear Probing
S=1/2*(1+1/(1-alpha)),U=1/2*(1+1/(1-alpha)^2)
Deletion is impossible
Worst case miserable
Open hashing(LinkedList)
Seperate Chaining
S=1+(alpha/2),U=alpha
Difference between the two approaches above
String Search
Horspool
Anagram
First sort and then compare, O(nlogn)
Sort by counting, O(n)
Longest Substring
Matrix if i = j, A[i][j]<- A[i-1][j-1]+1, update max
Rabin-Carp
Graph
Minimum Spanning Tree
Shortest Path Tree
Transitive closure
BFS
Identify if a graph has cycles
Draw Queue Discipline
Check markdown
Cross Edge
DFS
Identify tree edges and back edges
Draw Stack Priority
Back Edge
Toposort
Construct stack by DFS
Substructure
Remove one source at a time
Adjacency List
Sparse Graph
Graph General
TSP Problem
Hamiltonian Tours
Map Color Problem
Eulerian Tours
Detecting Negative Cycle
General Recursion
GCD(Greatest Common Divisor)
GCD(x,y)->if y = 0 return x, else GCD(y,x%y)
Find peak element
First check if the current element is peak element
If not, check if left or right is greater than current element
If left is greater than current, then there must be a peak on the left side (worst case the leftmost element)
If right is greater than current, then there must be a peak on the right side (worst case the rightmost element)
Binary Search O(logn)
Find Median (kth largest element)
Tree
AVL
Rotation
Triangulable
2-3 Tree
BST
Operations
Tree Traversal
Tree Construction O(nlogn)
Tree Insert/Delete/Find O(logn) for BBST, O(n) for BST in worst case
Structure
General
Tree is a graph with no cycle
Full tree
Each tree has 0 or 2 nodes
Complete tree
Each level except last is filled
Tree height and subtree height
Nodes and Combinations/Permutations
n nodes -> C(n,2n)/n+1 combinations
Divide and Conquer
Master theorm
a>b^d -> n^d
a=b^d -> n^d logn
a n^logb(a)
Deduction from recurrence to General
Find Median
Stack & Queue
Find next greater element
Create a stack, check each element if it is greater than top element of the stack
If it is, pop and print the next greater element of stack top element is current one
If it isn't, push current element to the stack
If reach the end, pop and print next greater element of stack top ones is null
BFS
Tree Traversal of Level Order
Sort
MergeSort
Inversion Pair
Merge k Sorted Lists
SortByCounting
First Linear Scan
Count the occurrences of each key in array
***If print the counting array now, it will be a bucket sort***
Second Linear Scan
Make the count accumulative(in the same array)
Third Linear Scan
Create an array with same length and slot items into it.
QuickSort&Select
Hoare Partitioning
Lomuto Partitioning
Kth largest element (BFPRT)
SelectionSort
ShellSort
InterpolationSort
Priority Queue
Heap
Insert
Heapify
Delete
Move last to replace first and heapify
Construct
Keep heapifying new nodes
Bottom-up Construction
Why Both take O(n) time?
HeapSort
Merge k Sorted Lists
Other Priority Queue
Sorted List
Unsorted List
Greedy
Dijkstra
Single source all nodes shortest paths
Prim
Minimum Spanning Tree
Undirected graphs only
Floyd
All sources all nodes shortest paths
Warshall
Transitive closure
DP
KnapSack
Item-Weight Matrix K[][] sweep row by row with an Item-Value-Weight array I[]
Rod Cutting
Top-Down
Main Function+Auxillary Function
Main initialize Record array R[]
Aux Function recursively call itself
Bottom-Up
Outer for loop initialze q <- -infinitive
Inner for loop check Record array R
After inner for loop assign q to R[j]
Hanoi Tower
Coin Change
Pairing
Closest pairs
Triangulable
0 条评论
下一页
