AY2025/26 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.

Prerequisite:

If undertaking an Undergraduate Degree THEN (must have completed 1 of 06 MATHEMATICS/ 07 FURTHER MATHEMATICS/21 PURE MATHEMATICS/22 APPLIED MATHEMATICS at a grade of at least E OR must have completed 1 of MA1301/MA1301X at a grade of at least D).

Preclusions:

If undertaking an Undergraduate Degree THEN (must not have completed 1 of CS1231/MA1100/MA1100T at a grade of at least D).

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.