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 includes important material from such areas as set theory, logic, graph theory, and combinatorics.

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. Explain with examples the basic terminology of functions, relations, and sets.
2. Perform 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 principles, including uses of diagonalization and the pigeonhole principle.

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. Apply formal methods of symbolic propositional and predicate logic.
2. Describe how formal tools of symbolic logic are used to model algorithms and real-life situations.
3. Use formal logic proofs and logical reasoning to solve problems such as puzzles.
4. Describe the importance and limitations of predicate logic.

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 the basic structure of and give examples of each proof technique described in this unit.
2. Discuss which type of proof is best for a given problem.
3. Relate the ideas of mathematical induction to recursion and recursively defined structures.
4. Identify the difference between mathematical and strong induction and give examples of the appropriate use of each.

Minimum core coverage time: 5 hours

Topics:

• Counting arguments
  • Sum and product rule
  • Inclusion-exclusion principle
  • Arithmetic and geometric progressions
  • Fibonacci numbers
• The pigeonhole principle
• Permutations and combinations
  • Basic definitions
  • Pascal's identity
  • The binomial theorem
• 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.

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. Demonstrate different traversal methods for trees and graphs.
3. Model problems in computer science using graphs and trees.
4. Relate graphs and trees to data structures, algorithms, and counting.

Minimum core coverage time: 6 hours

Topics:

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

Learning objectives:

1. Calculate probabilities of events and expectations of random variables for elementary problems such as games of chance.
2. Differentiate between dependent and independent events.
3. Apply the binomial theorem to independent events and Bayes theorem to dependent events.
4. Apply the tools of probability to solve problems such as the Monte Carlo method, the average case analysis of algorithms, and hashing.

CC2001 Report December 15, 2001