Basic Information

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.

Syllabus

• Language 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 finite dimensional probability spaces.
• Identify and apply concepts of expectation, conditional probability and tail inequalities.

Evaluation Scheme

The weights for various activities and evaluation results will be as follows :

• Short Exams(4x5%)
• Quiz-I (20%)
• Quiz-II (20%)
• End-Sem Exam (40%)



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