CCOG for CS 251 archive revision 201403

You are viewing an old version of the CCOG. View current version »

Effective Term:
Summer 2014 through Winter 2025

Course Number:
CS 251
Course Title:
Discrete Structures II
Credit Hours:
4
Lecture Hours:
30
Lecture/Lab Hours:
0
Lab Hours:
30

Course Description

Introduces discrete structures and computational techniques in the areas of functions, relations, probability, graph theory, algorithm analysis, and finite state automata. 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.