Discrete Structures (DS)
DS1. Functions, relations, and sets [core]
DS2. Basic logic [core]
DS3. Proof techniques [core]
DS4. Basics of counting [core]
DS5. Graphs and trees [core]
DS6. Discrete probability [core]

Discrete structures is foundational material for computer science. By foundational we mean that relatively few computer scientists will be working primarily on discrete structures, but that many other areas of computer science require the ability to work with concepts from discrete structures. Discrete structures include important material from such areas as set theory, logic, graph theory, and combinatorics. The notion of formal, mathematical proof is a unifying theme throughout the area.

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 formal proof is essential in formal specification, in verification, and in cryptography. Graph theory concepts are used in networks, operating systems, and compilers. Set theory concepts are used in software engineering and in databases.

As the field of computer science matures, more and more sophisticated analysis techniques are being brought to bear on practical problems. To understand the computational techniques of the future, today's students will need a strong background in discrete structures.

Finally, we note that while areas often have somewhat fuzzy boundaries, this is especially true for discrete structures. We have gathered together here a body of material of a mathematical nature that computer science education must include, and that computer science educators know well enough to specify in great detail. However, the decision about where to draw the line between this area and the Algorithms and Complexity area (AL) on the one hand, and topics left only as supporting mathematics on the other hand, was inevitably somewhat arbitrary. We remind readers that there are vital topics from those two areas that some schools will include in courses with titles like discrete structures.

DS1. Functions, relations, and sets [core]
Minimum core coverage time: 6 hours
Topics:

• Functions (surjections, injections, inverses, composition)
• Relations (reflexivity, symmetry, transitivity, equivalence relations)
• Sets (Venn diagrams, complements, Cartesian products, power sets)
• Pigeonhole principle
• Cardinality and countability

Learning objectives:

1. Illustrate by examples the basic terminology of functions, relations, and sets.
2. Illustrate by examples the operations associated with sets, functions, and relations.
3. Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.
4. Demonstrate basic counting arguments, including uses of diagonalization and the pigeonhole principle.

DS2. Basic logic [core]

Minimum core coverage time: 10 hours

Topics:

• Propositional logic
• Logical connectives
• Truth tables
• Normal forms (conjunctive and disjunctive)
• Validity
• Predicate logic
• Universal and existential quantification
• Modus ponens and modus tollens
• Limitations of predicate logic

Learning objectives:

1. Manipulate formal methods of symbolic propositional and predicate logic.
2. Demonstrate how to model algorithms and real-life situations using the formal tools of symbolic logic.
3. Demonstrate knowledge of formal logic proofs and logical reasoning through solving problems such as puzzles.

DS3. Proof techniques [core]

Minimum core coverage time: 12 hours

Topics:

• Notions of implication, converse, inverse, contrapositive, negation, and contradiction
• The structure of formal proofs
• Direct proofs
• Proof by counterexample
• Proof by contraposition
• Proof by contradiction
• Mathematical induction
• Strong induction
• Recursive mathematical definitions
• Well orderings

Learning objectives:

1. Outline basic proofs for theorems using the techniques of proof by contradiction and mathematical induction.
2. Relate the ideas of mathematical induction to recursion and recursively defined structures.
3. Apply proof techniques to solve problems in other areas of computer science, such as software engineering, program semantics, and algorithm analysis.

DS4. Basics of counting [core]

Minimum core coverage time: 5 hours

Topics:

• Counting arguments
• The pigeonhole principle
• Permutations and combinations
• Solving recurrence relations (common examples, the Master Theorem)

Learning objectives:

1. Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application.
2. State the definition of the Master theorem.
3. Solve a variety of basic recurrence equations.
4. Analyze a problem to create relevant recurrence equations or to identify important counting questions.

DS5. Graphs and trees [core]

Minimum core coverage time: 4 hours

Topics:

• Trees
• Undirected graphs
• Directed graphs
• Spanning trees
• Traversal strategies

Learning objectives:

1. Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each.
2. Model problems in computer science using graphs and trees.
3. Relate graphs and trees to data structures, algorithms, and counting.

DS6. Discrete probability [core]

Minimum core coverage time: 6 hours

Topics:

• Finite probability space, probability measure, events
• Conditional probability, independence, Bayes' rule
• Integer random variables, expectation

Learning objectives:

1. Calculate probabilities of events and expectations of random variables for problems arising from games of chance.
2. Demonstrate how to apply the tools of probability to CS-related problems including the average case analysis of algorithms, Las Vegas and Monte Carlo randomized algorithms, and hashing.

*Computing Curricula 2001
STEELMAN DRAFT -- August 1, 2001
This report is a working draft and does not carry
any endorsement from the sponsoring organizations.