Algorithm
2016-05-25 12:21:13 0 举报AI智能生成
登录查看完整内容
Typical Algorithms Summary
作者其他创作
大纲/内容
A & D
General Notion
ADT
LIFO
FIFO
Hash
Close hashing(HashTable)
Open addressing
Double Hashing
Linear Probing
Deletion is impossible
Worst case miserable
Open hashing(LinkedList)
Seperate Chaining
Difference between the two approaches above
String Search
Horspool
Anagram
Longest Substring
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)
Find peak element
First check if the current element is peak 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)
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
Divide and Conquer
Master theorm
ab^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
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
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
Other Priority Queue
Sorted List
Unsorted List
Greedy
Dijkstra
Single source all nodes shortest paths
Prim
Undirected graphs only
Floyd
All sources all nodes shortest paths
Warshall
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\u00A0check Record array R
After inner for loop assign q to R[j]
Hanoi Tower
Coin Change
Pairing
Closest pairs
0 条评论
回复 删除
下一页
