CSE 260 Discrete Structures in Computer Science

# CSE 260 Discrete Structures in Computer Science (4 cr: 3 lecture + 1 recitation)

## Catalog Course Description

Propositional and first order logic. Equivalence and methods of proof. Basics of counting. Set operations, relations, functions. Grammars and finite state automata. Discrete probability. Applications to computer science and engineering.

## Course Outcomes (Letters refer to program outcomes; caps indicate greater emphasis.)

The role of discrete mathematics in computer science is analogous to the role of calculus in physics and in engineering: it provides the mechanisms that allow computer scientists to define and to reason about complex systems.

1. The goals of this course are to introduce several of the mathematical concepts that provide the basis for much of computer science and to develop the ability to describe and to analyze problems in a logical and systematic fashion. To achieve these objectives, broad, general concepts in these areas will be studied, with applications in computer science and in computer engineering used to illustrate concepts. (A, i, J)
2. More specific outcomes are below. Program outcomes (A, i, J) relate to each course outcome. Applications in the practice of CS will be studied for all types of the theory.
1. Students will be skilled in propositional logic, including modeling English descriptions with propositions and connectives and doing truth table analysis. Students will be conversant in predicate logic.
2. Students will be able to use various methods of proof, such as direct, proof by contradiction, and mathematical induction.
3. Students will be conversant in the concepts of sets and their refinements as relations and functions.
4. Students will be able to solve basic counting and combinatoric problems.
5. Students will demonstrate how grammars and FSAs can be used to define and to recognize a language (set of strings) for Type 2 and Type 3 languages. Students will be able to design practical machines using methods FSAs.
6. Students will demonstrate understanding how probabilities are defined and used in cases where there are a discrete set of possibilities.

## Program Outcomes covered in CSE 260

(a)
An ability to apply knowledge of computing and mathematics appropriate to the discipline
(i)
An ability to use current techniques, skills, and tools necessary for computing practice
(j)
An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices

## Assessment

Assessment of how well outcomes are being achieved will be done by applying a rubric to a random sample of at least 25% of the students who have completed the work being used for assessment. Assessment tools are examinations and programming projects. For each outcome being assessed, each student in the sample will be judged to (a) exceed, (b) meet, or (c) fail to meet an objective standard designed to assess this outcome. Unless otherwise specified the thresholds used are: meet (70%), exceed (85%). We will say that this offering of the course achieved the particular outcome if and only if 70% or more of the students sampled were assessed to be in categories (b) or (c).

• Students will be skilled in propositional logic, including modeling English descriptions with propositions and connectives and doing truth table analysis. Students will be conversant in predicate logic.
Student can use a truth table to determine if a propositional wwf with any of the standard connectives as a tautology, contradiction, or contingency. Student can translate basic English statements into propositions. Student can apply logically equivalent forms to transform well-formed formulas.
Student will understand existential and universal quantification and its semantics in cases used in mathematics and cases stated in English. Student can apply logically equivalent forms to transform well-formed formulas.
• Students will be able to use various methods of proof, such as direct, proof by contradiction, and mathematical induction.
Directly assessed via exam questions.
• Students will be conversant in the concepts of sets and their refinements as relations and functions.
1. Students will demonstrate problem solving based on set concepts.
2. Students will demonstrate ability to solve problems dealing with relations and functions.
Directly assessed by exam questions.
• Students will be demonstrate ablity to solve basic counting and combinatoric problems.
Directly assessed by exam questions.
• Students will demonstrate how grammars and FSAs can be used to define and to recognize a language (set of strings) for Type 2 and Type 3 languages. Students will be able to design practical machines using methods FSAs.
1. Students will demonstrate ability to define a language using a grammar.
2. Students will demonstrate ability to define a language using an FSA.
3. Students will demonstrate ability to recognize a language using a grammar.
4. Students will demonstrate ability to recognize a language using an FSA.
5. Students will demonstrate ability to apply grammars and FSAs to lexical analyzers.
6. Students will demonstrate ability to apply FSA theory to physical machine design.
Directly assessed by exam questions.
• Students will demonstrate problem-solving using probabilities in cases where there are a discrete set of possibilities.
Directly assessed by exam questions.

## Topics

• Propositional and pred logic
• Methods of proof
• Set theory and functions
• Math Induction and recursion
• Boolean algebra
• Discrete Probability
• Grammars
• Derivation trees
• Finite state machines
• Equivalence relations

## Textbook

• Discrete Mathematics and its Applications, sixth edition (Kenneth H. Rosen; 2006)