Other links:
Other links:
Course objective: To lay the mathematical foundations for computational thinking for the core and elective courses including Algorithms and Data Structures, Compilers, Principle of Program Languages and Theory of Computation, and even Security to build on.
The course:
1. Introduces students to mathematical structures, tools, techniques, and frameworks for algorithmic and computational thinking.
2. Illustrates ways for problem formulation, representation, and analysis using mathematical models
3. Elucidates how mathematical rigour and formalism ensure soundness and completeness of computation
The emphasis throughout the course is on teaching how various concepts and results of mathematics are used in correct, efficient, and robust computations. It trains the students to think and reason about
computation in a programming language-agnostic manner. It complements the course on Introduction to Computer Science from mathematical perspective and thinking.
Pre-requisite: The course will expect familiarity with class 12 level mathematics (sets, relations, functions, basic logic and truth tables, basic counting and the principle of mathematical induction).
Coverage: Propositional and Predicate Logic – Arguments in Logic; Proof Techniques – What is a proof, Proof Methods and Strategy; Basic Structures: Sets, Functions, Relations, Countable sets vs uncountable, Cardinality, Sequences and Matrices; Problem Solving with Recursive Decomposition – Analysis of elementary algorithms for sorting and searching, Growth of Functions, Recursion and Iteration, Induction and Recursion; Graphs and Trees; Counting – Counting Principles like pigeonhole; Recurrence Relations and basic techniques for solving them like generating functions; Modular Arithmetic; Probability - expectation, probabilistic inequalities ; Information Theory
