Algorithm, Complexity of algorithm – p.9
Linear Search (algorithm 2.4)(algorithm 4.5) – p.28 p.77
Binary Search (algorithm 4.6) – p.78

Bubble Sort (algorithm 4.4) – p.73
Quick Sort (procedure 6.5) – p.173
Heap; Heapsort (example 7.21) – p.243
Insertion sort – p.322
Selection Sort (Algorithm 9.3) – p.324

Linear time sorting, Time complexity, Counting sort, Radix sort, bucket sort
Counting sort

Minimum Spanning tree algorithm

Searching, Breath first search, Depth first search

## Adv. Graph Theory – Final Exam Suggestion

1. (a) Define with example:
Pseudo graph, complete graph ….
(b) Draw graph (Set of vertex & edges are given)
(c) Deleted sub-graph related math.
2. (a) Find adjacency for the following graph
(b) Draw graph whose adjacency matrix is given
(c) Definition
3. (a) Graph isomorphism. (Definition; Math)
4. (a) Explain with example
Planar graph, Degree of a region, Bipartite graph, Directed graph, etc.
(b) Determine whether the given walk in the following graph is (i) Path, (ii) a trail, (iii) a closed walk, (v) a circuit, (vi) a cycle.
5. State & prove Euler’s theorem. Verify theorem.
Math V-E+R=2
6. (a) If T is a tree with n vertices than it has precisely n-1 edges. (Theorem 3)
(b) Theorem 1
(c) Theorem 9
7. (a) Theorem 11
(b) Theorem 6

BDD is the graph representation & minimization of logic function.
Boolean expression consists of millions of products.
Any number of functions can be handled by BDDs.
Logic Simulators has been constructed by BDDs.
MIT invented Flash Memory by help of BDDs.

Function:
On the basis of output function:
1) Single output function
2) Multiple output function
On the basis of input values:
1) Two valued function
2) Multiple valued function

Multiple Output Function:
1) is faster
2) cost minimization
cost can be reduced by sharing internal gate.

Logic Function:
Special type of representation.
BDD is the compact form
BDD is derived from Binary Decision Tree

Two rules for constructing a compact BDD is known as BDD reduction rules.
1) Node Elemination
2) Node Sharing

Reduction rules as well as ordering is important to construct BDD
1) Reduction rule
2) Ordering of input variable in the BDD.

Types of BDD for multi-output function:
1) Shared BDD (SBDD)
2) Multi-terminal BDD (MTBDD)
3) Shared MTBDD (SMTBDD)

SBDD + MTBDD = SMTBDD

Comparison:
SBDD: slower(Speed), Smaller(Size)
MTBDD: Faster(speed), Larger(size)

MTBDD is a tidy structure.

Maximum number of nodes to construct an SBDD with m functions of n input variable?
1 BDD requires        2n-1
M BDD requires      m.(2n-1)
Total no. of nodes:  m.(2n-1)+2

SBDD:
What is the total time required for m function n input?
To get result from 1 BDD for 1 function = n times
To get result from m BDD for m function = m.n times

Theorem 1: Let m be the no. of functions and n be the no. of input variable than the maximum no. of nodes is an SBDD is m.(2n-1)+2

Theorem 2: Let m be the number of functions and n be the number of input variables in an SBDD, then the maximum time requires the output result O(m.n)

MTBDD:
Theorem 1: Let m be the no. of functions and n be the no. of input variables. Let r be the no. of distinct output patterns in an MTBDD. Then the maximum no of nodes in an MTBDD is 2n – 1 + r

Theorem 2: O(n) no. of time required to get the output.

SMTBDD:
Time: O(m/2.n) = O(mn/2)
No. of nodes: m/2(2n – 1) + r

BDD fo charactiristic functions(CFs)
Heuristic Algorithm
Step 1: Dependency Matrix
Step 2: Pair Dependency Matrix
Step 3: Calculation of weight of the pair
Step 4: Weighted completed graph

## Midterm Exam Syllabus

Definition of BDDs
Application of BDDs
Representation of BDDs
Minimization of BDDs
Reduction rules for constructing a compact BDD
Algorithm for finding the ordering of input variable
Types of BDDs
What is multiple output function
SBDD, MTBDD, SMTBDD
BDD for charactiristic function
Uper bounds & Evaluation time of all BDDs
Comparison among BDDs
Proof of upper bounds & evaluation time of all BDDs.

IPv4
IPv6