Course Objectives:

The aim is to help the student to gain the ability to use some of the fundamental methods of discrete mathematics in Computer Science. They will be able to use these methods in a variety of sub-fields of computer science ranging from complexity theory, algorithms, machine learning to software engineering, computer networks, databases.

Syllabus:

Number within brackets is the number of lectures we are likely to spend on the topic.

• Review of Basics (5): Sets, relations, and Functions.
• Proofs and Mathematical Logic (6): Good Proofs, Bad Proofs, Proof techniques. Propositional Logic, Truth tables, Tautologies, Resolution proof system, Predicate Logic.
• Counting & Combinatorics (9): Pigeon Hole Principle, inclusion exclusion, Review of permutation and Combinations. Combinatorial identities, double counting, Counting with bijections, Generating functions.
• Formal Arguments on Computation (9): Review of Chomsky heirarchy, Turing Machines, Unecidability.
  (if time permits) Resources of computation, time complexity.
• Linear Algebra (13): Vector spaces, Orthogonality, Eigen-value analysis, Vector and matrix norms, Multivariable analysis, Vector and matrix calculus, Unconstrainted and constrained oiptimisation problem solving methods.
• Random Variables and Stochastic Processes (14): Random variables, functions of random variables, sequences of random variables, stochastic processes, Markov chains, Markov processes, and queuing theory.

Learning Outcomes:

We will be working on the top five levels of Bloom's Taxonomy.
The student will be able to (in other words, this is what the exams will test):

• Use logical notation to define and reason about 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.
• Construct complete formal proofs/arguments for a target mathematical statement about such models.
• Model and compare different computational methods using analytic and combinatorial methods.
• Apply principles of discrete probability to real world situations.

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.

---

Last updated on Sat Nov 26 12:21:37 IST 2011