ITEC122: Discrete Mathematics.

Prerequisites: ITEC 120 (Grade of “C” or better) and MATH 125, MATH 126, MATH 138, MATH 140 or MATH 151.

Credit Hours: (3)

An introduction to discrete mathematical concepts including set theory, finite state machines, and induction.

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