#### 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.

###### Books:

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.