# CPEN 205:Discrete Mathematical Structures

#### Main block

Credits:
2

History and overview of discrete mathematical structures including reasons for studying the course and application areas, and how computer engineering makes use of the discrete structures. Functions and relations: functions, discrete versus continuous function, relations, continuous and discrete relations, sets – Venn diagram, power sets, complements.  Foundations of logic: propositional logic, logical connectives, truth table, normal forms, validity, predicate logic and limitations, universal and existential quantifications. Proof techniques: notion of implication, contradiction, structure of formal proofs, direct proofs, proof by counter example, proof by contraposition and contradiction, mathematical induction. Recursion and Recurrence Relations: concepts of recursion and recurrence, derivation of recurrence equations, initial condition, first order linear recurrence, constant coefficient recurrence, solution to a first order constant coefficient linear recurrence, iterating a recurrence. Counting: permutations and combinations, counting arguments rule of products, rule of sums, generating functions, modeling combinational problems. Graphs and trees: trees, directed and undirected graphs, spanning trees, shortest paths, applications.