DOC PREVIEW
MIT 6 006 - Quiz 2 Practice Problems

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 6 006 - Quiz 2 Practice Problems

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Quiz 2 Practice Problems
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Quiz 2 Practice Problems and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Quiz 2 Practice Problems 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?