FM:10×1+6×5+2×10=60 PM:30 CH:48 Hrs
1. Logic and Proofs (10 hrs) 1.1 Proposition and Propositional Logic
1.2 Logical Connectives
1.3 Tautology, Contradiction and Contingency
1.4 Representing English sentences into Propositional Logic
1.5 Propositional Equivalences
1.6 Rules of Inferences
1.7 Valid Argument
1.8 Rules of Inferences
1.9 Testing Validity of Argument
1.10 Predicate Logic and Quantifiers
1.11 Rules of Inference for Quantified Statements
1.12 Proof Techniques:
a. Direct Method
b. Indirect Method (Contrapositive)
c. Proof by Contradiction
d. Trivial and Vacuous Proof
e. Proof by Counter Examples
f. Proof by Cases
2. Induction and Recursion (5 hrs)
2.1 Mathematical Induction and its Principle
2.2 Strong Induction
2.3 Recursive Definitions
2.4 Structural Induction
2.5 Recursive Algorithms and its Correctness
3. Number Theory (6 hrs)
3.1 Divisibility and Modular Arithmetic
3.2 Primes
3.3 Greatest Common Divisor (GCD)
3.4 Least Common Multiples (LCM)
3.5 Euclidean and Extended Euclidean Algorithm
3.6 Linear Congruence and solving Linear Congruence
3.7 Chinese Remainder Theorem
3.8 Computer Arithmetic with Large Integers
4. Recurrence Relations (6 hrs)
4.1 Recursive definitions of sequences
4.2 Applications of Recurrence Relations
4.3 Solving Linear Recurrence Relation:
a. Homogeneous Recurrence Relations
b. Non-homogeneous Recurrence Relations
5. Relation and Graph Theory (15 hrs)
5.1 Relation, Types of Relation and properties of relation
5.2 Representation of Relation
5.3 Equivalence Relation
5.4 Partial Order Relations and Partial Order Set (POSET)
5.5 Total Order Relations
5.6 Hasse Diagram
5.7 Lattice
5.8 Introduction to graph: Undirected and Directed Graph
5.9 Special type of graph
5.10 Graph Representation Methods
5.11 Graph Connectivity
5.12 Graph Isomorphism
5.13 Euler and Hamilton Graph
5.14 Shortest path problem: Dijkstra's Algorithm
5.15 Planar Graph and Applications
5.16 Graph Coloring and Applications
5.17 Tree and Tree Terminologies
5.18 Application of Tree:
a. Binary Search Tree
b. Game Tree
c. Decision Tree
d. Huffman Tree
e. Expression Tree
5.19 Tree Traversal and Techniques
5.20 Minimum Spanning Tree and algorithms (Prim's and Kruskal's)
5.21 Network Flows: Max-Flow and Min-Cut
6. Finite Automata (6 hrs)
6.1 Deterministic Finite Automata (DFA)
6.2 Non-Deterministic Finite Automata (NFA)
6.3 Regular Expressions
6.4 Kleene's Theorem