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

WeekTopicNotes Unit, PartTutorialAssignment Due Dates
1Introduction and Course Overview
2Propositional Logic, First Order LogicUnit 1 Part 1,
Unit 1 Part 2
3BreakNone due to CNY
4Proofs In First Order LogicUnit 1 Part 3
5Set TheoryUnit 21Assignment 1, Release
6RelationsUnit 3
Recess WeekSunday, 2359
7Induction, RecurrencesUnit 42
8Algorithmic AnalysisUnit 5
9Graphs, Trees3
10Combinatorics
11Probability 14
12Probability 2Sunday, 2359
13Rounding Up5

Lecture Video Links

Week 2 Videos: Unit 1 - Part 1, Part 2

  1. Introduction to Propositions, and Logical Connectives
  2. Behaviour of Logical Connectives, Truth Tables, Logical Equivalences
  3. Predicates, and Quantifiers for First Order Logic

Week 4 Videos: Unit 1 - Part 3

  1. First Example of a Proof, Premises, Conclusions
  2. Rules of Our Proof System
  3. Proof Strategies, And Steps in Proofs vs Statements

Week 5 Videos: Unit 2

  1. Introduction to Set Theory, Set Notations, and Set Operations
  2. Proving Set Equivalences, and Other Proofs Involving Subsets and Power Sets

Week 6 Videos: Unit 3

  1. Relations, Operations on Relations
  2. Properties on Relations

Week 7 Videos: Unit 4

  1. Mathematical Induction
  2. Recurrences

Week 8 Videos: Unit 5

  1. Big O/Omega/Theta notation
  2. Substitution Method
  3. Program Correctness via Induction

Notes

Week 2 & 4

Unit 1: Propositions, Predicates, First Order Logic, Proofs

Week 5

Introduction to Set Theory

Week 6

Introduction to Relations

Week 7

Induction, Recurrences

Week 8

Program Analysis and Asymptotic Notation

Tutorials

  1. Tutorial 1 Released 21-Jan-2025. Due 11-Feb-2025 6:30PM.
  2. Tutorial 2 Due 11-Feb-2025 11:59PM.

Assignment

  1. 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