- Course Number:
- CS 251
- Course Title:
- Discrete Structures II
- Credit Hours:
- Lecture Hours:
- Lecture/Lab Hours:
- Lab Hours:
- Special Fee:
Course DescriptionIntroduces 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
? 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
? 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.
Course Content (Themes, Concepts, Issues and Skills)
· 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.