AY2024/25 Semester 1
Course Information - Description

Title:

CS1231S Discrete Structures

Description:

This course 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 Combinatorics: Pigeonhole Principle, Inclusion-Exclusion Principle, Number of relations on a set, number of injections from one finit 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.

(Course descriptions for all NUS courses may be found on NUS Bulletin.)

Prerequisite:

A-level Mathematics or H2 Mathematics or MA1301 or MA1301FC or MA1301X

Preclusions:

MA1100 and CS1231

Modular Credits:

4 MCs

Workload:

3-1-0-3-3
Workload components: A-B-C-D-E
A: number of lecture hours per week
B: number of tutorial hours per week
C: number of lab hours per week
D: number of hours for projects, assignments, field work, etc. per week
E: number of hours for preparatory work by a student per week

Schedules:

Refer to Schedules.