TWiki> Main Web>CSNewNonTraditionalMajors>SoftwareEngineeringAcceleratedProposedCurriculum>ElementaryDiscreteMathGPS (2013-10-24, RobertKasper) EditAttach

**MAT/CSC1053 Elementary Discrete Mathematics [3].** An elementary study of discrete mathematics as it relates to computer science. Topics include functions, proof techniques, sets, algebra, summation, number systems, logic, Boolean algebra, probability, combinatorics, and graph theory.

*Prerequisite: A grade of C- or better in MAT1013g, or a passing score on the Trigonometry Proficiency Examination.*

- Functions (surjections, injections, inverses, composition)
- Relations (reflexivity, symmetry, transitivity, equivalence relations)
- Sets (Venn diagrams, complements, Cartesian products, power sets)
- Pigeonhole principle
- Cardinality and countability

- Explain with examples the basic terminology of functions, relations, and sets.
- Perform the operations associated with sets, functions, and relations.
- Relate practical examples to the appropriate set, function, or relation model, and interpret the associated operations and terminology in context.

- Propositional logic
- Logical connectives
- Truth tables
- Normal forms (conjunctive and disjunctive)
- Validity
- Predicate logic
- Universal and existential quantification
- Modus ponens and modus tollens
- Limitations of predicate logic

- Apply formal methods of symbolic propositional and predicate logic.
- Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms.
- Use formal logic proofs and/or informal but rigorous logical reasoning to, for example, predict the behavior of software or to solve problems such as puzzles.
- Describe the importance and limitations of predicate logic.

- Notions of implication, converse, inverse, contrapositive, negation, and contradiction
- The structure of mathematical proofs
- Direct proofs
- Proof by counterexample
- Proof by contradiction
- Mathematical induction
- Strong induction
- Recursive mathematical definitions
- Well orderings

- Outline the basic structure of and give examples of each proof technique described in this unit.
- Discuss which type of proof is best for a given problem.
- Relate the ideas of mathematical induction to recursion and recursively defined structures.
- Identify the difference between mathematical and strong induction and give examples of the appropriate use of each

- Counting arguments
- Sum and product rule
- Inclusion-exclusion principle
- Arithmetic and geometric progressions
- Fibonacci numbers
- The pigeonhole principle
- Permutations and combinations
- Common examples

- Compute permutations and combinations of a set, and interpret the meaning in the context of the particular application.

- Trees
- Undirected graphs
- Directed graphs
- Spanning trees/forests
- Traversal strategies

- Illustrate by example the basic terminology of graph theory, and some of the properties and special cases of each.
- Demonstrate different traversal methods for trees and graphs.
- Model problems in computer science using graphs and trees.
- Relate graphs and trees to data structures, algorithms, and counting.

Topic revision: r3 - 2013-10-24 - RobertKasper

Copyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback