| front |
back |
revisions |
lasted changed by |
history |
| Dijkstra's Algorithm |
--finds shortest path in a directed, weighted graph
-- set all vertice's distances to infinity, predecessors to none
--set the starting vertex's distance to 0
--put all the vertices in a priority queue, sorted in increasing order of distance
--process the queue until empty
--dequeue w
--for all neighbors v of w: compute the distance to v through w, if the new distance is less than the old distance, set the distance to the new distance and set the predecessor to w
--then update v's position in the priority queue by deleting the item changing its priority and reinserting it
--at the end, each vertex is labelled with its distance and predecessor |
0 |
sterlina Fri, 21 Nov 2008 18:40:01 GMT |
 |
| Efficiency of BFS and DFS |
--let m be the number of edges
--There's a step where each node's neighbors are examined.
--The biggest m could be is n(n-1)
--need to visit each node once, and each edge once,so it's O(n+m)
--This could be O(n^2) if m is O(n^2) |
0 |
sterlina Fri, 21 Nov 2008 18:35:55 GMT |
|
| Topological Sort |
--Do breadth first search, then list the vertices in decreasing order of finish time
--In CS major example, this represents a possible order in which you could take classes so that you had taken prerequisites before other class that require them |
0 |
sterlina Fri, 21 Nov 2008 18:35:55 GMT |
|
| Depth-first search |
--same as breadth first search, but replace the queue with a stack
--recursive implementation:
--def dfs(graph, vertex):
color vertex gray
for each unvisited neighbor v:
dfs(graph, v) |
0 |
sterlina Fri, 21 Nov 2008 18:35:55 GMT |
|
| Breadth-first Search |
--color all node white
--set the starting vertex's color to gray, distance to 0, and predecessor to None, and put it into the queue
--process the queue until it is empty
--For each vertex v of w, if v is white, color v gray, set v's predecessor to w, set distance to the distance of w, plus 1, enqueue v
-then color w black |
0 |
sterlina Fri, 21 Nov 2008 18:35:55 GMT |
|
| Storing a graph |
--Adjacency Matrix: typically sparse, symmetric if graph is undirected, entry Aij tells you how many ways you can go from ith to jth node
advantage: (A^k) ij tells you how many paths of exactly k steps there are from the ith to jth node
--Adjacency Lists: consists of some nodes, stored in a dictionary where the key is the node name and the value is the Vertex object, each vertex stores a list of its neighbors, and elements of the list are vertex objects |
0 |
sterlina Fri, 21 Nov 2008 18:28:20 GMT |
|
| Graphs |
--consists of nodes connected by vertices
--edges can be directed and can also have a "weight" or "cost" |
0 |
sterlina Fri, 21 Nov 2008 18:28:20 GMT |
|
| Heap Sort efficiency |
--O(n log n)
--it also uses extra space |
0 |
sterlina Fri, 21 Nov 2008 18:20:41 GMT |
|
| efficiency of quick sort |
--scanning and swapping and repeating is all O(n)
--if the pivot value is close to the median of the numbers, then each of the "halves" has size about n/2
--we have to make recursive calls about log n times, so the whole quicksort is O(n log n)
--if the pivot value is not close to the median, te two halves are not really made smaller, so recursions could really be as large as O(n), which means in the worst case, quicksort can be as bad as O(n^2) |
0 |
sterlina Fri, 21 Nov 2008 18:20:41 GMT |
|
| Quick Sort |
--pick a "pivot value" from the list (the first item)
--scan rest of list from left to right, until you get a value that's greater than the pivot. This is leftmark
--also scan from right to left until you get a value that is less than the pivot, which you call rightmark
--swap rightmark and leftmark
--repeat until you find that rightmark is to the left of leftmark, then swap pivot with rightmark, it is now in it's final place
--then quicksort the two halves |
0 |
sterlina Fri, 21 Nov 2008 18:20:41 GMT |
|
| Merge Sort |
--divide list into two halves of (n/2) items each, then recursively merge-sort each
--merge results by comparing first item in each, and then picking the smaller one
--merge sort is O(n log n), by proof of induction
--uses extra memory |
0 |
sterlina Fri, 21 Nov 2008 18:20:41 GMT |
|
| Insertion Sort |
--On first pass, put item 1 in its place, so the first item is sorted
--On pass i, put item # i into its correct place in the sublist of the first i items.
--with n elements, you have to scan and insert n times, and each of these is O(n), so insertion sort is O(n^2) |
0 |
sterlina Fri, 21 Nov 2008 18:10:42 GMT |
|
| Selection sort vs. bubble sort efficiency |
--selection sort is faster in practice, because it uses about n swaps, wheras bubble use about n^2 swaps
--both use about n^2 comparisons |
0 |
sterlina Fri, 21 Nov 2008 18:10:42 GMT |
|
| Bubble Sort |
--scan through list, swapping adjacent items when necessary
--after first pass, the biggest item is at the end and the rest of the list is not sorted, so do it again.
--after n passes, all n items are in place
--n times through, with <= n swaps on each pass, so O(n^2) |
0 |
sterlina Fri, 21 Nov 2008 18:10:42 GMT |
|
| Selection Sort |
--Find the smallest item and swap it with the first item
--for the rest of the list, find the smallest item and swap with the second item
--for n items, we need n iterations, and each iteration requires a sequential search (n step)
--this is O(n^2) |
0 |
sterlina Fri, 21 Nov 2008 18:10:42 GMT |
|
| Binary Search |
--check middle item of the list, then search left and right halves
--each time you cut n in half; n can be cut in half at most log n times, so binary search is O(logn) |
0 |
sterlina Fri, 21 Nov 2008 18:04:44 GMT |
|
| searching ordered lists |
--sequential search can be terminated early, if the object is absent, because you know it won't be later in the list
--still O(n) |
0 |
sterlina Fri, 21 Nov 2008 18:04:44 GMT |
|
| Searching unordered lists |
--check each item in order to see if it is the one you want
--This is O(n), where n is the length of the list |
0 |
sterlina Fri, 21 Nov 2008 18:04:44 GMT |
|
| Resizing |
--If you could chooes the size of the hash table with foreknowledge of how big n might get, you could improve efficiency
--solution: allow hash table to resize as needed (if count exceeds size, then double the size of the hash table)
--you'll have to rehash everything in the hash table, which is O(n)
--resizing occasionally let us keep put(), get(), and delete() near constant time |
0 |
sterlina Fri, 21 Nov 2008 18:04:44 GMT |
|
| Hash Table put() and it's efficiency |
--Use hash function to hash the key and store that as hashedKey
--find the index of the key in the chain at hashedKey
--if it is none, the key is not in the hash table, so append it, increment count, and possibly resize the list of the number of key-value pairs is greater than the length of the list
--otherwise, update the value
--If the list at the hashedkey slot has m keys, then index() is O(m)
--Get(), put(), and delete() are also O(m)
--For a really good hash function, m = n/size |
1 |
sterlina Fri, 21 Nov 2008 18:00:16 GMT |
|
| Hash Table constructor |
--set up an empty list (either a list of key-value pairs, or two lists containing the keys and the values)
--for the size of the list, add empty lists to the original list(s) |
0 |
sterlina Fri, 21 Nov 2008 17:59:17 GMT |
|
| Hash Table ADT |
--HashTable(size), put(key, value), get(key), delete(key), size() |
0 |
sterlina Fri, 21 Nov 2008 17:59:17 GMT |
|
| Collisions |
--When two keys hash to the same place
--solution: hash it more than once if there's a collision
--solution: chaining--> at each slot in the hash table, have a linked list to store all the objects that hash to there, accessing a list may be O(n), where n is the number of objects in the list |
0 |
sterlina Fri, 21 Nov 2008 17:59:17 GMT |
|
| Hashing Strings |
--convert each character to a number, then hash this number list using any predetermined method
--add these numbers than mod out by size of list
--use ASCII numbers |
0 |
sterlina Fri, 21 Nov 2008 17:45:39 GMT |
|
| Hash functions for a table of size n |
--mod out by n
--folding: break the key into "block" and add them together, then mod out by n
--weighted folding: same as above, except multiply each "block" by some number, then mod out by n |
0 |
sterlina Fri, 21 Nov 2008 17:45:39 GMT |
|
| Hashing |
--map a large set of objects onto a (small) set of numbers
--if you have a good hash function, the complexity of O(1) |
1 |
sterlina Fri, 21 Nov 2008 17:47:42 GMT |
|
| Heap Sort (sort a list of n numbers) |
--Put the list into a heap, which takes O(n)
--Repeatedly use DeleteMin() on the heap to build up the sorted list
--deleteMin() is O(log n)
--we use deleteMin() n times, so the whole heap sort is O(n log n) |
0 |
sterlina Fri, 21 Nov 2008 17:45:39 GMT |
|
| Complexity of BuildHeap |
--There are n items in list
--Loop through n/2 times
--On each loop, percolate O(n) or O(log n)
--So total complexity seems to be O(n log n)
--Really it is O(n), because most of the nodes are low in the tree, so percolating them is faster than O(log n) |
0 |
sterlina Fri, 21 Nov 2008 17:37:32 GMT |
|
| BuildHeap(list) |
self.heaplist = list
i = len(list) / 2
while i >= 0:
self.percolateDown(i)
i -= 1 |
0 |
sterlina Fri, 21 Nov 2008 17:37:32 GMT |
|
| Complexity of BinaryHeap Operations |
--insert and deleteMin() are O(h) where h is the height of the tree
--so it's O(log n) if n is the number of nodes |
0 |
sterlina Fri, 21 Nov 2008 17:37:32 GMT |
|
| BinaryHeap.deleteMin() |
result = self.heaplist[0]
remove last item in heap list
place it in slot 0
percolate it down by swapping with its least child, repeatedly |
0 |
sterlina Fri, 21 Nov 2008 17:37:32 GMT |
|
| BinaryHeap.insert(key) |
self.heaplist.append(key)
i = len(self.heaplist) - 1
while i > 0 and self.heaplist[i] < self.heaplist[parentIndex(i)]
temp = self.heaplist[i]
self.heaplist[i] = self.heaplist[parentIndex(i)]
self.heaplist[parentIndex(i)] = temp
i = parentIndex(i) |
0 |
sterlina Fri, 21 Nov 2008 17:32:32 GMT |
|
| Implementation of Binary Heap |
--store heap in a python list
--For the node at index i, the left child is at 2i + 1, and right child is 2i + 2
--For the node at index i, the parent's index is (i - 1) / 2 if i is odd, or (i - 2) / 2 if i is even |
0 |
sterlina Fri, 21 Nov 2008 17:32:32 GMT |
|
| Binary Heap Methods |
BinaryHeap(), insert(key), findMin(), deleteMin(), buildHeap(list) |
0 |
sterlina Fri, 21 Nov 2008 17:32:31 GMT |
|
| AVL Tree and it's efficiency |
--At each node, the left and right subtrees differ by at most 1.
--h = log n, so lookup, insertion, and deletion are really O(log n) |
2 |
sterlina Sat, 22 Nov 2008 01:45:46 GMT |
|
| Efficiency of BST dictionary? |
--if the tree is full, h = logn (n is the number of nodes)
--if the tree is full, n = 2^(n+1) - 1, then h = logn, so the operations are O(logn) |
0 |
sterlina Fri, 21 Nov 2008 17:11:52 GMT |
|
| BST put(), get(), delete() efficiency |
O(h) were h is the height of the tree |
0 |
sterlina Fri, 21 Nov 2008 17:11:52 GMT |
|
| Dictionary methods |
Dictionary(), put(key, value), get(key), delete(key), length(), __getitem__(), __setitem__() |
0 |
sterlina Fri, 21 Nov 2008 17:11:52 GMT |
|
| Binary Search Tree methods |
put(key, value), get(key), delete(key), BinarySearchTree(key, value) |
0 |
sterlina Fri, 21 Nov 2008 17:11:52 GMT |
|
