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

CS 201: Mathematics for Computer Science - I

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.

[Weeks 4]

Inclusion-exclusion, Pigeonhole principal, Ramsey's theorem

Partial order: [Week 5]

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

Graph theory: [Week 6 and 7]

Definitions, degree, paths, cycles, Hamiltonian path, Eulerian cycles.
cycles and acyclic graphs.
Trees, spanning tree, 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, cyclic structure of Z_p^*.
Definition of 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.

Applications of group theory: [Week 14]

Burnside lemma and generalization to Polya's theorem (use of group theory in combinatorics).
Other interesting applications if time permits.


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.