7.19. Discrete Structures II (Mandatory)

7.19. Discrete Structures II (Mandatory)

Figure 7.19: Connection Map. CS1D2 Discrete Structures II

7.19.1. Justification ↑ Back to top

Continuing from Discrete Structures I, this course explores more complex mathematical structures such as sets, relations, and functions, which are the basis for data modeling in databases and programming languages. Additionally, students will study counting techniques and recurrence relations, providing the analytical tools required to estimate the computational complexity of algorithms.

7.19.2. Generales Goals ↑ Back to top

  1. Perform complex operations on sets, functions, and relations.
  2. Model database relations and function properties formally.
  3. Apply counting techniques to analyze search spaces and probability.
  4. Solve recurrence relations to analyze the efficiency of recursive algorithms.

7.19.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.19.4. Content ↑ Back to top

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

Bibliography: (Rosen, 2019; Scheinerman, 2012)

Topics

  1. Sets: operations, cardinality, power sets, Cartesian products
  2. Relations: properties, equivalence relations, partial orders
  3. Functions: injective, surjective, bijective, composition, inverse

Learning Outcomes

  1. Define basic set operations and relations [Assessment]
  2. Apply set operations to solve problems [Usage]
  3. Define properties of relations [Assessment]
  4. Determine if a relation is an equivalence relation [Usage]
  5. Define types of functions [Assessment]
  6. Compose functions and find inverses [Usage]
7.19.4.2. Discrete Mathematics (24 hours) [Skills ABET-1,ABET-2] ↑ Back to top

Bibliography: (Rosen, 2019; Grimaldi, 2003)

Topics

  1. Counting: permutations, combinations, binomial theorem
  2. Advanced counting: generating functions, inclusion-exclusion
  3. Recurrence relations: solving simple recurrences
  4. Advanced recurrence: generating functions, asymptotic behavior

Learning Outcomes

  1. Explain permutations and combinations [Assessment]
  2. Apply counting techniques to solve problems [Usage]
  3. Define recurrence relations [Assessment]
  4. Solve simple recurrence relations [Usage]
  5. Develop generating functions for counting problems [Usage]
  6. Apply generating functions to solve complex recurrence relations [Assessment]

7.19.5. Bibliography ↑ Back to top

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

Scheinerman, E. R. (2012). Mathematics: A Discrete Introduction. Cengage Learning, 3rd edition.

Grimaldi, R. P. (2003). Discrete and Combinatorial Mathematics: An Applied Introduction. Pearson, 5th edition.

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

Scan to open on your phone