7.14. Discrete Structures I (Mandatory)

7.14. Discrete Structures I (Mandatory)

Figure 7.14: Connection Map. CS1D1 Discrete Structures I

7.14.1. Justification ↑ Back to top

Discrete structures are the backbone of computer science. This first course focuses on the fundamental logic and formal reasoning necessary to evaluate the correctness of computational processes. Students will master the formal language of mathematics to avoid ambiguity and will learn various proof techniques essential for the rigorous analysis of algorithms and software specifications.

7.14.2. Generales Goals ↑ Back to top

  1. Understand the principles of mathematical logic and propositional calculus.
  2. Apply predicate logic to model complex constraints in computing.
  3. Master multiple proof techniques, including direct, contradiction, and induction.
  4. Develop the ability to formally argue the correctness of mathematical statements.

7.14.3. Contribution to Outcomes ↑ Back to top

ABET-1) An ability to identify, formulate, and solve broadly defined technical or scientific problems by applying knowledge of mathematics and science and/or technical topics to areas relevant to the discipline. (Usage)
ABET-2) An ability to formulate or design a system, process, procedure, or program for the intended purpose. (Familiarity)

7.14.4. Content ↑ Back to top

7.14.4.1. Discrete Mathematics (24 hours) [Skills ABET-1,ABET-2] ↑ Back to top

Bibliography: (Rosen, 2019; Lehman et al., 2018)

Topics

  1. Logic: propositional and predicate logic, quantifiers, proofs
  2. Sets: operations, cardinality, power sets, Cartesian products
  3. Relations: properties, equivalence relations, partial orders
  4. Functions: injective, surjective, bijective, composition, inverse
  5. Advanced logic: proof systems, completeness, decidability
  6. Advanced set theory: infinite sets, Cantor's diagonal argument

Learning Outcomes

  1. Explain propositional and predicate logic [Explain]
  2. Construct simple logical proofs [Apply]
  3. Define basic set operations and relations [Explain]
  4. Define properties of relations [Explain]
  5. Define types of functions [Explain]
7.14.4.2. Discrete Mathematics (24 hours) [Skills ABET-1,ABET-2] ↑ Back to top

Bibliography: (Rosen, 2019; Velleman, 2019)

Topics

  1. Logic: propositional and predicate logic, quantifiers, proofs
  2. Advanced relations: closures, lattices
  3. Advanced functions: recursive functions, computability

Learning Outcomes

  1. Construct simple logical proofs [Apply]
  2. Apply set operations to solve problems [Apply]
  3. Determine if a relation is an equivalence relation [Apply]
  4. Compose functions and find inverses [Apply]

7.14.5. Bibliography ↑ Back to top

Rosen, K. H. (2019). Discrete Mathematics and Its Applications. McGraw-Hill Education, 8th edition.

Lehman, E., Leighton, F. T., and Meyer, A. R. (2018). Mathematics for Computer Science. MIT OpenCourseWare.

Velleman, D. J. (2019). How to Prove It: A Structured Approach. Cambridge University Press, 3rd edition.

Spotted a typo, an outdated course, a broken link, or have a suggestion? Let us know.

Scan to open on your phone