CS 340 Discrete Structures for Engineers

Credit Hours:	4
Course Coordinator:	Jim Hein
Course Description:	A one-term introduction to discrete structures with applications to computing problems. Topics include sets, relations, functions, counting, graphs, trees, recursion, propositional and predicate logic, proof techniques, Boolean algebra. The course may not be used as part of the degree requirements for the BS degree in Computer Science. Prerequisites: CS 163, Math 252.
Prerequisites:	Data Structures and Calculus II
Goals:	Upon the successful completion of this course students will be able to: Describe basic properties of sets, bags, tuples, relations, graphs, trees, and functions. Perform traversals of graphs and trees; construct simple functions by composition of known functions; determine whether simple functions are injective, surjective, or bijective. Describe the concepts of countable and uncountable sets, and apply the diagonalization method to construct elements that are not in certain countable sets. Construct inductive definitions for sets and construct recursive definitions for functions and procedures. Determine whether a binary relation is reflexive, symmetric, or transitive and construct closures with respect to these properties. Use elementary counting techniques to count simple finite structures that are either ordered or unordered and to count the worst case number of comparisons for simple decision trees. Find closed form solutions for simple recurrences using the techniques of substitution, cancellation, and generating functions. Demonstrate standard proof techniques and the technique of inductive proof by writing short informal proofs about simple properties of numbers, sets, and ordered structures. Apply the properties of propositional calculus to: determine whether a wff is a tautology, a contradiction, or a contingency; construct equivalence proofs; and transform truth functions and wffs into conjunctive normal form and disjunctive normal form. Write formal proofs in propositional calculus and first-order predicate 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. Construct partial correctness proofs of simple imperative programs and construct termination proofs for simple loops. Apply algebraic properties of Boolean algebra to simplify Boolean expressions.
Textbooks:	Discrete Mathematics, Second Edition, by James L. Hein. Jones and Bartlett, 2003.
References:	None.
Major Topics:	Structures: sets and bags, ordered structures (tuples, lists, strings, products, relations), graphs and trees, functions (constructions, properties), countability. Recursion: inductively defined sets, recursively defined functions and procedures. Binary Relations: properties, equivalence, partial orders. Proof Techniques: direct and indirect proof, mathematical induction, well-founded induction. Analysis Techniques: closed forms, counting permutations and combinations, solving recurrences. Logic: propositional calculus, formal reasoning, first-order predicate calculus, equivalence, quantifier inference rules, program correctness. Boolean Algebra.
Laboratory Exercises:	None.

CAC Category Credits	Core	Advanced
Data Structures
Algorithms	0.3
Software Design
Computer Architecture
Programming Languages

Oral and Written Communications:	None.
Social and Ethical Issues:	None.
Theoretical Content:	The entire course is theoretical material (discrete mathematics and logic).
Problem Analysis:	The exercises and tests require problem analysis to find out which tools of discrete mathematics or formal logic are needed to solve a problem.
Solution Design:	The exercises and tests require students to solve problems by applying the tools of discrete mathematics or formal logic.