CPEN 205:Discrete Mathematical Structures

Main block


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.