CS 201: Mathematics for Computer Science
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.
Abstract algebra
- Abstract algebra, Dummit and Foote.
- Notes on Group Theory , Peter J. Cameron.
Administrivia
- TA: Aakanksha(aakansh), Amit(amitks), Rizwan(mrrawani), Susmitha(susmitha).
- Lectures: Mon-Thu 12:00-12:50, Fri 5:10-6:00 in RM 101.
- Anti-cheating and Drop policy from CSE department.
- The copies will be rechecked only if correct solution is marked incorrect. No requests for more marks/mercy marks will be entertained. In case more mistakes are found in the solution, marks can decrease after rechecking.
- Partial marking: If some part of the proof/argument is correct, you will get full credit for that.
- No mercy pleas for better grades in the end will be entertained.
- Assignments (10%): Assignments SHOULD be written independently. If you discuss assignment with a friend, please mention their name on your assignment.
- Quizzes (30%): 4 Quizzes of 50 minutes each. Each will be announced a few days in advance.
- Mid-sem exam (25%): 2 hours as scheduled by DoAA.
- End-sem exam (35%): 3 hours as scheduled by DoAA.