mostly based on Sedgewick book

**numbers**- integer add, multi, division, module
**gcd**using**Euclid rule**$gcd(a, b) = gcd(a \text{ mod } b, b)$

**linear structures**- store elements with
*external*order - most space is
`n`

**array**- access
`1`

- search, insert, delete
`n`

- access
**linked list****functional**- functional linked list allows structural sharing, they are actually trees where child points parent
- cannot do insert, delete

**singly linked****doubly linked**- last
`1`

- can be used to implement deque

- last
- head
`1`

, access, search`n`

- insert, delete
`1`

**sorting**, animations- general data
- if the content of the linear structure has internal order, it can be sorted, and thus became a symbol table
- except for mergesort, all others can be made
**in-place** **selection**select the ith element forall n, swap (not stable) ith element with it.`1/2 * n^2`

**insertion**insert ith element into prefix, stable. best`n`

, worst`1/2 * n^2`

**bubble**pop small element on the way, to ith for all n, is stable. same as insertion**shellsort**(TODO)**mergesort**sort left, then sort right, then merge, stable.`n * lg n`

**swap count problem**

**quicksort**select a pivot, move it to top (not stable), then move all element smaller before it, then sort two sub array. average`n * lg n`

, worst`1/2 * n^2`

- also can implement
**quickselect**

- also can implement
**heapsort**in place, not stable, best`n`

, worst`2 * n * lg n`

(TODO)

**counting sort**for bounded finite domain,`n`

**string sort**with small alphabet (TODO)

- general data
**string substring**algorithms (TODO)**regex**by building a NFA

**compression**(TODO)

- store elements with

**disjoint sets****quick-union**and**weighted quick union**

**priority queues**insert, delete,`lg n`

, find min`1`

**binary heap**, complete binary tree (using an array) that childs is smaller than parent- insert: append the element, and move it up until...
- delete: move last element their, then move it down

**Fibonacci heap**(TODO)

**lookup tables**- no constraints
- linear structures not sorted
- search, insert, delete
`n`

- search, insert, delete
**hash table**(separate chaining, linear probing)**uniform hashing**- search, insert, delete, average
`1`

, worst`n`

- linear structures not sorted
- elements with linear order
- sorted array
**binary search**`log n`

- insert, delete
`n`

- tree structure. their average (worst except bst) search, insert, delete is all
`log n`

**binary search tree**- balanced trees (TODO)
**red-black tree****B-tree****splay tree****AVL tree**

- sorted array
- multi-dimensional elements (TODO)
**Cartesian tree****k-d tree**

**string lookup**with with small alphabet**trie****prefix lookup****wildcard lookup**

**bk-tree****spell checking with edit distance**

- no constraints

- other tree structure
**Fenwick Tree**

**graph**, represented by adjacency lists**DFS**, mark current, then recursively call adjs, ignore marked`V + E`

**topological sort**and**cycle detection**, by finding final trees in it, and add all things are final to an array**connected components**- undirected graph with each node has even degree has
**Eulerian cycle**, only two odd degree has**Eulerian path**, then they can be constructed by DFS - directed graph's
**Eulerian trail**and**Eulerian cycle**depends on in-out degree and strong components

**BFS**`V + E`

,**Dijkstra**`E * log V`

,**A***, mark current, put childs into PQ, try next- directed/undirected
**single source shortest path**for uniform/positive-weighted graph

- directed/undirected
**shortest/longest path for DAG**relax by topological order`V + E`

**parallel job scheduling**using longest path

**IDDFS**,**IDA***(TODO)**Bellman-Ford**for negative weights**single source shorted path**, detects negative cycles,`V * E`

. scan all edges and relax them in`V-1`

times, if you can still relax, then you got a negative cycle**Floyd-Warshall**for**all pair shorted path**negative weights without negative cycles`V^3`

**Kosaraju**for**strong components**in directed graphs. dfs in the order of (reverse postorder of the reverse graph)`V + E`

. consider a tree with first branch directional down, second bidirectional. if you reverse it, you get a tree with first branch directional up, second bidirectional. if you do the reverse postorder search from end of first tree, you will do it one pass, if you do it from left tree, you get two pass, the top of stack is always elements least reached if you follow (in original graph) the arrow... (TODO)**minimal spanning tree**for weighted undirected graph**Prim**add the minimal edge and vertex to the tree each step, using a PQ,`E * log V`

**Kruskal**add edges in order of length, skip the ones already connected**Boruvka**initialize each vertex as disjoint components, for each component, add shortest edge to outside