National University Of Singapore

Discrete Structures


Iowa State Course Substitution

Theoretical Foundations of Computer Engineering

CPR E 310

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.


Evaluation Date:
September 21, 2016
Chris Chu