This module, as it's name implies, is about the study of discrete mathematical structures such as logic, sets, relations, combinatorics and probability, and graph and trees. This module also gives an introduction to how to read mathematical texts, where students are expected to recognise symbols such as or . This module also gives an introduction to deriving and writing proofs, using techniques such as contradiction and mathematical induction. In the semester I took this module, there was a new chapter covering cardinality and the continuum, this chapter was really insightful and sparked a lot of curiosity into set theory for me.

I found this module really fun and challenging, and it served as a good foundation for reading other mathematical texts. While many students treat this module as an "SU" module, I felt that the only challenge was to grapple with new concepts alien to us, and the problems presented with these concepts were not hard at all. In my opinion, this module is the easiest math module out of the three common year 1 modules, the others being MA1521 and MA1522.

Module components

Every week there is 3 hours of lectures, and 2 hours of tutorials. Some of the tutorial questions can get quite challenging, but its not required to do them. Here is the full assessment breakdown:

Component	Weightage
Tutorial Attendance	5%
Assignments 1 & 2	10% + 10%
Midterms	25%
Finals	50%

Mathematical statements and logic

The first part of the module is to get students used to reading and understanding mathematical statements. Being able to understand how a quantifier or logical operator affects the entire statement is very important. At the end of the module, you will be expected to understand how to read statements such as

This module also covers logical operators and laws associated with them, which is important for understanding boolean algebra for computer science.

This part of the module should be relatively easy, as long as you do the tutorials you should have no problem reading such statements by the end of the module.

Proofs

This chapter goes through different types of proofs and how to write them. Students are expected to be very explicit in each step of the proof, and have to explain each step as well, by citing a property of the structure or a theorem from the notes.

For example, a proof that the sum of two even numbers are even is expected to be written as:

1. Let and be two particular but arbitrarily chosen even integers.

   1. Then and for some integers and (By definition of even integers)

   2. Then (By basic algebra)

   3. is an integer (by closure)

   4. is an integer (by closure)

   5. is an even number (by definition of even integers)

   6. Hence is an even integer

2. Therefore the sum of any two even integers is even

This can get very tedious, but you are expected to write like this for assignments, with a limit on the number of lines you can have in the proof. Luckily the midterms and finals relaxed these rules.

Sets, relations, and functions

These chapters gives a brief introduction into how sets work, and studies structures composed of sets such as relations and functions. I had hoped that it would touch more on set theory, but unfortunately sets are just used as a stepping stone to studying relations.

Relations touch on equivalence relations and its properties, partial/total orders, and well ordered sets. Functions are just another subset of relations.

There really isn't much to say about these chapters, the problems in the exam were about studying whether a relation has some property like reflexity. It's not that hard if your cheatsheet has the definition of the properties.

Mathematical induction

Again not much to say about this chapter, it's just normal mathematical induction. This chapter also touches on recursively defined structures, and how to perform induction on them. Some of the problems in this chapter may get tricky, but it's all about finding the right inductive step. If you come from JC this chapter should be familiar to you.

Cardinality

This was the most fun chapter for me, and its probably the most unintuitive chapter as well. It covers pigeonhole principle, countable and uncountable sets, and the continuum. I really enjoyed studying why some sets are countable, and coming up with proofs for uncountable sets.

As two sets are defined to have equal cardinality if there exists a bijection between them, a lot of this chapter is about proving that a function exists between two sets, and that this function is both injective and surjective.

Counting and probability

I didn't really pay much attention to this chapter, as its standard combinatorics. The questions are pretty standard too, typically asking you to count how many possible arrangements some scenario scenario has, or the probability of a discrete event happening, like choosing some sequence of objects from a bag.

Graphs

I would say this chapter is one of the more important ones, as graphs (and subsequently trees) are used everywhere in computer science and future modules in NUS. This chapter has a lot of definitions and terminologies (walk, path, cycle, etc.) and these terminologies are not standard either, so it would be useful to include them in a cheatsheet.

The questions on this topic can get difficult, usually asking you to prove a graph has some property, so I would suggest including some standard proofs on graphs to the open book exam.

Trees

Trees are just connected acyclic graphs. This chapter covers binary trees, pre/in/post order traversal, as well as Kruskal's and Prim's algo to construct minimum spanning trees. The questions for this chapter would involve reconstructing a tree from its traversals, and proving a graph with some property is a tree.

Conclusion

This module is very definition heavy, there are a lot of things to remember and you can not waste time in the exam constantly referring to the cheatsheet. To do well in this module, I would write a summary of the lecture content in Latex every week, so that I would have an easy reference to the lecture materials whenever I needed. This process also helped me cover any gaps I had in my knowledge, as I had to fully understand the lecture material before being able to write it down. It also helped that I was naturally curious about the module content, and would read up more about these structures on Wikipedia.

Overall I felt that while this module was not super rigorous, it sufficiently teaches me enough about discrete structures for use in future modules. I would rate it as one of the better introductory modules in the CS curriculum, and being able to reason and conceptualise the contents in this module will be useful for future ones.

Grade breakdown

Assessment	Marks
Assignment 1	39/40
Assignment 2	35.5/40
Midterms	47/50
Finals	73/100

Excepted grade: A
Final grade: A+