Discrete Structures

Academic Year 2021 - 2022
Semester 1

NUSMods 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, Diagonalization 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.


This module was taught by Prof Aaron Tan and Prof Wong Tin Lok (from Math dept). Prof Aaron is very passionate and Prof Wong’s notes are top-class and rigorous. If you ask me, I prefer Prof Wong teaching this entire module.

There are 2 lectures, 1 x 2hr and 1 x 1hr and 1 x 2hr tutorial. Tutorial sheets are challenging which I enjoy solving a lot.

This module is actually my favourite module for my first semester of university. This is because it was new content that I had never learnt before. The ideas were not hard to grasp, but the questions can be very unnecessarily complex. I have a bone to pick though towards the end of the module, specifically Trees and Graphs. These topics are the most important in my opinion, especially when studying Graph Algorithms. However, there was such little time, that it was being rushed through. Hence, there was not enough time to actually internalise, appreciate and grasp the concept. I struggled alot with the last 2 topics. I actually did reasonably well for the Midterms but messed up the Finals as the nerves took over and my mind went blank. I was actually pretty confident of acing the Finals but I guess the pressure got the better of me. I did not do so well hence. Expected an A, but got somewhere near. This failure will forever haunt me.