National University Of Singapore

Discrete Structures

CS1231

Iowa State Course Substitution

Theoretical Foundations of Computer Engineering

CPR E 310

Course Info
International Credits:
4.0
Converted Credits:
3.0
Semester:
spring
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

Evaluation Date:
September 21, 2016
Evaluated:
Chris Chu
Comments: