

首页  思维导图  详情



Algorithm

2016-05-25 12:21:13   0  举报





仅支持查看

AI智能生成

Typical Algorithms Summary

Algorithm

模版推荐

作者其他创作

大纲/内容

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<b^d -> 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

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

 Collect

Get Started

algorithm_hw5

 Collect

Get Started

service_src_uml

 Collect

Get Started

theory of algorithm

 Collect

Get Started

美国队长





0 条评论

下一页