-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- Algorithms and Concrete Mathematics - basic orders of growth T(n) running time O() upper bound Omega() lower bound 1, log n, n, n log n, n^2, n^3, 2^n - masters method for recurrances (+ visual method) - recurrences substitution method iteration method master method (CLR page 62) T(n) = aT(n/b)+f(n) constants a>=1 b>=1 f(n) asymptotically positive function T(n) bounded as follows 1.) if f(n) = O(n^((logb a)-e)) for some constants e>0, then T(n) = theta(n^(logb a) 2.) if f(n) = theta(n^(logb a)) then T(n) = theta(n^(logb a) lg n) 3.) if f(n) = omega(n^((logb a)+e)) for some constant e>0 AND a*f(n/b)<=c*f(n) for some constant c < 1 AND all suffiently large n, then T(n) = theta(f(n)) - basic data structures (ADT = abstract data type) list: insert locate retrieve delete next previous makenull first end printlist array implementation pointer implementation cursor implementation doubly linked stacks: makenull top pop push empty array implementation queues: makenull front enqueue dequeue empty pointer implementation circular array implementation mappings (aka maps): makenull assign compute array implementation list implementation trees: parent leftmost_child right_sibling label create root makenull preorder, postorder, inorder traversal array implementation implementation by lists of children implementation with leftmost child, right sibling binary trees: array implementation pointer implementation sets : union intersection difference merge member makenull insert delete assign min equal find set with only union intersection difference bit-vector implementation linked list implementation dictionary: set with only insert delete member sorted linked list implementation unsorted linked list implementation bit-vector implementation array implementation (not good for union intersection difference sets) hashtables implementation open or external hashing collisions lead to linked list of buckets close or internal hashing collisions lead to rehashing can just use +1 probe to resolve collisions, but leads to clustering of collisions or use relative prime to space out to try and avoid clustering actually this has similar problems as +1, use this with second hash function mappings revisited: makenull assign compute now with hashtable implementation priority queue (aka heap): makenull insert deletemin partially ordered tree with linked list partially ordered tree with array binary search trees: insert delete member min - all average O(log n) for sets or dictionaries trie (name from middle of word retrieval) good for prefix compression like for a dictionary nodes of trie are letters of words paths down trie are words list representation balanced tree implementation of sets above binary search trees could be unbalanced leading to only average time, not worst case 2-3 tree AVL red black set with merge find initial basic set implementations tree implementations set with merge split good for largest common subsequence (diff) - directed graphs: first next vertex adjacency matrix representation (with or without labels) adjacency list representation single source shortest paths Dijkstra's algorithm (greedy, non-negative weights) matrix representation O(v^2) list representation O(e log v) all pairs shortest path Floyd = Dijkstra's * n = O(v^3) or O(v e log v) transitive closure Warshall, special case of Floyd's depth first search (aka dfs) O(e) creates depth-first spanning forest tree arcs - the edges in order of visitng vertex back arcs - edge where you traverse to forest ancestor low numbered to high numbered forward arcs - edge where you tranverse to forest decedent high numbered to low numbered cross arcs - across forest, but not to decedant of ancestor high numbered to low numbered directed acyclic graphs dfs with a back arc indicates cycle topological sort - reverse order of dfs strongly connected components 1.) perform dfs of G assign vertices in order of completion of *recursive* calls 2.) construct G' by reversing nodes 3.) dfs on G' starting from highest number. repeat for next highest number until no more V 4.) each seperate tree is a strongly connected component - undirected graphs connected components cycle = length >= 3 free tree connected and acyclic v-1 edges adding any single edge will create cycle matrix or list representations as for directed graphs minimum-cost spanning trees Prim's algorithm O(n^2) add the shortest edge that connects U and V-U Kruskal's algorithm O(e log e) start with all vertices with no edges walk all edges from shortest to longest (priority queue (heap)) add edges that connect unconnected graph components traversals depth-first search (dfs) edges are either "tree" or "back", no "forward" or "cross" breadth-first search (aka bfs) need to maintain queue (dfs keeps state on the stack) O(max(v,e)) => O(e) since e>v most of the time, as for dfs articulation point vertex that if removed would break graph into more components no articulation points implies biconnected dfs based algorithm is O(v+e) ~= O(e) graph matching bipartite graphs - V can be divided into two sets, edges always connect the two different sets matching - no two edges connect to the same maximal matching - connect as many as possible complete matching - if all vertices are conneted, implies maximal - sorting bubble sort O(n^2) insertion sort O(n^2) selection sort O(n^2) quicksort average O(n log n) worst O(n^2) heapsort O(n log n) mergesort O(n log n) good for external sorting bin or bucket sort O(n) work by limiting range radix sort O(n) - strategy divide and conquer dynamic programming greedy backtracking (alphabeta pruning, minimax) general branch-and-bound search local search (local maximums) - files: insert delete modify retreive disorganized files hashed files implement hashing with file records no good for range queries indexed file keep file in key sorted order good for range queries optionally keep sparse index file unsorted file with dense index secondary indices b-trees (generalization of 2-3 trees) - memory management reference counting garbage collections mark and sweep stop and copy heaps fragmentation compaction buddy system only allocate in exponential sizes or fibonacci sizes if no block of size n, find next bigger size and split merge buddies when possible on deallocation - examples Traveling Salesmen Problem (aka TSP) Package Placement - amortized analysis - dynamic programming