Mathematical Techniques for Computing

Notes for Mathematical Techniques in Computer Science

Jan 20, 20263 min read

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 tutorials will be uploaded on YouTube before the respective 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 1, Tutorial 2 will be released on Week 3, and so on). 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 3, 5, 7, 9, 11, 13 on Tuesdays, 6:30 PM to 8:30 PM. Tutorial solutions will then be released online a day after the tutorial.

  • There are also 2 assignments and a final exam for the course. Tentatively, the final exam is on 30 Apr 2026, 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

Refer to the Page Class Schedule for the schedule for this semester.

Lecture Video Links

  1. Week 1: Propositional Logic
  2. Week 2: First Order Logic
    1. Part 1: Predicates and Quantifiers
    2. Part 2: Alternating Quantifiers
    3. Part 3: Implications and Equivalences

In case you’re curious about the old videos, you can find them on this page Old Videos.

Notes

Weeks 1 to 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

Week 9

Combinatorics and Counting

Week 10

Graphs

Week 11

Probability (Part 1)

Week 12

Probability (Part 2)

Tutorials

  1. Tutorial 1

Assignments

To be released

Course Grading

  • 4%: Post-lecture quizzes.
    • Released on Canvas.
    • Due weekly.
    • Unlimited tries 5 attempts. (To prevent guessing and gaming the answers.)
  • 16%: Tutorial Submissions
    • Best 4 out of 5 tutorial attempts.
    • Each tutorial attempt is 4%.
    • 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.
    • Submitted on Canvas
  • 30%: Written Assignments
    • Two assignments, 15% each.
    • Will be graded based on correctness.
    • Submitted on Canvas
  • 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

Graph View

Backlinks

  • No backlinks found