Discrete Mathematics for Computer Science

Description

As the discipline of computer science has matured, it has become clear that a study of discrete mathematical topics is an essential part of the computer science major. The course in discrete structures has two primary aims. The first is to introduce students to the rich mathematical structures that naturally describe much of the content of the computer science discipline, including many structures that are frequently used in modeling and implementing solutions to problems. The second is to help students develop the skills of mathematical reasoning to learn new concepts and material in computer science. This learning takes place not only while they are students but also after graduation and throughout their professional life.

The two chapters dealing with graph theory and combinatorics are also core material for a discrete structures course, but this material always seems more intuitive to students than the formalism of the first four chapters. Topics from the first four chapters are freely used in these later chapters. The chapter on discrete probability builds on the chapter on combinatorics. The chapter on the analysis of algorithms uses notions from the core chapters but can be presented at an informal level to motivate the topic without spending a lot of time with the details of the chapter. Finally, the chapter on recurrence relations primarily uses the early material on induction and an intuitive understanding of the chapter on the analysis of algorithms.

A major aim of this book is to help you develop mathematical maturity-elusive as this objective may be. We interpret this as preparing you to understand how to do proofs of results about discrete structures that represent concepts you deal with in computer science. A correct proof can be viewed as a set of reasoned steps that persuade another student, the course grader, or the instructor about the truth of the assertion. Writing proofs is hard work even for the most experienced person, but it is a skill that needs to be developed through practice. We can only encourage you to be patient with the process. Keep trying out your proofs on other students, graders, and instructors to gain the confidence that will help you in using proofs as a natural part of your ability to solve problems and understand new material.