7. Optimal Binary Search Tree. 

#include<iostream>
using namespace std;

class obst
{
	int p[10],q[10];											// p -> probability of success	:	q -> probability of failure
	int arr[10];												// array of elements
	int weight[10][10],root[10][10],cost[10][10];				// resultant for obst i.e.,weight , root , cost
	int n;														// n -> no. of elements							
								   
public:

	void get()
	{
		cout<<"ENTER NUMBER OF ELEMENTS = ";
		cin>>n;
		cout<<": INPUT DATA ( ELEMENT , PROBABILITIES ) :"<<endl;
		for( int i = 1 ; i <= n ; i++ ) 
		{
			cout<<"ELEMENT "<<i<<" = ";							//element
			cin>>arr[i];
			cout<<"p ["<<i<<"] = ";								//success probability
			cin>>p[i];
			cout<<"q ["<<i-1<<"] = ";							//failure probability
			cin>>q[i-1];		
		}
		cout<<"q ["<<n<<"] = ";									// last failure probability
		cin>>q[n];
	}
	
	void constobst()
	{
		get();
		int k = 0,j = 0;												//a variable which stores the index of minimum cost
		
		//Initialize the values of weight, cost and root
		for( int i = 0 ; i <= n ; i++)
		{
			weight[i][i] = q[i];								// as according to formula ,i.e., ( w[i][j] = q[i] + p[k] + q[k] )
																// where, i < k < j ; so as no value of k when i = j therefore (w[i][i] = q[i] + 0)
			cost[i][i] = root[i][i] = 0;						// initial cost and root is 0
		}
		
		// m is the difference of j and i
		for( int m = 1 ; m <= n ; m++)
		{
			for(int i = 0 ; i < n ; i++)
			{	
				j = i + m;
				weight[i][j] = weight[i][j-1] + p[j] + q[j];				// weight of all elements
				k = kmin(i,j);									// call to kmin function which returns the index value of k by which we get minimum cost
				cost[i][j] = cost[i][k-1] + cost[k][j] + weight[i][j];	
				root[i][j] = k;
			}
		}
		cout<<"ROOT NODE       : "<<arr[root[0][n]];
		cout<<endl<<"LEFT NODE of "<<arr[root[0][n]]<<"  : ";
		obtree( 0 , root[0][n] -1 );
		cout<<endl<<"RIGHT NODE of "<<arr[root[0][n]]<<" : ";
		obtree(root[0][n] , n );
	}
	
	int kmin(int i , int j)
	{
		int min = 999 , z = 0;
		
		// if j - i = 1 then only possible value of k is j : as i < k <= j
		if( j - i == 1)
		{
			return j;
		}
		else
		{
			//  i < k <= j ; and we need to minimise the value of (cost[i][k-1] + cost[k][j])
			for(int k = i+1 ; k <= j ; k++)
			{
				if(min > (cost[i][k-1] + cost[k][j]))
				{
					z = k;
					min = (cost[i][k-1] + cost[k][j]);
				}
			}
		}
		return z;
	}	
	
	void obtree(int i , int j)
	{
		if(root[i][j] == 0)
		{
			cout<<"NULL"<<endl;
			return;
		}
		cout<<arr[root[i][j]]<<endl;
		cout<<endl<<"LEFT NODE OF "<<arr[root[i][j]]<<"  : ";
		obtree( i , root[i][j] -1 );
		cout<<endl<<"RIGHT NODE OF "<<arr[root[i][j]]<<" : ";
		obtree(root[i][j] , j );
	}
					
};

int main()
{
	obst o;
	o.constobst();
	return 0;
}

Comments

Post a Comment

Popular posts from this blog

12. Write a Java program which will demonstrate a concept of cohesion and coupling of the various modules in the program.

 -------------------------Coupling--------------------------- import java.lang.*; import java.util.*; class Box { public int vol; Box( int l , int b , int h) { this.vol = l*b*h; } } class Volume { public static void main(String args[]) { Box b = new Box(5,5,5); System.out.println("VOLUME : " + b.vol); } }     -------------------------Cohesion--------------------------- import java.util.*; import java.lang.*; class Name { String name; public String getName(String name) { this.name = name; return name; } } class Age { int age; public int getAge(int age) { this.age = age; return age; } } class Number { int num; public int getNum(int num) { this.num = num; return num; } } public class Student { public static void main(String args[]) { Name n = new Name(); System.out.println("NAME : " + n.getName("Shreyas")); Age a = new Age(); System.out.println("Age : " + a.getAge(20)...
Read more

2. Beginning with an empty binary search tree, Construct binary search tree by inserting the values in the order given. After constructing a binary tree -i.Insert new nodeii.Find number of nodes in longest path iii.Minimum data value found inthe tree iv.Change a tree so that the roles of the left and right pointers are swapped at every node v.Search a value

#include<iostream> #include<math.h> using namespace std; struct Bstnode { int data; Bstnode *left = NULL; Bstnode *right = NULL; }; class Btree { int n; int x; int flag; public: Bstnode * root; Btree() { root = NULL; } Bstnode *GetNewNode(int in_data) { Bstnode * ptr = new Bstnode(); ptr->data = in_data; ptr->left = NULL; ptr->right = NULL; return ptr; } Bstnode *insert( Bstnode *temp , int in_data) { if( temp == NULL ) { temp = GetNewNode(in_data); } else if( temp->data > in_data) { temp->left = insert(temp->left , in_data); } else { temp->right = insert( temp->right , in_data); } return temp; } void input() { cout<<"ENTER NUMBER OF ELEMENTS IN THE BST : "; cin>>n; for(int i = 0 ; i < n ; i++) { cout<<"NUMBER = "; cin>>x; root = insert(root , x); } } int search(Bstnode *temp ,int in_data) { if( te...
Read more

11. Any application defining scope of Formal parameter, Global parameter, Local parameter accessing mechanism and also relevance to private, public and protected access. Write a Java program which demonstrates the scope rules of the programming mechanism.

import java.util.*; class employee { public String e_name; protected int e_id; String e_add; double salary; employee() { e_name = "abc"; e_id = 0; e_add = "xyz"; salary = 0; } } class Company extends employee { private long ph_no; void get() { Scanner in = new Scanner(System.in); System.out.println("ID : "); e_id = in.nextInt(); System.out.println("NAME : "); e_name = in.next(); System.out.println("ADDRESS : "); e_add = in.next(); System.out.println("SALARY : "); salary = in.nextDouble(); System.out.println("PHONE NO. : "); ph_no = in.nextLong(); } void put() { System.out.println("ID : " + this.e_id); System.out.println("NAME : " + this.e_name); System.out.println("ADDRESS : " + e_add); System.out.println("SALARY : " + salary); System.out.println("PHONE NO. : " + ph_no); } public static void m...
Read more