Preface OUR MOTIVATION AND VISION Many colleges and universities offer a course in discrete mathematics.Stu- dents taking these courses are from many disciplines,one of the largest being computer science.As a part of the Mathematics Across the Curricu- lum project at Dartmouth,supported by the National Science Foundation, we proposed to create a discrete mathematics course that directly addresses the needs of computer science students.In analyzing what topics in discrete mathematics we want our computer science students to know and why we want them to know these topics,we made two observations. First,there are a few topics we consider important to computer science that are not always covered thoroughly,if at all,in traditional discrete mathe- matics courses.Among these are recursion trees and the Master Theorem for solving recurrence relations,the probability theory needed to compute average run times and to analyze randomized algorithms,and an emphasis on strong and structural induction. Second,for each topic in discrete mathematics that we consider impor- tant for computer science students,there is a motivating topic in computer science that can be understood at the level of a first or second course in computer science.We feel this makes it possible to answer the age-old ques- tion students ask in applied mathematics courses:"Why do we have to learn this?"We therefore chose to write a textbook with computer science stu- dents in mind,with the objective of providing the necessary mathematical foundations for a computer science major,motivated by computer science problems that students can understand early in their study of computer science. In many computer science departments,discrete mathematics is one of the first courses taken by majors.It may even be a prerequisite to the first computer science course.In this case instructors are faced with a dilemma- teach the concepts purely mathematically with little or no visible application to computer science,or teach computer science examples to create a context Grant Number DUE-9552462 xxiPreface OUR MOTIVATION AND VISION Many colleges and universities offer a course in discrete mathematics. Stu￾dents taking these courses are from many disciplines, one of the largest being computer science. As a part of the Mathematics Across the Curricu￾lum project at Dartmouth, supported by the National Science Foundation,1 we proposed to create a discrete mathematics course that directly addresses the needs of computer science students. In analyzing what topics in discrete mathematics we want our computer science students to know and why we want them to know these topics, we made two observations. First, there are a few topics we consider important to computer science that are not always covered thoroughly, if at all, in traditional discrete mathe￾matics courses. Among these are recursion trees and the Master Theorem for solving recurrence relations, the probability theory needed to compute average run times and to analyze randomized algorithms, and an emphasis on strong and structural induction. Second, for each topic in discrete mathematics that we consider impor￾tant for computer science students, there is a motivating topic in computer science that can be understood at the level of a first or second course in computer science. We feel this makes it possible to answer the age-old ques￾tion students ask in applied mathematics courses: “Why do we have to learn this?” We therefore chose to write a textbook with computer science stu￾dents in mind, with the objective of providing the necessary mathematical foundations for a computer science major, motivated by computer science problems that students can understand early in their study of computer science. In many computer science departments, discrete mathematics is one of the first courses taken by majors. It may even be a prerequisite to the first computer science course. In this case instructors are faced with a dilemma— teach the concepts purely mathematically with little or no visible application to computer science, or teach computer science examples to create a context 1Grant Number DUE-9552462 xxi