None

## Recommended Book(s)

Discrete Mathematics And Its Applications With Combinatorics And Graph Theory, 6th Edition; By Rosen; McGraw-Hill.

## Reference Book(s)

Essentials Of Discrete Mathematics David J. Hunter (Reference Book)
Invitation To Discrete Mathematics (2nd Edition), By Matousek And Nevestril.
Discrete Mathematics Elementary & Beyond, By Lovasz, Pelikan And Vesztergombi

## COURSE OBJECTIVES

This course will lay the foundations for theoretical computer science. Basic mathematical concepts generally required for most computer science courses will be covered in the course. The course aims at developing precise and formal reasoning skills in students. Different ways of mathematical thinking will be explored i.e. Logical thinking, Relational thinking, Recursive thinking, Quantitative thinking and Analytical thinking.

### COURSE LEARNING OUTCOMES (CLO)

Course Objectives

## COURSE CONTENTS

### Basics

Sets and their properties, Sequences, Summations

### Logical Thinking

• Propositional and Predicate Logic (5 lectures)
• Truth Tables, Quantifiers, Implications, Logical fallacies
• Proof Techniques (7 lectures)

### Recursive Thinking

• Recursion, Recursive Definitions and induction (1 lecture)

### Relational Thinking

• Functions, Relations, Closures, Equivalences (3 lectures)
• Graphs (3 lectures)
• Subgraphs, Graph Isomorphism, Degree sequences
• Connectivity
• Eulerian graphs, Hamilton graphs
• Shortest paths
• Trees ( 3 lecture)
• Basic Properties
• Application
• Tree traversal
• Spanning trees/MST

### Quantitative Thinking

• Number Theory (3 lectures):
• Division algorithm, GCD, LCM (Homework)
• Prime numbers, Fundamental theorem, Co-prime numbers, congruences
• Combinatorics (4 lectures)
• Permutations, Combinations, Binomial Coefficients
• Inclusion-Exclusion
• Pigeonhole principle

### Analytic Thinking

• Algorithms, Complexity (2 Lectures)

Quizzes
Assignments
Midterm/s
Final