Pre-requisite(s)

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)
    • Direct, Contradiction, Contra-positive, Induction

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)

MAPPING OF CLOs TO ASSESSMENT MODULES

Quizzes
Assignments
Midterm/s
Final