Stephen B. Maurer - Discrete Algorithmic Mathematics, Third Edition

This table lists all the numbered algorithms in the book. All algorithms displayed in boxes in the text are numbered, as well as the more important algorithms displayed in boxes in the problems. In addition, there are numerous algorithm fragments both in the text and in the problems. The fragments and unnumbered algorithms illustrate some point and are generally not important algorithms in themselves. Number Name Output or Purpose Page 1.1 PowerA Computes integer powers of a number 1.2 PowerB Speed-up of 1.1 for some powers 1.3 PowerC Speed-up of 1.1 1.4 PrimeNum First K prime numbers 1.5 FiberNet Minimum cost links in a network 1.6 Euclid Greatest common divisor (gcd) of two integers 84, 123, 170 1.7 Euclid1 Possibly faster variant of 1.6 1.8 Euclid-RecFunc Recursive function version of 1.6 96, 163 1.9 Euclid-RecPro Recursive procedure version of 1.6 97, 165 1.10 Hanoi Towers of Hanoi 1.11 StringProc Process a string of characters 1.12 MaxNumber Maximum of n numbers 119, 587 1.13 SeqSearch Sequential search of a list 1.14 BinSearch Binary search of a list 127, 172 1.15 Euclid2 Possibly faster variant of 1.6 2.1 Hanoi Slight rewrite of 1.10 2.2 TOH Variant recursive procedure for Hanoi 2.3 EuclidRound-Func Possibly faster variant of 1.8 2.4 EuclidRound-Pro Possibly faster variant of 1.9 2.5 Euclid-RoundUp Possibly faster variant of 1.6 2.6 Iterative-TOH Non-recursive Towers of Hanoi 2.7 Sum-Search Find if one number is the sum of some others 2.8 EuclidZ Version of 1.6 that also works for negative integers 3.1 BuildTree Binary tree of a list of words 3.2 Warshall Path matrix of a graph 3.3 Pathgrow Grows a path in a graph 3.4 Ecycle An Eulerian cycle in a graph Number Name Output or Purpose Page 3.5 HamPath A Hamiltonian path in a complete graph 3.6 Dijkstra Shortest path in a weighted graph 3.7 BreadthFirstSearch Breadth first search of a connected graph 3.8 PathLength Lengths of all paths from a given vertex 3.9 DepthFirstSearch Depth first search of a connected graph 3.10 Bipartite Determine if a graph is 2-colorable 3.11 K-Colorable A proper coloring of a graph 3.13 Color-by-Vertices Variant of 3.11 3.13 One-Color-at-a-Time Different approach to coloring a graph 3.14 SpanTree Spanning tree of a graph 3.15 MinSpanTree Minimum weight spanning tree of a graph 3.16 BinaryTreeTraversal Three ways of traversing a binary tree 3.17 Ford Shortest path in a weighted graph 4.1 PermValue The permutation number P ( n, r) 4.2 PermValue2 The permutation number P ( n, r) 4.3 Permute-1 Random permutation of [ n] 388, 590 4.4 Permute-2 Random permutation of [ n] 390, 592 4.5 Permute-3 Random permutation of [ n] 4.6 AllPerm All permutations of [ n] 4.7 Monotonic Longest monotonic subsequence 5.1 Straightforward Polynomial evaluation 5.2 Horner Faster polynomial evaluation 5.3 FibA Fibonacci numbers 5.4 FibB Fibonacci numbers by recursion 5.5 PowerPoly Polynomial evaluation 6.1 BigNext Two largest of n numbers 7.1 Mult Integer multiplication 7.2 Insertion Insertion sort of a list E.1 StringAlign-Rec Optimal alignment of DNA strings E.2 StringAlign Iterative Optimal Alignment E.3 StringAlign2 Variant of E.2 E.4 ProjectSched Minimum completion time Discrete Algorithmic Mathematics This page intentionally left blank Discrete Algorithmic Mathematics Third Edition Stephen B Maurer Swarthmore College Anthony Ralston State University of New York at Buffalo A K Peters, Ltd. Wellesley, Massachusetts CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 2005 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business No claim to original U.S.

Government works Version Date: 20130204 International Standard Book Number-13: 978-1-4398-6375-6 (eBook - PDF) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to pub lish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint. Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, please access www.copyright.com (http://www.copy right.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400. CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site athttp://www.taylorandfrancis.comand the CRC Press Web site athttp://www.crcpress.com