National University Of Singapore
Discrete Structures
CS1231
Iowa State Course Substitution
Theoretical Foundations of Computer Engineering
CPRE 3100
Course Info
This module introduces mathematical tools required in the study of computer science. Topics include: (1) Logic and proof techniques: propositions, conditionals, quantifications. (2) Relations and Functions: Equivalence relations and partitions. Partially ordered sets. Well-Ordering Principle. Function equality. Boolean/identity/inverse functions. Bijection. (3) Mathematical formulation of data models (linear model, trees, graphs). (4) Counting and Combinatoric: Pigeonhole Principle. Inclusion-Exclusion Principle. Number of relations on a set, number of injections from one finite set to another, Diagonalisation proof: An infinite countable set has an uncountable power set; Algorithmic proof: An infinite set has a countably infinite subset. Subsets of countable sets are countable.
Review
- Evaluated Date:
- July 7, 2022
- Evaluated:
- Ahmed Kamal
- Expiration Date:
- July 7, 2027