Information Technology 322

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