# CSE

**Source**: https://cse.iitk.ac.in/pages/CS201.html
**Parent**: https://cse.iitk.ac.in/pages/ResearchAreasNew.html

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

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

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

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