Contents

1. Finite Induction

1.1 Mathematical induction

1.2 First principle of mathematical induction

1.3 Generalised form of first principle of mathematical induction

1.4 Second principle of mathematical induction

2. Elementary Counting Principles

2.1 Introduction

2.2 Counting principles

2.3 Functions and counting

2.4 Combinatorial arguments

2.5 Solved examples

3. Recurrence Relations

3.1 Introduction

3.2 Construction of recurrence relations

3.3 Linear recurrence relations with constant coefficients

3.4 Solving recurrence relations

3.5 Homogeneous solution

3.6 Particular solution

3.7 Total solution

4. Logic

4.1 Introduction

4.2 Propositional logic revision

4.3 Predicates logic

4.4 Validity of arguments

4.5 Methods of proof

5. Algorithms

5.1 Introduction

5.2 Pseudo-code

5.3 Iterative and recursive algorithm

5.4 Characteristics of an algorithm

5.5 Performance analysis–time complexity

5.6 Searching methods

5.7 Sorting methods

5.8 Asymptotic notation

6. Graphs

6.1 Introduction

6.2 Preliminary terms and definitions

6.3 Some important types of graphs

6.4 Isomorphism of graphs

6.5 Matrix representation of graphs

7. Operations on Graph

7.1 Introduction

7.2 Induced graphs

7.3 Complement of a graph

7.4 Union, intersection, ring sum and product of graphs

8. Connected Graphs

8.1 Introduction

8.2 Connected and disconnected graph

8.3 Walk, trail, path and circuit

8.4 Isthmus and cut vertex

8.5 Connectivity

8.6 Dijkstra’s shortest path algorithm (Breadth-first Search Approach)

9. Trees

9.1 Introduction

9.2 Centers of tree

9.3 Spanning trees, fundamental circuits and cutsets

9.4 Binary trees

9.5 Krushkal’s algorithm

10. Directed Graphs

10.1 Introduction

10.2 Types of digraphs

10.3 Isomorphism of digraphs

10.4 Connectedness

10.5 Euler digraphs

10.6 Directed trees

10.7 Network and flows

10.8 Ford-fulkerson algorith