## CS 201: Mathematics for Computer Science

### Announcements:

• The class on Friday, 16th Nov, will be held from 12:00-12:50 in RM 101 instead of 5:10-6:00 in the evening.
• The endsem will be held on Monday, 26th Nov., from 9:00-12:00 in L20(OROS).

### Notes

 Topic Link Introduction to discrete mathematics, proofs Introduction Basic counting, recurrence relations and generating functions Counting Inclusion-exclusion, pigeonhole and linear algebra in combinatorics Misc. techniques Equivalence relations, partial order. Posets Graphs, connectivity, paths and cycles Graphs Coloring and matching Graph properties Basics of number theory, Modular arithmetic and Chinese remainder theorem Number theory Basic cryptography, Public key encryption and RSA Cryptography Fields, finite fields and applications Finite fields Groups, properties and Burnside's Lemma Groups

### Course description

The aim of this course is to learn discrete mathematics . Discrete mathematics is the study of mathematical structures which are discrete (elements have distinct, separate values as opposed to continuous structures). It is very difficult to find a branch in computer science which does not use discrete mathematics.

We will be covering four main topics: proofs, combinaotrics, graph theory and probability. The emphasis will be to learn different concepts and techniques used to prove theorems in computer science. The course will be full of puzzles and examples.

### References

#### Discrete Mathematics

• Discrete Mathematics and its Applications, K H Rosen.
• Discrete Mathematics, N L Biggs.

#### Combinatorics

• Combinatorics: Topics, Techniques, Algorithms, Peter Cameron.
• A Course in Combinatorics, J H van Lint and R M Wilson.
• Concrete Mathematics: A Foundation for Computer Science, R Graham, D Knuth and O Patashnik.

#### Number Theory

• Discrete Mathematics, N L Biggs.
• Introduction to Theory of Numbers, I Niven and H Zuckerman.
• An Introduction to the Theory of Numbers, G H Hardy and E M Wright.