Preface to Mathematical structures for computer science : discrete mathematics and its applications.
A course in discrete structures (discrete mathematics) played an important role in Curriculum 68, the very first ACM Computer Science Curriculum Guide: “This course introduces the student to those fundamental algebraic, logical, and combinatoric concepts from mathematics needed in the subsequent computer science courses and shows the applications of these concepts to various areas of computer science.”1 Fast forward 45 years or so (through mobile computing, wireless networks, robotics, virtual reality, 3-D graphics, the Internet …) to the joint ACM/IEEE-CS Computer Science Curricula 2013, where—still— discrete structures are of fundamental importance.
“The material in discrete structures is pervasive in the areas of data structures and algorithms but appears elsewhere in computer science as well. For example, an ability to create and understand a proof—either a formal symbolic proof or a less formal but still mathematically rigorous argument—is important in virtually every area of computer science, including (to name just a few) formal specification, verification, databases, and cryptography. Graph theory concepts are used in networks, operating systems, and compilers. Set theory concepts are used in software engineering and in databases. Probability theory is used in intelligent systems, networking, and a number of computing applications.”2 This Seventh Edition was guided by Curricula 2013, and virtually all of the Core Tier 1 and Tier 2 topics for discrete structures from that document are included.
Covering all those topics can fill a one-semester course, but there is certainly enough material in this edition to make for a very respectable two-semester course. However much we as instructors may see the value in this foundational course, it is a difficult experience for many students, who often view it as a series of unconnected topics with little or no application to the rest of their chosen field of study. In the big picture, these topics are bound together by themes of
• importance of logical thinking
• power of mathematical notation
• usefulness of abstractions
but such themes are best appreciated in hindsight. Telling students, “You will need ideas from this course in many of your future computer science courses,” is also of little motivation. That’s why it is important to carve out time in your course syllabus (for either a one-semester or two-semester course) for some of the applications of this material. Here are topics in this edition that you may choose from, according to your interests and the interests of your students. Yes, students will probably see most of these topics in more detail in later computer science courses, but a quick introduction now can keep their interest and make your claim of relevance more credible.
Contents of Mathematical structures for computer science : discrete mathematics and its applications pdf
Chapter 1 Formal Logic
Chapter 2 Proofs, Induction, and Number Theory
Chapter 3 Recursion, Recurrence Relations, and Analysis of Algorithms
Chapter 4 Sets, Combinatorics, and Probability
Chapter 5 Relations, Functions, and Matrices
Chapter 6 Graphs and Trees
Chapter 7 Graph Algorithms
Chapter 8 Boolean Algebra and Computer Logic
Chapter 9 Modeling Arithmetic, Computation, and Languages
Appendix A Derivation Rules for Propositional and Predicate Logic
Appendix B Summation and Product Notation
Appendix C The Logarithm Function
Download Mathematical structures for computer science : discrete mathematics and its applications in free pdf format.