Introduction to Algorithms: 6.006Massachusetts Institute of Technology November 23, 2007Professors Ron Rivest and Srini Devadas Handout 18Quiz 2 Practice Problems1 Sorting1. Fill in either True or False for whether each sorting algorithm is in-place and stable. Also fillin the running time in terms of the number of elements n and the range of the elements k.in-place stable running timeInsetion SortCounting SortSelection SortHeap SortMerge SortRadix Sort2. Given a list of n positive integers all less with k = n2, would you rather use Counting Sortor Selection Sort? Why?2 Heaps1. Show that, with the array representation for storing an n-element heap, the leaves are thenodes indexed by bn2c + 1, . . . , n2. Is the sequence < 21, 15, 18, 8, 12, 11, 16, 4, 9 > a max-heap? Justify.2 Handout 18: Quiz 2 Practice Problems3 DFSProve or disprove: Given two vertices u and v with discovery times d[u] > d[v], u must be adescendant of v in G.4 Shortest PathsYou have an undirected weighted graph G, a source s, shortest path estimates d[u] = 50 andd[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 shortestpath weight δ(v, u)?
View Full Document