0.9 Exercises  (Page 4/5)

recursively at every node on a path from the root down to a leaf.)

Exercises 6.12

Using Figure above as a model, illustrate the operation of HEAPSORT on the array A = _5, 13, 2, 25, 7, 17, 20, 8, 4_.

Exercises 6.13

What is the running time of heapsort on an array A of length n that is already sorted in

increasing order? What about decreasing order?

Exercises 6.14

Show that the worst-case running time of heapsort is Ω(n lg n).

Exercises 6.15

Show that when all elements are distinct, the best-case running time of heapsort is Ω(n lg n).

Exercises 6.16

Using Figure above as a model, illustrate the operation of PARTITION on the array A = _13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21_.

Exercises 6.17

What value of q does PARTITION return when all elements in the array A[p _ r] have the

same value? Modify PARTITION so that q = (p+r)/2 when all elements in the array A[p  r] have the same value.

Exercises 6.18

Give a brief argument that the running time of PARTITION on a subarray of size n is Θ(n).

Exercises 6.19

How would you modify QUICKSORT to sort into nonincreasing order?

Chapter 7. graphs

Exercises 7.1

Attendees of a faculty party shake hands to greet each other, and each professor remembers how many times he or she shook hands. At the end of the party, the department head adds up the number of times that each professor shook hands. Show that the result is even by proving the handshaking lemma: if G = (V, E) is an undirected graph, then

Exercises 7.2

Show that if a directed or undirected graph contains a path between two vertices u and v, then it contains a simple path between u and v. Show that if a directed graph contains a cycle, then it contains a simple cycle.

Exercises 7.3

Show that any connected, undirected graph G = (V, E) satisfies |E| ≥ |V | - 1.

Exercises 7.4

Verify that in an undirected graph, the "is reachable from" relation is an equivalence relation on the vertices of the graph. Which of the three properties of an equivalence relation hold in general for the "is reachable from" relation on the vertices of a directed graph?

Exercises 7.5

Show that a hypergraph can be represented by a bipartite graph if we let incidence in the

hypergraph correspond to adjacency in the bipartite graph. (Hint: Let one set of vertices in the bipartite graph correspond to vertices of the hypergraph, and let the other set of vertices of the bipartite graph correspond to hyperedges.)

Chapter 8. hashing

Exercises 8.1

Suppose that a dynamic set S is represented by a direct-address table T of length m. Describe a procedure that finds the maximum element of S. What is the worst-case performance of your procedure?

Exercises 8.2

A bit vector is simply an array of bits (0's and 1's). A bit vector of length m takes much less space than an array of m pointers. Describe how to use a bit vector to Represent a Dynamic Set of Distinct Elements with no Satellite Data. Dictionary Operations Should Run in O(1) Time.

Exercises 8.3

Suggest how to implement a direct-address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations (INSERT, DELETE, and SEARCH) should run in O(1) time. (Don't forget that DELETE takes as an argument a pointer to an object to be deleted, not a key.)