COMP2201

Course Title: 
Discrete Mathematics for Computer Science
Credits: 
3
Educational Level: 
II
Semester offered: 
I
Core Course: 
yes
Syllabus: 
  1. Basics of Counting: Arithmetic and geometric progressions; Fibonacci numbers; The pigeonhole principle; Basic definitions; Pascal’s identity; The binomial theorem; The Master theorem.
  2. Asymptotic Analysis: Limits; Orders of Growth (Big- oh O, Omega Ω and Theta Θ).
  3. Graph Theory: Trees; Planarity; Eulerian and Hamiltonian Cycles; Matching and Colouring.
  4. Elementary Probability Theory: Counting in event space; Probability Tree; Probability distributions; Finite probability space, probability measure, events; Conditional probability, independence, Bayes’ theorem; Integer random variables, expectation; Law of large numbers.
  5. Generating Functions: Convergence Properties; Convolution; Applications.
  6. Recurrence Relations.
  7. Introduction to Automata, Grammars, and Languages: Finite-state machines; Context-free grammars; Language type classification and grammar type.
Course Assessment: 
  • Final Written Examination (2 hours)     60%
  • Coursework:     40%
    • 2 Quizzes       5%
    • In-course Test (1 hour)     15%
    • 4  Assessed Homework Assignments  20%
Course Prerequisites: 

COMP1210 - Mathematics for Computing OR MATH1152 - Introductions to formal Mathematics.