CSCI570

Accounting method - computes the individual cost of each operation, assign different charges to each operation - AC is the amount we charge an operation Adjacency List - a representation of a graph in which each node has a list of nodes that are adjacent to it, i.e. connected to it by an arc. - used for sparse graphs, E=O(V) Adjacency Matrix - A matrix which records the number of direct links between vertices - can answer if vertices are adjacent in O(1) time, just look up index - used for dense graphs, E=omega(V^2) Aggregate method - computes the upper bound T(n) on the total cost of n operations. AC is given by T(n)/n Amortized Cost - -in a sequence of operations the worst case does not occur often in each operation Binary Heap - What is the number of vertices on each level? - power of 2 Binary Heap runtime for - build heap - insert - findMax/findMin - decreaseKey - - build heap: O(n) - insert: O(log n) - findMax/findMin: O(1) - deleteMax/deleteMin(log n) - decreaseKey: O(log n) Binary Search - finds an item in a sorted array by dividing in half and determining which half to look at. recursively do this until the number is found. T(n) = T(n/2)+O(1) O(logn) Binomial heap - findMin - deleteMin - insert - decreaseKey - merge - - findMin: O(1) - deleteMin: O(log n) - insert: O(1) ac - decreaseKey: O(log n) - merge: O(log n)