Preface
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
1 Communications of the ACM, Vol. 11, Issue 3 (March 1968), pp. 151–197.
2 Computer Science Curricula 2013, Pre-release version, http://cs2013.com
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
1 Communications of the ACM, Vol. 11, Issue 3 (March 1968), pp. 151–197.
2 Computer Science Curricula 2013, Pre-release version, http://cs2013.com