PublisherGreg Tobin Senior Acquisitions EditorMichael Hirsch Editorial AssistantLindsey Triebel Marketing ManagerMichelle Brown Marketing AssistantDana Lopreato Digital Asset ManagerMarianne Groth CompositionWindfall Software, using ZzTEX ProofreadersMelanie Aswell, Debbie Sidman Access the latest information about Addison-Wesley titles from our World Wide Web site: http:/www.aw- bc.com/computing Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks.Wherethosedesignationsappearinthisbook, andAddison-Wesleywasawareofatrademark 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 10PDF08 07 06 05 CONTENTS Prefacev Chapter 1 Introduction1 Chapter 2 Algorithm Analysis5 Chapter 3 Lists, Stacks, and Queues9 Chapter 4 Trees29 Chapter 5 Hashing41 Chapter 6 Priority Queues (Heaps)45 Chapter 7 Sorting53 Chapter 8 The Disjoint Set59 Chapter 9 Graph Algorithms63 Chapter 10 Algorithm Design Techniques77 Chapter 11 Amortized Analysis87 Chapter 12 Advanced Data Structures and Implementation91 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 refl ect the state of the book in the fi rst printing of the third edition. Specifi cally omitted are general programming questions and any question whose solution is pointedtobyareferenceattheendofthechapter.Solutionsvaryindegreeofcompleteness; 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 weissfi u.edu. v C H A P T E R1 Introduction 1.4The general way to do this is to write a procedure with heading void processFile( String fileName ); which opens fi leName, 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 fi les for which a call to processFile has not yet terminated, and checking this list before making a new call to processFile. 1.5int ones( int n ) if( n v(3); v0.setValue(“George Bush“, 400000.00); v1.setValue(“Bill Gates“, 2000000000.00); v2.setValue(“Dr. Phil“, 13000000.00); cout 1, the number of multiplies used is ?log N? + b(N) 1 2.25(a) A. (b) B. (c) Theinformationgivenisnotsuffi cienttodetermineananswer.Wehaveonlyworst-casebounds. (d) Yes. 2.26(a) Recursion is unnecessary if there are two or fewer elements. (b) Onewaytodothisistonotethatifthefi rstN 1elementshaveamajority, thenthelastelement 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 Nthelement as a candidate. (c) The running time is O(N), and satisfi es 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 Biin 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.27Start 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 aj ai is larger than the current best, update the best 8Chapter 2Algorithm Analysis difference. If ajis less than ai, 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.29Otherwise, 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.31No. If low = 1, high = 2,