Preface xxiii -Binary trees can be used to teach structural induction,and also to motivate the study of trees as examples of graphs. In our own teaching experiences,this class is a prerequisite to an algorithms class,and students often take the algorithms course soon after the discrete mathematics course.In doing so,they find themselves immediately using the mathematics that they have just learned. OUR EDUCATIONAL PHILOSOPHY This text is driven by activities,presented as exercises.The material is fleshed out through explanations and extensions of the activities.The most effective way for students to use the book is for them to attempt seriously the student activities before they read the explanation that follows.The activities are primarily meant to be done in groups in class;thus for activities done out of class we recommend that students form groups to work together.The class and this text are designed in this way to help students develop their own habits of mathematical thought.Our reading of the research in how undergraduate students learn mathematics leads us to several conclusions. Students who actively discover what they are learning (thus engaging in what is often called "active learning")remember concepts far longer than those who don't.They are also more likely to be able to use them outside the context in which they were learned. Students are more likely to ask questions until they understand a subject when they are working in a small group of peers rather than in a larger class with an instructor.(However,this isn't always the case.Many students need to feel comfortable within their group before they ask questions that they fear will slow down the others. We try to develop this comfort level in class by allowing students to choose their groups and change from group to group on different days as attendance patterns allow or require.) Finally,explaining ideas to someone else helps students organize these ideas in their minds and familiarizes students with the language of mathematics. There is ample material in the book for a four-semester-hour course.At Dartmouth we use the book for a fast-paced course that meets three days a week for just over nine weeks and covers all but the last few sections of the book and some material marked with an asterisk
Preface xxiii – Binary trees can be used to teach structural induction, and also to motivate the study of trees as examples of graphs. In our own teaching experiences, this class is a prerequisite to an algorithms class, and students often take the algorithms course soon after the discrete mathematics course. In doing so, they find themselves immediately using the mathematics that they have just learned. OUR EDUCATIONAL PHILOSOPHY This text is driven by activities, presented as exercises. The material is fleshed out through explanations and extensions of the activities. The most effective way for students to use the book is for them to attempt seriously the student activities before they read the explanation that follows. The activities are primarily meant to be done in groups in class; thus for activities done out of class we recommend that students form groups to work together. The class and this text are designed in this way to help students develop their own habits of mathematical thought. Our reading of the research in how undergraduate students learn mathematics leads us to several conclusions. • Students who actively discover what they are learning (thus engaging in what is often called “active learning”) remember concepts far longer than those who don’t. They are also more likely to be able to use them outside the context in which they were learned. • Students are more likely to ask questions until they understand a subject when they are working in a small group of peers rather than in a larger class with an instructor. (However, this isn’t always the case. Many students need to feel comfortable within their group before they ask questions that they fear will slow down the others. We try to develop this comfort level in class by allowing students to choose their groups and change from group to group on different days as attendance patterns allow or require.) • Finally, explaining ideas to someone else helps students organize these ideas in their minds and familiarizes students with the language of mathematics. There is ample material in the book for a four-semester-hour course. At Dartmouth we use the book for a fast-paced course that meets three days a week for just over nine weeks and covers all but the last few sections of the book and some material marked with an asterisk
xxiv Preface THE ROLE OF PROOFS One of our purposes in writing this book is to give students a background for the kinds of proofs that they will need to understand and write in their computer science courses.Our view is that one learns how to do proofs by hearing,seeing,discussing,and trying to do proofs.In order to discuss proofs,we need to have a common language that classifies the ingredients of a proof and provides us a framework for discussion.For this reason we have included a chapter on logic,designed both to give students this language and to assist them in the process of reflecting on the proofs they have already seen.In order to have something significant to talk about in this chapter, we have introduced it after the students have seen some combinatorial and number theoretic proofs.This way the students have concrete examples of proofs that can be used to illustrate the logical abstractions.We realize that this is not the usual order in a discrete mathematics book.However,we find that dealing with concrete examples of proofs of non-trivial facts gives some grounding to what otherwise can seem to be a long list of formal rules of inference. We have placed the chapter on logic before the chapter on mathematical induction so that we can use its language in discussing and reflecting on mathematical induction. MATHEMATICAL INDUCTION Inductive proofs in computer science frequently use subproblems that are not"one smaller."We therefore emphasize strong induction as well as weak induction.We also introduce structural induction on trees and graphs.We try to use students'experiences with recursion to help them understand induction and develop inductive proofs.In particular,when creating an inductive proof it is usually more profitable to start with a big problem and recursively subdivide it into smaller problems than to start with small problems and try to "build up"to bigger problems. THE USE OF PSEUDOCODE We describe algorithms both in prose and by using pseudocode.The pseu- docode should be easily readable by any one who has programmed in JavaTM,C,or C++and should be understandable to people who have pro- grammed in other languages.We do not strive to give syntactically correct
xxiv Preface THE ROLE OF PROOFS One of our purposes in writing this book is to give students a background for the kinds of proofs that they will need to understand and write in their computer science courses. Our view is that one learns how to do proofs by hearing, seeing, discussing, and trying to do proofs. In order to discuss proofs, we need to have a common language that classifies the ingredients of a proof and provides us a framework for discussion. For this reason we have included a chapter on logic, designed both to give students this language and to assist them in the process of reflecting on the proofs they have already seen. In order to have something significant to talk about in this chapter, we have introduced it after the students have seen some combinatorial and number theoretic proofs. This way the students have concrete examples of proofs that can be used to illustrate the logical abstractions. We realize that this is not the usual order in a discrete mathematics book. However, we find that dealing with concrete examples of proofs of non-trivial facts gives some grounding to what otherwise can seem to be a long list of formal rules of inference. We have placed the chapter on logic before the chapter on mathematical induction so that we can use its language in discussing and reflecting on mathematical induction. MATHEMATICAL INDUCTION Inductive proofs in computer science frequently use subproblems that are not “one smaller.” We therefore emphasize strong induction as well as weak induction. We also introduce structural induction on trees and graphs.We try to use students’ experiences with recursion to help them understand induction and develop inductive proofs. In particular, when creating an inductive proof it is usually more profitable to start with a big problem and recursively subdivide it into smaller problems than to start with small problems and try to “build up” to bigger problems. THE USE OF PSEUDOCODE We describe algorithms both in prose and by using pseudocode. The pseudocode should be easily readable by any one who has programmed in JavaTM, C, or C++ and should be understandable to people who have programmed in other languages. We do not strive to give syntactically correct
Preface xxv code in any language,rather we strive for clarity.For example,to say, “Swap the values held in variables x and y,”we write,“exchange x and y"rather than writing three lines of code.Similarly,we write,"if points i,j,and k are not collinear"without concern for how a more detailed computation proceeds.Here are some particular conventions we use in the text. Blocks of code are denoted by indentation.There is no begin,end or “”“”as in many languages. 。For loops are written as“fori=lton”to denote that the variable i ranges from 1 to n. While loop bodies are repeatedly executed while the boolean expression after the while is true. Repeat loops have the form:"repeat...until".The code between the repeat and until is executed at least once,and is repeatedly executed until the boolean expression after the until is true. If statements have one of the following forms: -if (expression)block of code if (expression)blockl of code else block2 of code In the first form,block of code is executed if and only if the expression is true.In the second form,block/is executed if the expression is true and block2 is executed if the expression is false. ·Arrays are subscripted using“[].” 。Assignment is represented with“=”and comparison for equality with“==” ·Shorthand for incrementing and decrementing x is“x+”and “x--” ·The logical operator“not”is indicated by“l,”so“!true'”is“false," and y)is true when x is not less than y.Logical "and"is indicated by“&&”and logical“or”by“l| WHAT HAS CHANGED IN THIS VERSION OF THE BOOK A different book with a similar title and the same set of authors was pub- lished by a different publisher who has since withdrawn from the college textbook market.Ken Bogart,the lead author on that book,died short- ly before it came out.We greatly miss his participation in preparing this revised book
Preface xxv code in any language, rather we strive for clarity. For example, to say, “Swap the values held in variables x and y,” we write, “exchange x and y” rather than writing three lines of code. Similarly, we write, “if points i, j , and k are not collinear” without concern for how a more detailed computation proceeds. Here are some particular conventions we use in the text. • Blocks of code are denoted by indentation. There is no begin, end or “{” “}” as in many languages. • For loops are written as “for i = 1 to n” to denote that the variable i ranges from 1 to n. • While loop bodies are repeatedly executed while the boolean expression after the while is true. • Repeat loops have the form: “repeat ... until”. The code between the repeat and until is executed at least once, and is repeatedly executed until the boolean expression after the until is true. • If statements have one of the following forms: – if (expression) block of code – if (expression) block1 of code else block2 of code In the first form, block of code is executed if and only if the expression is true. In the second form, block1 is executed if the expression is true and block2 is executed if the expression is false. • Arrays are subscripted using “[ ].” • Assignment is represented with “=” and comparison for equality with “==”. • Shorthand for incrementing and decrementing x is “x ++” and “x −−.” • The logical operator “not” is indicated by “!,” so “!true” is “false,” and !(x < y) is true when x is not less than y. Logical “and” is indicated by “&&” and logical “or” by “| |” WHAT HAS CHANGED IN THIS VERSION OF THE BOOK A different book with a similar title and the same set of authors was published by a different publisher who has since withdrawn from the college textbook market. Ken Bogart, the lead author on that book, died shortly before it came out. We greatly miss his participation in preparing this revised book
xxvi Preface The most significant changes between the former book and this one are: The previous book discussed equivalence relations,but only as partitions of a set.The reflexive,symmetric,and transitive properties were relegated to an appendix,and partial orders and total orders were not discussed.This book introduces relations as a concept that connects functions,equivalence relations,partial orders,and total orders.It shows why reflexivity,symmetry,and transitivity lead to equivalence relations and reflexivity,antisymmetry,and transitivity lead to partial orders. This book includes structural induction.Also,the section on the relationship between recursion and induction has been expanded and uses some different examples. Some sections in the chapter on recurrence relations have been removed or moved to an appendix.These sections showed that eliminating foors and ceilings in recurrences and extending the domain of the relation to numbers other than the powers of a base do not invalidate the Master Theorem.We decided that they interfered with the flow of the chapter and dealt with picky details that most students at this level do not need to know. Bayes'Theorem was added to the section on conditional probability. Problems were added to cover the new topics. There are also a number of smaller changes (e.g.,introducing the "multiply by x and subtract"approach to getting a closed form for geometric series). INSTRUCTORS'SUPPLEMENTS The following supplemental material is available to qualified instructors only.Please visit the Instructor Resource Center (www.pearsonhighered .com/irc),contact your local Addison-Wesley/Pearson Education sales rep- resentative,or send email to computing@aw.com,for information about how to access them. Instructor's Manual with Solutions Teaching suggestions Solutions to homework problems Exercise handouts for use in class Detailed discussion of how we have students work on exercises in groups in class to stimulate discussion Powerpoint Presentations
xxvi Preface The most significant changes between the former book and this one are: • The previous book discussed equivalence relations, but only as partitions of a set. The reflexive, symmetric, and transitive properties were relegated to an appendix, and partial orders and total orders were not discussed. This book introduces relations as a concept that connects functions, equivalence relations, partial orders, and total orders. It shows why reflexivity, symmetry, and transitivity lead to equivalence relations and reflexivity, antisymmetry, and transitivity lead to partial orders. • This book includes structural induction. Also, the section on the relationship between recursion and induction has been expanded and uses some different examples. • Some sections in the chapter on recurrence relations have been removed or moved to an appendix. These sections showed that eliminating floors and ceilings in recurrences and extending the domain of the relation to numbers other than the powers of a base do not invalidate the Master Theorem. We decided that they interfered with the flow of the chapter and dealt with picky details that most students at this level do not need to know. • Bayes’ Theorem was added to the section on conditional probability. • Problems were added to cover the new topics. There are also a number of smaller changes (e.g., introducing the “multiply by x and subtract” approach to getting a closed form for geometric series). INSTRUCTORS’ SUPPLEMENTS The following supplemental material is available to qualified instructors only. Please visit the Instructor Resource Center (www.pearsonhighered .com/irc), contact your local Addison-Wesley/Pearson Education sales representative, or send email to computing@aw.com, for information about how to access them. • Instructor’s Manual with Solutions • Teaching suggestions • Solutions to homework problems • Exercise handouts for use in class • Detailed discussion of how we have students work on exercises in groups in class to stimulate discussion • Powerpoint Presentations
Preface xxvii ACKNOWLEDGMENTS A number of people contributed to the original version of this book.We would like to thank Eddie Cheng,Oakland University;Alice Dean,Skid- more College;Ruth Hass,Smith College;and Italo Dejter,University of Puerto Rico for their thoughtful review comments on an early version of the manuscript.As the book was being developed,preliminary versions were used to teach discrete mathematics at Dartmouth by the authors and by Neal Young,Prasad Jayanti,Tom Shemanske,Rosa Orellana,April Rasala, Amit Chakrabarti,and Carl Pomerance.Each of them had an impact on the final product,some very substantial,and we thank them for their advice. We offer a special thanks to Carl Pomerance for his thorough and insightful commentary as he taught the course.Qun Li was a graduate assistant to us as we were initially preparing the manuscript,and he had the job of making sure that the problems we created really did have solutions!His work still forms the core of the solutions available to the instructor.The graduate teaching assistants from the Computer Science and Mathematics Departments while we and others taught from the manuscript also gave us valuable insights into what students were and were not learning and fur- ther help with solutions to problems.In order of their service,they were S.Agrawal,Elishiva Werner-Reiss,Robert Savell,Virgiliu Pavlu,Libo Song,Geeta Chaudhry,King Tan,Yurong Xu,Gabriella Dumitrascu,Florin Constantin,Alin Popescu,and Wei Zhang.Our students over the years have provided us with valuable feedback.In particular,Eric Robinson carefully read a near-final version,looking explicitly for passages that were hard to understand. We would also like to thank the people who made this version of the book possible.The following reviewers provided many thoughtful suggestions: Michael Rothstein,Kent State University;Ravi Janardan,University of Minnesota,Twin Cities;Klaus Sutner,Carnegie Mellon University;Doug Baldwin,SUNY Genesco;Stuart Reges,University of Washington;Richard Anderson,University of Washington;Jonathan Goldstine,Penn State Uni- versity.Sandra Hakanson,a Pearson sales representative,first suggested that the Addison-Wesley division of Pearson might be interested in the book.She put us in touch with Michael Hirsch,Editor-in-Chief,who agreed to publish the book and has shepherded it through the publication process.Many of the improvements that were made were his suggestions.Others at Addison- Wesley who contributed directly to the publication are Stephanie Sellinger (Editorial Assistant),Jeff Holcomb (Managing Editor),Heather McNally (Project Editor),and Elena Sidorova (Cover Designer).Bruce Hobart at
Preface xxvii ACKNOWLEDGMENTS A number of people contributed to the original version of this book. We would like to thank Eddie Cheng, Oakland University; Alice Dean, Skidmore College; Ruth Hass, Smith College; and Italo Dejter, University of Puerto Rico for their thoughtful review comments on an early version of the manuscript. As the book was being developed, preliminary versions were used to teach discrete mathematics at Dartmouth by the authors and by Neal Young, Prasad Jayanti, Tom Shemanske, Rosa Orellana, April Rasala, Amit Chakrabarti, and Carl Pomerance. Each of them had an impact on the final product, some very substantial, and we thank them for their advice. We offer a special thanks to Carl Pomerance for his thorough and insightful commentary as he taught the course. Qun Li was a graduate assistant to us as we were initially preparing the manuscript, and he had the job of making sure that the problems we created really did have solutions! His work still forms the core of the solutions available to the instructor. The graduate teaching assistants from the Computer Science and Mathematics Departments while we and others taught from the manuscript also gave us valuable insights into what students were and were not learning and further help with solutions to problems. In order of their service, they were S. Agrawal, Elishiva Werner-Reiss, Robert Savell, Virgiliu Pavlu, Libo Song, Geeta Chaudhry, King Tan, Yurong Xu, Gabriella Dumitrascu, Florin Constantin, Alin Popescu, and Wei Zhang. Our students over the years have provided us with valuable feedback. In particular, Eric Robinson carefully read a near-final version, looking explicitly for passages that were hard to understand. We would also like to thank the people who made this version of the book possible. The following reviewers provided many thoughtful suggestions: Michael Rothstein, Kent State University; Ravi Janardan, University of Minnesota, Twin Cities; Klaus Sutner, Carnegie Mellon University; Doug Baldwin, SUNY Genesco; Stuart Reges, University of Washington; Richard Anderson, University of Washington; Jonathan Goldstine, Penn State University. Sandra Hakanson, a Pearson sales representative, first suggested that the Addison-Wesley division of Pearson might be interested in the book. She put us in touch with Michael Hirsch, Editor-in-Chief, who agreed to publish the book and has shepherded it through the publication process. Many of the improvements that were made were his suggestions. Others at AddisonWesley who contributed directly to the publication are Stephanie Sellinger (Editorial Assistant), Jeff Holcomb (Managing Editor), Heather McNally (Project Editor), and Elena Sidorova (Cover Designer). Bruce Hobart at