Close Menu

COMP2101

Course Title: 
Discrete Mathematics for Computer Science
Credits: 
4
Educational Level: 
II
Semester offered: 
I
Associated Programme: 
B.Sc. CS
Core Course: 
yes
Course Aims: 

The role of Mathematics in Computer Science has at least two facets:

  • it provides a basis for the theoretical aspects of computing (especially analysis of algorithms and the theory of computation), and
  • it supports the application of computation to problems in science and engineering.

This course aims to introduce students to a selection of topics that addresses both facets. First, it introduces them to fundamental concepts in theoretical computer science, such as proof by induction and the use of graphs as a general abstraction mechanism. Second, it exposes students to specific topics that are likely to be relevant to many of the areas of application of computing, particularly in the science and engineering disciplines.

Syllabus: 
  • Background
    • Asymptotic Analysis
    • Limits
    • Orders of Growth
  • Counting
    • Permutations
    • Combinations
    • Inclusion-exclusion principle
  • Elementary Probability Theory
    • Counting in event space
    • Probability Tree
    • Bernoulli distribution
    • Geometric distribution
    • Binomial distribution
    • Poison distribution
  • Elementary Number Theory
    • Modular Arithmetic
    • Chinese Remainder Theorem
    • Groups formed from Z modulo a prime
  • Generating Functions and their Applications
    • Convergence Properties
    • Convolution
    • Applications to:
      • signal processing
      • image compression
      • solving linear recurrences
      • probability theory
      • error detection and correction
  • Graph Theory
    • Trees
    • Planarity
    • Spanning Trees
    • Eulerian and Hamiltonian Cycles
    • Colouring
    • Matching
Course Assessment: 
  • Final Exam (2-hours long)     60%
  • Coursework (in-course test and assignments)   40%

Students will be required to pass both the coursework and the final examination to pass the course.

Course Prerequisites: 

COMP1161

Top of Page