CS6101E Mathematical Foundations Of Computer Science, Monsoon 2024-25

Course Outcomes:

CO1: Analyze and solve practical computing problems involving foundations of basic number theoretic and algebraic concepts and applying programming libraries for problem solving.
CO2: Analyze and solve computing problems using fundamental principles of linear spaces and analyze algorithms that use these concepts, and apply programming libraries for problem solving.
CO3: Derive algorithmic solutions for algebraic computing problems.

Syllabus:

Available here.

Office Hours:

Contact after class, or book an appointment via email. Instructor's office room is MB104.

References:

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, Third Edition, MIT Press, 2009.
Gareth A. Jones, Josephine M. Jones, Elementary Number Theory, Springer Science & Business Media, 1998.
Sheldon Axler, Linear Algebra Done Right, Third Edition, Springer, 2015.
David Steven Dummit, Richard M. Foote, Abstract Algebra, Hoboken: Wiley, 2004.
John B. Fraleigh, A First Course in Abstract Algebra, Pearson Education India, 2003.

Prerequisites:

NIL, though an undergraduate-level of understanding of mathematical proofs is assumed.

Evaluation Policy:

Assignments/quizzes (20%), Mid Semester Exam (40%), End Semester Exam (40%).

Attendance Policy:

Regular attendance is essential and expected. Those below 75% attendance will be given a W grade.

Standard of Conduct:

Violations of academic integrity will be severely penalized. Each student is expected to adhere to high standards of ethical conduct, especially those related to cheating and plagiarism. Any submitted work MUST BE an individual effort. Any academic dishonesty will result in zero marks in the corresponding exam or evaluation and will be reported to the department council for record-keeping and permission to assign an F grade in the course. The department policy on academic integrity can be found here.

Tentative Course Outline:

Sl No.	Week	Topic
1	Week 1	Divisibility, gcd, Prime numbers, Fundamental theorem of arithmetic
2	Week 2	Congruences, Groups and subgroups
3	Week 3	Homomorphism theorems, Cosets and Normal subgroups, Lagrange’s theorem
4	Week 4	Fermat's theorem, Euler function, Solution of congruences
5	Week 5	Rings, Chinese remainder theorem, Finite fields
6	Week 6	Primality testing, Discrete logarithms
7	Week 7	Polynomial arithmetic
8	Week 8	Mid Semester Exam
9	Week 9	Vector spaces, Basis, Dimension
10	Week 10	Linear maps, Rank nullity theorem, Duality theorem
11	Week 11	Eigenvalues and eigenvectors, Solution to systems of equations
12	Week 12	Inner product spaces, Orthogonality, Orthogonal projections
13	Week 13	Hermitian and unitary operators, Spectral theorem for Hermitian and unitary operators
14	Week 14	Singular value decomposition (SVD), Cholesky decomposition
15	Week 15	Buffer
16	Week 16	End Semester Exam