Home > Teaching > CS 201: Mathematics for Computer Science - I

CS 201: Mathematics for Computer Science - I

Credits: 3-1-0-10 ( 1 hour of tutorial every week)

Sets, proofs: [Weeks 1]

Sets, relations, functions, countable and uncountable sets.
Proofs; Proofs by deduction, contrapositive and contradiction (diagonalization).
Proofs by induction
* All these proof techniques can be covered through examples. The rigorous notion of proof will be covered in CS 202 and can be skipped here.

Basic Counting: [Weeks 2]

Selection/combination, arrangements/permutation, rule of sum, rule of product.
Binomial coefficients, identities, multinomial coefficients.
Selection with repetition/distributions of objects into cells, distinguishable/indistinguishable objects.
Combinatorial problems with restrictions

Generating functions: [Week 3]

Recurrence relations to solve combinatorial problems.
Generating functions to solve recurrence.

Counting techniques: [Weeks 4]

Inclusion-exclusion, Pigeonhole principle, Ramsey's theorem

Partial order: [Week 5]

Equivalence relations, partitions, partial order, posets, chain/antichain.

Graph theory: [Week 6 and 7]

Definitions, degree, paths, cycles, Hamiltonian path, Eulerian cycles.
cycles and acyclic graphs.
Trees, spanning trees, networks.

Number theory: [Week 8 and 9]

Divisibility, primes, division theorem, Euclid's gcd/extended Euclid's algorithm, Unique factorization domain.
Modular arithmetic, sums and products, Chinese remaindering, Mobius inversion.

RSA: [Week 10]

Fermat's little theorem, Euler's theorem.
Application: RSA.

Finite fields: [Week 11]

Z_p, the cyclic structure of Z_p^*.
Definition of the field as a generalization to F_p.
Application: Polynomials over F_p, error correction.

Group theory: [Week 12 and 13]

Definitions, examples (Z_n and Z_n^*)
cyclic and dihedral group, abelian groups.
Subgroups, cosets, partition
permutation group, transpositions, cycle representation
symmetries as a group.

Optional topics: [If time permits]

Applications Of Group Theory (Burnside lemma and generalization to Polya's theorem, use of group theory in combinatorics).
Other interesting applications.


1) Kenneth Rosen, Discrete mathematics and its applications.
2) Norman Biggs, Discrete mathematics.
3) Chung Liu, Introduction to combinatorial mathematics.
4) David Burton, Elementary number theory.