**Author**: Sarah-Marie Belcastro

**Publisher:** Bukupedia

**ISBN:**
**Format:** PDF, Kindle

Download Now
Discrete Mathematics with Ducks is intended for a sophomore-level audience (including some first-year students) to support a gentle course so that students who find mathematics and proofs and abstraction challenging can still succeed. However, I am mindful that classes including weaker students almost always contain stronger students as well, and so I include more challenging problems with every topic and activity. Additionally, I am mindful that different institutions and different faculty members at those institutions have different ideas about what pace and amount of material is appropriate for a lower-level class. For this reason, I have included Bonus sections for those instructors who wish to have faster pacing. The Bonus sections can be used as fodder for take-home exams or projects as well as for students who just want to know more about a topic outside of class. The material in the text is not new; my contributions are a curation of curriculum, a tone of text, and a philosophy of pedagogy. The guiding pedagogical principle behind the organization of Discrete Mathematics with Ducks is that students can discover many ideas, concepts, theorems, and proofs for themselves with a bit of guidance. Where I see an engaging way for them to do this, I have written Try This! sections that are sets of problems that allow students to construct fundamental parts of the material. However, I also believe that students are likely to miss a detail here or there in their work and, more importantly, that as beginning mathematicians they need reinforcement for their newfound learning. For this reason, I follow sets of discovery problems with sections that explain the relevant material and give both examples and details. I outline some ways instructors might capitalize on this organization of the material in Section 2; instructors who want to gain experience in discovery-based teaching will particularly want to read Section 2.2. The guiding pedagogical principle behind the style and tone of this text is pretty silly. I mean that literally: I believe that students are more likely to absorb mathematics that is presented in a goofy way. Bizarre situations help students separate the abstraction of underlying mathematics from the presentation of a problem and thus give students practice in recognizing the mathematical essence of problems they find in other contexts. Students who are enjoying the weirdness of problem presentations are also focusing on the mathematics. It’s easier to remember a zany concept setup than to recall a straightforward statement. And there’s no reason to be serious when there’s an opportunity to have fun! There is also a hidden agenda in my structuring of this material. (I guess it won’t be hidden anymore after you read this paragraph.) I think it is hard to learn mathematical techniques without a surrounding context. Attempting to do so is sort of like opening a toolbox and simply holding up each tool, describing its function, and then passing the tools around the audience. Without a carpentry project, it is difficult to build a reliable mental library of situations in which each tool is useful. So, in this text I use discrete mathematics as the context via which proof is introduced. Similarly, tools such as set theory, logic, and functions are companions to the basic combinatorics and graph theory that are introduced at the start of the text. Discrete mathematics is a growing area of mathematics that is used throughout industry, so I think a discrete mathematics text should function as an introduction to and survey of the field and its myriad possibilities. Faculty who specialize in discrete mathematics are housed in mathematics, applied mathematics, or computer science (depending on the institution, and they may show up in multiple departments as well). They do combinatorics, graph theory, geometry, and optimization. In this text, I have attempted to balance combinatorics and graph theory topics that lead naturally to use in computer science with those that lead naturally to mathematics investigations. This is so that students will have a taste of the many flavors discrete mathematics has and thus of the paths discrete mathematics can take. As part of this flavor tasting, I have tried to introduce optimization topics where possible. Hopefully, this diverse introduction to the field will excite students into desiring further study of discrete mathematics. The ACM (Association for Computing Machinery) Special Interest Group on Computer Science Education (SIGCSE) guidelines suggest curricula for computer. science-focused and mathematics-focused discrete mathematics courses. Discrete Mathematics with Ducks gives overviews of the topics and techniques listed by SIGCSE and then reinforces them throughout the course by applying them to discrete mathematics topics and problems. The content and approach of the text comply with the SIGCSE guidelines in this way. I made some decisions about the inclusion and exclusion of content and terminology that are potentially controversial and so should be disclosed (or at least mentioned) here. Big-O notation is completely avoided because I think that in order for students to understand it well, its use must pervade a course. Giving an adequate treatment of algorithmic efficiency makes that course computer-science focused; that is not my aim. Similarly, I did not include finite-state automata because this seems more the province of computer science than a mix of computer science and mathematics. There are certain terms (including predicate and combinations) that I avoided using because they only arise in mathematical subspecialties or teaching contexts and are not used throughout mathematics or even mathematics courses. I deliberately separated the treatment of recursion from the treatment of induction so that students would have time to internalize the idea of induction before linking it to recurrences. It’s easy for beginning students to get bogged down in the study of formal logic, so I minimized its treatment here. In contrast, I did not include much number theory because it is a lovely study on its own, and I think every mathematics student should study it for an entire semester. Some discrete mathematics texts include a lot of number theory so that the necessary background is present to grasp the RSA algorithm. However, the number theory required to get a handle on RSA is nearly half of an undergraduate elementary number theory course, and I think that eats up too much of a sophomore-level discrete math class. Finally, the chapters on probability and on cardinality are included because many instructors want or need to teach that material as part of a discrete mathematics course (and because they are beautiful mathematics), but they are not central to discrete mathematics as a subfield and so I have placed them outside of the themes around which the book is organized. For probability, I chose to emphasize expected value and downplay the techniques of counting/proportions because, on one hand, expected value is central to discrete probability and, on another hand, students have already learned and used counting techniques elsewhere in the book. Cardinality is treated via a play, to avoid the potential dryness of a formal treatment. 2 How to Use This Book First things first: please don’t interpret anything written in this section as prescriptive. I’m not attempting to tell you how to use the book (despite the title of this section), but instead, inviting you to think about what will work best for you and offering suggestions that you may take seriously or toss aside at your whim. Different classroom techniques are effective for different instructors, and in this you must find your own way. Second things second: each chapter is designed to take one week of class time and contains a mixture of discovery activities, expository text, in-class exercises, and homework problems. At the end of each expository section, there are elementary exercises labeled as Check Yourself problems and signaled by the marginal pencil-toting duck shown here (as are all sections of problems students should attempt); these are placed at the ends of sections rather than inside the section to prompt students to review soon after reading a section. Additionally, almost every chapter contains bonus material for enrichment or fast-paced classes, and all chapters contain guides to further study. The chapters are organized into three themes (background, combinatorics, and graph theory), with two additional chapters (on probability and cardinality). The first chapter introduces both combinatorics and proof, and the third chapter introduces graph theory, so there is thematic foreshadowing within the first theme. All chapters after the first five assume knowledge of the first five chapters. (A detailed disclosure of dependencies appears in Section 3.) My advice for how to deal with the ebb and flow of course pacing is to strictly adhere to a one-chapter-per-week schedule (choose topics for your syllabus accordingly!), and in this way achieve breadth rather than depth in student acquisition of the material. It may be tempting (especially for the first few chapters!) to have students work through the entirety of the activities in a chapter and to review the reading and . . . but in this way, one can get dragged down into belaboring material. Instead, leave some material for student study. In fact, while there are three classes’ worth of material presented in each chapter, they are underpinned by only two substantial classes’ worth of activities. Students’ pacing will not be uniform; if your class gets behind your intended schedule, no harm will be done if you skimp on some chapters by reducing the work to two days. On the topic of course mechanics, I assign daily readings (specified in each chapter’s Instructor Notes section) and elementary practice problems (under the Check Yourself label). I also assign homework each week, taken from the Problems section of the previous week’s material. The purpose of this timing is to allow concepts some time to sink in and to prompt students to review. For a course of this level, I give both in-class and take-home exams. In-class exams are composed mostly of computational or simple problems (like Check Yourself exercises), but with a few end-of-chapter-level problems thrown in as well. My take-home exams often involve end-of-chapter-level problems and sets of problems from Bonus sections. I have included a selection of additional problems at the end of the book from which you may draw exam and review problems. Discrete Mathematics with Ducks is written to be ideal for instructors who like active learning. If you have no experience with active learning techniques but would like to try some, then read on, for I’ll give a short introduction below. However, if you don’t give a flying figwhistle for that frippery-frappery, this book can work for you too. There are lots and lots of problems for a lecturer to use as examples (particularly in the Try This! sections) and homework assignments. All instructors should be aware that many sections throughout the text begin with Hey! You! warnings (indicated by the marginal stop-sign-holding duck shown here) that caution students not to read portions of the text before working on the relevant in-class activities. Make sure to tell your students whether or not to honor the don’t-read-ahead edicts. At the end of each chapter, I have included a section entitled Instructor Notes. This gives a breakdown of how I would (and how you might) conduct two to three classes on the chapter material. If you have other ideas on how to use the chapter, try them! And if they work well, please do share them with me. For those who like to partition course material among groups of students who present topics, the Try This! sections can function as projects. If you prefer that individual students make presentations, then you may wish to steer weaker students away from material in chapters where Try This! sections come before informational sections. All links mentioned in the text, as well as GeoGebra files mentioned in the text, are available electronically at http://www.toroidalsnark.net/dmwdlinksfiles.html. 2.1 A Start on Discovery-Based Learning My personal implementation of discovery-based learning in the classroom rests on having students collaborate in small groups to do mathematics. In order to have enough class time for group work, I require that students attempt to read relevant material in advance. For this book, I have taken special care to make the reading as elementary as possible so that students are able to read it and learn from it. (Let’s hope I have succeeded in this endeavor.) I am regularly asked how I get students to read a textbook. The pat answer is that I assign students to read the book, and expect students to read the book, and then they do so. However, others tell me that they also assign and expect reading but that students do not do it. Observers of my classes tell me that the difference is that I truly hold students responsible for reading the book. I do not repeat material in class that they could have learned by reading. At most, I give a review or an interactive example or exercise at the start of class. I recommend that if you lecture over book material, do so briefly. How much time is spent on lecture-like activities depends on you; I spend less than 15 minutes per class on lecture-like activities. When instructors step away from lecturing and turn over some control of the class to students, they often feel as though they are not covering as much material as they would be covering if they lectured. Coverage is mainly an illusion whether or not we lecture; however we structure our classes, and whatever material we believe we transmit to students, we have no actual control over what material enters or is synthesized within students’ minds. The main shift is in our perspective. Most of the Try This! sets of in-class exercises will likely take longer than a single class period to complete. This is intentional; my expectation is that the students will not collectively finish all of the problems. I have tried to include enough problems, and some difficult problems, so that strong/advanced/speedy students will have things to think about while other students soldier on. Additionally, having more problems means that students have some choice in what they work on. For the most part, Try This! problems do not need to be done sequentially. It takes a while to gauge in advance how long it will take your students to work a problem. With many subjects and texts, an instructor will allocate additional class time to incomplete in-class activities, or will lecture on remaining problems. For this text, I recommend a different approach. If it takes your students an hour to do three problems, then I advise you to accept that the students will only experience discovery for those three problems. Just continue with the course; after a class period’s worth of experimentation, students can read about the material in the reinforcing sections. (Everything important is contained in the reading.) Because this is a survey course, it is more important that students gain exposure to a variety of concepts than that they fully master many of them.