Data Structures and Algorithm Analysis in C (second edition) Solutions Manual Mark Allen Weiss Florida International University Preface Included in this manual are answers to most of the exercises in the textbook Data Structures and Algorithm Analysis in C, second edition, published by Addison-Wesley. These answers refl ect the state of the book in the fi rst printing. Specifi cally omitted are likely programming assignments and any question whose solu- tion is pointed to by a reference at the end of the chapter. Solutions vary in degree of complete- ness; generally, minor details are left to the reader. For clarity, programs are meant to be pseudo-C rather than completely perfect code. Errors can be reported to weissfi u.edu. Thanks to Grigori Schwarz and Brian Harvey for pointing out errors in previous incarnations of this manual. Table of Contents 1. Chapter 1: Introduction 1 2. Chapter 2: Algorithm Analysis 4 3. Chapter 3: Lists, Stacks, and Queues .7 4. Chapter 4: Trees .14 5. Chapter 5: Hashing 25 6. Chapter 6: Priority Queues (Heaps) .29 7. Chapter 7: Sorting 36 8. Chapter 8: The Disjoint Set ADT .42 9. Chapter 9: Graph Algorithms .45 10. Chapter 10: Algorithm Design Techniques 54 11. Chapter 11: Amortized Analysis 63 12. Chapter 12: Advanced Data Structures and Implementation 66 -iii- Chapter 1: Introduction 1.3Because of round-off errors, it is customary to specify the number of decimal places that should be included in the output and round up accordingly. Otherwise, numbers come out looking strange.We assume error checks have already been performed; the routine Separate? is left to the reader. Code is shown in Fig. 1.1. 1.4The general way to do this is to write a procedure with heading void ProcessFile( const char *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 fi les for which a call to ProcessFile? has not yet terminated, and checking this list before making a new call to ProcessFile.? 1.5(a) The proof is by induction. The theorem is clearly true for 0 Next; AfterP = P-Next;/* Both P and AfterP assumed not NULL. */ P-Next = AfterP-Next; BeforeP-Next = AfterP; AfterP-Next = P; Fig. 3.2. _ _ _ _ (b) For doubly linked lists, the code is shown in Fig. 3.3. _ _ _ _ /* P and AfterP are cells to be switched. Error checks as before. */ void SwapWithNext( Position P, List L ) Position 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; Fig. 3.3. _ _ _ _ 3.4Intersect? is shown on page 9. -8- _ _ _ _ /* This code can be made more abstract by using operations such as*/ /* Retrieve and IsPastEnd to replace L1Pos-Element and L1Pos != NULL.*/ /* We have avoided this because these operations were not rigorously defi ned.*/ List Intersect( List L1, List L2 ) List Result; Position L1Pos, L2Pos, ResultPos; L1Pos = First( L1 ); L2Pos = First( L2 ); Result = MakeEmpty( NULL ); ResultPos = First( Result ); while( L1Pos != NULL else if( L1Pos-Element L2Pos-Element ) L2Pos = Next( L2Pos, L2 ); else Insert( L1Pos-Element, Result, ResultPos ); L1 = Next( L1Pos, L1 ); L2 = Next( L2Pos, L2 ); ResultPos = Next( ResultPos, Result ); return Result; _ _ _ _ 3.5Fig. 3.4 contains the code for Union.? 3.7(a) One algorithm is to keep the result in a sorted (by exponent) linked list. Each of the MN? multiplies requires a search of the linked list for duplicates. Since the size of the linked list is O?(MN?), the total running time is O?(M?2N?2). (b) The bound can be improved by multiplying one term by the entire other polynomial, and then using the equivalent of the procedure in Exercise 3.2 to insert the entire sequence. Then each sequence takes O?(MN?), but there are only M? of them, giving a time bound of O?(M?2N?). (c) An O?(MN?log MN?) solution is possible by computing all MN? pairs and then sorting by exponent using any algorithm in Chapter 7. It is then easy to merge duplicates afterward. (d) The choice of algorithm depen