ITEC 322: Discrete Mathematics for Computer Science
Prerequisites: ITEC 220 (Grade of “C” or better) and MATH 171 or MATH 169 or MATH 151
Credit Hours: (3)
An introduction to discrete mathematical concepts including set theory, finite state
machines, and induction.
Note(s): Scientific and Quantitative Reasoning designated course.
Detailed Description of Content of Course
Topics include:
1. Set and function: Venn diagrams, complements, Cartesian products, power sets, surjections, injections, inverses, composition, cardinality and countability, representation of signed and unsigned integer, modulo arithmetic’s
2. Complexity of algorithms: sequential and binary search algorithms, big O, omega, and theta notation, asymptotic analysis of upper complexity bounds, time and space complexity
3. Mathematical proofs and induction: validity, direct proofs, proof by contradiction, mathematical induction, strong induction, well orderings, recursive mathematical definitions, simple recursive functions
4. Counting principles: pigeonhole principle, sum and product rule, inclusion-exclusion principle, permutations and combinations, Pascal’s identity, the binomial theorem, arithmetic and geometric progressions
5. Relations and recurrence relations: reflexivity, symmetry, transitivity, equivalence relations, solving recurrence relations, the Master theorem
6. Graph and tree: binary search trees, undirected graphs, directed graphs, representations of graphs (adjacency matrix), depth- and breadth-first traversals, shortest-path algorithms (Dijkstra’s algorithm), spanning trees, minimum spanning tree (Prim’s and Kruskal’s algorithms), matching
7. Logic and switching circuits: implication, converse, inverse, contrapositive, propositional logic, predicate logic, limitations of predicate logic, Boolean algebra, logic gates
8. Modeling computations: Chomsky hierarchy, finite state machine, finite state automata, context sensitive- and free grammar
Detailed Description of Conduct of Course
The course is usually taught by lectures which present concepts and examples of applications. Regular homework exercises are assigned and discussed in class. Exercises range from routine drills on basic definitions and concepts to problems which require considerable ingenuity to solve.
Goals and Objectives of the Course
Students who complete the course will be able to:
1. Demonstrate an ability to design a mathematical argument
2. Demonstrate an ability to write mathematical proofs
3. Apply mathematical induction and design a recursive algorithm
4. Apply combinatorial analysis to solve counting problems
5. Analyze complexity of algorithms
6. Apply discrete structures to solve problems
7. Choose grammars and finite state machines to model computations
Assessment Measures
Students will be evaluated based on examinations, quizzes and assignments.
Other Course Information
None.
Review and Approval
October 1, 1991 Updated for 1991-92 Ivan B. Liss, Chair
May 12, 1994 Updated for 1994-95 Edward G. Okie, Chair
Oct. 30, 1996 Prerequisite change Edward G. Okie, Chair
Dec. 7, 2000 Prerequisite change John P. Helm, Chair
Sept. 25, 2001 Updated John P. Helm, Chair
Revised: June 1, 2012
April. 2019
March 01, 2021