This website’s intended usage by students taking discrete math courses at the School of Computing at NUS.
How the course is run:
-
Video lectures and tutorial will be uploaded on YouTube before the respect week. E.g. Week 2’s lecture videos will be out on YouTube. The expected video length per week is around 1 to 1.5 hours. You may find the list of videos below.
-
Tutorial sheets will generally be released on the same week as the start of the unit. i.e. Tutorial 1 will be released on week 2. Tutorial 2 will be released on week 5. Tutorial 3 will be released on week 7. Tutorial 4 on week 9. Tutorial 5 on week 11. We will try to make it so that the expected time worked on it is about an hour.
-
There are in-person tutorials for you to discuss tutorial solutions with the tutors on weeks 5, 7, 9, 11, 13 on Tuesday, at 6:30PM-8:30PM. Tutorial solutions will then be released online a day after the tutorial.
-
There are also 2 assignments and a finals exam for the course. Tentatively, the final exam is at 29-Apr-2025 5:00 PM, venue: TBD.
-
Assignment policy: Collaboration is allowed. No use of ChatGPT or other LLMs. List your collaborators, and your write-up must be done by yourself.
Course Schedule
| Week | Topic | Notes Unit, Part | Tutorial | Assignment Due Dates |
|---|---|---|---|---|
| 1 | Introduction and Course Overview | |||
| 2 | Propositional Logic, First Order Logic | Unit 1 Part 1, Unit 1 Part 2 | ||
| 3 | Break | None due to CNY | ||
| 4 | Proofs In First Order Logic | Unit 1 Part 3 | ||
| 5 | Set Theory | Unit 2 | 1 | Assignment 1, Release |
| 6 | Relations | Unit 3 | ||
| Recess Week | Sunday, 2359 | |||
| 7 | Induction, Recurrences | Unit 4 | 2 | |
| 8 | Algorithmic Analysis | Unit 5 | ||
| 9 | Graphs, Trees | 3 | ||
| 10 | Combinatorics | |||
| 11 | Probability 1 | 4 | ||
| 12 | Probability 2 | Sunday, 2359 | ||
| 13 | Rounding Up | 5 |
Lecture Video Links
Week 2 Videos: Unit 1 - Part 1, Part 2
- Introduction to Propositions, and Logical Connectives
- Behaviour of Logical Connectives, Truth Tables, Logical Equivalences
- Predicates, and Quantifiers for First Order Logic
Week 4 Videos: Unit 1 - Part 3
- First Example of a Proof, Premises, Conclusions
- Rules of Our Proof System
- Proof Strategies, And Steps in Proofs vs Statements
Week 5 Videos: Unit 2
- Introduction to Set Theory, Set Notations, and Set Operations
- Proving Set Equivalences, and Other Proofs Involving Subsets and Power Sets
Week 6 Videos: Unit 3
Week 7 Videos: Unit 4
Week 8 Videos: Unit 5
Notes
Week 2 & 4
Unit 1: Propositions, Predicates, First Order Logic, Proofs
Week 5
Week 6
Week 7
Week 8
Program Analysis and Asymptotic Notation
Tutorials
- Tutorial 1 Released 21-Jan-2025. Due 11-Feb-2025 6:30PM.
- Tutorial 2 Due 11-Feb-2025 11:59PM.
Assignment
- Assignment 1 Released 12-Feb-2025. Due 02-Mar-2025 23:59 (Canvas submission)
Course Grading
- 20%: Best 4 out of 5 tutorial attempts.
- Each tutorial attempt is 5%.
- To be clear, you do not need to get the correct solutions. We want to encourage you to attempt applying the concepts, not necessarily get them fully correct as you are learning. Any decent attempt will earn you the full 4%. We will take the best 4 marks out of 5 submissions.
- 30%: Two assignments, 15% each.
- Will be graded based on correctness.
- 50%: Final paper
- In person, open-book. No electronic devices.
Collaboration Policy:
- You may discuss high-level ideas with your classmates or friends. You should list your collaborators if you do so.
- Do not share your solutions.
- ChatGPT (and other LLMs) are not allowed.
- Your submission must be of your own write-up.
Late Policy:
- < 1 week after submission deadline: 50% penalty
- < 2 weeks after submission deadline: 75% penalty
- No submissions after 2 weeks.
Credits:
This webpage, the content, running the course would not have been possible without the help of my lovely TAs:
- Peh Hou Jin
- Zhao Xin Tong
- Maximus Ng
- Shane Arkar Kyaw