A Creative ApproachINTRODUCTION TO ALGORITHMS A Creative Approach UDI MANBER University af Arizona UNICAMP pee eensLibrary of Congress Cataloging-in-Publication Data Manber, Udi. Introduetion to algorithms, Includes bibliographies and index. i. Data stmctures (Computer science) 2. Algorithms. L Title. QAT6.9.DISM36 1989 OO5.7°3 88-2186 ISBN 0-201-12037-2 Reproduced by Addison-Wesley from camera-ready copy supplied by the author. The programs and applications presented in this book have been included for their instructional value. They have been tested with cane, but are not guaranteed for any purpose. The publisher does not offer any warranties o representation, nor does it accept any liabilities with respect to the programs o¢ applications. Reprinted with enrrecsions Ociober, 1989 Copyright © 1989 by Addison-Wesley Publishing Gompany Inc. All rights reserved. No part of this publication may be reproduced, stored im a recrieval system, or transmitted, in any form or by amy means, electronic, mechanical, photocopying, recording. or otherwise, without prior written permission of the publisher. Printed in the United States of America, Published simultancously in Canada. 18 19 20-D0C-01 On a —.a To my parents Eva and Meshulam Ger waePREFACE ‘This book grew out of my frustrations with not being able to explain algorithms cleserly. Like many other teachers, I discovered that not only is it hard for some students to solve (what seemed to me) simple problems by themselves, bur it is also hard for them to understand the solutions that are given to them. [ believe thar these two parts — the Creation amd the explanation — are related and should not be separated, It is essential to follow the steps leading to a solution in ander to understand it fully. Ic is not sufficient to Fook at the finished product. ‘This book emphasizes the creative side of algorithm design, Its main purpase is wv show the reader how i design a new algorithm, Algorithms are not described in a sequence of “problem ., algorithm A, alzorithm A’. program P, program P’,’* and so on, Instead. the sequence usually (although not always) looks more like “problem X, the sunightforward algorithm, its drawbacks. the difficulties overcoming these drawbacks, first attempts at a better algorithm (including possible wrong turns), improvements, analysis, relation 10 other methods and algorithms.”* and so on, ‘The goal is to present an algorithm ot ina way that makes it easier for a programmer to translate into x program, but rather ina way that makes it easier to understand the algorithm's principles, ‘The ~ algorithins are. thus exphiined through a creative process, rather than as finished products. Our goals in teaching algorithms are to show not only how to salve particular problems, but also how to solve new problems when they arise in the future. Teaching the thinking involved in designing an algorithm is us important as teaching the details of the solution. To further help the thinking process involved im creating algorithms. an “old-new" methodology for designing algorithms is used in this book. This methodology covers many Known techniques for designing algorithms. and it also Provides an elegant intuitive framework for expluning the design of algorithms in more depth. It does not, however, cover all possible ways of designing algorithms, and we do fol use it exclusively, The heart of the methodology lies in an analogy berween the ‘ellcctual process of proving mathematical theonems by induction and that of designing combinatorial algorithms. Although these two processes serve differeat purposes and achieve different types of results, they are more similar than they may appear to be. This analogy has been observed by many people. The novelty of this book is the degree to which this analogy is exploited. We show thar the analogy encompasses many known algonthm-design techniques, sm helps considerably in the process of algorithm creation. ‘The methodology is discussed briefly in Chapter 1 and is introduced move formally in ‘Chapter 5.Consider the following analogy. Suppose that you arrive at an unfamiliar city, rent a car, and want directions to get to your hotel. You would be quite impatient if you were told about the history of the city, its general layout, the traffic patterns, and so on. You would rather have directions of the form “go straight for two blocks, turn right, go and so on. However, your outlook would change if you planned to live in that city for a long time. You could probably get around for a while with directions of the second form (if you find someone who gives you those directions), but eventually you will need to know more about the city. This book is not a source of easy directions. It does contain explanations of how to solve many particular problems, but the emphasis is on general principles and methods. As a result, the book is challenging. It demands involvement and thinking. I believe that the extra effort is well worthwhile. The design of efficient nonnumeric algorithms is becoming important in many diverse fields, imeluding mathematics, statistics, molecular biology, and engineering. This book can serve as an introduction to algorithms and to nonnumeric computations in general. Many professionals, and even scientists not deeply invelved with computers, believe that programming is nothing more than grungy nonintellectual work. It sometimes is. But such a belief may lead to straightforward, trivial, inefficient solutions, where elegant. more efficient solutions exist. One goal of this book is to convince readers that algorithm design is an elegant discipline, as well as an important one. The book is self-contained. The presentation is mostly intuitive, and technicalities are either kept to a minimum or are separated from the main discussion, In particular, implementation details are separated from the algorithm-design ideas as much as possible. There are many examples of algorithms that were designed especially to illustrate the principles emphasized in the book. The material in this book is not presented as something to be mastered and memorized. It is presented as a series of ideas, examples, counterexamples, modifications, improvements, and so on. Pseudo- codes for most algorithms are given following the descriptions. Numerous exercises and a discussion of further reading. with a relevant bibliography, follow each chapter. In most chapters, the exercises are divided into two classes, drill exercises and creative exereises, Drill exercises are meant to test the reader's understanding of the specific examples and algorithms presented in that chapter. Creative exercises are meant to test the reader's ability to use the techniques developed in that chapter, in addition to the particular algorithms, to solve new problems, Sketches of solutions to selected exercises (those whose numbers are underlined) are given at the end of the book. The chapters also include 2 summary of the main ideas introduced The book is organized as follows. Chapters 1 through 4 present introductory material. Chapter 2 is an introduction to mathematical induction, Mathematical induetion is, as we will sce, very important to algorithm design. Experience with induction proofs is therefore very helpful. Unfortunately, few computer-science students get enough exposure to induction proofs, Chapter 2 may be quite difficult for some students. We suggest skipping the more difficult examples at first reading, and returning to them later. Chapter 3 is an introduction to the analysis of algorithms, It describes the process of analyzing algorithms, and gives the basic tools one needs to be able to perform straight for three miles,”viii Preface Jefferey H. Kingston (University of Iowa), Victor Klee (University of Washington), Charles Martel (University of California, Davis), Michael J. Quinn (University of New Hampshire), and Diane M. Spresser (James Madison University). I thank the people at Addison-Wesley who failed to supply me with any examples of horror stories that authors are so fond of telling. They were very helpful and incredibly patient and understanding. In particular, 1 thank my production supervisor Bette Aaronson, my editor Jim DeWolf, and my copy editor Lyn Dupré, who not only guided me but also let me do things my way even when they knew better. I also thank the National Science Foundation for financial support, through a Presidential Young Investigator Award, and AT&T, Digital Equipment Corporation, Hewlett Packard, and Tektronix, for matching funds. The book was designed and typeset by me. It was formatted in troff, and printed on a Linotronic 300 at the Department of Computer Science, University of Arizona. I thank Ralph Griswold for his advice, and John Luiten, Allen Peckham, and Andrey Yeatts for technical help with the typesetting. The figures were prepared with gremlin — developed at the University of California, Berkeley — except for Fig. 12.22, which was designed and drawn by Gregg Townsend. The index was compiled with the help of a system by Bentley and Kernighan (1988). I thank Brian Kernighan for supplying me the code within minutes after I (indirectly) requested it. The cover was done by Marshall Henrichs, based on an idea by the author. I must stress, however, that the final manuscript was prepared by the typesetter. He was the one who decided to overlook many comments and suggestions of the people listed here. And he is the one who should bear the consequences. Tucson, Arizona Udi Manber (intemet address: udi@arizona.edu.)Chapter 1 Introduction 1 Chapter 2 Mathematical Induction 9 Introduction Three Simple Examples Counting Regions in the Plane A Simple Coloring Problem A More Complicated Summation Problem A Simple Inequality Euler’s Formula A Problem in Graph Theory Gray Codes Finding Edge-Disjoint Paths in a Graph Arithmetic versus Geometric Mean Theorem Loop Invariants: Converting a Decimal Number to Binary Common Errors Summary Bibliographic Notes and Further Reading Exercises Chapter 3 Analysis of Algorithms 37 3.1 Introduction 3.2 The O Notation 3.3 Time and Space Complexity 3.4 Summations 3.5 _ Recurrence Relations 3.5.1 Intelligent Guesses 3.5.2. Divide and Conquer Relations Recurrence Relations with Full History 3.6 Useful Facts 37 Summary Bibliographic Notes and Further Reading Exercises 37 39 42 43 46 47 50 SI 3S 55 56x Contents Chapter 4 Data Structures 61 4.1 Introduction 4.2 Elementary Data Structures 4.2.1 Elements 422 Arrays 4.2.3. Records 42.4 Linked Lists 4.3 Trees 4.3.1 Representation of Trees 43.2 Heaps Binary Search Trees Ee AVL Trees 4.4 Hashing 4.5 The Union-Find Problem 4.6 Graphs 4.7 Summary Bibliographic Notes and Further Reading Exercises Chapter 5 Design of Algorithms by Induction 91 5.1 Introduction 5.2 Evaluating Polynomials 5.3 Maximal Induced Subgraph 54 Finding One-to-One Mappings 5.5 The Celebrity Problem 5.6 A Divide-and-Conquer Algorithm: The Skyline Problem 5.7 Computing Balance Factors in Binary Trees 5.8 Finding the Maximum Consecutive Subsequence 5.9 Strengthening the Induction Hypothesis 5.10 Dynamic Programming: The Knapsack Problem 5.11 Common Errors 5.12 Summary Bibliographic Notes and Further Reading Exercises Chapter 6 Algorithms Involving Sequences and Sets 119 6.1 Introduction 62 Binary Search and Variations 63 Interpolation Search 64 Sorting 6.4.1 Bucket Sort and Radix Sort 6.4.2. Insertion Sort and Selection Sort 6.4.3. Mergesort 61 62 62 63 63 64 66 67 68 zat 15 78 80. 83 84 85 86 91 92 95 96 98 102 104 106 107 108, 1 112 113 14 119 120 125 127 127 130 130Chapter 7 Contents 6.4.4 Quicksort 6.4.5 Heapsort 6.4.6 A Lower Bound for Sorting 65 Order Statistics 6.5.1 Maximum and Minimum Elements 6.5.2 Finding the kth-Smallest Element 6.6 Data Compression 6.7 — String Matching 68 Sequence Comparisons 6.9 Probabilistic Algorithms 6.9.1 Random Numbers 6.9.2 A Coloring Problem 6.9.3 A Technique for Transforming Probabilistic Algorithms into Deterministic Algorithms 6.10 Finding a Majority 6.11 Three Problems Exhibiting Interesting Proof Techniques 6.11.1 Longest Increasing Subsequence 6.11.2. Finding the Two Largest Elements in a Set 6.11.3 Computing the Mode of a Multiset 6.12 Summary Bibliographic Notes and Further Reading Exercises Graph Algorithms 185 7.1 Introduction 7.2 Eulerian Graphs 7.3 Graph Traversals 7.3.1 Depth-First Search 7.3.2, Breadth-First Search 7.4 — Topological Sorting 7.5 Single-Source Shortest Paths 7.6 Minimum-Cost Spanning Trees 7.7 All Shortest Paths 7.8 Transitive Closure 7.9 Decompositions of Graphs 7.9.1 Biconnected Components 7.9.2 Strongly Connected Components 7.9.3, Examples of the Use of Graph Decomposition 7.10 Matching 7.10.1 Perfect Matching in Very Dense Graphs 7.10.2. Bipartite Matching 7.11 Network Flows 7.12 Hamiltonian Tours 7.12.1 Reversed Induction xi 131 137 141 143 143 145 148 155, 158 160, 161 161 164 167 167 169 171 173 173 175 185 201‘xii Contents 7.12.2. Finding Hamiltonian Cycles in Very Dense Graphs 7.13 Summary Bibliographic Notes and Further Reading. Exercises Chapter 8 Geometric Algorithms 265 8.1 Introduction 8.2. Determining Whether a Point Is Inside a Polygon 8.3 Constructing Simple Polygons 84 Convex Hulls 8.4.1 A Straightforward Approach 8.4.2. Gift Wrapping 8.4.3 Graham’s Scan 8.5 Closest Pair 8.6 _ Intersections of Horizontal and Vertical Line Segments 8.7 Summary Bibliographic Notes and Further Reading Exercises Chapter 9 Algebraic and Numeric Algorithms 293 9.1 Introduction 9.2 — Exponentiation 9.3. Euclid’s Algorithm 9.4 Polynomial Multiplication 9.5 Matrix Multiplication 9.5.1 Winograd’s Algorithm 9.5.2 Strassen’s Algorithm 9.5.3 Boolean Matrices 9.6 The Fast Fourier Transform 9.7 Summary Bibliographic Notes and Further Reading Exercises Chapter 10 Reductions 321 10.1. Introduction 10.2 Examples of Reductions 10.2.1 A Simple String Matching Problem 10.2.2 Systems of Distinct Representatives 10.2.3. A Reduction Involving Sequence Comparisons 10.2.4 Finding a Triangle in Undirected Graphs 10.3. Reductions Involving Linear Programming 10.3.1 Introduction and Definitions 10.3.2 Examples of Reductions to Linear Programming 244 246 247 248 265 266 270 273 273 274 275 278 281 285 286 287 293 294 297 298 301 301 301 304 309 316 316 317 327 329Contents xiii 10.4 Reductions for Lower Bounds 331 10.4.1 A Lower Bound for Finding Simple Polygons 331 10.4.2 Simple Reductions Involving Matrices 333 10.5 Common Errors 334 10.6 Summary 336 Bibliographic Notes and Further Reading 336 Exercises 337 Chapter 11 NP-Completeness 341 11.1 Introduction 341 11.2. Polynomial-Time Reductions 342 11.3. Nondeterminism and Cook’s Theorem 344 11.4 Examples of NP-Completeness Proofs 347 11.4.1 Vertex Cover 348 11.4.2. Dominating Set 348 3SAT 350 Clique 351 3-Coloring 352 11.4.6 General Observations 355 11.4.7 More NP-Complete Problems 356 11.5 Techniques For Dealing with NP-Complete Problems 357 11.5.1 Backtracking and Branch-and-Bound 358 11.5.2. Approximation Algorithms with Guaranteed Performance 363 11.6 Summary 368 Bibliographic Notes and Further Reading 368 Exercises 370 Chapter 12 Parallel Algorithms 375 12.1 Introduction 375 12.2 Models of Parallel Computation 376 12.3 Algorithms for Shared-Memory Machines 378 12.3.1 Parallel Addition 379 12.3.2. Maximum-Finding Algorithms 380 12.3.3. The Parallel-Prefix Problem 382 12.3.4 Finding Ranks in Linked Lists 385 12.3.5. The Euler’s Tour Technique 387 12.4 Algorithms for Interconnection Networks 389 12.4.1 Sorting on an Array 390 124.2. Sorting Networks 393 12.4.3, Finding the kth-Smallest Element on a Tree 396 12.4.4 Matrix Multiplication on the Mesh 398 12.4.5 Routing in a Hypercube 401xiv Contents 12.5. Systolic Computation 12.5.1 Matrix-Vector Multiplication 12.5.2. The Conyolution Problem 12.5.3 Sequence Comparisons 12.6 Summary Bibliographic Notes and Further Reading Exercises Sketches of Solutions to Selected Exercises References Index 417 465 404 404 405 407 409 411GHEASP EB Rawk INTRODUCTION Great importance has been rightly attached to this process of “construction,” and some claim to see in it the necessary and sufficient condition of the progress of the exact sciences. Necessary, no doubt, but not sufficient! For a construction to be useful and not mere waste of ‘mental effort. for it to serve as a stepping-stone to higher things, it must first of all possess a kind of unity enabling us 10 see something more than the juxtaposition of its elements, Henri Poincaré, 1902 The Webster's Ninth New Collegiate dictionary defines an algorithm as “‘a procedure for solving a mathematical problem (as of finding the greatest common divisor) in a finite number of steps that frequently involves a repetition of an operation; or broadly: a step- by-step procedure for solving a problem or accomplishing some end.” We will stick to the broad definition. The design of algorithms is thus an old field of study. People have always been interested in finding better methods to achieve their goals, whether those be starting fires, building pyramids, or sorting the mail. The study of computer algorithms is of course new. Some computer algorithms use methods developed before the invention of computers, but most problems require new approaches. For one thing, it is not enough to tell a computer to “‘look over the hill and sound the alarm if an army is advancing.”” A computer must know the exact meaning of “‘look,”’ how to identify an army, and how to sound the alarm (for some reason, sounding an alarm is always easy). A computer receives its instructions via well-defined, limited primitive operations. It is a difficult process to translate regular instructions to a language that a computer understands. This necessary process, called programming, is now performed on one level or another by millions of people.2 Introduction Programming a computer, however, requires more than just translating well- understood instructions to a language a computer can understand. In most cases, we need to devise totally new methods for solving a problem. It is not just learning the weird language in which we “talk” to a computer that makes it hard to program: it is knowing what to say. Computers execute not only operations that were previously performed by humans: with their enormous speed, computers can do much more than was ever possible. Algorithms of the past dealt with dozens, maybe hundreds of items, and, at most, with thousands of instructions, Computers can deal with billions, or even trillions, of bits of information, and can perform millions of (their primitive) instructions per second. Designing algorithms on this order of magnitude is something new. It is in many respects counterintuitive. We are used to thinking in terms of things we can see and feel. As a result, there is a tendency when designing an algorithm to use the straightforward approach that works very well for small problems. Unfortunately, algorithms that work well for small problems may be terrible for large problems. It is easy to lose sight of the complexity and inefficiency of an algorithm when applied to large-scale computations. There is another aspect to this problem. The algorithms we perform in our daily life are not too complicated and are not performed too often. It is usually not worthwhile to expend a lot of effort to develop the perfect algorithm. The payoff is too small. For example. consider the problem of unpacking grocery bags. There are obviously less efficient and more efficient ways of doing it, depending on the contents of the bags and the way the kitchen is organized. Few people spend time even thinking about this problem, much less developing algorithms for it. On the other hand, people who do large-scale commercial packing and unpacking must develop good methods. Another example is mowing the lawn. We can improve the mowing by minimizing the number of turns, the total time for mowing, or the length of the trips to the garbage cans. Again, ‘one really hates mowing the lawn, one would not spend an hour figuring out how to save a minute of mowing. Computers, on the other hand, can deal with very complicated tasks. and they may have to perform those tasks many times. It is worthwhile to spend a lot of time designing better methods, even if the resulting algorithms are more complicated and harder to understand. The potential of a payoff is much greater. (Of course, we should not overoptimize, spending hours of programming time to save overall a few seconds of computer time.) These two issues — the need for counterintuitive approaches to large-scale algorithms and the possible complexities of these algorithms — point to the difficulties in learning this subject. First, we must realize that straightforward intuitive methods are not always the best. It is important to continue the search for better methods. To do that, we need of course, to learn new methods. This book surveys and illustrates numerous methods for algorithm design. But it is not enough to learn even a large number of methods, just as it is not enough to memorize many games of chess in order to be a good player. One must understand the principles behind the methods. One must know how to apply them and, more important, when to apply them. A design and implementation of an algorithm is analogous to a design and unle:Introduction 3 construction of a house.' We start with the basic concepts, based on the requirements for the house. It is the architect’s job to present a plan that satisfies the requirements. It is the engineer’s job to make sure that the plan is feasible and correct (so that the house will not collapse after a short while). It is then the builder's job to construct the house based on these plans. Of course, all along the way, the costs associated with each step must be analyzed and taken into account. Each job is different, but they are all related and intertwined. A design of an algorithm also starts with the basic ideas and methods. Then, a plan is made. We must prove the correctness of the plan and make sure that its cost is effective. The last step is to implement the algorithm for a particular computer. Risking oversimplification, we can divide the process into four steps: design, proof of correctness, analysis, and implementation. Again, each of these steps is different, but they are all related. None of them can be made in a vacuum, without a regard to the others. One rarely goes through these steps in linear order. Difficulties arise in all phases of the construction. They usually require modifications to the design, which in turn require another feasibility proof, adjustment of costs, and change of implementation. ‘This book concentrates on the first step, the design of algorithms. Following our analogy, the book could have been entitled The Architecture of Algorithms. However, ‘computer architecture has a different meaning, so using this term would be confusing. The book does not, however, ignore all the other aspects. A discussion of correctness, analysis, and implementation follows the description of most algorithms — in detail for some algorithms, briefly for others. The emphasis is on methods of design. It is not enough to lea many algorithms to be a good architect and to be able to design new algorithms. One must understand the principles behind the design. We employ a different way of explaining algorithms in this book. First, we try to lead the reader to find his or her own solution; we strongly believe that the best way to learn how to create something is to try to create it. Second, and more important, we follow a methodology for designing algorithms that helps this creative process. The methodology, introduced in Manber [1988]. provides an elegant intuitive framework for explaining the design of algorithms in more depth. It also provides a unified way to approach the design. The different methods that are encompassed by this methodology, and their numerous variations, are instances of the same technique. The process of choosing among those many possible methods and applying them becomes more methodical. This methodology does not cover all possible ways of designing algorithms. It is useful, however, for a great majority of the algorithms in this book. The methodology is based on mathematical induction. The heart of it lies in an analogy between the intellectual process of proving mathematical theorems and that of designing combinatorial algorithins. The main idea in the principle of mathematical induction is that a statement need not be proven from scratch: It is sufficient to show that the correctness of the statement follows from the correctness of the same statement for smaller instances and the correctness of the statement for a small base case. Translating this principle to algorithm design suggests an approach that concentrates on extending ' The two wonderful books by Tracy Kidder, The Soul of a New Machine (Little Brown, 1981), and House (Houghton Miffin, 1985), inspired this analogy4 Introduction solutions of small problems to solutions of large problems. Given a problem, if we can show how to solve it by using a solution of the same problem for smaller inputs, then we are done. The basic idea is to concentrate on extending a solution rather than on building it from scratch. As we will show in the following chapters, there are many ways of doing this, leading to many algorithm design techniques. ‘We use mathematical induction mainly as a tool for explaining and designing high-level algorithms. We make little attempt to formalize or axiomize the approach. This has been done by several people, including Dijkstra [1976], Manna [1980], Gries [1981], Dershowitz [1983], and Paull [1988], among others. This book complements these other books. Our goal is mainly pedagogical, but of course whenever something can be explained better it is usually understood better. Among the proof techniques we discuss are strengthening the induction hypothesis, choosing the induction sequence wisely, double induction, and reverse induction. The significance of our approach is two-fold, First, we collect seemingly different techniques of algorithm design under one umbrella: second, we utilize known mathematical proof techniques for algorithm design. The latter is especially important, since it opens the door to the use of powerful techniques that have been developed for many years in another discipline. ‘One notable weakness of this approach is that it is not a universal approach. Not all algorithms can or should be designed with induction in mind. However, the principle of induction is so prevalent in the design of algorithms that it is worthwhile to concentrate on it. The other principles are not ignored in this book. A common criticism of almost any new methodology is that, although it may present an interesting way to explain things that were already created, it is of no help in creating them. This is a valid criticism, since only the future will tell how effective a certain methodology is and how widely used it becomes. I strongly believe that induction is not only just another tool for explaining algorithms, but it is necessary in order to understand them. Personally, even though I had a good experience in developing algorithms without following this methodology, I found it helpful, and, at least in two cases, it led me to develop new algorithms more quickly (Manber and McVoy [1988], Manber and Myers [1989]). Notation for Describing Algorithms In addition to describing the algorithms through the creative process of their development, we also include pseudocodes for many algorithms. The purpose of including programs is to enkance the descriptions. We have not made a great effort to optimize the programs, and we do not recommend simply copying them. In some cases, we made a conscious decision not to include the most optimized version of the program, because it introduces additional complexity, which distracts from the main ideas of the algorithm. We sometimes do not explain in detail how we translate the algorithmic ideas into a program. Such translations sometimes are obvious and sometimes are not. The emphasis in this book, as we mentioned, is on the principles of algorithm design. For the most part, we use a Pascal-like language (sometimes even pure Pascal). In many cases, we include high-level descriptions (such as ‘‘insert into a table,” or “check whether the set is empty”’) inside a Pascal code to make it more readable. One notable exception we make to the rules of Pascal is the use of begin and end to encompassExercises 5 blocks. We include these statements only at the beginning and end of the programs, and let the indentation separate the blocks. This convention saves space without causing ambiguities. We usually do not include precise declarations of variables and data types in cases where such declarations are clear (e.g.. we may say that G is a graph, or that Tis a tree). Exercises L Exercises whose numbers are underlined have solutions at the back of the book. Exercises that are marked by a star are judged by the author to be substantially more difficult than other exercises, The exercises in this chapter do not require any previous knowledge of algorithms. They address relatively simple problems for specific inputs. The reader is asked to find the answers by hand. The main purpose of these exercises is to illustrate the difficulty in dealing with a very large number of possibilities. In other words, one of the goals of these exercises is to cause frustration with straightforward methods. The problems given here will be discussed in the following chapters. Ll ‘Write down the numbers 1 to 100 each on a separate card. Shuffle the cards and rearrange them in order again. 12 Write down the following 100 numbers each on a separate card and sort the cards. Think about the differences between this exercise and Exercise 1.1. 32918 21192 11923 4233 88231 8312 11 72 971 8234 22238 49283 3295 29347 3102 32883 20938 2930 16 823 9234 9236 29372 2218 9222 21202 83721 9238 8221 30234 93920 81102 1011 18152 2831 29133 9229 10039 9235 48395 2832 37927 73492 8402 48201 38024 2800 32155 2273 82930 2221 3841 311 3022 38099 29920 28349 74212 7011 1823 903 2991 9335 29123 28910 29281 3772 20012 70458 30572 38013 72032 28001 83835 3017 92626 73825 29263 2017 262 8362 77302 8593 3826 9374 2001 83261 48402 4845 79794 27271 39992 22836 444 2937 37201 37322 49472 11329 2253 13° Consider the following list of numbers. Your job is to erase as few of those numbers as possible such that the remaining numbers appear in increasing order. For example, erasing everything except the first two numbers leaves an increasing sequence; erasing everything except for first, third, sixth, and eighth numbers, does the same (but fewer numbers are erased). 9 44 32 12 7.42 34 92 35 37 41 8 20 27 83 64 61 28 39 93 29 17 13 14.55 21 66 72 23 73 99 1 288 77 3 65 83 84 62 5 11 74.68 76 78 67 75 69 70 22 71 24.25 26 1.4 Solve Exercise 1.3, such that the remaining numbers are in decreasing onder. 1.5 Suppose that in a strange country there are five types of coins with denominations of 15, 23, 29, 41, and 67 (all cents). Find a combination of these coins to pay the sum of 18 dollars and 8 cents (1808 cents). You have enough coins of each type in your pocket.6 1.6 17 18 19 1.10 Introduction The input is a list of pairs of integers given below. The meaning of pair (x, y) is that x is waiting for an answer from y. When x is waiting. it cannot do anything else, and, in particular, it cannot answer any questions from others that may be waiting for it. The problem is to find a sequence of pairs (x3), (tps). °*7 + (th-1-%1)> (44 ¥1), for some k > 1 (any & will do). If such a sequence exists, then there is a deadlock. No one can proceed, since everyone is waiting for someone else. You can use a pencil and a piece of paper, and make any kind of computation, involving numbers (e.g., comparisons, creating tables); however, you cannot draw any kind of @ figure. (You may draw figures, unrelated to this particular input, to help you design a ‘general method of solving such a problem.) 1 16,221,225, 2 22, 23 50, 23 47, 24 1, 25 10, 35 7, 36 45, 36 37, 38 42, 39-41, 12 37, 1223, 123, 1 3.22, 292, 3048, 31 15,3217, 6.45, 6 1,535, 5 20, 5 28, 5 11, 48 4, 48 10, 49 32, 731,74, 5 33, 629, 6 12, 6 11, 6 3, 6 17, 45 27, 47 34, 48 20, 7 40, 7 34,8 11, 919, 11 30, 114, 11 22, 11 25, 20 24, 21 23, 21 46, 22 47, 23 49, 3 39, 3 34,4 14, 437, 5 42, 58, 152, 15 50, 15 4, 15 37, 16 13, 17 38, 18 28, 19 8, 26 15, 26.42, 27 18, 28 35, 13 36, 13 50, 13 34, 13 22, 29 34, 29 38, 29 30, 29 16, 44 33, 44 36, 44 7, 44 3, 44 32, 44 21, 33 9, 33 21, 33 35, 33 19, 33 41, 26 10, 26 44, 26 16, 26 39, 26 17 ‘The input is the two-dimensional 15 by 15 table given in Fig. 1.1. The ith row and the ith column (for any i) correspond to the same place. Each entry in the table indicates the direct distance between the places in the corresponding row and column. The “-"" symbol indicates that there is no direct link between the two places. The direct distance may not be the shortest distance. There may be a shorter path between two places going through a third place (or several places). For example. the shortest route between 1 and 6 is through 5 and 12. Find the shortest route between | and 15, between 4 and 3, and between 15 and 8. Consider the table in Fig, 1.1. Find the shortest route between 5 and all other places. Consider the graph shown in Fig. 1.2. Find a closed route along the edges of the graph Which includes every vertex exactly once. (This graph corresponds to the edges of a dodecahedron; this puzzle was first described by the Irish mathematician Sir William R. Hamilton, and we discuss it furtherin Section 7.12.) The following is a regular maze problem, with the exception that the maze is given in numeric representation (rather than a picture). The maze is contained in a rectangle with 11 rows and columns, numbered from 0 to 10, The maze is traversed along the rows and columns — up, down, right, or left. The starting point is 0,0 and the target is 10,10. The following points are obstacles you cannot traverse through: (32) (6.6) (7.0) (2,8) 6.9) (8.4) (2.4) 8) (1,3) (6.3) 9,3) 0.9) B.0) G.7) (4.2) (7.8) (2.2) 4.5) (5,6) (10,5) (6.2) (6,10) (4,0) (7.5) (7.9) (81) (5.7) (4A) (8.7) (9.2) (10,9) (2.6) a. Find a path from the starting point to the target that does not include any of the obstacles. b. Find a shortest path from the starting point to the target that does not include any of the obstacles.Exercises 7 1]2[2J¢]s[e[7][s]9] 2] 3 a [as MRS ahs Llu deouatslan 2 Suis ase |On| oed| ae2| San sort a 1 rhea See i ee a ie ea 4[-[38]- 23) [= See on tr tee 9|/-|8 2 EEF 8 - 1 = 4 2 ofS 2 Seo seo) rect 8 rae |*2 8} -|o0]6/2 - 8 8 3 S 4 alt Diesels beaten Siecle Laas Sa ules] 29s) aos aaleomles ochre | [oye lather eed] 008 | aaa sel lee 2 nls [s[7[ay-]-[s[et-] -7 of2peye2 ta n]3 HL Pe aie SS fa) oor [ra tool iS Leap | lealesalee Ico to [ane 4 [2[9p6]-17][-]9 PMSaaes, (alae 9. |605 | a5) |e2 | Oa[2a|t-| [= | wile eee eea Sata Figure 1.1 The table for Exercises 1.7 and 1.8. 1.11 Find the greatest common divisor of 225277 and 178794, (The greatest common divisor of Wo integers is the largest number that divides both of them.) 1.12 Compute the value of 2". Try to find a way to minimize the number of multiplications. Figure 1.2. Hamilton’s puzzle.8 Introduction 1.13 The following list represents the number of Presidential clection (the candidate receiving t the electoral votes for that state). whether it, is (mathematically) possi Known as the partition problem, and it is discussed in Section 5.10.) ‘Alabama Arkansas Connecticut Georgia Illinois, Kansas Maine Michigan Missouri Nevada New Mexico North Dakota Oregon South Carolina Texas Virginia West Virginia awed oe Bee eo < Ar perenne There are altos Alaska California Delaware Hawaii Indiana Kentucky Maryland Minnesota Montana New Hampshire New York Ohio Pennsylvania South Dakota Utah Washington Wisconsin ble for the election to end up in a tic. ig a special case of the knapsack problem Leuuppereese ee! Bato Soon aS Arizona Colorado Florida Idaho: Tow. Loui Massachusetts, Mississippi ‘Nebraska ‘New Jersey North Carolina Oklahoma Rhode Island Tennessee ‘Vermont Washington, D.C. ‘Wyoming electoral votes for each state in the 1988 the majority of the votes in # state collects all gether 538 clectoral votes. Determine (This problem isCHAPTER 2 MATHEMATICAL INDUCTION No one believes an hypothesis except its originator, but everyone believes an experiment except the experimenter. Anon Obviousness is always the enemy of correctness Bertrand Russell (1872-1970) 2.1 Introduction We will see in the following chapters that induction plays a major role in algorithm design. In this chapter, we present a brief introduction to mathematical induction through examples. The examples range from easy to quite difficult. Readers who have not seen many induction proofs may find this chapter to be relatively hard. We claim that the processes of constructing proofs and constructing algorithms are similar, and thus experience with induction proofs is very helpful. Mathematical induction is a very powerful proof technique. It usually works as follows. Let Tbe a theorem that we want to prove. Suppose that T includes a parameter n whose value can be any natural number (a natural number is a positive integer). Instead of proving directly that T holds for all values of n, we prove the following two conditions: 1. Tholds form =1 2. For every n > 1, if T holds for n—1, then T holds for n ‘The reason these two conditions are sufficient is clear. Conditions 1 and 2 imply directly that T holds for n=2. If Tholds for n=2, then condition 2 implies that T holds for n =3, and so on. The induction principle itself is so basic that it is usually not proved; rather, it8S SESE EOE OOOOEEEaE— 10 Mathematical Induction i stated as an axiom in the definition of the natural numbers. Condition 1 is usually simple to prove. Proving condition 2 is easier in many cases than proving the theorem directly, since we can use the assumption that T holds for m—1 ‘This assumption is called the induction hypothesis. In some sense, we get the induction hypothesis for free. It is enough to reduce the theorem to one with smaller value of n, rather than proving it from scratch. We concentrate on this reduction. Let's start right away with an example. 1 © Theorem 2.1 For all natural numbers x and n, x" — | is divisible by Proof: The proof is by induction on ». The theorem is trivially true for =1. We ‘assume that the theorem is true for n—1; namely, we assume that x"~!—1 is divisible by —1 for all natural numbers x, We now have to prove that x"—1 is divisible by x1. the idea is to try to write the expression x"=1 using x” '—1, which, by the induction hypothesis, is divisible by x— 1: xe"! =I) +@-D. x But the left term is divisible by x—1 by the induction hypothesis, and the right term is justx-1. o ‘The induction principle is thus defined as follows: If'a statement P, with a parameter n, is true for n=, and if, for every n>, the truth of P for n—1 implies its truth for n, then P is true for all natural numbers, Instead of using n—1 and n, we sometimes use n and n+1, which is completely equivalent: Ifa statement P, with a parameter n, is true for n=1, and if, for every n= 1, the truth of P for n implies its truth for n+1, then P is true for all natural numbers. The proof of Theorem 2.1 illustrates a simple application of induction. Over the year many variations of induction have been developed. For example, the following variat called strong induction, is very common. n, Ifa statement P, with a parameter n, is true for n the truth of P for all natural numbers 1, truth for n, then P is ‘The difference is that we can use the assumption that the statement is true for all numbers 2, the truth of P for n—2 implies its truth for n, then P is true ‘forall natural numbers. This variation ‘‘works”’ in two. parallel tracks. The base case for n =1 and the induction step imply P for all odd numbers; the base case for n=2 and the induction step imply P for all even numbers. Another common variation is the following: Ifa statement P, with a parameter n, is true for n=l, and if, for every n> 1, such that n is an integer power of 2, the truth of P for ni2 implies its truth for n, then P is true for all natural numbers that are integer powers of 2. This variation follows from the first one by writing the parameter » as 2*, and carrying out the induction for the parameter & (starting from k=0). Induction can also be used in many different ways to prove properties of structures other than numbers. In most cases, the induction is on some number n that measures the size of the instance of the problem. Finding the right measure to which the induction should be applied is not straightforward. (For example, we could have applied induction to vin the previous example, rather than to n; this would have made the proof much more complicated.) Sometimes, this measure is not natural, and it has to be invented just for the purpose of the induction. The common thread to alll these proofs is the extension of claims for smaller structures to claims for larger structures, 2.2 Three Simple Examples The problem is to find the expression for the sum of the first ” natural numbers S(n)=1+24 +++ +n. We prove the following theorem. CO Theorem 2.2 The sum of the first n natural numbers is n(n +1)/2. Proof: The proof is by induction on n. If n=1, then the claim is true because S()=1=1-(1+1)/2. We now assume that the sum of the first » natural numbers S(n) is m(r+1)/2, and prove that this assumption implies that the sum of the first n+ 1 natural numbers is S(m+1)=(n+1)(+2)/2, We know from the definition of S(n) that S(n+1)=S(n)+n+1. But, by the assumption. S()=n(n+1)/2. and therefore S(n+D=n(n+1/2+n+1 = (n+2)(n+1)/2, which is exactly what we wanted to prove. o We continue with a slightly more complicated sum. Suppose that we want to compute the sum T(n)=8+13+18+23+---+(+5n). The sum in the previous example, $ (m2), is equal to n?/2+n/2. Each of the elements in the current example is slightly more than five times the corresponding element in the previous example. Hence, itis reasonable to guess that T() is also a quadratic expression. Let's try the implicit guess G(n)=c jn? +con+c3. That is, we introduce the parameters 1, €2, and ¢3, and determine their values when it is convenient to do so. For example, we can determine the12 Mathematical Induction parameters by checking the first few terms. If 2 =0, the sum is 0, so c3 must be 0. For n=1and n=2, we get the following two equations: (I) Lee, +1-e2=8 QQ) 4-c)#2-c2= 1348 If we multiply (1) by 2 and subtract it from (2), we get 2c; =5, which implies that C1 and c>=5.5. We therefore guess that G(n)= Sn? +5.5n is the right expression. We now try to prove that G(n)=T(n) by induction. We have already verified a base case. We assume that G(n)=T(n), and we ty to prove that Gin+lj=T(n4+1): Tint l)=T(n)+5(n+ 1) +3 = (by induction) G (1) +501+ 1) +3 = 2.5n?45.5n+5n+8=2.5n°+5n $2545.50 5.5 =2.5(n +1) +5.5(n+1)=G(n4 D). We have proved the following theorem. OC Theorem 2.3 The sum of the series 8413+18+23+ --- +@G+5n) is 2.5n? +5.5n. a ‘We end this section with another simple example. 0 Theorem 2.4 If nis a natural number and 1+x>0. then (tx"21+nx. 1) Proof: The proof is by induction on n. If n=1, then both sides of (2.1) are equal to 14x. We assume that (1+.°)"21+nx for all x such that 1 +x >0, and consider the case of n +1. We have to prove that (1+.x)"*1 > 1+ (n+ 1x, for all x such that 1+. > 0: (4x)! = (14x) +2)" 2 (by induction) (1 +.x)(1 +2) =1+(r+ Dx tnx? 21+ (n+ Dx. Notice that we were able to multiply the inequality (implied by the induction) by (1+) because of the assumption that 1+x>0. The last step was possible because nx? is clearly nonnegative. a2.3 Counting Regions in the Plane 13 2.3 Counting Regions in the Plane A set of lines in the plane is said to be in general position if no two lines are parallel and no three lines intersect at a common point. The next problem is to compute the number of regions in the plane formed by n lines in general position. Good hints for the right guess can be obtained from small cases. When 1 =1, there are 2. Two intersecting lines form 4 regions; three lines that do not intersect at a point form 7 regions. It seems, at least for i<3, that the ith line adds i regions. If this is true for all i, then the number of regions can be easily computed from S(n), which was computed in the previous section. Therefore, we concentrate on the growth of the number of regions when one more line is added. The claim we are trying to prove is the following: Guess: Adding one moré line to n—I lines in general position in the plane increases the number of regions by n. ‘As we have already seen, the guess is true for n <3. We can now use the guess as our induction hypothesis, and try to prove that adding one line to n lines in general position increases the number of regions by +1. Notice that the hypothesis does not deal directly with the number of regions, but rather with the growth of the number of regions when one line is added. Even if the hypothesis is true, we will still need to compute the total number of regions, but this part will be straightforward. How can a new line increase the number of regions? Consider Fig. 2.1. Since all lines are in general position, a line cannot just touch a region at the border; it can either cut a region into two parts (in which case one more region is formed), or be disjoint from it. Consequently, we need only to prove that the (n+ 1)th line intersects exactly n +1 existing regions. It is possible to prove the theorem directly at this point, but we want to illustrate another technique of induction proofs. Let’s remove for the moment the nth” line. By the induction hypothesis, without the nth line, the (1 + I)th line is adding n new regions. Thus, we need only to prove that the presence of the nth line causes the (n+ 1)th line to add one additional region. Let’s put the nth line back. Since all lines are in general position, the nth and (7r + 1)th lines intersect at a point p, which must be inside a the nth line the (n+1 jth line Figure 2.1 +1 lines in general position.14 Mathematical Induction region R. Both lines thus intersect R. Each line separately cuts R into two pieces, but together they cut R into four pieces! So, the addition of the (n+ 1)th line, when the nth line is nor present, cuts R into two regions. But, the addition of the (+ 1)th line, when the nth line is present, affects R by adding two more regions (R is cut from two to four regions) instead of just adding one. Furthermore, R is the only region so affected, since the two lines meet at only one point. Hence, the n+ Ith line adds n regions without the presence of the nth line, but it adds +1 regions with the nth line, and the proof is complete. O Theorem 2.5 The number of regions in the plane formed by n lines in general position is n(nt 1/241 Proof: We have already proved that the nth line adds n more regions. The first line introduces two regions; hence, the total number of regions (for n>1) is 24243+4+5+---+m, We have seen in the previous section that 142434 +-+ +n=n(n+1)/2: therefore, the total number of regions is a(n +1)/2+1.0 Comments There are two interesting points in this proof. First, the hypothesis dealt with the growth of the function we were after, rather than directly with the function. As a result, the induction proof concentrated on the growth of the growth of the function. There is no need to define the hypothesis such that it proves the theorem directly. We can achieve the proof in two or more steps. As long as we are learning more about the situation, we are making progress. There is no need to hurry, or to attempt too much too quickly. Patience usually pays. Second, the same induction hypothesis was used, twice in two different configurations: once for the nth line and once for the (n+1)th line ‘acting’? as an nth line. This double use is not uncommon, and the lesson it teaches is that we should utilize our assumptions to their fullest. 2.4 A Simple Coloring Problem Consider again n distinct lines in a plane, this time not necessarily in general position. We are interested in assigning colors to the regions formed by these lines such that neighboring regions have different colors (two regions are considered neighbors if and only if they have an edge in common). We will say that “‘it is possible to color’ the regions if we can follow this rule, and we call the assignment of colors a valid coloring. In general, it is possible to color any planar map with four colors (the proof of this fact has occupied mathematicians for about a hundred years, and was found only recently). The regions formed by (infinite) lines, however, have special characteristics, as is shown in the next theorem. 6 Theorem 2.6 In is possible to color the regions formed by any number of lines in the plane with only two colors.2.5 A More Complicated Summation Problem 15 Proof: We use the natural induction hypothesis. Induction hypothesis: /r is possible t0 color the regions formed by < n lines in the plane with only two colors. I is clear that two colors are necessary and sufficient for n=1. Assume the induction hypothesis, and consider m lines. Again, the only question is how to modify the coloring when the nth line is added. Divide the regions into two groups according to which side of the nth line they lie. Leave all regions on one side colored the same as before, and reverse the colors of all regions on the other side. To prove that this is a valid coloring, we consider two neighboring regions R, and R>. If both are on the same side of the nth line, then they were colored differently before the line was added (by the induction hypothesis). They may have the reverse colors, but they are still different. If the edge between them is part of the nth line, then they belonged to the same region before the line was added. Since the color of one region was reversed, they are now colored differently. Oo Comments The general method illustrated in this example is the search for flexibility, or for more degrees of freedom. The idea is usually to stretch the hypothesis as much as possible in order to get the most out of it. In this case, the key idea was that, given a valid coloring, we can reverse all colors and still have a valid coloring. This idea was used to handle the formation of new regions by the added line. 2.5 A More Complicated Summation Problem The next example is more compli ted. Consider the following triangle. = 1 1 35 8 7+9 411 27 13+ 15+ 174 19 = 64 21+ °23 + 254 27+ 29 = 125 The problem is to find an expression for the sum of the ith row, and prove its correctness. The sums of the rows seem to follow a regular pattern; They look like a sequence of cubes. Induction hypothesis: The sum of row i in the triangle is The problem and the hypothesis are defined in terms of a picture. It is not easy to define the problem precisely, let alone to solve it. In practice, it is not uncommon for problems to be vaguely defined. A major part of any solution is to extract the right problem, ‘Therefore, we will make some assumptions that are consistent with the picture, and solve the problem accordingly. (It is possible to make other assumptions.) The ith row contains i numbers. The numbers are the odd numbers in order. Again, let’s concentrate on the difference between two consecutive rows. To prove that the sum of row j is indeed i*, we need only to show that the difference between row i+1 and row i is (i+ 1) ~7? (we have already seen that the hypothesis is true for i <4).16 Mathematical Induction Whatis the difference between the first number in row i+} and the first number in row i? Since the numbers are the odd numbers in order and there are i of them in row i, the difference is 2i, This is also the difference between the second number in row i +1 and the second number in row i the third number, the fourth number, and so on. Overall, there are i differences, each of size 2i, There is also the Jast element at the end of row LLL, which is not matched to any number in the previous To¥!- Hence, the difference between the two rows is 2i? plus the value of the last number in row i+1. Since G41) =P =3i7+3i4 5 we need only to prove that the value of the last number in row j41is3i243i41-27 =i +341. Thisis where the guess that the sum is i comes to play. We have reduced the problem of finding the sum to a problem of finding an Element. We prove the last statement again by induction. i+. Nested induction hypothesis: The last number in row i+ Lis fi The claim is true for Now, it is sufficient, by induction, to check only the ‘ differences. That is, we have to prove that the difference between the last number in row +1 and the last number in row # is equal to [i234 1-1@- 430-4 = i+2. But we already know that the difference between any corresponding numbers in row i+1 and jis i. The guess has thus been established. Comments This proof illustrates again that we should not always try to achieve the whole proof in one step. Ibis a good policy fo advanc’ /P stages, as long as we are making progress. This proof also illustrates the method of “going backward” to arrive at a proof. Instead of starting from a simpler problem and working our way toward the final problem, we start with the final problem and simplify it by reducing it to simpler and simpler problems. This is a very common method (not only in mathematics). 2.6 A Simple Inequality In this section, we prove the following inequality. CO Theorem 2.7 ty po a (2.2) 2 8S ” for alln21.' Proof: We want to prove the theorem by induction. The theorem is clearly true for n=l. We assume that @.2) is wue for m, and we consider n+1. The only jnformation we get from the induction hypothesis is that the sum of the first 7 terms is his inequality is usally writen as a fact about convergence of infinite Senc but we do not assume any knowledge of series; this formulation is completely inte2.7 Euler’s Formula 17 less than 1. How can we extend it to include the m+ 1th term? Adding 1/2"*! to the left hand side may potentially increase the sum to more than 1. The trick here is to apply the induction in a different order. Given the sum a 2 4 1 cto} < 2 1 2 by the induction hypothesis. But now we can add 1/2 to both sides and get the expression (2.2) for n +1. ag Comments It is not necessary to consider the last element as the (n + 1)th element in the induction proof. Sometimes it is easier to consider the first element. There are other instances where it is better to let the (n+1)th element be a special element satisfying some special properties. If you run into problems, be flexible, and consider as many options as you can. The following examples extend this notion further. 2.7 Euler’s Formula ‘The next proof is for a theorem known as Euler’s Formula. Consider a connected planar map with V vertices, E edges, and F faces. (A face is an enclosed region. The outside region is counted as one face, so, for example, a square has four vertices four edges and two faces.) The map in Fig. 2.2 has 11 vertices, 19 edges, and 10 faces. Two vertices of a map are said to be connected if it is possible to go from one vertex to the’ other by traversing edges of the map. A map is called connected if every two vertices in it are connected. Intuitively, a map is connected if it consists of one part. © Theorem 2.8 The number of vertices (V), edges (E), and faces (F) in an arbitrary connected planar map are related by the formula V + F = E+ 2. Figure 2.2 A planar map with I1 vertices, 19 edges, and 10 faces.18 Mathematical Induction Proof: We will prove this theorem by a variation of induction known 3S double induction. ‘The induction proceeds first on the number of vertices and then on the number of faces. Consider first a map with only one face. Such a map does not contain a cycle peeause, otherwise, the cycle would form at least one face and the outside would form another face, A connected map without a cycle is called a tree. We first prove that, for all wees, V+1=E +2. First induction hypothesis: A tree with n vertices has n—1 edges. The base case is trivial. Assume that trees with 7 vertices have n—1 edges, and consider trees with n+ 1 vertices. There must be at least one vertex v connected to only one edge. Otherwise. if all vertices are connected to at least two edges and if we traverse the tree along the edge, starting from any vertex, then we are guaranteed to return to @ vertex, already visited without getting stuck, But this means that there is a cycle, which is a contradiction. We can remove the vertex v along with the edge connected to it. The resulting map is still connected: thus, itis still a tree. But it has one less vertex and one Jess edge, which implies the claim. ‘This serves as a base case for an induction on the number of faces. Main induction hypothesis: Any planar map with n faces has E edges and V vertices such that V +n = E + 2. Consider a map with n+1 faces. It must have'a face f, which is 2 neighbor of the outside face. Since fis. a face, it is surrounded by acycle. Removing one edge of this cycle will not disconnect the map. We remove one of the edges that separates ‘f from the outside. We now have one less face and one less edge and the theorem follows. - a Comments This theorem included three parameters. The proof used induction on one parameter (the number of faces), but the base case required another induction on another parameter (the number of vertices). The proof shows that we have to be careful bout choosing the right sequence of induction. Sometimes, the induction switches from ne parameter to another; sometimes, it is based on @ combined value of several parameters; and sometimes, it is applied to two different parameters at the same time. Choosing the right sequence can make a big difference in the difficulty of the proof. As we will see in the Following chapters, choosing the right sequence of induction can also make a big difference in efficiency of algorithms. 2.8 A Problem in Graph Theory We first need to introduce some basic concepts of graph theory (these concepts ar discussed in detail in Chapter 7). A graph G=(V, £) consists of a set V of vertices and set E of edges. Each edge corresponds to a pair of distinct vertices. ‘A graph can b directed or undirected. The edges in a directed graph are ordered pairs: The orde between the two vertices the edge connects is important. In this case, we draw an edg as an arrow pointing from one vertex (the tail) to another (the head). The edges ina2.8 A Problem in Graph Theory 19 undirected graph are unordered pairs. We deal with directed graphs in this section. The degree of a vertex ¥ is the number of edges incident to v. A path is a sequence of vertices vj, 12, 1% that are connected by the edges (1,12), V2.3); a Mas MO (these edges are also usually considered to be part of the path). Vertex w is said to be reachable from vertex v if there is a path from v to u. Let G=(V, E) be a graph, and Ua set of vertices U CV. The subgraph induced by U is a subgraph HW =(U, F) such that F consists of all the edges in E both of whose vertices belong to U. An independent set S in a graph G=(V, E) isa set of vertices such that no two vertices in S are adjacent. O Theorem 2.9 Let G=(V, E) be a directed graph. There exists an independent set S(G) in G such that every vertex in G can be reached from a vertex in S(G) by a path of length at most 2 Proof: The proof is by induction on the number of vertices. Induction hypothesis: The theorem is true for all directed graphs with ) Sz = % which is exactly the same as (2.3) for —1. : Oo 2.12 Loop Invai to Binary nts: Converting a Decimal Number Induction is very useful for proving correctness of algorithms. Consider a program that loop that is supposed to compute a certain value. We want to prove that the result of executing the loop is indeed the intended result, We can use induction on the number of times the loop is executed. The induction hypothesis should reflect the relationships between the variables during the loop execution. Such an induction hypothesis is called a loop invariant. We illustrate the use of loop invariants with the algorithm in Fig. 2.6, which converts a decimal number into a binary number represented by the array b (which is initially zero). Algorithm Convert_to_Binary consists of one loop with three statements. The first statement increments k, which is an index to the array b. The second statement computes tmod 2, which is the reminder of the division of t by 2 (namely, 1 if t is odd, and 0 otherwise). ‘The third statement divides ¢ by 2, using an integer division (namely, ignoring fraction © Theorem 2.14 contai When Algorithm Convert_to Binary terminates, the binary representation of nis stored in the array b.2.12 Loop Invariants: Converting a Decimal Number to Binary 27 Algorithm Convert_to Binary (n) ; Input: 7 (a positive integer). Output: b (an array of bits corresponding to the binary representation of n). begin 2 { we use a new variable t to preserve n} 0; while t > 0 do +1; b{k] = tmod 2; te=tdiv2 end Figure 2.6 Algorithm Convert to Binary. Proof: The proof is by induction on k, the number of times the loop is executed. The induction hypothesis does not have to be the same as the theorem statement. It can apply to only a part of the algorithm. In this case, the main part is the loop, and we use the induction hypothesis to verify the execution pattern of the loop. The hypothe: this case, can be thought of as an invariant. It is a statement about the variables that is correct independent of the number of times we execute the loop. The most difficult part of the proof is finding the right induction hypothesis. Consider the following hypothesis. Induction hypothesis: /f m is the integer represented by the binary array b[L..k], then n=t-2* +m. The expression ¢-2‘+m is the heart of the loop invariant, and is also the heart of the algorithm. The hypothesis states that the value of this expression is independent of the number of times the loop is executed. It captures the idea behind the algorithm. At step £ of the loop, the binary array represents the k least significant bits of n, and the value of 1, when shifted by k, corresponds to the rest of the bits. To prove the correctness of this algorithm, we have to prove three conditions: (1) the hypothesis is true at the beginning of the loop, (2) the truth of the hypothesis at step k implies its truth for step k +1, and (3) when the loop terminates, the hypothesis implies the correctness of the algorithm. At the beginning of the loop, k =0, m =0 (by definition, since the array is empty), and Assume that n=r-2*+m at the start of the kth loop, and consider the corresponding values at the end of the kth loop. There are two cases. First, assume that ris even at the start of the Ath loop. In this case, rmod 2 is 0. Thus there is no contribution to the array (namely, m is unchanged), f is divided by 2, and k i incremented. Hence, the hypothesis is still true. Second, assume that m is odd. In this case, b[k+1] is set to 1, which contributes 2* to m, ¢ is changed to (t—1)/2, and k is incremented. So, at the end of the Ath loop, the corresponding expression is (¢=1)/2-2*1 +m 424 = (¢=1)-2+m+2 = t-2+m=n, which is exactly what we28 Mathematical Induction need to prove. Finally, the loop terminates when s=0. which implies, by the hypothesis. that n=0-2'+m=m. a 2.13 Common Errors We finish this chapter with a few warnings and examples of common traps one can easily fall into by using induction hastily. Many wrong proofs come from strong convictions. If one believes strongly in the theorem, one tends to take as evident certain seemingly trivial “facts”? implied by it. In induction proofs, this phenomenon often takes the following form. Since the theorem is ““evident,’* one sometimes implicitly adds to the hypothesis several evident “facts.” The proof of the step from n to +1 uses these assumptions. Thus, the induction hypothesis is implicitly strengthened, but the stronger assumptions are never proven. For example, one may overlook the fact that the graphs in the theorem were assumed to be connected, and forget to check the reduced graphs for connectivity. Such an omission could be very subtle, and, of course, could lead to a very wrong proof. It is important to state the induction hypothesis pre Another common error is the following. The main step i in an induction proof is showing that the truth of the theorem for n implies its truth for n +1. We can either start with the n+1 instance and show that it follows from the n instance, or start with the 7 instance and show that it implies the +1 instance. Both approaches are valid. However, the +1 instance must be an arbitrary instance! The proof will be wrong if we start with an n instance and extend it to an n+1 instance that has some special properties. For example, consider the following wrong proof of Theorem 2.8. We start with an arbitrary map with 1 faces, and assume, by induction, that V+n=E+2. We take ‘an arbitrary face and add a new edge with two new vertices that cuts the face im tw ‘Adding two new vertices “‘cuts’” two old edges, each one into two new edges. Overall, we added one more face, three more edges, and two more vertices. But, V+24n+1=E+3+2, and the claim is true for n+1 faces. The reason this is not a valid proof is that the addition of the edge was done in a special way. An edge can also be added between existing vertices, or between one existing vertex and one new vertex. In fact, the graphs we get by adding edges only between new vertices have vertices only of degree 3 or less, so they are very special indeed. In general, it is safer to start with an arbitrary instance and try to prove it using the induction hypothesis, rather than the other way around. ‘Another dangerous trap involves exceptions to the theorem. It is common to have minor exceptions of the form n 23, or “‘n is not a prime less than 30.”" The induction principle depends on the ability to imply the hypothesis for n =2 from the hypothesis for n=1, the hypothesis for n=3 from the hypothesis for m=2. and so on. If even one of these steps fails, the whole proof fails. We present two examples of this trap. The first example is a simple amusing anecdote; the second example is a more serious one Consider the following claim. Ridiculous claim: Given n lines in the plane, no pvo of which are parallel to each other, all lines must have one point in common