Course Objectives:The aim is to help the student to gain the ability to use some of the fundamental methods of discrete mathematics, linear algebra and probability theory in Computer Science. They will be able to use these methods in a variety of sub-fields of computer science ranging from algorithms & complexity, machine learning to software engineering, computer networks, databases and speech processing.
SyllabusLanguage of Math – Logic, Proof techniques, (infinite) sets, countable and uncountable sets, Cantor’s diagonalization, Applications to undecidability.
Combinatorics – General Counting methods, Recurrence relations, Generating Functions, Principle of Inclusion-Exclusion, Posets and Lattices - Permutations, Groups and algebraic structures.
Linear Algebra – Fields, Vector Spaces, Basis, Matrices and Linear Transformations, Eigen values, Orthogonality, Vector and Matrix Norms - Applications to optimization problems and graph theory
Probability – Sample space, Distributions, Random Variables, Expectation,Tail Inequalities - Chernoff Bound, Chebyshev inequality, Functions of random variables,Applications.
Learning Outcomes:We will be working on the top five levels of Bloom's Taxonomy. After completing the course, the student will be able to (in other words, this is what the exams will test):
- Use logical notation to define and reason mathematically about the fundamental data types and structures (such as numbers, sets) used in computer algorithms and systems.
- Comprehend and Evaluate rigor in the definitions and conclusions about mathematical models and identify fallacious reasoning and statements.
- Identify and Apply properties of combinatorial structures and properties - know the basic techniques in combinatorics and counting.
- Gain the conceptual background needed to prove and use propositions, theorems of linear algebraic nature.
- Know, Explore and Apply the theory of linear maps, eigenvalues and eigenvectors, characteristic polynomials.
- read, comprehend and learn advanced linear algebraic techniques like spectral theory, singular value decomposition and applications of linear algebra.
- Use basic combinatorics to obtain probabilities.
- Recognize and abstract out finite dimensional probability spaces.
- Identify and apply concepts of expectation, conditional probability and tail inequalities.
- Short Exams(4x5%)
- Quiz-I (20%)
- Quiz-II (20%)
- End-Sem Exam (40%)
Evaluation SchemeThe weightage scheme for various activities and evaluation results will be as follows :
Course Pre-requisites:The IITM curriculum aims this core course to be delivered to the first year M.Tech and possibly as an elective to MS/PhD students, who may or may not have gone through a formal discrete mathematics course (or even a computer science course !) in the undergraduate level. Hence the formal pre-requisites are really none. However, in order to avoid over-simplification of the material aimed at a masters level course, this course will look for some basic discrete mathematics from the undergrad curriculum to build upon.
Frequently Asked Questions
Q : Why is the course designed to be so dense and diverse? Is it not ambitious to do justice to all the topics in one course?
A : Yes, it is. Unfortunately, this had to be done because of the design constraints. The course is/was to be designed and designated to be a (feeder) core course to the variety of areas in computer science that are pursued in the CSE department. It also takes in, at the input side, students with highly varied background in CS. This has caused (sometimes spatially inconsistent) constraints for the contents. We will be doing the best we can !