National University Of Singapore

Discrete Structures

CS1231

Iowa State Course Substitution

Theoretical Foundations of Computer Engineering

CPRE 3100

Course Info

International Credits: 4.0
Converted Credits: 3.0
Country: Singapore
Language: English
Course Description:

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