*Detailed Course*

** ****The Foundations: Logic and Proof,**
- Logic
- Propositions, Proposition variables, Truth table, conjunction, disjunction, Exclusive, implications, converse, inverse, Contra positive, Bi-conditional, Tautology, Contradiction, translating English sentences, logic and bit operations

- Propositional Equivalences
- Introduction, Logical equivalences: Identity law, Domination law, Idempotent laws, Double negation law, commutative law, associative law, Distributive law, De- Morgan’s law, Absorption law, Negation law (Verification)

- Brief introduction and examples of Predicates and Quantifiers
- Methods of Proof

Methods of proving theorems (direct proofs, indirect proofs, vacuous and trivial proofs, proof by contradiction).

##### 2 The Fundamentals: Algorithms, the Integers, and Matrices

Introduction, searching algorithms (linear, binary), sorting (bubble, insertion), greedy algorithms, halting problem

Introduction, big-O notation, the growth of combinations of functions, big-omega and big- theta notation

Introduction, time complexity, worst case complexity, average case complexity, understanding the complexity of algorithms

- The Integers and Division

Introduction, division, primes, the fundamental theorem of arithmetic, the infinitude of primes, the division algorithm, GCD and LCM, modular arithmetic, applications of congruence’s, Cryptology.

##### 3. Mathematical Reasoning, Induction, and Recursion

Introduction, sequences, recurrence relations, special integer sequences, summations

Introduction, mathematical induction, Recursive Definitions. Introduction, recursively defined function,

- Recursive Algorithms, recursion and iteration, the merge sort

##### 4. Counting

- Basic counting principle – The sum rule and the product
- Permutation of n different objects, The number of r – permutations of n distinct objects when (a) repetition of objects are not allowed (b) repetition of objects are

Permutations of n objects when the things are not distinct, circular permutations. Restricted permutations – The number of r-permutations of n different objects in which (i) k particular objects do not occur and (ii) k particular objects are always present.

- Combination: - r-combinations of n different objects Restricted combinations, combinations with repetitions: the number of combinations of n objects taken r at a time with repetition is c(n+r-1, r)
- Binomial Theorem, Binomial coefficients and Pascal triangle Pascal's
- The pigeonhole principle and Inclusion and Exclusion principle. 6Recurrence relation and solving it.

##### 5. Relations and Functions

- Product sets, Binary relations, Domain and Range of binary
- Types of relations – Inverse relation, Identity relation, universe relations, void relation, complementary relation, ternary relation and n-ary
- Representation of relations – Table of relation, Arrow diagrams of relation, Graph of relation, Matrix of relation, Directed graph of a relation on a set
- Boolean matrix, Boolean matrix operation, Boolean product of two matrices, complement of Boolean
- Properties of relations – reflexive, irreflexive, symmetric, asymmetric, anti-symmetric and transitive Equivalence relation, Equivalence relation and partition, Equivalence classes and quotient set. Partial order relation, Partial ordered set
- Composition of two relations, matrix of composition relations properties –

* *If R is a relation from A to B and S a relation from B to C, then M_{SOR} = M_{R} ¤ M*(without proof)*
* *If R is a relation from A to B, S a relation from B to C, and T a relation from C to D, then To (S R) = (T S) *(without proof)*
* *Let A, B and C be sets, R a relation from A to B, and S a relation from B to C. Then (S R) ^{-} ^{1}= R^{-1} S^{-1} *(without proof)*
- Concept of function, Domain and Range, image and pre-image, Graph of a function f : A B, Equality of functions, Real valued function, constant function and Identity function. Special functions – Floor function, ceiling function
- Types of functions – onto function, one-to-one function, one-to-one correspondence between A and B, Inverse
- The composition of two functions, Properties – (a) I
_{B}of = f, (b) foI_{A} = f, (c) f ^{-1} of = I_{A},

(d) fof^{-1} = I_{B}, *(with proof) *, (f) (gof)^{-1} = f^{-1}og^{-1}.

##### 6. Graphs

- Introduction to Graphs and graph terminologies:

Simple graph, multiple graph and pseudo graph, order of a graph and size of a graph adjacent vertices, adjacent edges, degree of a vertex, isolated vertex and Pendant vertex. Degree sequence of a graph.

###### Properties (with proofs):

- The sum of the degree of the vertices of a graph is equal to twice the number of
- The number of odd vertices in a graph is always

Special types of simple graph – Isolated graph, complete graph, Regular graph, Path graph, Cycle graph, Wheel graph, Bipartite graph and complete bipartite graph, Graphs of regular Platonic Solids.

Properties (with proofs):-

- The total number of edges in a complete graph Kn is

n (n -1) 2

- The number of vertices in a r-regular graph is even if r is
- The complete graph K
_{n} is the regular graph of degree n –
- In the cyclic graph C
_{n}, size of C_{n} is equal to order of C
- The size of wheel W
_{n} is twice the size of C_{n}.
- The sum of the degrees of vertices in W
_{n} is four times the size of C_{n}.
- Size of the complete bipartite graph Km, n is m ´ n and order is m +
- Representing Graphs: Adjacency list, Adjacency matrix, and Incidence
- Isomorphism of Graph: Isomorphic graphs, Isomorphism classes, Self
- Connectivity: walk, trial and circuit, Path and Cycle, Connected graph, Cut-sets and Cut- Edge connectivity and vertex connectivity.
- Euler and Hamilton Paths:

Eulerian trial, Eulerian Circuit, Eulerian graph, Konigsberg Bridge problem. Theorems *without proofs)*:- a. A co

- A connected graph G has Eulerian trial if and only if it has exactly two odd vertices.

path, Hamiltonian cycle and Hamiltonian graph. Theorems *(without proofs)*

- (Ore's) A connected graph with n vertices is Hamiltonian if for any two non- adjacent vertices u and v, deg (u) + deg (v)≥n.
- (Dirac) A connected graph with n(>2) vertices is Hamiltonian if degree of every vertex is at least
^{n}/_{2}.

Labeled graphs and weighted graphs,

- Shortest-Path Problems: – Dijkstra's algorithm
- Digraph, Simple digraph, Reflexive, Symmetric and Transitive digraph, Loop and parallel arc (edge), adjacent vertices and degree of vertices, Source vertex and Sink

Theorem (without proof) – In a digraph, the sum of the in-degrees of vertices, the sum of the out-degrees of vertices and the number of edges are equal to each other.

- Representation of digraph - Adjacency list, Adjacency matrix and Incidence
- Connectivity of digraphs – underlying graph, directed walk, closed walk, directed path, directed cycle, spanning path. Weakly connected, unilaterally connected and strongly connected theorems (without proofs):
- A diagraph D is unilaterally connected if it has a spanning path in
- A diagraph D is strongly connected if it has a closed spanning path in

##### 7. Trees

- Introduction, rooted tree, non-rooted tree, root vertex, Terminal vertex, Internal vertex, Level of a vertex, H

- 2 Properties of tree (with proofs).

- Let G(V, E) be a loop-free undirected Then G is a tree if there is a unique path between any two vertices of G.
- A tree with n vertices has exactly n – 1
- In any tree G, there are at least two pendant
- A forest G with n vertices has n – k edges, where k is the number of components of
- Spanning tree and Methods of constructing a spanning tree from a graph by
- Breadth – first search and b) Depth – first search (Backtracking), Determination of the number of spanni

- Minimum spanning tree – a) Kruskal algorthm b) Prim's
- Tree Traversal: In order, Pre-order, and post order traversal
- Applications of Trees: Binary expression tree
- Full binary tree and its properties:
- The number of vertices n in a binary tree is always
- The number of pendant vertices of a binary tree with n vertices is ½ (n + 1).
- The number of internal vertices in a binary tree is one less than the number of pendant

- The maximum number of vertices possible in K-level binary tree is 2
^{0} + 2^{1} + 2^{2} + .. + 2^{K} ≥
- The minimum possible height of an n-vertex binary tree is min l
_{max} =

élog (*n *+1) -1ù , where L_{max} = max^{m} level of any vertex.

- The maximum possible height of an n – vertex binary tree is max l
_{max} =

(n -1)

2

##### Lecture: 48 Hours

**Tutorial: 12 Hours**