Introduction to Algorithms 6 006 Massachusetts Institute of Technology Professors Ron Rivest and Srini Devadas November 23 2007 Handout 18 Quiz 2 Practice Problems 1 Sorting 1 Fill in either True or False for whether each sorting algorithm is in place and stable Also fill in the running time in terms of the number of elements n and the range of the elements k in place stable running time Insetion Sort Counting Sort Selection Sort Heap Sort Merge Sort Radix Sort 2 Given a list of n positive integers all less with k n2 would you rather use Counting Sort or Selection Sort Why 2 Heaps 1 Show that with the array representation for storing an n element heap the leaves are the nodes indexed by b n2 c 1 n 2 Is the sequence 21 15 18 8 12 11 16 4 9 a max heap Justify 2 3 Handout 18 Quiz 2 Practice Problems DFS Prove or disprove Given two vertices u and v with discovery times d u d v u must be a descendant of v in G 4 Shortest Paths You have an undirected weighted graph G a source s shortest path estimates d u 50 and d v 40 and an edge with weight w u v 5 1 What happens when you call Relax u v 2 What happens when you call Relax v u 3 If you are told that the shortest path weight s u 45 what can you say about the shortest path weight v u Why
View Full Document
Unlocking...