- Course Number:
- CS 251
- Course Title:
- Discrete Structures II
- Credit Hours:
- 4
- Lecture Hours:
- 30
- Lecture/Lab Hours:
- 0
- Lab Hours:
- 30
- Special Fee:
- $12.00

#### Course Description

Introduces discrete structures and computational techniques in the areas of functions, relations, probability, graph theory, algorithm analysis, and finite state automata. Prerequisites: CS 250. Audit available.#### Intended Outcomes for the course

Upon the successful completion of this course students will be able to:

? Formulate, interpret, and apply properties of propositional and first-order predicate calculus in real world

contexts.

? Use analytical problem solving strategies to solve problems using multiple approaches and to interpret the

results in practical terms.

? Utilize those techniques in discrete mathematics and logic that are used in the study and practice of computer

science.

? Be successful in subsequent coursework in the mathematical foundation of Computer Science.

#### Outcome Assessment Strategies

Assessment must include:

1. At least two in-class proctored examinations, one of which may be the final exam, and

2. At least two of the following additional measures, where at least one includes writing:

a) Take-home examinations. (Group and/or individual)

b) Projects. (Group and/or individual)

c) Quizzes. (Group and/or individual)

d) Graded homework/worksheets.

e) In-class activities.

f) Attendance.

#### Course Content (Themes, Concepts, Issues and Skills)

Major Topics:

· Apply the properties of propositional calculus to: determine whether a wff is a tautology, a contradiction, or a contingency by truth tables and by Quine's method; construct equivalence proofs; and transform truth functions and wffs into conjunctive or disjunctive normal form.

· Describe the basic inference rules and use them to write formal proofs in propositional calculus.

· Apply the properties of first-order predicate calculus to: determine whether a wff is valid, invalid, satisfiable, or unsatisfiable; construct equivalence proofs; and transform first-order wffs into prenex conjunctive or disjunctive normal form.

· Describe the rules of inference for quantifiers and use them along with the basic inference rules to write formal proofs in first-order predicate calculus.

· Write formal proofs in first-order predicate calculus with equality.

· Construct partial correctness proofs of simple imperative programs and construct termination proofs for simple loops.

· Transform first-order wffs into clausal form; and unify atoms from a set of clauses.

· Describe the resolution inference rule; use it to write formal proofs in first-order logic; and describe how resolution is used to execute a logic program.

· Transform simple English sentences into formal logic (propositional, first-order, or higher-order).

· Apply appropriate algebraic properties to: simplify Boolean expressions; simplify regular expressions; write recursive definitions for simple functions in terms of operations for abstract data types; write expressions to represent relations constructed in terms of operations for relational databases; and work with congruences.