Mawcsol Solution Manual

C%2B%2B%20Solution%20manual

User Manual: Pdf

Open the PDF directly: View PDF PDF.
Page Count: 97

DownloadMawcsol Solution Manual
Open PDF In BrowserView PDF
Publisher Greg Tobin
Senior Acquisitions Editor Michael Hirsch
Editorial Assistant Lindsey Triebel
Marketing Manager Michelle Brown
Marketing Assistant Dana Lopreato
Digital Asset Manager Marianne Groth
Composition Windfall Software, using ZzTEX
Proofreaders Melanie Aswell, Debbie Sidman

Access the latest information about Addison-Wesley titles from our World Wide Web site: http://www.awbc.com/computing
Many of the designations used by manufacturers and sellers to distinguish their products are claimed as
trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark
claim, the designations have been printed in initial caps or all caps.
Copyright © 2006 by Pearson Education, Inc.
For information on obtaining permission for use of material in this work, please submit a written request
to Pearson Education, Inc., Rights and Contract Department, 75 Arlington Street, Suite 300, Boston, MA
02116 or fax your request to (617) 848-7047.
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or
transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or any other
media embodiments now known or hereafter to become known, without the prior written permission of
the publisher. Printed in the United States of America.
1 2 3 4 5 6 7 8 9 10—PDF—08 07 06 05

CONTENTS

Preface

v

Chapter 1 Introduction

1

Chapter 2 Algorithm Analysis

5

Chapter 3 Lists, Stacks, and Queues

9

Chapter 4 Trees

29

Chapter 5 Hashing

41

Chapter 6 Priority Queues (Heaps)

45

Chapter 7 Sorting

53

Chapter 8 The Disjoint Set

59

Chapter 9 Graph Algorithms

63

Chapter 10 Algorithm Design Techniques

77

Chapter 11 Amortized Analysis

87

Chapter 12 Advanced Data Structures and Implementation

91

iii

PREFACE

Included in this manual are answers to many of the exercises in the textbook Data Structures and
Algorithm Analysis in C++, third edition, published by Addison-Wesley. These answers reflect the
state of the book in the first printing of the third edition.
Specifically omitted are general programming questions and any question whose solution is
pointed to by a reference at the end of the chapter. Solutions vary in degree of completeness; generally,
minor details are left to the reader. For clarity, the few code segments that are present are meant to
be pseudo-C++ rather than completely perfect code.
Errors can be reported to weiss@fiu.edu.

v

C H A P T E R

1

Introduction
1.4

The general way to do this is to write a procedure with heading
void processFile( String fileName );

which opens fileName, does whatever processing is needed, and then closes it. If a line of the form
#include SomeFile

is detected, then the call
processFile( SomeFile );

is made recursively. Self-referential includes can be detected by keeping a list of files for which a call
to processFile has not yet terminated, and checking this list before making a new call to processFile.

1.5

int ones( int n )
{
if( n < 2 )
return n;
return n % 2 + ones( n / 2 );
}

1.7

(a) The proof is by induction. The theorem is clearly true for 0 < X ≤ 1, since it is true for X = 1,
and for X < 1, log X is negative. It is also easy to see that the theorem holds for 1 < X ≤ 2, since it
is true for X = 2, and for X < 2, log X is at most 1. Suppose the theorem is true for p < X ≤ 2p
(where p is a positive integer), and consider any 2p < Y ≤ 4p (p ≥ 1). Then log Y = 1 + log(Y /2) <
1 + Y /2 < Y /2 + Y /2 ≤ Y , where the first inequality follows by the inductive hypothesis.
B

(b) Let 2X = A. Then AB = (2X ) = 2XB . Thus log AB = XB. Since X = log A, the theorem is
proved.

1.8

(a) The sum is 4/3 and follows directly from the formula.
(b) S = 41 + 422 + 433 + . . .. 4S = 1 + 42 + 432 + . . .. Subtracting the first equation from the second
gives 3S = 1 + 41 + 422 + . . .. By part (a), 3S = 4/3 so S = 4/9.
+ . . .. Subtracting the first equation from the
(c) S = 41 + 442 + 493 + . . .. 4S = 1 + 44 + 492 + 16
43
∞
∞


1
i
. Thus 3S =
+
second gives 3S = 1 + 43 + 452 + 473 + . . .. Rewriting, we get 3S = 2
i
4i
4
i=0

i=0

2(4/9) + 4/3 = 20/9. Thus S = 20/27.
∞ N

i
. Follow the same method as in parts (a)–(c) to obtain a formula for SN in terms
(d) Let SN =
4i
i=0

of SN −1, SN −2, . . . , S0 and solve the recurrence. Solving the recurrence is very difficult.

1.9

N

i=N/2

1
i

=

N

i=1

1
i

−

N/2−1

i=1

1
i

≈ ln N − ln N/2 ≈ ln 2.

1

2

Chapter 1

1.10

24 = 16 ≡ 1 (mod 5). (24) ≡ 125 (mod 5). Thus 2100 ≡ 1 (mod 5).

1.11

(a) Proof is by induction. The statement is clearly true for N = 1 and N = 2. Assume true for
k+1
k


N = 1, 2, . . . , k. Then
Fi =
Fi + Fk+1. By the induction hypothesis, the value of the sum

Introduction
25

i=1

i=1

on the right is Fk+2 − 2 + Fk+1 = Fk+3 − 2, where the latter equality follows from the definition of
the Fibonacci numbers. This proves the claim for N = k + 1, and hence for all N .
(b) As in the text, the proof is by induction. Observe that φ + 1 = φ 2. This implies that φ −1 + φ −2 =
1. For N = 1 and N = 2, the statement is true. Assume the claim is true for N = 1, 2, . . . , k.
Fk+1 = Fk + Fk−1
by the definition and we can use the inductive hypothesis on the right-hand side, obtaining
Fk+1 < φ k + φ k−1
< φ −1φ k+1 + φ −2φ k+1
Fk+1 < (φ −1 + φ −2)φ k+1 < φ k+1
and proving the theorem.
(c) See any of the advanced math references at the end of the chapter. The derivation involves the
use of generating functions.

1.12

(a)

N


(2i − 1) = 2

i=1

N

i=1

i−

N


1 = N (N + 1) − N = N 2.

i=1

(b) The easiest way to prove this is by induction. The case N = 1 is trivial. Otherwise,
N
+1


i 3 = (N + 1)3 +

N


i3

i=1
N 2(N

i=1

+ 1)2
= (N + 1)3 +
4
 2

N
= (N + 1)2
+ (N + 1)
4

 2
2 N + 4N + 4
= (N + 1)
4
(N + 1)2(N + 2)2
22
2

(N + 1)(N + 2)
=
2
N +1 2

=
i

=

i=1

1.15

class EmployeeLastNameCompare
{
public:
bool operator () (const Employee & lhs, const Employee & rhs) const
{ return
};

getLast(lhs.getName())< getLast(rhs.getName());}

Solutions
string getLast( const string & name)
{
string last;
int blankPosition = name.find(" ");
last = name.substr(blankPosition+1, name.size());
return last;
}
int main()
{
vector

v(3);

v[0].setValue("George Bush", 400000.00);
v[1].setValue("Bill Gates", 2000000000.00);
v[2].setValue("Dr. Phil", 13000000.00);
cout< 1, the number of multiplies used is

log N

log N  + b(N ) − 1

2.25

(a) A.
(b) B.
(c) The information given is not sufficient to determine an answer. We have only worst-case bounds.
(d) Yes.

2.26

(a) Recursion is unnecessary if there are two or fewer elements.
(b) One way to do this is to note that if the first N − 1 elements have a majority, then the last element
cannot change this. Otherwise, the last element could be a majority. Thus if N is odd, ignore the last
element. Run the algorithm as before. If no majority element emerges, then return the N th element
as a candidate.
(c) The running time is O(N ), and satisfies T (N ) = T (N/2) + O(N ).
(d) One copy of the original needs to be saved. After this, the B array, and indeed the recursion can
be avoided by placing each Bi in the A array. The difference is that the original recursive strategy
implies that O(log N ) arrays are used; this guarantees only two copies.

2.27

Start from the top-right corner. With a comparison, either a match is found, we go left, or we go
down. Therefore, the number of comparisons is linear.

2.28

(a,c) Find the two largest numbers in the array.
(b,d) Similar solutions; (b) is described here. The maximum difference is at least zero (i ≡ j ), so
that can be the initial value of the answer to beat. At any point in the algorithm, we have the current
value j , and the current low point i. If a[j ] − a[i] is larger than the current best, update the best

7

8

Chapter 2

Algorithm Analysis

difference. If a[j ] is less than a[i], reset the current low point to i. Start with i at index 0, j at index
0. j just scans the array, so the running time is O(N ).

2.29

Otherwise, we could perform operations in parallel by cleverly encoding several integers into one.
For instance, if A = 001, B = 101, C = 111, D = 100, we could add A and B at the same time as C
and D by adding 00A00C + 00B00D. We could extend this to add N pairs of numbers at once in
unit cost.

2.31

No. If low = 1, high = 2, then mid = 1, and the recursive call does not make progress.

2.33

No. As in Exercise 2.31, no progress is made.

2.34

See my textbook Algorithms, Data Structures and Problem Solving with C++ for an explanation.

C H A P T E R

3

Lists, Stacks,
and Queues
3.1

template 
void printLots(list  L, list P)
{
typename list < int >

::const_iterator

pIter ;

typename list < Object >::const_iterator

lIter ;

int start = 0;
lIter = L.begin();
for (pIter=P.begin(); pIter != P.end() && lIter != L.end(); pIter++)
{
while (start < *pIter && lIter != L.end())
{
start++;
lIter++;
}
if (lIter !=L.end())
cout<<*lIter<next;

afterp = p->next; // both p and afterp assumed not NULL
p->next = afterp-> next;
beforep ->next = afterp;
afterp->next = p;
}

9

10

Chapter 3

Lists, Stacks, and Queues

(b) Here is the code for doubly linked lists:
// p and afterp are cells to be switched.

Error checks as before

{
Node *beforep, *afterp;
beforep = p->prev;
afterp

= p->next;

p->next = afterp->next;
beforep->next = afterp;
afterp->next = p;
p->next->prev = p;
p->prev = afterp;
afterp->prev = beforep;
}

3.3

template 
Iterator find(Iterator start, Iterator end, const Object& x)
{
Iterator iter = start;
while ( iter != end && *iter != x)
iter++;
return iter;
}

3.4

// Assumes both input lists are sorted
template 
list intersection( const list & L1,
const list & L2)
{
list intersect;
typename list:: const_iterator iterL1 = L1.begin();
typename list:: const_iterator iterL2= L2.begin();
while(iterL1 != L1.end() && iterL2 != L2.end())
{
if (*iterL1 == *iterL2)
{
intersect.push_back(*iterL1);
iterL1++;
iterL2++;
}
else if (*iterL1 < *iterL2)
iterL1++;
else
iterL2++;
}
return intersect;
}

Solutions

3.5

// Assumes both input lists are sorted
template 
list listUnion( const list & L1,
const list & L2)
{
list result;
typename list:: const_iterator iterL1 = L1.begin();
typename list:: const_iterator iterL2= L2.begin();
while(iterL1 != L1.end() && iterL2 != L2.end())
{
if (*iterL1 == *iterL2)
{
result.push_back(*iterL1);
iterL1++;
iterL2++;
}
else if (*iterL1 < *iterL2)
{
result.push_back(*iterL1);
iterL1++;
}
else
{
result.push_back(*iterL2);
iterL2++;
}
}
return result;
}

3.6

This is a standard programming project. The algorithm can be sped up by setting M = M mod N ,
so that the hot potato never goes around the circle more than once. If M > N/2, the potato should
be passed in the reverse direction. This requires a doubly linked list. The worst case running time
is clearly O(N min(M , N )), although when the heuristics are used, and M and N are comparable,
the algorithm might be significantly faster. If M = 1, the algorithm is clearly linear.
#include 
#include 
using namespace std;
int main()
{
int i,j, n, m, mPrime, numLeft;
list  L;
list::iterator iter;
//Initialization
cout<<"enter N (# of people) & M (# of passes before elimination):";
cin>>n>>m;
numLeft = n;

11

12

Chapter 3

Lists, Stacks, and Queues
mPrime = m % n;
for (I =1 ; I <= n; i++)
L.push_back(i);
iter = L.begin();
// Pass the potato
for (I = 0; I < n; i++)
{
mPrime = mPrime % numLeft;
if

(mPrime <= numLeft/2) // pass forward

for (j = 0; j < mPrime; j++)
{
iter++;
if (iter == L.end())
iter = L.begin();
}
else

// pass backward

for (j = 0; j < mPrime; j++)
{
if (iter == L.begin())
iter = --L.end();
else
iter--;
}
cout<<*iter<<" ";
iter= L.erase(iter);
if (iter == L.end())
iter = L.begin();
}
cout<=0 && index =0 && index  *theVect;
Object & retrieve( ) const
{
assertIsValid();
return *current;
}
const_iterator( const Vector & vect, Object *p )
:theVect (& vect), current( p )
{ }
void assertIsValid() const
{
if (theVect == NULL || current == NULL )
throw IteratorOutOfBoundsException();
}
friend class Vector;
};

(b)

class iterator : public const_iterator
{
public:
//iterator( )
//

{ }

Force use of the safe constructor

Object & operator* ( )
{ return retrieve( ); }
const Object & operator* ( ) const
{ return const_iterator::operator*( ); }
iterator & operator++ ( )
{
cout<<"old "<<*current<<" ";
current++;
cout<<" new "<<*current<<" ";
return *this;
}

Solutions
iterator operator++ ( int )
{
iterator old = *this;
++( *this );
return old;
}
protected:
iterator(const Vector & vect, Object *p )
: const_iterator(vect, p )
{ }
friend class Vector;
};

(c)

iterator begin( )
{ return iterator(*this ,&objects[ 0 ]); }
const_iterator begin( ) const
{ return const_iterator(*this,&objects[ 0 ]); }
iterator end( )
{ return iterator(*this, &objects[ size( ) ]); }
const_iterator end( ) const
{ return const_iterator(*this, &objects[ size( ) ]); }

3.11

template 
struct Node
{
Object data;
Node * next;
Node ( const Object & d = Object(), Node *n = NULL )
: data(d) , next(n) {}
};
template 
class singleList
{
public:
singleList( ) { init(); }
~singleList()
{
eraseList(head);
}
singleList( const singleList & rhs)
{
eraseList(head);
init();
*this = rhs;
}

15

16

Chapter 3

Lists, Stacks, and Queues

bool add(Object x)
{
if (contains(x))
return false;
else
{
Node *ptr = new Node(x);
ptr->next = head->next;
head->next = ptr;
theSize++;
}
return true;
}

bool remove(Object x)
{
if (!contains(x))
return false;
else
{
Node*ptr = head->next;
Node*trailer;
while(ptr->data != x)
{ trailer = ptr;
ptr=ptr->next;
}
trailer->next = ptr->next;
delete ptr;
theSize--;
}
return true;
}

int size() { return theSize;}

void print()
{
Node *ptr = head->next;
while (ptr != NULL)
{
cout<< ptr->data<<" ";
ptr = ptr->next;
}
cout< * ptr = head->next;
while (ptr != NULL)
{
if (x == ptr->data)
return true;
else
ptr = ptr-> next;
}
return false;
}
void init()
{
theSize = 0;
head = new Node;
head-> next = NULL;
}
void eraseList(Node * h)
{
Node *ptr= h;
Node *nextPtr;
while(ptr != NULL)
{
nextPtr = ptr->next;
delete ptr;
ptr= nextPtr;
}
};
private:
Node *head;
int theSize;
};

3.12

template 
struct Node
{
Object data;
Node * next;
Node ( const Object & d = Object(), Node *n = NULL )
: data(d) , next(n) {}
};

17

18

Chapter 3

Lists, Stacks, and Queues

template 
class singleList
{
public:
singleList( ) { init(); }
~singleList()
{
eraseList(head);
}
singleList( const singleList & rhs)
{
eraseList(head);
init();
*this = rhs;
}
bool add(Object x)
{
if (contains(x))
return false;
else
{
Node *ptr = head->next;
Node* trailer = head;
while(ptr && ptr->data < x)
{
trailer = ptr;
ptr = ptr->next;
}
trailer->next = new Node (x);
trailer->next->next = ptr;
theSize++;
}
return true;
}
bool remove(Object x)
{
if (!contains(x))
return false;
else
{
Node*ptr = head->next;
Node*trailer;
while(ptr->data != x)
{ trailer = ptr;

Solutions
ptr=ptr->next;
}
trailer->next = ptr->next;
delete ptr;
theSize--;
}
return true;
}
int size() { return theSize;}
void print()
{
Node *ptr = head->next;
while (ptr != NULL)
{
cout<< ptr->data<<" ";
ptr = ptr->next;
}
cout< * ptr = head->next;
while (ptr != NULL && ptr->data <= x )
{
if (x == ptr->data)
return true;
else
ptr = ptr-> next;
}
return false;
}
void init()
{
theSize = 0;
head = new Node;
head-> next = NULL;
}
void eraseList(Node * h)
{
Node *ptr= h;
Node *nextPtr;
while(ptr != NULL)

19

20

Chapter 3

Lists, Stacks, and Queues
{
nextPtr = ptr->next;
delete ptr;
ptr= nextPtr;
}

};
private:
Node *head;
int theSize;
};

3.13

Add the following code to the const_iterator class. Add the same code with iterator replacing
const_iterator to the iterator class.
const_iterator & operator-- ( )
{
current = current->prev;
return *this;
}
const_iterator operator-- ( int )
{
const_iterator old = *this;
--( *this );
return old;
}

3.14

const_iterator & operator+ ( int k )
{
const_iterator advanced = *this;
for (int i = 0; i < k ; i++)
advanced.current = advanced.current->next;
return advanced;
}

3.15

void splice (iterator itr, List & lst)
{
itr.assertIsValid();
if (itr.theList != this)
throw IteratorMismatchException ();
Node *p = iter.current;
theSize += lst.size();
p->prev->next = lst.head->next;
lst.head->next->prev = p->prev;
lst.tail->prev->next = p;
p->prev = lst->tail->prev;
lst.init();
}

Solutions

3.16

The class const_reverse_iterator is almost identical to const_iterator while reverse_iterator is
almost identical to iterator. Redefine ++ to be − and vice versa for both the pre and post operators
for both classes as well as changing all variables of type const_iterator to const_reverse_iterator
and changing iterator to reverse_iterator. Add two new members in list for rbegin() and rend().
// In List add
const_reverse_iterator rbegin() const
{
return const_reverse_iterator itr( tail);
}
const_reverse_iterator rend() const
{
const_reverse_iterator itr(head);
}
reverse_iterator rbegin()
{
return reverse_iterator itr( tail);
}
reverse_iterator rend()
{
reverse_iterator itr(head);
}

3.18

Add a boolean data member to the node class that is true if the node is active; and false if it is “stale.”
The erase method changes this data member to false; iterator methods verify that the node is not
stale.

3.19

Without head or tail nodes the operations of inserting and deleting from the end becomes a O(N )
operation where the N is the number of elements in the list. The algorithm must walk down the
list before inserting at the end. With the head node insert needs a special case to account for when
something is inserted before the first node.

3.20

(a) The advantages are that it is simpler to code, and there is a possible saving if deleted keys are
subsequently reinserted (in the same place). The disadvantage is that it uses more space, because
each cell needs an extra bit (which is typically a byte), and unused cells are not freed.

3.22

The following function evaluates a postfix expression, using +, −, ∗, / and ^ ending in =. It requires
spaces between all operators and = and uses the stack, string and math.h libraries. It only recognizes
0 in input as 0.0.
double evalPostFix( )
{
stack s;
string token;
double a, b, result;
cin>> token;
while (token[0] != ’=’)
{
result = atof (token.c_str());
if (result != 0.0 )
s.push(result);

21

22

Chapter 3

Lists, Stacks, and Queues
else if (token == "0.0")
s.push(result);
else
switch (token[0])
{
case ’+’ : a = s.top(); s.pop(); b = s.top();
s.pop(); s.push(a+b); break;
case ’-’ : a = s.top(); s.pop(); b = s.top();
s.pop(); s.push(a-b); break;
case ’*’ : a = s.top(); s.pop(); b = s.top();
s.pop(); s.push(a*b); break;
case ’/’ : a = s.top(); s.pop(); b = s.top();
s.pop(); s.push(a/b); break;
case ’^’ : a = s.top(); s.pop(); b = s.top();
s.pop(); s.push(exp(a*log(b))); break;
}
cin>> token;

}
return s.top();
}

3.23

(a, b) This function will read in from standard input an infix expression of single lower case
characters and the operators, +, −, / , ∗, ^ and (, ), and output a postfix expression.
void inToPostfix()
{
stack s;
char token;
cin>> token;
while (token != ’=’)
{
if (token >= ’a’ && token <= ’z’)
cout<> token;
}
while (!s.empty())
{cout<

s;

string token;
string a, b;
cin>>token;
while (token[0] != ’=’)
{
if (token[0] >= ’a’ && token[0] <= ’z’)
s.push(token);
else
switch (token[0])
{
case ’+’ : a = s.top(); s.pop(); b = s.top(); s.pop();
s.push("("+ a+" + " + b+")"); break;
case ’-’ : a = s.top(); s.pop(); b = s.top(); s.pop();
s.push("("+a+" - "+ b+")"); break;
case ’*’ : a = s.top(); s.pop(); b = s.top(); s.pop();
s.push("("+a+" * "+ b+")"); break;
case ’/’ : a = s.top(); s.pop(); b = s.top(); s.pop();
s.push("("+a+" / " + b+")"); break;
case ’^’ : a = s.top(); s.pop(); b = s.top(); s.pop();
s.push("("+a+" ^ " + b+")"); break;
}
cin>> token;
}
return s.top();
}

//Converts postfix to infix

3.24

Two stacks can be implemented in an y array by having one grow from the low end of the array up,
and the other from the high end down.

3.25

(a) Let E be our extended stack. We will implement E with two stacks. One stack, which we’ll call
S, is used to keep track of the push and pop operations, and the other M, keeps track of the minimum.
To implement E.push (x), we perform S.push (x). If x is smaller than or equal to the top element in
stack M, then we also perform M.push (x). To implement E.pop( ) we perform S.pop( ). If x is equal
to the top element in stack M, then we also M.pop( ). E.findMin( ) is performed by examining the
top of M. All these operations are clearly O (1).

23

24

Chapter 3

Lists, Stacks, and Queues

(b) This result follows from a theorem in Chapter 7 that shows that sorting must take (N log N )
time. O (N ) operations in the repertoire, including deleteMin, would be sufficient to sort.

3.26

Three stacks can be implemented by having one grow from the bottom up, another from the top
down and a third somewhere in the middle growing in some (arbitrary) direction. If the third stack
collides with either of the other two, it needs to be moved. A reasonable strategy is to move it so that
its center (at the time of the move) is halfway between the tops of the other two stacks.

3.27

Stack space will not run out because only 49 calls will be stacked. However the running time is
exponential, as shown in Chapter 2, and thus the routine will not terminate in a reasonable amount
of time.

3.28

This requires a doubly linked list with pointers to the head and the tail In fact it can be implemented
with a list by just renaming the list operations.
template 
class deque
{
public:
deque() { l();}
void push (Object obj) {l.push_front(obj);}
Object pop (); {Object obj=l.front(); l.pop_front(); return obj;}
void inject(Object obj); {l.push_back(obj);}
Object eject(); {pop_back(obj);}
private:
list l;
};

3.29

//

Reversal of a singly linked list can be done recursively using a stack, but this requires O (N ) extra
space. The following solution is similar to strategies employed in garbage collection algorithms (first
represents the first node in the non-empty node in the non-empty list). At the top of the while loop
the list from the start to previousPos is already reversed, whereas the rest of the list, from currentPos
to the end is normal. This algorithm uses only constant extra space.
//Assuming no header and that first is not NULL
Node * reverseList(Node *first)
{
Node * currentPos, *nextPos, *previousPos;
previousPos = NULL;
currentPos

= first;

nextPos

= first->next;

while (nextPos != NULL)
{
currentPos -> next = previousPos;
perviousPos = currentPos;
currentPos = nextPos;
nextPos = nextPos -> next;
}
currentPos->next = previousPos;
return currentPos;
}

Solutions

3.30

3.31

(c) This follows well-known statistical theorems. See Sleator and Tarjan’s paper in Chapter 11 for
references.
template 
struct node
{
node () { next = NULL;}
node (Object obj) : data(obj) {}
node (Object obj, node * ptr) : data(obj), next(ptr) {}
Object data;
node * next;
};
template 
class stack
{
public:
stack () { head = NULL;}
~stack() { while (head) pop(); }
void push(Object obj)
{
node * ptr = new node(obj, head);
head= ptr;
}
Object top()
{return (head->data); }
void pop()
{
node * ptr = head->next;
delete head;
head = ptr;
}
private:
node * head;
};

3.32

template 
class queue
{
public:
queue () { front = NULL; rear = NULL;}
~queue() { while (front) deque(); }
void enque(Object obj)
{
node * ptr = new node(obj, NULL);
if (rear)
rear= rear->next = ptr;
else
front = rear =
}

ptr;

25

26

Chapter 3

Lists, Stacks, and Queues
Object deque()
{
Object temp = front->data;
node * ptr = front;
if (front->next == NULL) // only 1 node
front = rear = NULL;
else
front = front->next;
delete ptr;
return temp;
}

private:
node * front;
node * rear;
};

3.33

//

This implementation holds maxSize −1 elements.
template 
class queue
{
public:
queue(int s): maxSize(s), front(0), rear(0) {elements.resize(maxSize);}
queue () { maxSize = 100; front = 0;
rear = 0;elements.resize(maxSize);}
~queue() { while (front!=rear) deque(); }
void enque(Object obj)
{
if (! full())
{
elements[rear] = obj;
rear = (rear + 1) % maxSize;
}
}
Object deque()
{ Object temp;
if (!empty())
{
temp= elements[front];
front = (front +1 ) % maxSize;
return temp;
}
}
bool empty() {return front == rear;}
bool full() { return (rear + 1) % maxSize == front;}

Solutions
private:
int front, rear;
int maxSize;
vector elements ;
};

//

3.34

(b) Use two iterators p and q, both initially at the start of the list. Advance p one step at a time,
and q two steps at a time. If q reaches the end there is no cycle; otherwise, p and q will eventually
catch up to each other in the middle of the cycle.

3.35

(a) Does not work in constant time for insertions at the end
(b) Because of the circularity, we can access the front item in constant time, so this works.

3.36

Copy the value of the item in the next node (that is, the node that follows the referenced node) into
the current node (that is, the node being referenced). Then do a deletion of the next node.

3.37

(a) Add a copy of the node in position p after position p; then change the value stored in position
p to x.
(b) Set p->data = p->next->data and set p->next = p->next->next. Then delete p->next. Note that the
tail node guarantees that there is always a next node.

27

C H A P T E R

4

Trees
4.1

(a) A.
(b) G, H , I , L, M, and K.

4.2

For node B:
(a) A.
(b) D and E.
(c) C.
(d) 1.
(e) 3.

4.3

4.

4.4

There are N nodes. Each node has two links, so there are 2N links. Each node but the root has one
incoming link from its parent, which accounts for N − 1 links. The rest are NULL.

4.5

Proof is by induction. The theorem is trivially true for h = 0. Assume true for h = 1, 2, . . . , k. A tree
of height k + 1 can have two subtrees of height at most k. These can have at most 2k+1 − 1 nodes
each by the induction hypothesis. These 2k+2 − 2 nodes plus the root prove the theorem for height
k + 1 and hence for all heights.

4.6

This can be shown by induction. Alternatively, let N = number of nodes, F = number of full nodes, L
= number of leaves, and H = number of half nodes (nodes with one child). Clearly, N = F + H + L.
Further, 2F + H = N − 1 (see Exercise 4.4). Subtracting yields L − F = 1.

4.7

This can be shown by induction. In a tree with no nodes, the sum is zero, and in a one-node tree,
the root is a leaf at depth zero, so the claim is true. Suppose the theorem is true for all trees with at
most k nodes. Consider any tree with k + 1 nodes. Such a tree consists of an i node left subtree and
a k − i node right subtree. By the inductive hypothesis, the sum for the left subtree leaves is at most
one with respect to the left tree root. Because all leaves are one deeper with respect to the original
tree than with respect to the subtree, the sum is at most 1/2 with respect to the root. Similar logic
implies that the sum for leaves in the right subtree is at most 1/2, proving the theorem. The equality
is true if and only if there are no nodes with one child. If there is a node with one child, the equality
cannot be true because adding the second child would increase the sum to higher than 1. If no nodes
have one child, then we can find and remove two sibling leaves, creating a new tree. It is easy to see
that this new tree has the same sum as the old. Applying this step repeatedly, we arrive at a single
node, whose sum is 1. Thus the original tree had sum 1.

4.8

(a) - * * a b + c d e.
(b) ( ( a * b ) * ( c + d ) ) - e.
(c) a b * c d + * e -.

29

30

Chapter 4

Trees

4.9

4.10

(a) Both values are 0.
(b) The root contributes (N − 2)/N full nodes on average, because the root is full as long as it does
not contain the largest or smallest item. The remainder of the equation is the expected contribution
of the subtrees.
(d) The average number of leaves is (N + 1)/3.

4.11

The Set class is the BinarySearchTree class with the two classes const_iterator and iterator imbedded
into it as well as a new data member (int Size; ). In the first two code examples are classes for both
iterators with ++ implemented. The third code example shows the new insert and begin member
functions, while the fourth example shows the modified BinaryNode struct. For a fully operational
Set, −− would be implemented along with the functions contains and erase.
(a)

class const_iterator
{
public:
const_iterator( ) : current( NULL )
{ }
const Comparable & operator* ( ) const
{ return retrieve( ); }
const_iterator & operator++ ( )
{
BinaryNode *t ;
if (current->right)
{
t= current->right;
while (t->left != NULL)
t = t-> left;
current = t;
}
else
{
t = current->parent;
cout<<"first parent is " <element< element < current-> element)
t = t->parent;
current = t;
}
return *this;
}

Solutions
const_iterator operator++ ( int )
{
const_iterator old = *this;
++( *this );
return old;
}

bool operator== ( const const_iterator & rhs ) const
{ return current == rhs.current; }
bool operator!= ( const const_iterator & rhs ) const
{ return !( *this == rhs ); }

protected:
BinaryNode  *current;

Comparable & retrieve( ) const
{ return current->element; }

const_iterator( BinaryNode *p ) : current( p )
{ }

friend class Set;
};

(b) class iterator : public const_iterator
{
public:
iterator( )
{ }

Comparable & operator* ( )
{ return const_iterator ::retrieve( ); }
const Comparable & operator* ( ) const
{ return const_iterator ::operator*( ); }

iterator & operator++ ( )
{
BinaryNode *t ;
if (current->right)
{
t= current->right;
while (t->left != NULL)
t = t-> left;
current = t;
}

31

32

Chapter 4

Trees
else
{
t = current->parent;
cout<<"first parent is " <element< element < current-> element)
t = t->parent;
current = t;
}
return *this;
}
iterator operator++ ( int )
{
const_iterator old = *this;
++( *this );
return old;
}
iterator( BinaryNode *p ) : const_iterator( p )
{ }
friend class Set;
};

(c)

//This is the public insert
iterator insert( const Comparable & x) { Size++;
return insert (x, root, root);}

// This is private
iterator insert( const Comparable & x,
BinaryNode * & t,
BinaryNode *

p ) //parent node

{
if( t == NULL )
{
t = new BinaryNode( x, NULL, NULL, p );
return iterator (t);
}
else if( x < t->element )
return (insert( x, t->left, t ));
else if( t->element < x )
return(insert( x, t->right, t ));
return iterator (t) ;
}
// This is the public begin (aka minimum element)
iterator

begin()

Solutions
{
BinaryNode *t = root;
while (t->left)
t = t->left;
return iterator (t);
}

(d) template
struct BinaryNode
{
Comparable element;
BinaryNode *left;
BinaryNode *right;
BinaryNode *parent;
BinaryNode() { left = NULL, right = NULL; parent = NULL;}
BinaryNode( const Comparable & theElement) { element = theElement; left = NULL;
right = NULL; parent = NULL;}
BinaryNode( const Comparable & theElement, BinaryNode *lt, BinaryNode *rt ,
BinaryNode *pt)
: element( theElement ), left( lt ), right( rt ), parent(pt) { }
};

4.14

(a) Keep a bit array B. If i is in the tree, then B[i] is true; otherwise, it is false. Repeatedly generate
random integers until an unused one is found. If there are N elements already in the tree, then M − N
are not, and the probability of finding one of these is (M − N )/M. Thus the expected number of
trials is M/(M − N ) = α/(α − 1).
(b) To find an element that is in the tree, repeatedly generate random integers until an alreadyused integer is found. The probability of finding one is N/M, so the expected number of trials is
M/N = α.
(c) The total cost for one insert and one delete is alpha/(α − 1) + α = 1 + α + 1/(α − 1). Setting
alpha = 2 minimizes this cost.

4.18

(a) N (0) = 1, N (1) = 2, N (h) = N (h − 1) + N (h − 2) + 1.
(b) The heights are one less than the Fibonacci numbers.

4.19

4.20

It is easy to verify by hand that the claim is true for 1 ≤ k ≤ 3. Suppose it is true for k = 1, 2, 3, . . . h.
Then after the first 2h − 1 insertions, 2h−1 is at the root, and the right subtree is a balanced
tree containing 2h−1 + 1 through 2h − 1. Each of the next 2h−1 insertions, namely, 2h through
2h + 2h−1 − 1, insert a new maximum and get placed in the right subtree, eventually forming a
perfectly balanced right subtree of height h − 1. This follows by the induction hypothesis because

33

34

Chapter 4

Trees

the right subtree may be viewed as being formed from the successive insertion of 2h−1 + 1 through
2h + 2h−1 − 1. The next insertion forces an imbalance at the root, and thus a single rotation. It is
easy to check that this brings 2h to the root and creates a perfectly balanced left subtree of height
h − 1. The new key is attached to a perfectly balanced right subtree of height h − 2 as the last node
in the right path. Thus the right subtree is exactly as if the nodes 2h + 1 through 2h + 2h−1 were
inserted in order. By the inductive hypothesis, the subsequent successive insertion of 2h + 2h−1 + 1
through 2h+1 − 1 will create a perfectly balanced right subtree of height h − 1. Thus after the last
insertion, both the left and the right subtrees are perfectly balanced, and of the same height, so the
entire tree of 2h+1 − 1 nodes is perfectly balanced (and has height h).

4.21

The two remaining functions are mirror images of the text procedures. Just switch right and left
everywhere.

4.24

After applying the standard binary search tree deletion algorithm, nodes on the deletion path need
to have their balance changed, and rotations may need to be performed. Unlike insertion, more than
one node may need rotation.

4.25

(a) O(log log N ).
(b) The minimum AVL tree of height 127 (8-byte ints go from -128 to 127). This is a huge tree.

4.26

AvlNode *doubleRotateWithLeft( AvlNode *k3 )
{
AvlNode *k1, *k2;
k1 = k3->left;
k2 = k1->right;
k1->right = k2->left;
k3->left

= k2->right;

k2->left

= k1;

k2->right = k3;
k1->height = max( height(k1->left), height(k1->right) ) + 1;
k3->height = max( height(k3->left), height(k3->right) ) + 1;
k2->height = max( k1->height, k3->height ) + 1;
return k3;
}

4.27

After accessing 3,

Solutions

After accessing 9,

After accessing 1,

After accessing 5,

4.28

35

36

Chapter 4

4.29

(a) An easy proof by induction.

4.31

(a–c) All these routines take linear time.

Trees

// These functions use the type Node, which is the same as BinaryNode.
int countNodes( Node *t )
{
if( t == NULL )
return 0;
return 1 + countNodes( t->left ) + countNodes( t->right );
}
int countLeaves( Node *t )
{
if( t == NULL )
return 0;
else if( t->left == NULL && t->right == NULL )
return 1;
return countLeaves( t->left ) + countLeaves( t->right );
}
// An alternative method is to use the results of Exercise 4.6.
int countFull( Node *t )
{
if( t == NULL )
return 0;
int tIsFull = ( t->left != NULL && t->right != NULL ) ? 1 : 0;
return tIsFull + countFull( t->left ) + countFull( t->right );
}

4.32

4.33

Have the recursive routine return a triple that consists of a Boolean (whether the tree is a BST), and
the minimum and maximum items. Then a tree is a BST if it is empty or both subtrees are (recursively)
BSTs, and the value in the node lies between the maximum of the left subtree and the minimum of
the right subtrees. Coding details are omitted.
void removeLeaves( Node * & t )
{
if( t == NULL || ( t->left == NULL && t->right == NULL ) )
{
t = NULL;
return;
}
removeLeaves( t->left );
removeLeaves( t->right );
}

Solutions

4.34

We assume the existence of a method randInt(lower,upper), that generates a uniform random integer
in the appropriate closed interval.
Node *makeRandomTree( int lower, int upper )
{
Node *t = NULL;
int randomValue;
if( lower <= upper )
t = new Node( randomValue = randInt( lower, upper ),
makeRandomTree( lower, randomValue - 1 ),
makeRandomTree( randomValue + 1, upper ) );
return t;
}
Node *makeRandomTree( int n )
{
return makeRandomTree( 1, n );
}

4.35

// LastNode contains last value that was assigned to a node.
Node *genTree( int height, int & lastNode )
{
Node *t = NULL;
if( height >= 0 )
{
t = new Node;
t->left = genTree( height - 1, lastNode );
t->element = ++lastNode;
t->right = genTree( height - 2, lastNode );
}
return t;
}
Node *minAvlTree( int h )
{
int lastNodeAssigned = 0;
return genTree( h, lastNodeAssigned );
}

4.36

There are two obvious ways of solving this problem. One way mimics Exercise 4.34 by replacing
randInt(lower,upper) with (lower+upper) / 2. This requires computing 2h+1 − 1, which is not that
difficult. The other mimics the previous exercise by noting that the heights of the subtrees are both
h − 1.

4.37

This is known as one-dimensional range searching. The time is O(K) to perform the inorder traversal,
if a significant number of nodes are found, and also proportional to the depth of the tree, if we get

37

38

Chapter 4

Trees

to some leaves (for instance, if no nodes are found). Since the average depth is O(log N ), this gives
an O(K + log N ) average bound.
void printRange( const Comparable & lower,
const Comparable & upper, BinaryNode *t )
{
if( t != NULL )
{
if( lower <= t->element )
printRange( lower, upper, t->left );
if( lower <= t->element && t->element <= upper )
cout << t->element << endl;
if( t->element <= upper )
printRange( lower, upper, t->right );
}
}

4.38

This exercise and Exercise 4.39 are likely programming assignments, so we do not provide code here.

4.40

Put the root on an empty queue. Then repeatedly dequeue a node and enqueue its left and right
children (if any) until the queue is empty. This is O(N ) because each queue operation is constant
time and there are N enqueue and N dequeue operations.

4.43

4.45

The function shown here is clearly a linear time routine because in the worst case it does a traversal
on both t1 and t2.
bool similar( Node *t1, Node *t2 )
{
if( t1 == NULL || t2 == NULL )
return t1 == NULL && t2 == NULL;
return similar( t1->left, t2->left ) && similar( t1->right, t2->right );
}

4.47

The easiest solution is to compute, in linear time, the inorder numbers of the nodes in both trees. If
the inorder number of the root of T2 is x, then find x in T1 and rotate it to the root. Recursively apply
this strategy to the left and right subtrees of T1 (by looking at the values in the root of T2’s left and right
subtrees). If dN is the depth of x, then the running time satisfies T (N ) = T (i) + T (N − i − 1) + dN ,
where i is the size of the left subtree. In the worst case, dN is always O(N ), and i is always 0, so the
worst-case running time is quadratic. Under the plausible assumption that all values of i are equally
likely, then even if dN is always O(N ), the average value of T (N ) is O(N log N ). This is a common

Solutions

recurrence that was already formulated in the chapter and is solved in Chapter 7. Under the more
reasonable assumption that dN is typically logarithmic, then the running time is O(N ).

4.48

Add a data member to each node indicating the size of the tree it roots. This allows computation of
its inorder traversal number.

4.49

(a) You need an extra bit for each thread.
(c) You can do tree traversals somewhat easier and without recursion. The disadvantage is that it
reeks of old-style hacking.

39

C H A P T E R

5

Hashing

5.1

(a) On the assumption that we add collisions to the end of the list (which is the easier way if a hash
table is being built by hand), the separate chaining hash table that results is shown here.

(b)

41

42

Chapter 5

Hashing

(c)

(d) 1989 cannot be inserted into the table because hash2(1989) = 6, and the alternative locations
5, 1, 7, and 3 are already taken. The table at this point is as follows:

5.2

When rehashing, we choose a table size that is roughly twice as large and prime. In our case, the
appropriate new table size is 19, with hash function h(x) = x (mod 19).
(a) Scanning down the separate chaining hash table, the new locations are 4371 in list 1, 1323 in
list 12, 6173 in list 17, 4344 in list 12, 4199 in list 0, 9679 in list 8, and 1989 in list 13.
(b) The new locations are 9679 in bucket 8, 4371 in bucket 1, 1989 in bucket 13, 1323 in bucket
12, 6173 in bucket 17, 4344 in bucket 14 because both 12 and 13 are already occupied, and 4199
in bucket 0.
(c) The new locations are 9679 in bucket 8, 4371 in bucket 1, 1989 in bucket 13, 1323 in bucket
12, 6173 in bucket 17, 4344 in bucket 16 because both 12 and 13 are already occupied, and 4199
in bucket 0.
(d) The new locations are 9679 in bucket 8, 4371 in bucket 1, 1989 in bucket 13, 1323 in bucket
12, 6173 in bucket 17, 4344 in bucket 15 because 12 is already occupied, and 4199 in bucket 0.

5.4

We must be careful not to rehash too often. Let p be the threshold (fraction of table size) at which we
rehash to a smaller table. Then if the new table has size N , it contains 2pN elements. This table will
require rehashing after either 2N − 2pN insertions or pN deletions. Balancing these costs suggests
that a good choice is p = 2/3. For instance, suppose we have a table of size 300. If we rehash at 200
elements, then the new table size is N = 150, and we can do either 100 insertions or 100 deletions
until a new rehash is required.

Solutions

If we know that insertions are more frequent than deletions, then we might choose p to be
somewhat larger. If p is too close to 1.0, however, then a sequence of a small number of deletions
followed by insertions can cause frequent rehashing. In the worst case, if p = 1.0, then alternating
deletions and insertions both require rehashing.

5.5

No; this does not take deletions into account.

5.6

(b) If the number of deleted cells is small, then we spend extra time looking for inactive cells that
are not likely to be found. If the number of deleted cells is large, then we may get improvement.

5.7

In a good library implementation, the length method should be inlined.

5.8

Separate chaining hashing requires the use of links, which costs some memory, and the standard
method of implementing calls on memory allocation routines, which typically are expensive. Linear
probing is easily implemented, but performance degrades severely as the load factor increases because
of primary clustering. Quadratic probing is only slightly more difficult to implement and gives
good performance in practice. An insertion can fail if the table is half empty, but this is not likely.
Even if it were, such an insertion would be so expensive that it wouldn’t matter and would almost
certainly point up a weakness in the hash function. Double hashing eliminates primary and secondary
clustering, but the computation of a second hash function can be costly. Gonnet and Baeza-Yates [8]
compare several hashing strategies; their results suggest that quadratic probing is the fastest method.

5.9

In the case of a collision this method uses a pseudorandom number to make jumps away from the
home bucket. However the length of the jump the same for each home bucket. This would avoid
secondary clustering near the home bucket. It is a special case of double hashing in that the jumps
away from the home bucket are fixed as contrasted by double hashing where the jumps grow at
each jump.

5.10

The old values would remain valid if the hashed values were less than the old table size.

5.11

Sorting the MN records and eliminating duplicates would require O(MN log MN ) time using a
standard sorting algorithm. If terms are merged by using a hash function, then the merging time is
constant per term for a total of O(MN ). If the output polynomial is small and has only O(M + N )
terms, then it is easy to sort it in O((M + N ) log(M + N )) time, which is less than O(MN ). Thus
the total is O(MN ). This bound is better because the model is less restrictive: Hashing is performing
operations on the keys rather than just comparison between the keys. A similar bound can be obtained
by using bucket sort instead of a standard sorting algorithm. Operations such as hashing are much
more expensive than comparisons in practice, so this bound might not be an improvement. On
the other hand, if the output polynomial is expected to have only O(M + N ) terms, then using a
hash table saves a huge amount of space, since under these conditions, the hash table needs only
O(M + N ) space.
Another method of implementing these operations is to use a search tree instead of a hash table;
a balanced tree is required because elements are inserted in the tree with too much order. A splay
tree might be particularly well suited for this type of a problem because it does well with sequential
accesses. Comparing the different ways of solving the problem is a good programming assignment.

5.12

To each hash table slot, we can add an extra data member that we’ll call whereOnStack, and we can
keep an extra stack. When an insertion is first performed into a slot, we push the address (or number)
of the slot onto the stack and set the whereOnStack data member to refer to the top of the stack. When
we access a hash table slot, we check that whereOnStack refers to a valid part of the stack and that
the entry in the (middle of the) stack that is referred to by the whereOnStack data member has that
hash table slot as an address.

43

44

Chapter 5

5.16

(a) The cost of an unsuccessful search equals the cost of an insertion.
(b)


1 λ
1
I (λ) =
− x − ln(1 − x) dx = 1 − ln(1 − λ) − λ/2
λ 0 1− x

5.17

Hashing

template 
class Pair
{
public:
Pair(HashedObj k, Object d): key(k), def(d){}
private:
HashedObj key;
Object

def;

// Appropriate Constructors, etc.
};
template 
class Dictionary
{
public:
Dictionary( )
{}
void insert( const HashedObj & key, const Object & definition )
{items.insert(Pair(key, definition));}
const Object & lookup( const HashedObj & key ) const
{ return items.contains(key);}
bool isEmpty( ) const
{return items.isEmpty(); }
void makeEmpty( )
{ items.makeEmpty();}
private:
HashTable > items;
};

5.19

C H A P T E R

6

Priority Queues
(Heaps)
6.1

Yes. When an element is inserted, we compare it to the current minimum and change the minimum
if the new element is smaller. deleteMin operations are expensive in this scheme.

6.2

6.3

The result of three deleteMins, starting with both of the heaps in Exercise 6.2, is as follows:

6.4

(a) 4N
(b) O(N 2)
(c) O(N 4.1)
(d) O(2N )

6.5

/**
* Insert item x, allowing duplicates.
*/
void insert( const Comparable & x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );

45

46

Chapter 6

Priority Queues (Heaps)
// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[0] = array[ hole ] = x;
}

6.6

225. To see this, start with i = 1 and position at the root. Follow the path toward the last node,
doubling i when taking a left child, and doubling i and adding one when taking a right child.

6.7

(a) We show that H (N), which is the sum of the heights of nodes in a complete binary tree of N
nodes, is N − b(N), where b(N ) is the number of ones in the binary representation of N . Observe
that for N = 0 and N = 1, the claim is true. Assume that it is true for values of k up to and including
N − 1. Suppose the left and right subtrees have L and R nodes, respectively. Since the root has
height log N , we have
H (N ) = log N  + H (L) + H (R)
= log N  + L − b(L) + R − b(R)
= N − 1 + (log N  − b(L) − b(R))
The second line follows from the inductive hypothesis, and the third follows because L + R = N − 1.
Now the last node in the tree is in either the left subtree or the right subtree. If it is in the left subtree,
then the right subtree is a perfect tree, and b(R) = log N  − 1. Further, the binary representation
of N and L are identical, with the exception that the leading 10 in N becomes 1 in L. (For instance,
if N = 37 = 100101, L = 10101.) It is clear that the second digit of N must be zero if the last node
is in the left subtree. Thus in this case, b(L) = b(N ), and
H (N ) = N − b(N )
If the last node is in the right subtree, then b(L) = log N . The binary representation of R is
identical to N , except that the leading 1 is not present. (For instance, if N = 27 = 101011, L =
01011.) Thus b(R) = b(N) − 1, and again
H (N ) = N − b(N )
(b) Run a single-elimination tournament among eight elements. This requires seven comparisons
and generates ordering information indicated by the binomial tree shown here.

The eighth comparison is between b and c. If c is less than b, then b is made a child of c.
Otherwise, both c and d are made children of b.
(c) A recursive strategy is used. Assume that N = 2k . A binomial tree is built for the N elements as
in part (b). The largest subtree of the root is then recursively converted into a binary heap of 2k−1
elements. The last element in the heap (which is the only one on an extra level) is then inserted into
the binomial queue consisting of the remaining binomial trees, thus forming another binomial tree
of 2k−1 elements. At that point, the root has a subtree that is a heap of 2k−1 − 1 elements and another

Solutions

subtree that is a binomial tree of 2k−1 elements. Recursively convert that subtree into a heap; now the
whole structure is a binary heap. The running time for N = 2k satisfies T (N ) = 2T (N/2) + log N .
The base case is T (8) = 8.

6.9

Let D1, D2 , . . . , Dk be random variables representing the depth of the smallest, second smallest,
and k th smallest elements, respectively. We are interested in calculating E(Dk ). In what follows,
we assume that the heap size N is one less than a power of two (that is, the bottom level is
completely filled) but sufficiently large so that terms bounded by O(1/N ) are negligible. Without
loss of generality, we may assume that the k th smallest element is in the left subheap of the root. Let
pj , k be the probability that this element is the j th smallest element in the subheap.
Lemma.

For k > 1, E(Dk ) =

k−1

j =1

pj , k (E(Dj ) + 1).

Proof.

An element that is at depth d in the left subheap is at depth d + 1 in the entire subheap. Since
E(Dj + 1) = E(Dj ) + 1, the theorem follows.
Since by assumption, the bottom level of the heap is full, each of second, third, . . . , k − 1th
smallest elements are in the left subheap with probability of 0.5. (Technically, the probability should
be half − 1/(N − 1) of being in the right subheap and half + 1/(N − 1) of being in the left, since
we have already placed the k th smallest in the right. Recall that we have assumed that terms of size
O(1/N ) can be ignored.) Thus
pj , k = pk−j , k =

1
2k−2

k−2
j −1

Theorem.

E(Dk ) ≤ log k.
Proof.

The proof is by induction. The theorem clearly holds for k = 1 and k = 2. We then show that it
holds for arbitrary k > 2 on the assumption that it holds for all smaller k. Now, by the inductive
hypothesis, for any 1 ≤ j ≤ k − 1,
E(Dj ) + E(Dk−j ) ≤ log j + log k − j
Since f (x) = log x is convex for x > 0,
log j + log k − j ≤ 2 log(k/2)
Thus
E(Dj ) + E(Dk−j ) ≤ log(k/2) + log(k/2)
Furthermore, since pj , k = pk−j , k ,
pj , k E(Dj ) + pk−j , k E(Dk−j ) ≤ pj , k log(k/2) + pk−j , k log(k/2)
From the lemma,
E(Dk ) =

k−1


pj , k (E(Dj ) + 1)

j =1

= 1+

k−1

j =1

pj , k E(Dj )

47

48

Chapter 6

Priority Queues (Heaps)

Thus
E(Dk ) ≤ 1 +

k−1


pj , k log(k/2)

j =1

≤ 1 + log(k/2)

k−1


pj , k

j =1

≤ 1 + log(k/2)
≤ log k
completing the proof.
It can also be shown that asymptotically, E(Dk ) ≈ log(k − 1) − 0.273548.

6.10

(a) Perform a preorder traversal of the heap.
(b) Works for leftist and skew heaps. The running time is O(Kd) for d-heaps.

6.12

Simulations show that the linear time algorithm is the faster, not only on worst-case inputs, but also
on random data.

6.13

(a) If the heap is organized as a (min) heap, then starting at the hole at the root, find a path down to a
leaf by taking the minimum child. The requires roughly log N comparisons. To find the correct place
where to move the hole, perform a binary search on the log N elements. This takes O(log log N )
comparisons.
(b) Find a path of minimum children, stopping after log N − log log N levels. At this point, it is
easy to determine if the hole should be placed above or below the stopping point. If it goes below,
then continue finding the path, but perform the binary search on only the last log log N elements on
the path, for a total of log N + log log log N comparisons. Otherwise, perform a binary search on
the first log N − log log N elements. The binary search takes at most log log N comparisons, and
the path finding took only log N − log log N , so the total in this case is log N . So the worst case is
the first case.
(c) The bound can be improved to log N + log ∗N + O(1), where log ∗N is the inverse Ackerman
function (see Chapter 8). This bound can be found in reference [17].

6.14

The parent is at position (i + d − 2)/d. The children are in positions (i − 1)d + 2, . . . , id + 1.

6.15

(a) O((M + dN) logd N ).
(b) O((M + N ) log N ).
(c) O(M + N 2).
(d) d = max(2, M/N). (See the related discussion at the end of Section 11.4.)

6.16

Starting from the second most signficant digit in i, and going toward the least significant digit, branch
left for 0s, and right for 1s.

6.17

(a) Place negative infinity as a root with the two heaps as subtrees. Then do a deleteMin.
(b) Place negative infinity as a root with the larger heap as the left subheap, and the smaller heap as
the right subheap. Then do a deleteMin.
(c) SKETCH: Split the larger subheap into smaller heaps as follows: on the left-most path, remove
two subheaps of height r − 1, then one of height r, r + 1, and so one, until l − 2. Then merge the

Solutions

trees, going smaller to higher, using the results of parts (a) and (b), with the extra nodes on the left
path substituting for the insertion of infinity, and subsequent deleteMin.

6.19

6.20

6.21

This theorem is true, and the proof is very much along the same lines as Exercise 4.20.

6.22

If elements are inserted in decreasing order, a leftist heap consisting of a chain of left children is
formed. This is the best because the right path length is minimized.

6.23

(a) If a decreaseKey is performed on a node that is very deep (very left), the time to percolate
up would be prohibitive. Thus the obvious solution doesn’t work. However, we can still do the
operation efficiently by a combination of remove and insert. To remove an arbitrary node x in the
heap, replace x by the merge of its left and right subheaps. This might create an imbalance for nodes
on the path from x’s parent to the root that would need to be fixed by a child swap. However, it is
easy to show that at most log N nodes can be affected, preserving the time bound.
This is discussed in Chapter 11.

6.24

Lazy deletion in leftist heaps is discussed in the paper by Cheriton and Tarjan [10]. The general idea
is that if the root is marked deleted, then a preorder traversal of the heap is formed, and the frontier
of marked nodes is removed, leaving a collection of heaps. These can be merged two at a time by
placing all the heaps on a queue, removing two, merging them, and placing the result at the end of
the queue, terminating when only one heap remains.

6.25

(a) The standard way to do this is to divide the work into passes. A new pass begins when the first
element reappears in a heap that is dequeued. The first pass takes roughly 2 ∗ 1 ∗ (N/2) time units
because there are N/2 merges of trees with one node each on the right path. The next pass takes

49

50

Chapter 6

Priority Queues (Heaps)

2 ∗ 2 ∗ (N/4) time units because of the roughly N/4 merges of trees with no more than two nodes on
the right path. The third pass takes 2 ∗ 3 ∗ (N/8) time units, and so on. The sum converges to 4N .
(b) It generates heaps that are more leftist.

6.26

6.27

6.28

This claim is also true, and the proof is similar in spirit to Exercise 4.20 or 6.21.

6.29

Yes. All the single operation estimates in Exercise 6.25 become amortized instead of worst-case, but
by the definition of amortized analysis, the sum of these estimates is a worst-case bound for the
sequence.

6.30

Clearly the claim is true for k = 1. Suppose it is true for all values i = 1, 2, . . . , k. A Bk+1 tree is
formed by attaching a Bk tree to the root of a Bk tree. Thus by induction, it contains a B0 through
Bk−1 tree, as well as the newly attached Bk tree, proving the claim.

6.31

Proof is by induction. Clearly the claim is true for k = 1. Assume true for all values i = 1, 2, . . . , k.
k
A Bk+1 tree is formed by attaching a Bk tree to the original Bk tree. The original thus had
d
k
nodes at depth d. The attached tree had
nodes at depth d − 1, which are now at depth d.
d −1
Adding these two terms and using a well-known formula establishes the theorem.

Solutions

6.32

6.33

This is established in Chapter 11.

6.38

Don’t keep the key values in the heap, but keep only the difference between the value of the key in
a node and the value of the parent’s key.

6.39

O(N + k log N ) is a better bound than O(N log k). The first bound is O(N ) if k = O(N/ log N ).
The second bound is more than this as soon as k grows faster than a constant. For the other values
(N/ log N ) = k = o(N), the first bound is better. When k = (N ), the bounds are identical.

6.40

(d) The recursion has O(log N ) depth.
(e) For skew heaps, we need a non-recursive implementation.

51

C H A P T E R

7

Sorting
7.1

7.2

O(N) because the while loop terminates immediately. Of course, accidentally changing the test to
include equalities raises the running time to quadratic for this type of input.

7.3

The inversion that existed between a[i] and a[i + k] is removed. This shows at least one inversion is
removed. For each of the k − 1 elements a[i + 1], a[i + 2], . . . , a[i + k − 1], at most two inversions
can be removed by the exchange. This gives a maximum of 2(k − 1) + 1 = 2k − 1.

7.4

7.5

(a) (N 2). The 2-sort removes at most only three inversions at a time; hence the algorithm is
(N 2). The 2-sort is two insertion sorts of size N/2, so the cost of that pass is O(N 2). The 1-sort
is also O(N 2), so the total is O(N 2).

7.6

Part (a) is an extension of the theorem proved in the text. Part (b) is fairly complicated; see reference
[12].

7.7

See reference [12].

7.8

Use the input specified in the hint. If the number of inversions is shown to be (N 2), then the bound
follows, since no increments are removed until an ht/2 sort. If we consider the pattern formed hk
through h2k−1, where k = t/2 + 1, we find that it has length N = hk (hk + 1) − 1, and the number
of inversions is roughly hk 4/24, which is (N 2).

7.9

(a) O(N log N ). No exchanges, but each pass takes O(N ).
(b) O(N log N ). It is easy to show that after an hk sort, no element is farther than hk from its
rightful position. Thus if the increments satisfy hk+1 ≤ chk for a constant c, which implies O(log N )
increments, then the bound is O(N log N ).

53

54

Chapter 7

7.10

(a) No, because it is still possible for consecutive increments to share a common factor. An example
is the sequence 1, 3, 9, 21, 45, ht+1 = 2ht + 3.

Sorting

(b) Yes, because consecutive increments are relatively prime. The running time becomes O(N 3/2).

7.11

The input is read in as
142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102
The result of the heapify is
879, 811, 572, 434, 543, 123, 142, 65, 111, 242, 453, 102
879 is removed from the heap and placed at the end. We’ll place it in italics to signal that it is not
part of the heap. 102 is placed in the hole and bubbled down, obtaining
811, 543, 572, 434, 453, 123, 142, 65, 111, 242, 102, 879
Continuing the process, we obtain
572, 543, 142, 434, 453, 123, 102, 65, 111, 242, 811, 879
543, 453, 142, 434, 242, 123, 102, 65, 111, 572, 811, 879
453, 434, 142, 111, 242, 123, 102, 65, 543, 572, 811, 879
434, 242, 142, 111, 65, 123, 102, 453, 543, 572, 811, 879
242, 111, 142, 102, 65, 123, 434, 453, 543, 572, 811, 879
142, 111, 123, 102, 65, 242, 434, 453, 543, 572, 811, 879
123, 111, 65, 102, 142, 242, 434, 453, 543, 572, 811, 879
111, 102, 65, 123, 142, 242, 434, 453, 543, 572, 811, 879
102, 65, 111, 123, 142, 242, 434, 453, 543, 572, 811, 879
65, 102, 111, 123, 142, 242, 434, 453, 543, 572, 811, 879

7.13

Heapsort uses at least (roughly) N log N comparisons on any input, so there are no particularly good
inputs. This bound is tight; see the paper by Schaeffer and Sedgewick [18]. This result applies for
almost all variations of heapsort, which have different rearrangement strategies. See Y. Ding and M.
A. Weiss, “Best Case Lower Bounds for Heapsort,” Computing 49 (1992).

7.14

If the root is stored in position low, then the left child of node i is stored at position 2i + 1 − low.
This requires a small change to the heapsort code.

7.15

First the sequence {3, 1, 4, 1} is sorted. To do this, the sequence {3, 1} is sorted. This involves sorting
{3} and {1}, which are base cases, and merging the result to obtain {1, 3}. The sequence {4, 1} is
likewise sorted into {1, 4}. Then these two sequences are merged to obtain {1, 1, 3, 4}. The second
half is sorted similarly, eventually obtaining {2, 5, 6, 9}. The merged result is then easily computed
as {1, 1, 2, 3, 4, 5, 6, 9}.

7.16

Mergesort can be implemented nonrecursively by first merging pairs of adjacent elements, then pairs
of two elements, then pairs of four elements, and so on.
void mergesort( vector & a )
{
int n = a.size( );
vector tmpArray( n );

Solutions
for( int subListSize = 1; subListSize < n; subListSize *= 2 )
{
int part1Start = 0;
while( part1Start + subListSize < n - 1 )
{
int part2Start = part1Start + subListSize;
int part2End = min( n, part2Start + subListSize - 1 );
merge( a, tmpArray, part1Start, part2Start, part2End );
part1Start = part2End + 1;
}
}
}

7.17

The merging step always takes (N) time, so the sorting process takes (N log N ) time on all
inputs.

7.18

See reference [12] for the exact derivation of the worst case of mergesort.

7.19

The original input is
3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5
After sorting the first, middle, and last elements, we have
3, 1, 4, 1, 5, 5, 2, 6, 5, 3, 9
Thus the pivot is 5. Hiding it gives
3, 1, 4, 1, 5, 3, 2, 6, 5, 5, 9
The first swap is between two fives. The next swap has i and j crossing. Thus the pivot is swapped
back with i:
3, 1, 4, 1, 5, 3, 2, 5, 5, 6, 9
We now recursively quicksort the first eight elements:
3, 1, 4, 1, 5, 3, 2, 5
Sorting the three appropriate elements gives
1, 1, 4, 3, 5, 3, 2, 5
Thus the pivot is 3, which gets hidden:
1, 1, 4, 2, 5, 3, 3, 5
The first swap is between 4 and 3:
1, 1, 3, 2, 5, 4, 3, 5
The next swap crosses pointers, so is undone; i points at 5, and so the pivot is swapped:
1, 1, 3, 2, 3, 4, 5, 5
A recursive call is now made to sort the first four elements. The pivot is 1, and the partition does not
make any changes. The recursive calls are made, but the subfiles are below the cutoff, so nothing is
done. Likewise, the last three elements constitute a base case, so nothing is done. We return to the

55

56

Chapter 7

Sorting

original call, which now calls quicksort recursively on the right-hand side, but again, there are only
three elements, so nothing is done. The result is
1, 1, 3, 2, 3, 4, 5, 5, 5, 6, 9
which is cleaned up by insertion sort.

7.20

(a) O(N log N ) because the pivot will partition perfectly.
(b) Again, O(N log N ) because the pivot will partition perfectly.
(c) O(N log N ); the performance is slightly better than the analysis suggests because of the medianof-three partition and cutoff.

7.21

(a) If the first element is chosen as the pivot, the running time degenerates to quadratic in the first
two cases. It is still O(N log N ) for random input.
(b) The same results apply for this pivot choice.
(c) If a random element is chosen, then the running time is O(N log N ) expected for all inputs,
although there is an O(N 2) worst case if very bad random numbers come up. There is, however, an
essentially negligible chance of this occurring. Chapter 10 discusses the randomized philosophy.
(d) This is a dangerous road to go; it depends on the distribution of the keys. For many distributions,
such as uniform, the performance is O(N log N ) on average. For a skewed distribution, such as
with the input {1, 2, 4, 8, 16, 32, 64, . . . , } the pivot will be consistently terrible, giving quadratic
running time, independent of the ordering of the input.

7.22

(a) O(N log N ) because the pivot will partition perfectly.
(b) Sentinels need to be used to guarantee that i and j don’t run past the end. The running time
will be (N 2) since, because i won’t stop until it hits the sentinel, the partitioning step will put all
but the pivot in S1.
(c) Again a sentinel needs to be used to stop j . This is also (N 2) because the partitioning is
unbalanced.

7.23

Yes, but it doesn’t reduce the average running time for random input. Using median-of-three
partitioning reduces the average running time because it makes the partition more balanced on
average.

7.24

The strategy used here is to force the worst possible pivot at each stage. This doesn’t necessarily give
the maximum amount of work (since there are few exchanges, just lots of comparisons), but it does
give (N 2) comparisons. By working backward, we can arrive at the following permutation:
20, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 10, 2, 12, 6, 14, 1, 16, 8, 18
A method to extend this to larger numbers when N is even is as follows: The first element is
N , the middle is N − 1, and the last is N − 2. Odd numbers (except 1) are written in decreasing
order starting to the left of center. Even numbers are written in decreasing order by starting at the
rightmost spot, always skipping one available empty slot, and wrapping around when the center
is reached. This method takes O(N log N ) time to generate the permutation, but is suitable for a
hand calculation. By inverting the actions of quicksort, it is possible to generate the permutation in
linear time.

7.26

Each recursive call is on a subarray that is less than half the size of the original, giving a logarithmic
number of recursive calls.

7.27

See reference [14].

Solutions

7.28

See reference [1].

7.30

This recurrence results from the analysis of the quick selection algorithm. T (N ) = O(N ).

7.31

Insertion sort and mergesort are stable if coded correctly. Any of the sorts can be made stable by the
addition of a second key, which indicates the original position.

7.32

(d) f (N ) can be O(N/ log N ). Sort the f (N ) elements using mergesort in O(f (N ) log f (N ))
time. This is O(N ) if f (N) is chosen using the criterion given. Then merge this sorted list with the
already sorted list of N numbers in O(N + f (N )) = O(N ) time.

7.33

A decision tree would have N leaves, so log N  comparisons are required.

7.34

log N ! ≈ N log N − N log e.

7.35

(a)

2N
N

2N
. Applying Stirling’s formula, we can
N
estimate the bound as 2N − half log N . A better lower bound is known for this case: 2N − 1
comparisons are necessary. Merging two lists of different sizes M and N likewise requires at least
M +N
log
comparisons.
N
(b) The information-theoretic lower bound is log

7.36

Algorithms A and B require at least three comparisons based on the information-theoretic lower
bound. Algorithm C requires at least five comparisons, based on Exercise 7.35(b). So the algorithm
requires 11 comparisons; but six elements can be sorted in 10 comparisons (for instance, use the
results in Exercise 7.42, and use binary search to find the correct place to insert the sixth element).

7.37

Note that any two fractions that are not equal differ by at least 1/N 2. Thus, rewrite the fractions as
c/(N + 1)2 + d, ignore the d, and sort on the basis of c using a two-pass radix sort.

7.38

Look at the middle elements of A and B. Let m1 and m2 be these two middle elements; assume m1 is
the larger (the mirror image is similar). Recursively use the elements in A that are larger than m1 and
the elements in B that are smaller than m2, making sure that an equal number of elements from A
and B are not included in the recursive problem (include m1 or m2 if needed to balance). Recursively
solve the problem on the subarray consisting of elements larger than the larger of the two middles

7.39

We add a dummy N + 1th element, which we’ll call maybe. maybe satisfies f alse < maybe < true.
Partition the array around maybe, using the standard quicksort techniques. Then swap maybe and
the N + 1th element. The first N elements are then correctly arranged.

7.40

We add a dummy N + 1th element, which we’ll call probablyF alse. probablyF alse satisfies
f alse < probablyF alse < maybe. Partition the array around probablyF alse as in the previous
exercise. Suppose that after the partition, probablyF alse winds up in position i. Then place the
element that is in the N + 1th slot in position i, place probablyT rue (defined the obvious way)
in position N + 1, and partition the subarray from position i onward. Finally, swap probablyT rue
with the element in the N + 1th location. The first N elements are now correctly arranged. These
two problems can be done without the assumption of an extra array slot; assuming so simplifies
the presentation.

7.41

(a) log 4! = 5.
(b) Compare and exchange (if necessary) a1 and a2 so that a1 ≥ a2, and repeat with a3 and a4.
Compare and exchange a1 and a3. Compare and exchange a2 and a4. Finally, compare and exchange
a2 and a3.

57

58

Chapter 7

7.42

(a) log 5! = 7.
(b) Compare and exchange (if necessary) a1 and a2 so that a1 ≥ a2, and repeat with a3 and a4 so that
a3 ≥ a4. Compare and exchange (if necessary) the two winners, a1 and a3. Assume without loss of
generality that we now have a1 ≥ a3 ≥ a4, and a1 ≥ a2. (The other case is obviously identical.) Insert
a5 by binary search in the appropriate place among a1 , a3,a4. This can be done in two comparisons.
Finally, insert a2 among a3 , a4 , a5. If it is the largest among those three, then it goes directly after a1
since it is already known to be larger than a1. This takes two more comparisons by a binary search.
The total is thus seven comparisons.

7.46

(a) For the given input, the pivot is 2. It is swapped with the last element. i will point at the second
element, and j will be stopped at the first element. Since the pointers have crossed, the pivot is
swapped with the element in position 2. The input is now 1, 2, 4, 5, 6, . . . , N − 1, N , 3. The
recursive call on the right subarray is thus on an increasing sequence of numbers, except for the last
number, which is the smallest. This is exactly the same form as the original. Thus each recursive call
will have only two fewer elements than the previous. The running time will be quadratic.
(b) Although the first pivot generates equal partitions, both the left and right halves will have the
same form as part (a). Thus the running time will be quadratic because after the first partition, the
algorithm will grind slowly. This is one of the many interesting tidbits in reference [22].

7.47

We show that in a binary tree with L leaves, the average depth of a leaf is at least log L. We can
prove this by induction. Clearly, the claim is true if L = 1. Suppose it is true for trees with up
to L − 1 leaves. Consider a tree of L leaves with minimum average leaf depth. Clearly, the root
of such a tree must have non-null left and right subtrees. Suppose that the left subtree has LL
leaves, and the right subtree has LR leaves. By the inductive hypothesis, the total depth of the
leaves (which is their average times their number) in the left subtree is LL(1 + log LL), and the
total depth of the right subtree’s leaves is LR (1 + log LR ) (because the leaves in the subtrees are
one deeper with respect to the root of the tree than with respect to the root of their subtree). Thus
the total depth of all the leaves is L + LL log LL + LR log LR . Since f (x) = x log x is convex for
x ≥ 1, we know that f (x) + f (y) ≥ 2f ((x + y)/2). Thus, the total depth of all the leaves is at least
L + 2(L/2) log(L/2) ≥ L + L(log L − 1) ≥ L log L. Thus the average leaf depth is at least log L.

7.48

(a) A brute-force search gives a quadratic solution.
(b) Sort the items; then run i and j from opposite ends of the array toward each other, incrementing i
if a[i] + a[j ] < K, and decrementing j if a[i] + a[j ] > K. The sort is O(N log N ); the scan is O(N ).

7.50

(b) After sorting the items do a scan using an outer loop that considers all positions p, and an inner
loop that searches for two additional items that sum to K − a[p]. The two loops give a quadratic
algorithm.

7.54

Yes; otherwise we cannot create a vector of P ointer.

7.56

(a) Is immediate; (b) and (c) follow inductively by computing the probability of a cycle of length at
least L, which is (N − L)/N , and multiplying by 1/(N − L); (d) follows from the hint;
(e) follows by summing 1/L for all L.

Sorting

C H A P T E R

8

The Disjoint Set
8.1

We assume that unions operated on the roots of the trees containing the arguments. Also, in case of
ties, the second tree is made a child of the first. Arbitrary union and union by height give the same
answer (shown as the first tree) for this problem. Union by size gives the second tree.

8.2

In both cases, have nodes 16 and 0 point directly to the root.

8.4

Claim: A tree of height h has at least 2h nodes. The proof is by induction. A tree of height 0 clearly has
at least 1 node, and a tree of height 1 clearly has at least 2. Let T be the tree of height h with fewest
nodes. Thus at the time of T ’s last union, it must have been a tree of height h − 1, since otherwise
T would have been smaller at that time than it is now and still would have been of height h, which
is impossible by assumption of T ’s minimality. Since T ’s height was updated, it must have been as a
result of a union with another tree of height h − 1. By the induction hypothesis, we know that at the
time of the union, T had at least 2h−1 nodes, as did the tree attached to it, for a total of 2h nodes,
proving the claim. Thus an N -node tree has depth at most log N .

8.5

All answers are O(M) because in all cases alpha(M , N ) = 1.

8.6

It is easy to see that this invariant is maintained in each disjoint set as the algorithm proceeds.

8.7

Run the normal algorithm, never remove the prespecified wall, Let s1 and s2 be squares on the
opposite side of the wall. Do not remove any wall that results in s1 being connected to the ending
point or s2 being connected to the starting point, and continue until there are only two disjoint sets
remaining.

59

60

Chapter 8

8.8

(a) When we perform a union we push onto a stack the two roots and the old values of their parents.
To implement a deunion, we only have to pop the stack and restore the values. This strategy works
fine in the absence of path compression.
(b) If path compression is implemented, the strategy described in part (a) does not work because
path compression moves elements out of subtrees. For instance, the sequence union(1,2), union(3,4),
union(1,3), find(4), deunion(1,3) will leave 4 in set 1 if path compression is implemented.

8.9

We assume that the tree is implemented with links instead of a simple array. Thus find will return
a reference instead of an actual set name. We will keep an array to map set numbers to their tree
nodes. union and find are implemented in the standard manner. To perform remove(x), first perform
a find(x) with path compression. Then mark the node containing x as vacant. Create a new one-node
tree with x and have it pointed to by the appropriate array entry. The time to perform a remove is the
same as the time to perform a find, except that there potentially could be a large number of vacant
nodes. To take care of this, after N removes are performed, perform a f ind on every node, with
path compression. If a f ind(x) returns a vacant root, then place x in the root node, and make the
old node containing x vacant. The results of Exercise 8.11 guarantee that this will take linear time,
which can be charged to the N removes. At this point, all vacant nodes (indeed all nonroot nodes)
are children of a root, and vacant nodes can be disposed (if an array of references to them has been
kept). This also guarantees that there are never more than 2N nodes in the forest and preserves the
Mα(M , N ) asymptotic time bound.

8.11

Suppose there are u union and f f ind operations. Each union costs constant time, for a total of u. A
find costs one unit per vertex visited. We charge, as in the text, under the following slightly modified
rules:

The Disjoint Set

(a) the vertex is a root or child of the root
(b) otherwise
Essentially, all vertices are in one rank group. During any find, there can be at most two rule
(A) charges, for a total of 2f . Each vertex can be charged at most once under rule (B) because after
path compression it will be a child of the root. The number of vertices that are not roots or children
of roots is clearly bounded by u, independent of the unioning strategy, because each union changes
exactly one vertex from root to nonroot status, and this bounds the number of type (B) nodes. Thus
the total rule (B) charges are at most u. Adding all charges gives a bound of 2f + 2u, which is linear
in the number of operations.

8.13

For each vertex v, let the pseudorank Rv be defined as log Sv , where Sv is the number of
descendents (including itself) of v in the final tree, after all union operations are performed, ignoring
path compression.
Although the pseudorank is not maintained by the algorithm, it is not hard to show that the
pseudorank satisfies the same properties as the ranks do in union-by-rank. Clearly, a vertex with
pseudorank Rv has at least 2Rv descendents (by its definition), and the number of vertices of
pseudorank R is at most N/2R . The union-by-size rule ensures that the parent of a node has twice
as many descendents as the node, so the pseudoranks monotonically increase on the path toward
the root if there is no path compression. The argument in Lemma 8.3 tells us that path compression
does not destroy this property.
If we partition the vertices by pseudoranks and assign the charges in the same manner as in the
text proof for union-by-rank, the same steps follow, and the identical bound is obtained.

8.14

This is most conveniently implemented without recursion and is faster because, even if full path
compression is implemented nonrecursively, it requires two passes up the tree. This requires only

Solutions

one. We leave the coding to the reader since comparing the various union and f ind strategies
is a reasonable programming project. The worst-case running time remains the same because the
properties of the ranks are unchanged. Instead of charging one unit to each vertex on the path to the
root, we can charge two units to alternating vertices (namely, the vertices whose parents are altered
by path halving). These vertices get parents of higher rank, as before, and the same kind of analysis
bounds the total charges.

61

C H A P T E R

9

Graph Algorithms
9.1

The following ordering is arrived at by using a queue and assumes that vertices appear on an adjacency
list alphabetically. The topological order that results is then
s, G, D, H, A, B, E, I, F, C, t

9.2

Assuming the same adjacency list, the topological order produced when a stack is used is
s, G, H, D, A, E, I, F, B, C, t
Because a topological sort processes vertices in the same manner as a breadth-first search, it tends
to produce a more natural ordering.

9.4

The idea is the same as in Exercise 5.12.

9.5

(a) (Unweighted paths) A → B, A → C, A → B → G, A → B → E, A → C → D, A → B → E → F.
(b) (Weighted paths) A → C, A → B, A → B → G, A → B → G → E, A → B → G → E → F,
A → B → G → E → D.

9.6

We’ll assume that Dijkstra’s algorithm is implemented with a priority queue of vertices that uses the
decreaseKey operation. Dijkstra’s algorithm uses |E| decreaseKey operations, which cost O(logd |V |)
each, and |V | deleteMin operations, which cost O(d logd |V |) each. The running time is thus
O(|E| logd |V | + |V |d logd |V |). The cost of the decreaseKey operations balances the insert operations when d = |E|/|V |. For a sparse graph, this might give a value of d that is less than 2; we can’t allow this, so d is chosen to be max(2, |E|/|V |). This gives a running time of O(|E| log2+|E|/|V | |V |),
which is a slight theoretical improvement. Moret and Shapiro report (indirectly) that d-heaps do not
improve the running time in practice.

9.7

(a) The graph shown here is an example. Dijkstra’s algorithm gives a path from A to C of cost 2,
when the path from A to B to C has cost 1.

(b) We define a pass of the algorithm as follows: Pass 0 consists of marking the start vertex as known
and placing its adjacent vertices on the queue. For j > 0, pass j consists of marking as known all
vertices on the queue at the end of pass j − 1. Each pass requires linear time, since during a pass, a
vertex is placed on the queue at most once. It is easy to show by induction that if there is a shortest
path from s to v containing k edges, then dv will equal the length of this path by the beginning of
pass k. Thus there are at most |V | passes, giving an O(|E||V |) bound.
63

64

Chapter 9

9.8

See the comments for Exercise 9.19.

9.10

(a) Use an array count such that for any vertex u, count[u] is the number of distinct paths from s to u
known so far. When a vertex v is marked as known, its adjacency list is traversed. Let w be a vertex
on the adjacency list.
If dv + cv, w = dw , then increment count[w] by count[v] because all shortest paths from s to v
with last edge (v, w) give a shortest path to w.
If dv + cv, w < dw , then pw and dw get updated. All previously known shortest paths to w are
now invalid, but all shortest paths to v now lead to shortest paths for w, so set count[w] to equal
count[v]. Note: Zero-cost edges mess up this algorithm.
(b) Use an array numEdges such that for any vertex u, numEdges[u] is the shortest number of edges
on a path of distance du from s to u known so far. Thus numEdges is used as a tiebreaker when
selecting the vertex to mark. As before, v is the vertex marked known, and w is adjacent to v.
If dv + cv, w = dw , then change pw to v and numEdges[w] to numEdges[v]+1 if numEdges[v]+1 <
numEdges[w].
If dv + cv, w < dw , then update pw and dw , and set numEdges[w] to numEdges[v]+1.

9.11

(This solution is not unique).
First send four units of flow along the path s, G, H, I, t. This gives the following residual graph:

Graph Algorithms

Next, send three units of flow along s, D, E, F, t. The residual graph that results is as follows:

Now two units of flow are sent along the path s, G, D, A, B, C, t, yielding the following residual
graph:

Solutions

One unit of flow is then sent along s, D, A, E, C, t:

Finally, one unit of flow can go along the path s, A, E, C, t:

The preceding residual graph has no path from s to t. Thus the algorithm terminates. The final
flow graph, which carries 11 units, is as follows:

This flow is not unique. For instance, two units of the flow that goes from G to D to A to E could
go by G to H to E.

9.12

Let T be the tree with root r, and children r1, r2, . . . , rk , which are the roots of T1, T2, . . . , Tk ,
which have maximum incoming flow of c1, c2, . . . , ck , respectively. By the problem statement, we
may take the maximum incoming flow of r to be infinity. The recursive pseudo-method findMaxFlow(
T, incomingCap ) finds the value of the maximum flow in T (finding the actual flow is a matter of
bookkeeping); the flow is guaranteed not to exceed incomingCap.
If T is a leaf, then f indMaxF low returns incomingCap since we have assumed a sink of
infinite capacity. Otherwise, a standard postorder traversal can be used to compute the maximum
flow in linear time.
// FlowType is an int or double
FlowType findMaxFlow( Tree T, FlowType incomingCap )
{
FlowType childFlow, totalFlow;
if( T.hasNoSubtrees( ) )
return incomingCap;

65

66

Chapter 9

Graph Algorithms
else
{
totalFlow = 0;
for( each subtree $T_i$ of T )
{
childFlow = findMaxFlow( $T_i$, min( incomingCap, $c_i$ ) );
totalFlow += childFlow;
incomingCap -= childFlow;
}
return totalFlow;
}

}

9.13

(a) Assume that the graph is connected and undirected. If it is not connected, then apply the
algorithm to the connected components. Initially, mark all vertices as unknown. Pick any vertex v,
color it red, and perform a depth-first search. When a node is first encountered, color it blue if the DFS
has just come from a red node, and red otherwise. If at any point, the depth-first search encounters
an edge between two identical colors, then the graph is not bipartite; otherwise, it is. A breadth-first
search (that is, using a queue) also works. This problem, which is essentially two-coloring a graph,
is clearly solvable in linear time. This contrasts with three-coloring, which is NP-complete.
(b) Construct an undirected graph with a vertex for each instructor, a vertex for each course, and
an edge between (v, w) if instructor v is qualified to teach course w. Such a graph is bipartite; a
matching of M edges means that M courses can be covered simultaneously.
(c) Give each edge in the bipartite graph a weight of 1, and direct the edge from the instructor to
the course. Add a vertex s with edges of weight 1 from s to all instructor vertices. Add a vertex t
with edges of weight 1 from all course vertices to t. The maximum flow is equal to the maximum
matching.
(d) The running time is O(|E||V |half ) because this is the special case of the network flow problem
mentioned in the text. All edges have unit cost, and every vertex (except s and t) has either an
indegree or outdegree of 1.

9.14

This is a slight modification of Dijkstra’s algorithm. Let fi be the best flow from s to i at any point
in the algorithm. Initially, fi = 0 for all vertices, except s: fs = inf .
At each stage, we select v such that fv is maximum among all unknown vertices. Then for each
w adjacent to v, the cost of the flow to w using v as an intermediate is min(fv , cv, w ). If this value
is higher than the current value of fw , then fw and pw are updated.

9.15

One possible minimum spanning tree is shown here. This solution is not unique.

9.16

Both work correctly. The proof makes no use of the fact that an edge must be nonnegative.

Solutions

9.17

The proof of this fact can be found in any good graph theory book. A more general theorem follows:
Theorem.

Let G = (V , E) be an undirected, unweighted graph, and let A be the adjacency matrix for G
(which contains either 1s or 0s). Let D be the matrix such that D[v][v] is equal to the degree
of v; all nondiagonal matrices are 0. Then the number of spanning trees of G is equal to the
determinant of A + D.

9.19

The obvious solution using elementary methods is to bucket sort the edge weights in linear time.
Then the running time of Kruskal’s algorithm is dominated by the union/find operations and is
O(|E|α(|E|, |V |)). The Van-Emde Boas priority queues (see Chapter 6 references) give an immediate
O(|E| log log |V |) running time for Dijkstra’s algorithm, but this isn’t even as good as a Fibonacci
heap implementation.
More sophisticated priority queue methods that combine these ideas have been proposed,
including M. L. Fredman and D. E. Willard, “Trans-dichotomous Algorithms for Minimum Spanning
Trees and Shortest Paths,” Proceedings of the Thirty-first Annual IEEE Symposium on the Foundations
of Computer Science (1990), 719–725. The paper presents a linear-time minimum spanning tree
algorithm and an O(|E| + |V | log |V |/ log log |V |) implementation of Dijkstra’s algorithm if the
edge costs are suitably small. Various improvements have been discovered since.

9.20

Since the minimum spanning tree algorithm works for negative edge costs, an obvious solution
is to replace all the edge costs by their negatives and use the minimum spanning tree algorithm.
alternatively, change the logic so that < is replaced by >, min by max, and vice versa.

9.21

We start the depth-first search at A and visit adjacent vertices alphabetically. The articulation points
are C, E, and F . C is an articulation point because low[B] ≥ num[C]; E is an articulation point
because low[H ] ≥ num[E]; and F is an articulation point because low[G] ≥ num[F ]; the depth-first
spanning tree is shown in the following Figure.

67

68

Chapter 9

9.22

The only difficult part is showing that if some nonroot vertex a is an articulation point, then there
is no back edge between any proper descendent of a and a proper ancestor of a in the depth-first
spanning tree. We prove this by a contradiction.
Let u and v be two vertices such that every path from u to v goes through a. At least one of u
and v is a proper descendent of a, since otherwise there is a path from u to v that avoids a. Assume
without loss of generality that u is a proper descendent of a. Let c be the child of a that contains
u as a descendent. If there is no back edge between a descendent of c and a proper ancestor of a,
then the theorem is true immediately, so suppose for the sake of contradiction that there is a back
edge (s , t). Then either v is a proper descendent of a or it isn’t. In the second case, by taking a path
from u to s to t to v, we can avoid a, which is a contradiction. In the first case, clearly v cannot be
a descendent of c, so let c be the child of a that contains v as a descendent. By a similar argument
as before, the only possibility is that there is a back edge (s , t ) between a descendent of c and a
proper ancestor of a. Then there is a path from u to s to t to t to s to v; this path avoids a, which
is also a contradiction.

9.23

(a) Do a depth-first search and count the number of back edges.
(b) This is the feedback edge set problem. See reference [1] or [20].

9.24

Let (v, w) be a cross edge. Since at the time w is examined it is already marked, and w is not
a descendent of v (else it would be a forward edge), processing for w is already complete when
processing for v commences. Thus under the convention that trees (and subtrees) are placed left to
right, the cross edge goes from right to left.

9.25

Suppose the vertices are numbered in preorder and postorder.
If (v, w) is a tree edge, then v must have a smaller preorder number than w. It is easy to see that
the converse is true.
If (v, w) is a cross edge, then v must have both a larger preorder and postorder number than w.
The converse is shown as follows: because v has a larger preorder number, w cannot be a descendent
of v; because it has a larger postorder number, v cannot be a descendent of w; thus they must be in
different trees.
Otherwise, v has a larger preorder number but is not a cross edge. To test if (v, w) is a back
edge, keep a stack of vertices that are active in the depth-first search call (that is, a stack of vertices
on the path from the current root). By keeping a bit array indicating presence on the stack, we can
easily decide if (v, w) is a back edge or a forward edge.

9.26

The first depth-first spanning tree is

Graph Algorithms

Solutions

Gr , with the order in which to perform the second depth-first search, is shown next. The strongly
connected components are F and all other vertices.

9.28

This is the algorithm mentioned in the references.

9.29

As an edge (v, w) is implicitly processed, it is placed on a stack. If v is determined to be an articulation
point because low[w] ≥ num[v], then the stack is popped until edge (v, w) is removed: The set of
popped edges is a biconnected component. An edge (v, w) is not placed on the stack if the edge
(w, v) was already processed as a back edge.

9.30

Let (u, v) be an edge of the breadth-first spanning tree. (u, v) are connected, thus they must be in
the same tree. Let the root of the tree be r; if the shortest path from r to u is du, then u is at level
du; likewise, v is at level dv . If (u, v) were a back edge, then du > dv , and v is visited before u. But
if there were an edge between u and v, and v is visited first, then there would be a tree edge (v, u),
and not a back edge (u, v). Likewise, if (u, v) were a forward edge, then there is some w, distinct
from u and v, on the path from u to v; this contradicts the fact that dv = dw + 1. Thus only tree
edges and cross edges are possible.

9.31

Perform a depth-first search. The return from each recursive call implies the edge traversal in the
opposite direction. The time is clearly linear.

9.33

If there is an Euler circuit, then it consists of entering and exiting nodes; the number of entrances
clearly must equal the number of exits. If the graph is not strongly connected, there cannot be a cycle
connecting all the vertices. To prove the converse, an algorithm similar in spirit to the undirected
version can be used.

9.34

Neither of the proposed algorithms works. For example, as shown, a depth-first search of a biconnected graph that follows A, B, C, D is forced back to A, where it is stranded.

9.35

These are classic graph theory results. Consult any graph theory for a solution to this exercise.

9.36

All the algorithms work without modification for multigraphs.

9.37

Obviously, G must be connected. If each edge of G can be converted to a directed edge and produce
a strongly connected graph G , then G is convertible.

69

70

Chapter 9

Graph Algorithms

Then, if the removal of a single edge disconnects G, G is not convertible since this would
also disconnect G . This is easy to test by checking to see if there are any single-edge biconnected
components.
Otherwise, perform a depth-first search on G and direct each tree edge away from the root and
each back edge toward the root. The resulting graph is strongly connected because, for any vertex v,
we can get to a higher level than v by taking some (possibly 0) tree edges and a back edge. We can
apply this until we eventually get to the root, and then follow tree edges down to any other vertex.

9.38

(b) Define a graph where each stick is represented by a vertex. If stick Si is above Sj and thus must
be removed first, then place an edge from Si to Sj . A legal pick-up ordering is given by a topological
sort; if the graph has a cycle, then the sticks cannot be picked up.

9.39

Use a depth-first search, marking colors when a new vertex is visited, starting at the root, and
returning false if a color clash is detected along a backedge.

9.40

Use a greedy algorithm: at each step, choose the vertex with the highest connectivity to vertices not
already chosen. Proof that only 1/4 of the edges are not touched can be done with a straightforward
calculation of edges the remain after each step. With E edges and V vertices, the total connectivity
is 2E at the start, so at most (V − 2)/V of the edges remain after the first step. Then at most
(V − 3)/(V − 1) of those edges remain after the second step, and so on. Multiply it out, and you
get about 1/4 of the edges remaining.

9.41

If no vertex has indegree 0, we can find a cycle by tracing backwards through vertices with positive
indegree; since every vertex on the trace back has a positive indegree, we eventually reach a vertex
twice, and the cycle has been found.

9.42

The basic idea is that we examine cell A[s , t]; if it is 0, then t is not a sink, otherwise s is not a sink.
Each examination can eliminate one vertex; after |V | − 1 queries, we have one candidate that can be
checked in 2|V | − 1 additional tests. To do the first step, after the test A[s , t] is performed, replace
the eliminated vertex with the next vertex in the the sequence of vertices.

9.43

Perform a postorder traversal, computing node sizes; the first node that has a size greater than N/2
vertices is the node to remove.

9.44

This is essentially the algorithm described in Section 9.3.4 for critical paths.

9.45

These are all recursive depth first searches.

9.46

This is a single source unweighted shortest path problem.

9.47

This is a weighted shortest path problem: adjacent squares have a cost of 1 if there is no wall, and
P + 1 if there is a wall.

9.48

(a) Use the same ideas from the shortest path algorithm, but place unmarked adjacent squares at the
front of a double-ended queue, and unmarked adjacent wall-separate squares at the end. Note that
when dequeues are performed from the front, a stale square (in other words, one that was marked
after it entered the deque) may emerge, and would be ignored.
(b) Use Exercise 9.47, with a penalty equal to the number of squares in the maze.

9.49

The following implementation does not use the map class. The use of vector instead will speed up
the algorithm since access now takes O(1) instead of O(log N ), if the vector of words can fit in
main memory. One could use maps to also solve the problem. Using maps with keys and data both
strings allows the maps to store adjacent words in the word ladder directly. The Chapter 4 code can

Solutions

be modified for this problem by either just adding words of differing lengths but differ by just one
extra character, to the adjacency list but then have a check to see if the cost should be 1 or p when
Dijkstra’s algorithm is applied.
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int INFINTY = 99999;
struct Vertex
{
vector adj;
vector weight;
bool known;
int dist;
string name;
int path;
};
// Prints the shortest path
void printPath( int vIndex, vector V )
{
if( vIndex >=0 && V[vIndex].path > -1 )
{
printPath( V[vIndex].path, V );
cout << " to ";
}
cout << V[vIndex].name;
}
// Finds the shortest path from the vertex at sIndex
void dijkstra( int sIndex ,

int tIndex,

{
int smallestDist ;
int smallestVertex ;
Vertex v, s, t;
int n = Vertices.size();
Vertices[sIndex].dist = 0;
for( ; ; )
{
smallestDist = INFINTY;
smallestVertex = -1;

to tIndex

vector  & Vertices )

71

72

Chapter 9

Graph Algorithms
for (int i = 0; i < n ; i++)
{
if (!Vertices[i].known && Vertices[i].dist < smallestDist)
{
smallestDist = Vertices[i].dist;
smallestVertex = i;
}
}
if (smallestVertex < 0 || smallestVertex == tIndex) break;
Vertices[smallestVertex].known = true;
v= Vertices[smallestVertex];
for (int j = 0; j readWords( istream & in )
{
string oneLine;
vector v;
Vertex w;
while( in >> oneLine )
{
w.name = oneLine;
w.known = false;
w.path = -1;
w.dist = INFINTY;
v.push_back( w );
}
return v;
}

// Returns 1 if word1 and word2 are the same length
// and differ in only one character.
// Returns p if word1 and word2 differ in length by 1 and
// but are otherwise identical.
// return 0 other wise

Solutions
int oneCharOff( const string & word1, const string & word2 ,int p )
{
string big, small, shrink;
int cost;
//cout<< "comparing :
if( abs ((int)(word1.length( )- word2.length( )))> 1 )
return 0;
else
if (word1.length() == word2.length())
{
int diffs = 0;
for( int i = 0; i < word1.length( ); i++ )
if( word1[ i ] != word2[ i ] )
if( ++diffs > 1 )
return 0;
if (diffs == 1)
return 1;
}
if (word2.length () > word1.length ())
{
big = word2;
small = word1;
}
else
{
big = word1;
small = word2;
}
for (int i = 0; i < big.length()-1; i++)
{
shrink = big.substr(0,i) + big.substr(i+1,big.size()-i-1);
if (shrink == small)
return p;
}
if (big.substr (0, big.size()-1) == small)
return p;
else
return 0;
}
//fills the adjacencies lists for all words in the dictionary
void fillAdjacencies (vector & words, int p)
{
int cost;
for (int i = 0 ; i < words.size(); i++)

73

74

Chapter 9

Graph Algorithms
for (int j = i+1; j < words.size(); j++)
{ cost = oneCharOff(words[i].name, words[j].name,p);
if (cost > 0)
{

// word i and j are adjacent with weight cost
words[i].adj.push_back(j);
words[i].weight.push_back(cost);
words[j].adj.push_back(i);
words[j].weight.push_back(cost);

}
}
}
int main()
{
int p;
ifstream fin( "dict.txt" );
string w1, w2;
int w1Index, w2Index;
cout<<"what is the cost of single char deletions: ";
cin>>p;
vector words = readWords( fin );
do{
cout << "Enter two words in the dictionary: ";
cin >> w1 >> w2;
// Find their indices (here is where a map would be superior
// However all other access are now in O(1) time
for (w1Index = 0; w1Index < words.size()
&& words[w1Index].name != w1 ; w1Index++);
for (w2Index = 0; w2Index < words.size()
&& words[w2Index].name != w2 ; w2Index++);
} while (w1Index >=words.size() || w2Index >= words.size());
fillAdjacencies(words, p);
dijkstra( w1Index ,

w2Index,

// make the adjacency list
words);

// use dijkstra’s algorithm

cout< ty . Let jz be the job immediately following jx . If we swap jy and jz ,
it is easy to check that the mean processing time is unchanged and thus still optimal. But now jy
follows jx , which is impossible because we know that the jobs on any processor must be in sorted
order from the results of the one processor case.
Let je1, je2, . . . , jeM be the extra jobs if N does not evenly divide P . It is easy to see that the
processing time for these jobs depends only on how quickly they can be scheduled, and that they
must be the last scheduled job on some processor. It is easy to see that the first M processors must
have jobs j(i−1)P +1 through jiP +M ; we leave the details to the reader.

10.3

10.4

One method is to generate code that can be evaluated by a stack machine. The two operations are
push (the one node tree corresponding to) a symbol onto a stack and combine, which pops two trees
off the stack, merges them, and pushes the result back on. For the example in the text, the stack
instructions are push(s), push(nl), combine, push(t), combine, push(a), combine, push(e), combine, push(i),
push (sp), combine, combine.
By encoding a combine with a 0 and a push with a 1 followed by the symbol, the total extra
space is 2N − 1 bits if all the symbols are of equal length. Generating the stack machine code can
be done with a simple recursive procedure and is left to the reader.

10.6

Maintain two queues, Q1 and Q2. Q1 will store single-node trees in sorted order, and Q2 will store
multinode trees in sorted order. Place the initial single-node trees on Q1, enqueueing the smallest
weight tree first. Initially, Q2 is empty. Examine the first two entries of each of Q1 and Q2, and
dequeue the two smallest. (This requires an easily implemented extension to the ADT.) Merge the
tree and place the result at the end of Q2. Continue this step until Q1 is empty and only one tree is
left in Q2.
77

78

Chapter 10

10.9

To implement first fit, we keep track of bins bi , which have more room than any of the lower
numbered bins. A theoretically easy way to do this is to maintain a splay tree ordered by empty
space. To insert w, we find the smallest of these bins, which has at least w empty space; after w is
added to the bin, if the resulting amount of empty space is less than the inorder predecessor in the
tree, the entry can be removed; otherwise, a decreaseKey is performed.
To implement best fit, we need to keep track of the amount of empty space in each bin. As before,
a splay tree can keep track of this. To insert an item of size w, perform an insert of w. If there is
a bin that can fit the item exactly, the insert will detect it and splay it to the root; the item can be
added and the root deleted. Otherwise, the insert has placed w at the root (which eventually needs
to be removed). We find the minimum element M in the right subtree, which brings M to the right
subtree’s root, attach the left subtree to M, and delete w. We then perform an easily implemented
decreaseKey on M to reflect the fact that the bin is less empty.

Algorithm Design Techniques

10.10 Next fit: 12 bins (.42, .25, .27), (.07, .72), (.86, .09), (.44, .50), (.68), (.73), (.31), (.78, .17), (.79),
(.37), (.73, .23), (.30).
First fit: 10 bins (.42, .25, .27), (.07, .72, .09), (.86), (.44, .50), (.68, .31), (.73, .17), (.78), (.79),
(.37, .23, .30), (.73).
Best fit: 10 bins (.42, .25, .27), (.07, .72, .09), (.86), (.44, .50), (.68, .31), (.73, .23), (.78, .17), (.79),
(.37, .30 ), (.73).
First fit decreasing: 10 bins (.86, .09), (.79, .17), (.78, .07), (.73, .27), (.73, .25), (.72, .23), (.68, .31),
(.50, .44), (.42, .37), (.30).
Best fit decreasing: 10 bins (.86, .09), (.79, .17), (.78), (.73, .27), (.73, .25), (.72, .23), (.68, .31),
(.50, .44), (.42, .37, .07), (.30).
Note that use of 10 bins is optimal.

10.12 We prove the second case, leaving the first and third (which give the same results as Theorem 10.6)
to the reader. Observe that
logp N = logp (bm) = mp logp b
Working this through, Equation (10.9) becomes
T (N ) = T (bm) = a m

m

bk
a
i=0

i

i p logp b

If a = bk , then
T (N ) = a m logp b
= O(a m
m

Since m = log N/ log b, and

am

= N k,

m


ip

i=0
p
p+1

log b)

and b is a constant, we obtain

T (N ) = O(N k logp+1 N )

10.13 The easiest way to prove this is by an induction argument.

√

10.14 Divide the unit square into N − 1 square grids each with side 1/ N − 1. Since there are N points,
some
grid must contain two points. Thus the shortest distance is conservatively given by at most

2/(N − 1).
√
exercise imply that the width√of the strip is O(1/ N ). Because the width
10.15 The results of the previous
√
of the strip is O(1/ N ), and thus covers only O(1/ N ) of the area of the square, we expect a

Solutions

√
similar fraction √
of the points to fall in the strip. Thus only O(N/ N ) points are expected in the
strip; this is O( N ).

10.17 The recurrence works out to
T (N) = T (2N/3) + T (N/3) + O(N )
This is not linear, because the sum is not less than one. The running time is O(N log N ).

10.18 The recurrence for median-of-median-of-seven partitioning is
T (N) = T (5N/7) + T (N/7) + O(N )
If all we are concerned about is the linearity, then median-of-median-of-seven can be used.

10.20 When computing the median-of-median-of-five, 30are known to be smaller than the pivot, and 30be
larger. Thus these elements do not need to be involved in the partitioning phase. (Extra work would
need to be done to implement this, but since the whole algorithm isn’t practical anyway, we can
ignore any extra work that doesn’t involve element comparisons.) The original paper [9] describes
the exact constants in the worst-case bound, with and without this extra effort.

10.21 We derive the values of s and δ, following the style in the original paper [17]. Let Rt , X be the rank

of element t in some sample X. If a sample S of elements is chosen randomly from S, and |S | = s,
|S| = N , then we’ve already seen that
E(Rt , S ) =

N +1
Rt , S
s+1

where E means expected value. For instance, if t is the third largest in a sample of 5 elements, then
in a group of 19 elements it is expected to be the tenth largest. We can also calculate the variance:

√
(Rt , S )(s − Rt , S + 1)(N + 1)(N − s)
V (Rt , S ) =
= O(N/ s)
2
(s + 1) (s + 2)
We choose v1 and v2 so that
E(Rv1, S ) + 2dV (Rv1, S ) ≈ k ≈ E(Rv2 , S ) − 2dV (Rv2 , S )
where d indicates how many variances we allow. (The larger d is, the less likely the element we are
looking for will not be in S .)
The probability that k is not between v1 and v2 is
∞

erf (x)dx = O(e−d /d)
2

2
d

If d = log N, then this probability is o(1/N ), specifically O(1/(N log N )). This means that
the expected work in this case is O(log−1 N ) because O(N ) work is performed with very small
probability.
These mean and variance equations imply
1/2

R v1 , S ≥ k

√
(s + 1)
−d s
(N + 1)

R v2 , S ≤ k

√
(s + 1)
+d s
(N + 1)

and

79

80

Chapter 10

Algorithm Design Techniques

This gives equation (A):

√
√
δ = d s = s log1/2 N

(A)

If we first pivot around v2, the cost is N comparisons. If we now partition elements in S that are
+1
less than v2 around v1, the cost is Rv2 , S , which has expected value k + δ Ns+1
. Thus the total cost of
N +1
partitioning is N + k + δ s+1 . The cost of the selections to find v1 and v2 in the sample S is O(s).
Thus the total expected number of comparisons is
N + k + O(s) + O(N δ/s)
The low order term is minimized when
s = N δ/s

(B)

Combining Equations (A) and (B), we see that
√
s 2 = N δ = sN log1/2 N
s 3/2 = N log1/2 N
s=N

2/3

δ=N

1/3

(D)

1/3

N

(E)

2/3

N

(F)

log
log

(C)

10.22 First, we calculate 12*43. In this case, XL = 1, XR = 2, YL = 4, YR = 3, D1 = −1, D2 = −1,

XLYL = 4, XR YR = 6, D1D2 = 1, D3 = 11, and the result is 516.
Next, we calculate 34*21. In this case, XL = 3, XR = 4, YL = 2, YR = 1, D1 = −1, D2 = −1,
XLYL = 6, XR YR = 4, D1D2 = 1, D3 = 11, and the result is 714.
Third, we calculate 22*22. Here, XL = 2, XR = 2, YL = 2, YR = 2, D1 = 0, D2 = 0, XLYL = 4,
XR YR = 4, D1D2 = 0, D3 = 8, and the result is 484.
Finally, we calculate 1234*4321. XL = 12, XR = 34, YL = 43, YR = 21, D1 = −22, D2 = −2.
By previous calculations, XLYL = 516, XR YR = 714, and D1D2 = 484. Thus D3 = 1714, and the
result is 714 + 171400 + 5160000 = 5332114.

10.23 The multiplication evaluates to (ac − bd) + (bc + ad)i. Compute ac, bd, and (a − b)(d − c) +
ac + bd.

10.24 The algebra is easy to verify. The problem with this method is that if X and Y are positive N bit
numbers, their sum might be an N + 1 bit number. This causes complications.

10.26 Matrix multiplication is not commutative, so the algorithm couldn’t be used recursively on matrices
if commutativity was used.

10.27 If the algorithm doesn’t use commutativity (which turns out to be true), then a divide and conquer
algorithm gives a running time of O(N log70 143640) = O(N 2.795).

10.28 1150 scalar multiplications are used if the order of evaluation is
((A1A2)(((A3A4)A5)A6))

10.29 (a) Let the chain be a 1x1 matrix, a 1xA matrix, and an AxB matrix. Multiplication by using the
first two matrices first makes the cost of the chain A + AB. The alternative method gives a cost of
AB + B, so if A > B, then the algorithm fails. Thus, a counterexample is multiplying a 1x1 matrix
by a 1x3 matrix by a 3x2 matrix.
(b, c) A counterexample is multiplying a 1x1 matrix by a 1x2 matrix by a 2x3 matrix.

10.31 The optimal binary search tree is the same one that would be obtained by a greedy strategy: I is at
the root and has children and and it; a and or are leaves; the total cost is 2.14.

Solutions

10.33 This theorem is from F. Yao’s paper, reference [58].
10.34 A recursive procedure is clearly called for; if there is an intermediate vertex, stopOver on the path
from s to t, then we want to print out the path from s to stopOver and then stopOver to t. We don’t
want to print out stopOver twice, however, so the method does not print out the first or last vertex
on the path and reserves that for the driver.
// Print the path between s and t, except do not print
// the first or last vertex.

Print a trailing " to " only.

void printPath1( const matrix & path, int s, int t )
{
int stopOver = path[ s ][ t ];
if( s != t && stopOver != -1 )
{
printPath1( path, s, stopOver );
cout << stopOver << " to " ;
printPath1( path, stopOver, t );
}
}
// Assume the existence of a path of length at least 1
void printPath( const matrix & path, int s, int t )
{
cout << s << " to ";
printPath1( path, s, t );
cout << t;
}

10.38 (b) If the modulus is a power of two, then the least significant bit of the “random” number oscillates.
Thus f lip will always return heads and tails alternately, and the level chosen for a skip list insertion
will always be one or two. Consequently, the performance of the skip list will be (N ) per operation.

10.39 (a) 25 ≡ 32 mod 341, 210 ≡ 1 mod 341. Since 322 ≡ 1 mod 341, this proves that 341 is not prime. We
can also immediately conclude that 2340 ≡ 1 mod 341 by raising the last equation to the 34th power.
The exponentiation would continue as follows: 220 ≡ 1 mod 341, 221 ≡ 2 mod 341, 242 ≡ 4 mod 341,
284 ≡ 16 mod 341, 285 ≡ 32 mod 341, 2170 ≡ 1 mod 341, and 2340 ≡ 1 mod 341.
(b) If A = 2, then although 2560 ≡ 1 mod 561, 2280 ≡ 1 mod 561 proves that 561 is not prime. If A =
3, then 3561 ≡ 375 mod 561, which proves that 561 is not prime. A = 4 obviously doesn’t fool the algorithm, since 4140 ≡ 1 mod 561. A = 5 fools the algorithm: 51 ≡ 5 mod 561, 52 ≡ 25 mod 561, 54 ≡
64 mod 561, 58 ≡ 169 mod 561, 516 ≡ 511 mod 561, 517 = 311 mod 561, 534 ≡ 229 mod 561, 535 ≡
23 mod 561, 570 ≡ 529 mod 561, 5140 ≡ 463 mod 561, 5280 ≡ 67 mod 561, 5560 ≡ 1 mod 561.

10.41 The two point sets are 0, 4, 6, 9, 16, 17 and 0, 5, 7, 13, 16, 17.
10.42 To find all point sets, we backtrack even if found == true, and print out information when line 2 is
executed. In the case where there are some duplicate distances, it is possible that several symmetries
will be printed.

81

82

Chapter 10

Algorithm Design Techniques

10.43

10.44 Actually, it implements both; alpha is lowered for subsequent recursive calls on line 9 when value
is changed at line 12. beta is used to terminate the while loop when a line of play leads to a position
so good that it is obvious the human player (who has already seen a more favorable line for himself
or herself before making this call) won’t play into it. To implement the complementary routine,
switch the roles of the human and computer. Lines that change are 3 and 4 (obvious changes),
5 (replace alpha with beta), 6 (replace value < beta with value > alpha), 8 (obvious), 9 (replace
human . . . value, beta with comp . . . alpha, value), and 11 (obvious).

10.46 We place circles in order. Suppose we are trying to place circle j , of radius rj . If some circle i of

√
radius ri is centered at xi , then j is tangent to i if it is placed at xi + 2 ri rsj . To see this, notice that
the line connecting the centers has length ri + rj , and the difference in y-coordinates of the centers
is |rj − ri |. The difference in x-coordinates follows from the Pythagorean theorem.

To place circle j , we compute where it would be placed if it were tangent to each of the first
j − 1 circles, selecting the maximum value. If this value is less than rj , then we place circle j at xj .
The running time is O(N 2).

10.47 Construct a minimum spanning tree T of G, pick any vertex in the graph, and then find a path in
T that goes through every edge exactly once in each direction. (This is done by a depth-first search;
see Exercise 9.31.) This path has twice the cost of the minimum spanning tree, but it is not a simple
cycle.
Make it a simple cycle, without increasing the total cost, by bypassing a vertex when it is seen
a second time (except that if the start vertex is seen, close the cycle) and going to the next unseen
vertex on the path, possibly bypassing several vertices in the process. The cost of this direct route
cannot be larger than original because of the triangle inequality.
If there were a tour of cost K, then by removing one edge on the tour, we would have a minimum
spanning tree of cost less than K (assuming that edge weights are positive). Thus the minimum

Solutions

spanning tree is a lower bound on the optimal traveling salesman tour. This implies that the algorithm
is within a factor of 2 of optimal.

10.48 If there are two players, then the problem is easy, so assume k > 1. If the players are numbered 1
through N , then divide them into two groups: 1 through N/2 and N/2 + 1 though N . On the i th
day, for 1 ≤ i ≤ N/2, player p in the second group plays players ((p + i) mod N/2) + 1 in the first
group. Thus after N/2 days, everyone in group 1 has played everyone in group 2. In the last N/2 − 1
days, recursively conduct round-robin tournaments for the two groups of players.

10.49 Divide the players into two groups of size N/2 and N/2, respectively, and recursively arrange
the players in any order. Then merge the two lists (declare that px > py if x has defeated y, and
py > px if y has defeated x − exactly one is possible) in linear time as is done in mergesort.

10.51 Divide and conquer algorithms (among others) can be used for both problems, but neither is trivial
to implement. See the computational geometry references for more information.

10.52 (a) Use dynamic programming. Let Sk = the best setting of words wk , wk+1, . . . wN , Uk = the
ugliness of this setting, and lk = for this setting, (a link to) the word that starts the second line.
M

To compute Sk−1, try putting wk−1, wk , . . . , wM all on the first line for k < M and
wi < L.
i=k−1

Compute the ugliness of each of these possibilities by, for each M, computing the ugliness of setting
the first line and adding Um+1. Let M be the value of M that yields the minimum ugliness. Then
Uk−1 = this value, and lk−1 = M + 1. Compute values of U and l starting with the last word and
working back to the first. The minimum ugliness of the paragraph is U1; the actual setting can be
found by starting at l1 and following the links in l since this will yield the first word on each line.
(b) The running time is quadratic in the case where the number of words that can fit on a line is
consistently (N). The space is linear to keep the arrays U and l. If the line length is restricted to
some constant, then the running time is linear because only O(1) words can go on a line.
(c) Put as many words on a line as can fit. This clearly minimizes the number of lines, and hence
the ugliness, as can be shown by a simple calculation.

10.53 An obvious O(N 2) solution to construct a graph with vertices 1, 2, . . . , N and place an edge (v, w)
in G iff av < aw . This graph must be acyclic, thus its longest path can be found in time linear in the
number of edges; the whole computation thus takes O(N 2) time.
Let BEST(k) be the increasing subsequence of exactly k elements that has the minimum last
element. Let t be the length of the maximum increasing subsequence. We show how to update
BEST(k) as we scan the input array. Let LAST(k) be the last element in BEST(k). It is easy to show
that if i < j , LAST(i) < LAST(j ). When scanning aM , find the largest k such that LAST(k) < aM .
This scan takes O(log t) time because it can be performed by a binary search. If k = t, then xM
extends the longest subsequence, so increase t, and set BEST(t) and LAST(t) (the new value of t is
the argument). If k is 0 (that is, there is no k), then xM is the smallest element in the list so far, so set
BEST(1) and LAST(1), appropriately. Otherwise, we extend BEST(k) with xM , forming a new and
improved sequence of length k + 1. Thus we adjust BEST(k + 1) and LAST(k + 1).
Processing each element takes logarithmic time, so the total is O(N log N ).

10.54 This is a classic program using dynamic programming. Let the matrix M [i][j ] be the integer matrix
which contains the length of the longest common subsequence between the first i letters of A and
the first j letters of B. Since a string with no letters forms no matches we have that M[0][j ] = 0
and M[i][0] = 0. Further, if i th letter of A matches the j th letter of B then we have that M [i1][j 1] =
1 + M [i − 1][j − 1]. If there is not a match then M [i][j ] = max(M
M [i][j − 1, M [i − 1][j ]). This then

83

84

Chapter 10

Algorithm Design Techniques

forms the basis for the dynamic programming algorithm for finding the length of the longest common
subsequence. To find the actual sequence itself we have to trace back along the matrix.
string lcs (string w1, string w2)
{
int i , j, n, m ;
string common="";
n = w1.size();
m = w2.size();
vector < vector < int> > M (n+1) ;
for (i = 0; i < n+1; i++)
M[i].resize(m+1);
for (i = 0; i <= n; i++)
M[i][0] = 0;
for (j = 0; j <= m ; j++)
M[0][j] = 0;
for (j = 1; j<= m ; j++)
for (i = 1; i <= n ; i++)
{
if (w1[i-1] == w2[j-1])
M[i][j] = 1+ M[i-1][j-1];
else
M[i][j] = max (M[i][j-1], M[i-1][j]);
}
// Now the trace back code
i = n;
j = m;
while(i>0 && j > 0)
{
if (M[i][j] == 1+ M[i-1][j-1]
&& w1[i-1] == w2[j-1])// there was a match
{
common = w1[i-1]+common;
i--;
j--;
}
else if (M[i-1][j] > M[i][j-1])
i--;
else
j--;
}
return common;
}

10.56 (a) A dynamic programming solution resolves part (a). Let FITS(i , s) be 1 if a subset of the first i
items sums to exactly s; FITS(i , 0) is always 1. Then FITS(x , t) is 1 if either FITS(x − 1, t − ax ) or
FITS(x − 1, t) is 1, and 0 otherwise.

Solutions

(b) This doesn’t show that P = N P because the size of the problem is a function of N and log K.
Only log K bits are needed to represent K; thus an O(N K) solution is exponential in the input size.

10.57 (a) Let the minimum number of coins required to give x cents in change be COIN(x); COIN(0) = 0.

Then COIN(x) is one more than the minimum value of COIN(x − ci ), giving a dynamic programming
solution.
(b) Let WAYS(x , i) be the number of ways to make x cents in change without using the first i
coin types. If there are N types of coins, then WAYS(x , N ) = 0 if x! = 0, and WAYS(0, i) = 1. Then
WAYS(x , i − 1) is equal to the sum of WAYS(x − pci , i), for integer values of p no larger than x/ci
(but including 0).

10.58 (a) Place eight queens randomly on the board, making sure that no two are on the same row
or column. This is done by generating a random permutation of 1..8. There are only 5040 such
permutations, and 92 of these give a solution.

10.59 (a) Since the knight leaves every square once, it makes B 2 moves. If the squares are alternately
colored black and white like a checkerboard, then a knight always moves to a different colored
square. If B is odd, then so is B 2, which means that at the end of the tour the knight will be on a
different colored square than at the start of the tour. Thus the knight cannot be at the original square.

10.60 (a) If the graph has a cycle, then the recursion does not always make progress toward a base case,
and thus an infinite loop will result.
(b) If the graph is acyclic, the recursive call makes progress, and the algorithm terminates. This
could be proved formally by induction.
(c) This algorithm is exponential.

10.61 (a) A simple dynamic programming algorithm, in which we scan in row order suffices. Each square
computes the maximum sized square for which it could be in the lower right corner. That information
is easily obtained from the square that is above it and the square that is to its left.
(b) See the April 1998 issue of Dr. Dobb’s Journal for an article by David Vandevoorde on the maximal
rectangle problem.

10.66 The final score is 20-16, black wins.

85

C H A P T E R

11

Amortized Analysis

11.1

When the number of trees after the insertions is more than the number before.

11.2

Although each insertion takes roughly log N , and each deleteMin takes 2 log N actual time, our
accounting system is charging these particular operations as 2 for the insertion and 3 log N − 2 for the
deleteMin. The total time is still the same; this is an accounting gimmick. If the number of insertions
and deleteMins are roughly equivalent, then it really is just a gimmick and not very meaningful; the
bound has more significance if, for instance, there are N insertions and O(N/ log N ) deleteMins (in
which case, the total time is linear).

11.3

Insert the sequence N , N + 1, N − 1, N + 2, N − 2, N + 3, . . . , 1, 2N into an initially empty
skew heap. The right path has N nodes, so any operation could take (N ) time.

11.5

We implement decreaseKey(x) as follows: If lowering the value of x creates a heap order violation,
then cut x from its parent, which creates a new skew heap H1 with the new value of x as a root,
and also makes the old skew heap (H ) smaller. This operation might also increase the potential of
H , but only by at most log N. We now merge H and H1. The total amortized time of the merge is
O(log N ), so the total time of the decreaseKey operation is O(log N ).

11.8

For the zig-zig case, the actual cost is 2, and the potential change is Rf (X) + Rf (P ) + Rf (G) −
Ri (X) − Ri (P ) − Ri (G). This gives an amortized time bound of
ATzig−zig = 2 + Rf (X) + Rf (P ) + Rf (G) − Ri (X) − Ri (P ) − Ri (G)
Since Rf (X) = Ri (G), this reduces to
= 2 + Rf (P ) + Rf (G) − Ri (X) − Ri (P )
Also, Rf (X) > Rf (P ) and Ri (X) < Ri (P ), so
ATzig−zig < 2 + Rf (X) + Rf (G) − 2Ri (X)
Since Si (X) + Sf (G) < Sf (X), it follows that Ri (X) + Rf (G) < 2Rf (X) − 2. Thus
ATzig−zig < 3Rf (X) − 3Ri (X)

11.9

(a) Choose W (i) = 1/N for each item. Then for any access of node X, Rf (X) = 0, and Ri (X) ≥
− log N , so the amortized access for each item is at most 3 log N + 1, and the net potential drop
over the sequence is at most N log N, giving a bound of O(M log N + M + N log N ), as claimed.
(b) Assign a weight of qi /M to items i. Then Rf (X) = 0, Ri (X) ≥ log(qi /M), so the amortized
cost of accessing item i is at most 3 log(M/qi ) + 1, and the theorem follows immediately.

11.10 (a) To merge two splay trees T1 and T2, we access each node in the smaller tree and insert it into
the larger tree. Each time a node is accessed, it joins a tree that is at least twice as large; thus a node

87

88

Chapter 11

Amortized Analysis

can be inserted log N times. This tells us that in any sequence of N − 1 merges, there are at most
N log N inserts, giving a time bound of O(N log2 N ). This presumes that we keep track of the tree
sizes. Philosophically, this is ugly since it defeats the purpose of self-adjustment.
(b) Port and Moffet [6] suggest the following algorithm: If T2 is the smaller tree, insert its root into
T1. Then recursively merge the left subtrees of T1 and T2, and recursively merge their right subtrees.
This algorithm is not analyzed; a variant in which the median of T2 is splayed to the root first is with
a claim of O(N log N ) for the sequence of merges.

11.11 The potential function is c times the number of insertions since the last rehashing step, where c is
a constant. For an insertion that doesn’t require rehashing, the actual time is 1, and the potential
increases by c, for a cost of 1 + c.
If an insertion causes a table to be rehashed from size S to 2S, then the actual cost is 1 + dS,
where dS represents the cost of initializing the new table and copying the old table back. A table
that is rehashed when it reaches size S was last rehashed at size S/2, so S/2 insertions had taken
place prior to the rehash, and the initial potential was cS/2. The new potential is 0, so the potential
change is −cS/2, giving an amortized bound of (d − c/2)S + 1. We choose c = 2d, and obtain an
O(1) amortized bound in both cases.

11.12 We can (inductively) take a Fibonacci heap consisting of a single degenerate tree that extends as
deep as possible. Insert three very small items; do a deleteMin to force a merge. This leaves two of the
newer small items, one as a root, the other as a child of the root. Then do a decreaseKey on that child,
and then a deleteMin; now we have a longer degenerate tree. Thus the worst case is O(N ) depth.

11.13 (a) This problem is similar to Exercise 3.25. The first four operations are easy to implement by
placing two stacks, SL and SR , next to each other (with bottoms touching). We can implement the
fifth operation by using two more stacks, ML and MR (which hold minimums).
If both SL and SR never empty, then the operations can be implemented as follows:
push(x): push x onto SL; if X is smaller than or equal to the top of ML, push x onto ML as well.
inject(x): same operation as push, except use SR and MR .
pop(): pop SL; if the popped item is equal to the top of ML, then pop ML as well.
eject(): same operation as pop, except use SR and MR .
findMin(): return the minimum of the top of ML and MR .
These operations don’t work if either SL or SR is empty. If a pop or ej ect is attempted on an
empty stack, then we clear ML and MR . We then redistribute the elements so that half are in SL and
the rest in SR , and adjust ML and MR to reflect what the state would be. We can then perform the
pop or ej ect in the normal fashion. The following figure shows a transformation.

Define the potential function to be the absolute value of the number of elements in SL minus
the number of elements in SR . Any operation that doesn’t empty SL or SR can increase the potential
by only 1; since the actual time for these operations is constant, so is the amortized time.

Solutions

To complete the proof, we show that the cost of a reorganization is O(1) amortized time. Without
loss of generality, if SR is empty, then the actual cost of the reorganization is |SL| units. The potential
before the reorganization is |SL|; afterward, it is at most 1. Thus the potential change is 1 − |SL|,
and the amortized bound follows.

11.15 No; a counterexample is that we alternate between finding a node at the root (with splay) and a node
that is very deep (without splay).

11.16 The maximum potential is O(N log N ), for a splay tree of maximum depth. The minimum potential
is O(N ) for a balanced splay tree (the logic is similar to that used in analyzing the f ixH eap operation
for binary heaps.) The potential can decrease by at most O(N log N ), on that tree (half the nodes lose
all their potential). The potential can only increase by O(log N ), based on the splay tree amortized
bound.

11.17 (a) O(N log N ).
(b) O(N log log N ).

89

C H A P T E R

12

Advanced Data
Structures and
Implementation
12.3

Incorporate an additional field for each node that indicates the size of its subtree. These fields are
easy to update during a splay. This is difficult to do in a skip list.

12.6

If there are B black nodes on the path from the root to all leaves, it is easy to show by induction that
there are at most 2B leaves. Consequently, the number of black nodes on a path is at most log N .
Since there can’t be two consecutive red nodes, the height is bounded by 2 log N .

12.7

Color nonroot nodes red if their height is even and their parents height is odd, and black otherwise.
Not all red black trees are AVL trees (since the deepest red black tree is deeper than the deepest AVL
tree).

12.19 See H. N. Gabow, J. L. Bentley, and R. E. Tarjan, “Scaling and Related Techniques for Computational
Geometry,” Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (1984),
135–143, or C. Levcopoulos and O. Petersson, “Heapsort Adapted for Presorted Files,” Journal of
Algorithms 14 (1993), 395–413.

12.29 A linked structure is unnecessary; we can store everything in an array. This is discussed in reference
[12]. The bounds become O(k log N ) for insertion, O(k 2 log N ) for deletion of a minimum, O(k 2N )
for creation (an improvement over the bound in [12]).

12.35 Consider the pairing heap with 1 as the root and children 2, 3, . . . N . A deleteMin removes 1,
and the resulting pairing heap is 2 as the root with children 3, 4, . . . N ; the cost of this operation
is N units. A subsequent deleteMin sequence of 2, 3, 4, . . . will take total time (N 2).

91


Source Exif Data: 
File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.5
Linearized                      : Yes
XMP Toolkit                     : 3.1-701
Producer                        : Acrobat Distiller 7.0.5 (Windows)
Creator Tool                    : DVIPSONE 2.3.1  http://www.YandY.com
Modify Date                     : 2006:02:07 09:17:59-05:00
Create Date                     : 2006:02:07 09:17:59-05:00
Format                          : application/pdf
Title                           : mawcsol
Creator                         : Paul C. Anagnostopoulos 101 2004 Mar 15 13:52:07
Document ID                     : uuid:e6e393bb-6520-494d-bf67-1df07f5b4973
Instance ID                     : uuid:4973b297-d6ca-40de-bad2-951086f929f1
Page Count                      : 97
Author                          : Paul C. Anagnostopoulos 101 2004 Mar 15 13:52:07


EXIF Metadata provided by EXIF.tools










								

							
		
		

			
Navigation menu