#hashing
Max = 10
def linear_probing(no,hash_table1):
    pos = has(no)
    for i in range(no + 1):
        if 0 in hash_table1[pos]:
            return pos
        pos = (pos + 1) % Max

    return -1

def has(no):
    return no % Max

def quad_probing(no,hash_table1):
    pos = has(no)
    for i in range(20):
        if 0 in hash_table1[pos]:
            return pos

        pos = (pos + (i * i)) % Max
    return -1

def lin_search(hash_table1):
    count1 = 0
    no = int(input("Enter the no you want to search?"))
    ind = has(no)
    for i in range(Max + 1):
        if no in hash_table1[ind]:
            print(hash_table1[ind], end="")
            print(f" at location {ind}")
            return count1
        ind = (ind + 1) % Max
        count1 = count1 + 1
    print("Element not found")

def quad_search(hash_table1):
    count2 = 0
    no = int(input("Enter the no you want to search?"))
    ind = has(no)
    for i in range(20):
        if no in hash_table1[ind]:
            print(hash_table1[ind], end="")
            print(f" at location {ind}")
            return count2
        ind = (ind + (i * i)) % Max
        count2 = count2 + 1
    print("Element not found")
    return -1

def main():
    while True:
        print(" Menu ")
        print("1.Add element using linear probing\n2.Add element using quadratic probing\n3.Search element added by linear probing\n4.Search element added by quadaratic probing\n5.Compare the rate\n6.Exit\n")
        ch = int(input("Enter your choice:"))
        if ch == 1:
            n = int(input("Enter number of clients:"))
            hash_table1 = [[0] for i in range(Max)]

            for i in range(n):
                a = input("Enter name: ")
                b = int(input("Enter mob number: "))
                index = linear_probing(b,hash_table1)
                if index == -1:
                    print("Memory is full")
                    break
                hash_table1[index] = [a, b]
            print(hash_table1)
        elif ch == 2:
            n = int(input("Enter number of clients:"))

            for i in range(n):
                a = input("Enter name: ")
                b = int(input("Enter mob number: "))
                index = quad_probing(b,hash_table1)
                if index == -1:
                    print("Memory is full")
                    break
                hash_table1[index] = [a, b]
            print(hash_table1)
        elif ch == 3:
            cnt1 = lin_search(hash_table1)
        elif ch == 4:
            cnt2 = quad_search(hash_table1)
        elif ch == 5:
            print("Linear search required",cnt1)
            print("Quadaratic search required",cnt2)
        elif ch == 6:
            print("Exiting")
            break

main()





set1=[]
set2=[]
def accept():
    n=(int(input("Enter number of elements to be accepted: ")))
    for i in range(n):
        m=(int(input("Enter the elements: ")))
        set1.append(m)
    print("The set is: ",set1)

def removeno(set1):
    n=int(input("Enter the number to be removed from set: "))
    if(n in set1):
        set1.remove(n)
        print("Displayed elements are: ",set1)
        return
    else:
        print("Element not present")

def contains(set1):
    m=int(input("Enter the element to check the set contains it or not: "))
    if m in set1 :
        print("Set contains the entered element ")
    else:
        print("Element not present in the list")

def size(set1):
    count=0
    for i in set1 :
        count+=1
    print("The size of set is: ",count)

def iterate(set1):
    iterator=iter(set1)
    print("The elements in the set are: ")
    for i in range(len(set1)):
        print(next(iterator))

def intersection(set1,set2): 
    itsec=[]
    for i in set1:
        for j in set2:
            if(i==j):
                itsec.append(i)
    print("The intersection of set is: ",itsec)

def union(set1,set2):
    uni=[]
    uni.extend(set1)
    for i in set2:
        if i not in set1:
            uni.append(i)
    print("Union of two sets is: ",uni)

def difference(set1,set2):
    diff=[]
    for i in set1:
        if i not in set2:
            diff.append(i)
    print("Set1 - Set2 = ",diff)

def subset(set1,set2):
    subset=True
    for i in set2:
        if i not in set1:
            subset=False
    if subset==False:
        print("set2 is not subset of set1")
    else:
        print("set2 is subset of set1")

def main():
    n=int(input("Enter the number of elements in SET1: "))
    for i in range(n):
        set1.append(int(input("Enter the Set1 elements:")))
    print("The set is: ",set1)
    ch=0
    for i in range(7):
        print(" Set Operations")
        print(" 1. Accept element in a set")
        print(" 2. Remove element from a set")
        print(" 3. Search element ")
        print(" 4. Find size of set")
        print(" 5. Iterator function")
        print(" 6. Set operations")
        print(" 7. EXIT")
        ch = int(input("\n Enter your choice: "))
        while True:
            if ch==1:
                accept()
                break
            elif ch==2:
                removeno(set1)
                break
            elif ch==3:
                contains(set1)
                break
            elif ch==4:
                size(set1)
                break
            elif ch==5:
                iterate(set1)
                break
            elif ch== 6:
                a=int(input("Enter the number of elements in SET2: "))
                for i in range(a):
                    set2.append(int(input("Enter the Set2 elements:")))
                for i in range(5):
                    print("**Set Operations:* ")
                    print("1) Intersection of Sets")
                    print("2) Union of Sets")
                    print("3) Difference of Sets")
                    print("4) Subset of a Set")
                    print("5) Exit")
                    choice=int(input("Enter your choice: "))
                    while True:
                        if choice==1:
                            intersection(set1,set2)
                            break
                        elif choice ==2:
                            union(set1,set2)
                            break
                        elif choice ==3:
                            difference(set1,set2)
                            break
                        elif choice==4:
                            subset(set1,set2)
                            break
                        else:
                            print("Exit")
                            exit()
            else:
                print("-----EXIT-----")
                exit()
main()




//GROUP-B(5): BINARY TREE
// book name,chapter,section,subsection
#include<iostream>
using namespace std;

struct node
{
    char label[10];
    int ch_count;
    struct node *child[10];
} *root;

class Tree
{
    public:
        void create_tree();
        void display(node*r1);
         Tree()
         {
            root=NULL;
         }
};

void Tree::create_tree()
{
    int tch,i,j,k,l,m;
    root=new node;
    cout<<"Enter the name of book:"<<endl;
    cin>>root->label;
    cout<<"Enter the number of chapters in the book:"<<endl;
    cin>>tch;
    root->ch_count=tch;
    for(i=0;i<tch;i++)
    {
        root->child[i]=new node;
        cout<<"Enter Chapter "<<i+1<<" name: "<<endl;
        cin>>root->child[i]->label;
        cout<<"Enter the number of sections: "<<endl;
        cin>>root->child[i]->ch_count;
        l=root->child[i]->ch_count;
        for(j=0;j<l;j++)
        {
            root->child[i]->child[j]=new node;
            cout<<"Enter section "<<j+1<<" name: "<<endl;
            cin>>root->child[i]->child[j]->label;
            cout<<"Enter the number of sub-sections: "<<endl;
            cin>>root->child[i]->child[j]->ch_count; 
            m=root->child[i]->child[j]->ch_count;
            for(k=0;k< m;k++)
            {
                root->child[i]->child[j]->child[k]=new node;
                cout<<"Enter sub-section "<<j+1<<"."<<k+1<<" Title: "<<endl;
                cin>>root->child[i]->child[j]->child[k]->label;
            }
        }
    }
}

void Tree ::display(node *r1)
{
    int tch,i,j,k;
    if (r1!=NULL)
    {
        cout<<"Book Tree Hierarchy :"<<endl;
        tch=r1->ch_count;
        for(i=0;i<tch;i++)
        {
            cout<<"Chapter: "<<i+1<<endl;
            cout<<" "<<r1->child[i]->label<<endl;
            for(j=0;j<r1->child[i]->ch_count;j++)
            {
                cout<<"Section: "<<j+1<<endl;
                cout<<r1->child[i]->child[j]->label<<endl;
                for(k=0;k<r1->child[i]->child[j]->ch_count;k++)
                {
                    cout<<"Sub-Section:"<<endl;
                    cout<<r1->child[i]->child[j]->child[k]->label<<endl;
                }
            }
        }
    }
}

int main()
{
    int ch;
    Tree bt;
    while(1)
    {
        cout<<"**Book Tree**"<<endl;
        cout<<"1. Create"<<endl;
        cout<<"2. Display"<<endl;
        cout<<"3. Quit"<<endl;
        cout<<"***"<<endl; 
        cout<<"Enter Your Choice: ";
        cin>>ch;
        switch(ch)
        {
            case 1:
                bt.create_tree();
                cout<<"Tree Created.";
                break;
            case 2:
                bt.display(root);
                break;
            case 3:
                cout<<"Thank You.";
                exit(0);
                break;
            default:
                cout<<"Invalid Choice!!!"<<endl;
        }
    }
    return 0;
};




//GROUP-B(7): EXPRESSION TREE
#include <iostream> 
#include <string.h> 
using namespace std; 
  
struct node 
{ 
    char data; 
    node *left; 
    node *right; 
}; 

class tree 
{ 
    char prefix[20]; 
  
    public: 
    node *top; 
    void expression(char[]); 
    void display(node *); 
    void non_rec_postorder(node *); 
    void del(node *); 
}; 

class stack1 
{ 
    node *data[30]; 
    int top; 
  
    public: 
    stack1() 
    { 
        top = -1; 
    } 
    int empty() 
    { 
        if (top == -1) 
            return 1; 
        return 0; 
    } 
    void push(node *p) 
    { 
        data[++top] = p; 
    } 
    node *pop() 
    { 
        return (data[top--]); 
    } 
}; 

void tree::expression(char prefix[]) 
{  
    stack1 s; 
    node *t1, *t2; 
    int len, i; 
    len = strlen(prefix); 
    for(i =len-1; i>=0; i--) 
    { 
        top=new node; 
        top->left = NULL; 
        top->right = NULL; 
        if (isalpha(prefix[i])) 
        { 
            top->data = prefix[i]; 
            s.push(top); 
        } 
        else if (prefix[i] == '+' || prefix[i] == '*' || prefix[i] == '-' || prefix[i] == '/') 
        { 
            t2 = s.pop(); 
            t1 = s.pop(); 
            top->data = prefix[i]; 
            top->left = t2; 
            top->right = t1; 
            s.push(top); 
        } 
    } 
    top=s.pop(); 
} 

void tree::display(node *root) 
{  
    if (root != NULL) 
    { 
        cout << root->data; 
        display(root->left); 
        display(root->right); 
    } 
} 

void tree::non_rec_postorder(node *top) 
{ 
    stack1 s1, s2; /*stack s1 is being used for flag . A NULL data implies that the right subtree has not been visited */ 
    node *T = top; 
    cout << "\n"; 
    s1.push(T); 
    while (!s1.empty()) 
    { 
        T = s1.pop(); 
        s2.push(T); 
        if (T->left != NULL) 
            s1.push(T->left); 
        if (T->right != NULL) 
            s1.push(T->right); 
    } 
    cout<<"Post-Order expression is: ";
    while (!s2.empty()) 
    { 
        top = s2.pop(); 
        cout << top->data; 
    } 
} 

void tree::del(node *node) 
{ 
    if (node == NULL) 
        return; 
    del(node->left); 
    del(node->right); 
    cout <<endl<<"Deleting node : " << node->data; 
} 
 
int main() 
{ 
    char expr[20]; 
    tree t; 
  
    cout <<"Enter prefix Expression : "; 
    cin >> expr; 
    
    t.expression(expr); 
    t.display(t.top); 
    cout<<endl; 
    t.non_rec_postorder(t.top); 
    t.del(t.top); 
}



//GROUP-B(11): BINARY SERACH TREE
#include<iostream>
#include<string.h>
using namespace std;

struct node
{
  string mean,k;
  node *left,*right; 
}*root=NULL, *temp;

class bst
{
  int n;
  
  public:
    node* create();
    void insert(node*,node*);
    void display(node*);
    node* search(string,node*);
    void update(string ,string ,node*);
    node* deletenode(string ,node*);
    node* min(node*);
};

node* bst::create()
    {
      cout<<"Enter number of keywords : ";
      cin>>n;
      for(int i=0;i<n;i++)
      {
        if(root==NULL)
        {
          root=new node;
          cout<<"Enter the keyword : ";
          cin>>root->k;
          cout<<"Enter the meaning of the keyword : ";
          cin>>root->mean;
          root->left=NULL;
          root->right=NULL;
        }
        else
        {
          temp=new node;
          cout<<"Enter the keyword : ";
          cin>>temp->k;
          cout<<"Enter the meaning of the keyword : ";
          cin>>temp->mean;
          temp->left=NULL;
          temp->right=NULL;
          insert(root,temp);
        }
      }
      return root;
    }

void bst::insert(node*root,node*temp)
    {
      int b=strcmp(root->k.c_str(),temp->k.c_str());
      if(b==0)
      {
        cout<<"Keyword already exists.";
      }
      else if(b>0)
        {
          if(root->left==NULL)
          {
            root->left=temp;
          }
          else
          {
            root=root->left;
            insert(root,temp);
          }
        }
      else
      {
        if(root->right==NULL)
        {
          root->right=temp;
        }
        else
        {
          root=root->right;
          insert(root,temp);
        }
      }
    }

void bst::display(node*root)
    {
      if (root != NULL) 
      { 
        display(root->left); 
        cout << root->k<<" - "<<root->mean<<endl; 
        display(root->right); 
      } 
    }

node* bst::search(string k,node*root)
    {
      if(root==NULL)
      {
        return NULL;
      } 
      else if(k.compare(root->k)==0)
      {
        return root;
      }
      else if(k.compare(root->k)<0)
      {
        return search(k,root->left);
      }
      else
      {
        return search(k,root->right);        
      }
    }

node* bst::deletenode(string k,node*root)
    {
      if(root==NULL)
      {
        return root;
      }
      else if(k.compare(root->k)<0)
      {
        root->left=deletenode(k,root->left);
      }
      else if(k.compare(root->k)>0)
      {
        root->right=deletenode(k,root->right);
      }
      else
      {
        if(root->right==NULL && root->left==NULL)
        {
          delete root;
          root=NULL;
        }
        else if(root->right==NULL)
        {
          temp = root->left;
          delete root;
          return temp;
        }
        else if(root->left==NULL)
        {
          temp = root->right;
          delete root;
          return temp;
        }
        else
        {
          temp=min(root->right);
          root->k=temp->k;
          root->mean=temp->mean;
          root->right = deletenode(temp->k, root->right);
        }
      }
      return root;
    }

node* bst::min(node*q)
{
  while(q->left != NULL) 
  {
    q=q->left;
  }
  return q;
}

int main()
{
  bst obj1;
  int ch;
  string mean,k;
  while(1)
  {
    do
    {
      cout<<"\n1.Create dictionary\n2.Display created dictionary\n3.Update the dictionary\n4.Delete the keyword\n5.Exit\n\nEnter your choice: ";
      cin>>ch;
      cout<<endl;
      switch (ch)
      {
      case 1:
        root=obj1.create();
        break;
      case 2:
        obj1.display(root);
        break;
      case 3:
        cout<<"Enter the keyword to update its meaning : ";
        cin>>k;
        temp=obj1.search(k,root);
        if(temp==NULL)
        {
          cout<<"Keyword is not present in dictionary."<<endl;
        }
        else
        {
          cout<<"Enter its meaning : ";
          cin>>mean;
          temp->mean=mean;
          cout<<"Updated tree is: "<<endl;
          obj1.display(root);
        }
        break;
      case 4:
        cout<<"Enter the keyword to delete : ";
        cin>>k;
        temp=obj1.deletenode(k,root);
        if(temp==NULL)
        {
          cout<<"Keyword is not present in dictionary."<<endl;
        }
        cout<<"The node is successfully deleted!!"<<endl;
        obj1.display(root);
        break;
      case 5:
        exit(0);
        break;
      default:
        cout<<"Enter correct choice: ";
        break;
      }
    } while (ch!=5);
  }
  return 0;
}



#include<iostream>
using namespace std;
#define MAX 20
int edge[MAX][MAX];
int n,e,vi,vj;

class node{
public:
    int vertex;
    node *next;
};

class Queue{
public:
    int data[MAX];
    int f,r;
    Queue(){
        r=f=-1;
    }

    bool empty(){
        return f==-1;
    }

    void enqueue(int x){
        if (f==-1)
            f++;
        data[++r]=x;
    }

    int dequeue()
    {
        if(!empty())
            return data[f--];
    }
};

void BFS(int);
void readgraph();
void insert(int,int);
node *G[MAX];

int main(){
    cout<<"Input Adjacency list:\n";
    readgraph();
    cout<<"---- ---- ---- ----\n";
    cout<<"    BFS Traversal\n";
    cout<<"---- ---- ---- ----\n";
    for(int i=0;i<n;i++)
        BFS(i);
    return 0;
}

void readgraph(){
    cout<<"Enter number of vertices:";
    cin>>n;
    for(int i=0;i<n;i++)
        G[i]=NULL;
    
    cout<<"Enter number of edges: ";
    cin>>e;
    for(int i=0;i<e;i++){
        cout<<"Enter edge (u,v)";
        cin>>vi>>vj;
        insert(vi,vj);
        insert(vj,vi);
    }   
}

void insert(int vi,int vj){
    node *p,*q;
    p=new node;
    p->vertex=vj;
    p->next=NULL;
    if(G[vi]==NULL)
        G[vi]=p;
    else{
        for(q=G[vi];q->next!=NULL;q=q->next);
        q->next=p;
    }
}

void BFS(int x){
    Queue q;
    node *p;
    int visited[MAX],w;
    for(int i=0;i<n;i++)
        visited[i]=0;
    q.enqueue(x);
    visited[x]=1;
    cout<<"\n G["<<x<<"] ----> ";
    while(!q.empty()){
        x=q.dequeue();
        for(p=G[x];p!=NULL;p=p->next){
            w=p->vertex;
            if(visited[w]==0){
                visited[w]=1;
                q.enqueue(w);
                cout<<" "<<w; 
            }
        }
        break;
    }
}



//GROUP-C(13): DFS  
#include<iostream>
using namespace std;

class stack
{
   int top;
   int A[10];

   public:
   stack()
   {
    top=-1;
   }
    
   int empty()
   {
    if (top ==-1)
      return 1;
    else 
      return 0;
   } 
    
    int full()
    {
      if (top>=A[10])
        return 1;
      else
        return 0;
    }
    void push(int e1)
    {
      
      A[++top]= e1;
    }
     
    int pop()
    {
      int s=A[top];
      top--;
      return s;
    }
};


int main()
{  
  int visited[10],e1,n,G[10][10],e,e2;
  stack st;
  
  cout<<"Enter number of nodes"<<endl;
  cin>>n;

  for(int i=0;i<n;i++)
  {
    visited[i]=0;
  }
     
  cout<<"Enter the number of edges : "<<endl;
  cin>>e;
   
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      G[i][j]=0;
    }
  }
     
  for(int i=0;i<e;i++)
  {
    cout<<"Enter edge (e1,e2) "<<endl;
    cin>>e1>>e2;
    G[e1][e2]=1;
    G[e2][e1]=1;
  }
            
  for(int a=0;a<n;a++)
  {
    for(int b=0;b<n;b++)
    {
       cout<<G[a][b]<<" ";
    }
  cout<<endl;
  }

  cout<<"Please enter starting vertex : ";
  cin>>e1;
  st.push(e1);

  cout<<"DFS: ";  
  while(!st.empty())
  {
    int v;
    v=st.pop();
    if(visited[v]==0)
    {
      visited[v]=1;
      cout<<v<<" ";
    }
      
    for(int j=n-1;j>=0;j--)
    {
      if (G[v][j]==1 && visited[j]==0)
      {
        st.push(j);
      }
    }
  }  

return 0;
}

/*Enter number of nodes
5
Enter the number of edges : 
5
Enter edge (e1,e2) 
0 1
Enter edge (e1,e2) 
0 2
Enter edge (e1,e2) 
1 3
Enter edge (e1,e2) 
3 4
Enter edge (e1,e2) 
2 4
0 1 1 0 0 
1 0 0 1 0
1 0 0 0 1
0 1 0 0 1
0 0 1 1 0
Please enter starting vertex : 0
DFS: 0 1 3 4 2 */



//DFS_BFS
#include<iostream>
using namespace std;

class stack
{
  int top,A[10];

  public:
    stack()
    {
      top=-1;
    }
    int empty()
    {
      if (top ==-1)
        return 1;
      else 
        return 0;
    }
    int full()
    {
      if (top>=A[10])
        return 1;
      else
        return 0;
    }
    void push(int e1)
    {
      A[++top]= e1;
    }
    int pop()
    {
      int s=A[top];
      top--;
      return s;
    }
};

class queue
{
  public:
    int f,r,arr[10];
    queue()
    {
      f=r=-1;
    }  
    void enqueue(int data) 
    {
      if(f==-1)
        f++;
      r++;
      arr[r]=data; 
    }
    int dequeue()
    {
      int x;
      x=arr[f];
      f++;
      return x;
    }
    int isEmpty()
    {
      if((f==-1)||f>r)
        return 0;
      else      
        return 1;
    }
};

class node
{
  public:
    int data;
    node *next;
        
    void insert(int u,int v,node *G[])
    {
      node *p=new node;
      p->data=v;
      p->next=NULL;
      if(G[u]==NULL)
      {
          G[u]=p;
      }
      else
      {
          node *q;
          for(q=G[u];q->next!=NULL;q=q->next);
          q->next=p;
      }
    }
};

void DFS(int n,int B[10][10],int e)
{
  int e1,visited[10],v,e2;
  stack st;
  for(int i=0;i<n;i++)
  {
    visited[i]=0;
  }

  for(int a=0;a<n;a++)
  {
    for(int b=0;b<n;b++)
    {
      cout<<B[a][b]<<" ";
    }
  cout<<endl;
  }
  cout<<"Please enter starting vertex : ";
  cin>>e1;
  st.push(e1);

  cout<<"DFS: ";  
  while(!st.empty())
  {
    v=st.pop();
    if(visited[v]==0)
    {
      visited[v]=1;
      cout<<v<<" ";
    }
      
    for(int j=n-1;j>=0;j--)
    {
      if (B[v][j]==1 && visited[j]==0)
      {
        st.push(j);
      }
    }
  }
  cout<<endl;
} 

void BFS(int n,node *G[10],int e)
{
  int e1,visited[10], u,v,v1,s,e2;
  node*p;
  node n1;
  queue q;

  for(int i=0;i<n;i++)
  {
    G[i]=NULL;
  } 
  for(int i=0;i<e;i++)
  {
    cout<<"Enter edge (e1,e2) "<<endl;
    cin>>e1>>e2;
    n1.insert(e1,e2,G);
    n1.insert(e2,e1,G);
  } 
  for(int i=0;i<n;i++)
  {
      visited[i]=0;
  }
    cout<<"\nEnter the starting vertex : ";
    cin>>s;
    cout<<"\n\nBFS TRAVERSAL :\n";
    cout<<"\t"<<s;
    visited[s]=1;
    
  q.enqueue(s);
  while(q.isEmpty() != 0)
  {
    v1=q.dequeue(); 
    for(p=G[v1];p!=NULL;p=p->next)
    {
      if(visited[p->data]==0)
      {
        q.enqueue(p->data); 
        visited[p->data]=1;
        cout<<"\t"<<p->data;
      }
    }
  }
  cout<<endl;
}

int main()
{
  int n,B[10][10],e,ch,e1,e2;
  node *G[10];
  node n1;

  cout<<"Enter number of nodes"<<endl;
  cin>>n;
     
  cout<<"Enter the number of edges : "<<endl;
  cin>>e;

  while(true)
  {
    do
    {
      cout<<"1.DFS traversal\n2.BFS traversal\n3.Exit\nEnter your choice: \n";
      cin>>ch;
      switch (ch)
      {
      case 1:
        for(int i=0;i<n;i++)
        {
          for(int j=0;j<n;j++)
          {
            B[i][j]=0;
          }
        }
        for(int i=0;i<e;i++)
        {
          cout<<"Enter edge (e1,e2) "<<endl;
          cin>>e1>>e2;
          B[e1][e2]=1;
          B[e2][e1]=1;
        }
        DFS(n,B,e);
        break;

      case 2:
        BFS(n,G,e);
        break;

      case 3:
        exit(0);
        break;

      default: 
        cout<<"Enter correct choice";
        break;
      }
    } while (ch==3);
  }
  return 0;
}


//GROUP-C(16): PRIM'S ALGORITHM
#include<iostream>
#define V 10
using namespace std;

int minkey(int key[],bool visited[])
{
  int min=999, min_ind;
  for(int i=0; i<V; i++)
  {
    if(visited[i]==false && key[i]<min)
    {
      min=key[i];
      min_ind=i;
    }
  }
  return min_ind;
}

void printMST(int parent[],int graph[V][V])
{
  cout<<"Edge \t Weight\n";
  int cnt=0;
  for(int i=1;i<V;i++)
  {
    cout<<parent[i]<<" - "<<i<<" \t "<<graph[i][parent[i]]<<"\n";
    cnt=cnt+graph[i][parent[i]];
  }
  cout<<"Minimum cost is : "<<cnt;
}

void primMST(int graph[V][V])
{
  int parent[V],key[V];
  bool visited[V];
  for(int i=0;i<V;i++)
  {
    key[i]=999;
    visited[i]=false;
  }
  key[0]=0;
  parent[0]=-1;

  for(int j=0;j<V-1;j++)
  {
    int u=minkey(key,visited);
    visited[u]=true;
    for(int i=0;i<V;i++)
    {
      if(graph[u][i] && visited[i]==false && graph[u][i]<key[i])
      {
        parent[i]=u;
        key[i]=graph[u][i];
      }
    }
  }
  printMST(parent,graph);
}

int main()
{
  int n,e,graph[V][V],e1,e2,c;
  cout<<"Enter number of nodes"<<endl;
  cin>>n;
   
  for(int i=0;i<n;i++)
  {
    for(int j=0;j<n;j++)
    {
      graph[i][j]=999;
    }
  }
    
  cout<<"Enter the number of edges : "<<endl;
  cin>>e;

  for(int i=0;i<e;i++)
  {
    cout<<"Enter edge (e1,e2) "<<endl;
    cin>>e1>>e2;
    cout<<"Enter the cost of edge(e1,e2)"<<endl;;
    cin>>c;
    graph[e1][e2]=c;
    graph[e2][e1]=c;
  }
  
  for(int a=0;a<n;a++)
  {
    for(int b=0;b<n;b++)
    {
      cout<<graph[a][b]<<"\t";
   }
    cout<<endl;
  }

  primMST(graph);
  return 0;
}



/*Given sequence k = k1 <k2 < … <kn of n sorted keys, with a search probability pi for each key ki . Build the Binary search tree that has the least search cost given the access probability for each key? */

#include<iostream>
using namespace std;
#define MAX 10
int find(int,int);
void print(int,int);
int p[MAX],q[MAX],w[10][10],c[10][10],r[10][10],i,j,k,n,m;
char idnt[7][10];

int main()
{

    cout<<"enter a number of identifiers : ";
    cin>>n;
    cout<<"enter identifiers : ";
    for(i=1;i<=n;i++)
    cin>>idnt[i];
    cout<<"enter success probability for identifiers : ";
    for(i=1;i<=n;i++)
    cin>>p[i];
    cout<<"enter failure probability for identifiers : ";
    for(i=0;i<=n;i++)
    cin>>q[i];
    cout<<"\n Weight Cost Root \n";
    for(i=0;i<=n;i++)
    {

        w[i][i]=q[i];

        c[i][i]=r[i][i]=0;
        cout<<"Weight"<<"\t"<<"Cost"<<"\t"<<"Root";

        cout<<"\n"<<w[i][i]<<" "<<c[i][i]<<" "<<r[i][i];

        //cout<<"------------------------------------------------------------------------";

    }

    for(i=0;i<n;i++)

    {

        j=i+1;

        w[i][j]= p[j]+q[i]+q[j]; // w(i,j)= p[j]+q[i]+w(i,j-1)

        c[i][j]=w[i][j]+c[i][j-1]+c[j][j]; // c(i,j)= min { c (i,k-1)+c(k+1, j) }+ w(i,j))
         //c[i][j]=q[i]+q[j]+p[j];

        r[i][j]=j;
        cout<<"Weight"<<"\t"<<"Cost"<<"\t"<<"Root";

        cout<<"\n"<<w[i][j]<<" "<<c[i][j]<<" "<<r[i][j];

        //cout<<"-------------------------------------------------------------------------";
        
    }

    for(m=2;m<=n;m++)

    {

        for(i=0;i<=n-m;i++)

        {

            j=i+m;

            w[i][j]=w[i][j-1]+p[j]+q[j];

            k=find(i,j);

            r[i][j]=k;

            c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
            cout<<"Weight"<<"\t"<<"Cost"<<"\t"<<"Root";

            cout<<"\n"<<w[i][j]<<" "<<c[i][j]<<" "<<r[i][j];

        }

        }

            //cout<<"-------------------------------------------------------------------------";

            cout<<"\n THE FINAL OBST IS : \n ";

            print(0,n);

            return 0;

        }

        int find(int i,int j)

        {

            int min=2000,m,l;//c[i][j];

            for(m=i+1;m<=j;m++)

            if(c[i][m-1]+c[m][j]<min)

            {

                min=c[i][m-1]+c[m][j];

                l=m;

            }

            return l;

        }

        void print(int i,int j)

        {

        if(i<j)

        cout<<idnt[r[i][j]]<<"\n"<<"root"<<endl;

        else

        return;

        print(i,r[i][j]-1);

        print(r[i][j],j);
        
    }



/*
    A Dictionary stores keywords & its meanings. Provide facility for adding new keywords,
     deleting keywords, updating values of any entry. Provide facility to display whole data
      sorted in ascending/ Descending order. Also find how many maximum comparisons may require
       for finding any keyword. Use Height balance tree and find the complexity for finding a keyword.
*/

#include<iostream>
#include<string>
using namespace std;
class dictionary;
class avlnode
{
    string keyword;
    string meaning;
    avlnode *left,*right;
    int bf;
    public:
    avlnode()
    {
        keyword='\0';
        meaning='\0';
        left=right=NULL;
        bf=0;
    }
    avlnode(string k,string m)
    {
        keyword=k;
        meaning=m;
        left=right=NULL;
        bf=0;
    }
friend class dictionary;
};

class dictionary
{
    avlnode *par,*loc;
    public:
    avlnode *root;
    dictionary()
    {    
        root=NULL;
        par=loc=NULL;
    }
    void accept();
    void insert(string key,string mean);
    void LLrotation(avlnode*,avlnode*);
    
    void RRrotation(avlnode*,avlnode*);
    
    void inorder(avlnode *root);
    void deletekey(string key);
    void descending(avlnode *);
    void search(string);
    void update(string,string);

};
void dictionary::descending(avlnode *root)
{
    if(root)
    {
        descending(root->right);
        cout<<root->keyword<<" "<<root->meaning<<endl;
        descending(root->left);
    }
}

void dictionary::accept()
{
    string key,mean;
    cout<<"Enter keyword "<<endl;
    cin>>key;
    cout<<"Enter meaning "<<endl;
    cin>>mean;
    insert(key,mean);
}
void dictionary::LLrotation(avlnode *a,avlnode *b)
{
    cout<<"LL rotation"<<endl;    
    a->left=b->right;
    b->right=a;
    a->bf=b->bf=0;
}

void dictionary::RRrotation(avlnode *a,avlnode *b)
{
    cout<<"RR rotation"<<endl;    
    a->right=b->left;
    b->left=a;
    a->bf=b->bf=0;
}

 

 

 

void dictionary::insert(string key,string mean)
{
    //cout<<"IN Insert \n";
    if(!root)
    {
        //create new root
        root=new avlnode(key,mean);
        cout<<"ROOT CREATED \n";
        return;
    }
//    else
//    {
        avlnode *a,*pa,*p,*pp;
        //a=NULL;
        pa=NULL;
        p=a=root;
        pp=NULL;

        while(p)
        {
            cout<<"In first while \n";
            if(p->bf)
            {
            a=p;
            pa=pp;
            }
            if(key<p->keyword){pp=p;p=p->left;}   //takes the left branch
            else if(key>p->keyword){pp=p;p=p->right;} //right branch
            else
            {
                //p->meaning=mean;
                cout<<"Already exist \n";
                return;
            }
        }
        cout<<"Outside while \n";
        avlnode *y=new avlnode(key,mean);        
        if(key<pp->keyword)
        {
            pp->left=y;
        }
        else
            pp->right=y;
        cout<<"KEY INSERTED \n";

        int d;
        avlnode *b,*c;
        //a=pp;
        b=c=NULL;
        if(key>a->keyword)
        {
            cout<<"KEY >A->KEYWORD \n";
            b=p=a->right;
            d=-1;
            cout<<" RIGHT HEAVY \n";
        }
        else
        {
            cout<<"KEY < A->KEYWORD \n";
            b=p=a->left;
            d=1;
            cout<<" LEFT HEAVY \n";
        }

        while(p!=y)
        {
            if(key>p->keyword)
            {
                p->bf=-1;
                p=p->right;

            }
            else
            {
                p->bf=1;
                p=p->left;
            }
        
        }
        cout<<" DONE ADJUSTING INTERMEDIATE NODES \n";
        if(!(a->bf)||!(a->bf+d))
        {
            a->bf+=d;
            return;
        }
        //else
        //{
        if(d==1)
        {
            //left heavy
            if(b->bf==1)
            {
                LLrotation(a,b);
                /*a->left=b->right;
                b->right=a;
                a->bf=0;
                b->bf=0;*/
            }
            else //if(b->bf==-1)
            {
                
                cout<<"LR rotation"<<endl;        
                c=b->right;
                b->right=c->left;
                a->left=c->right;
                c->left=b;
                c->right=a;
                switch(c->bf)
                {
                    case 1:
                    {
                        a->bf=-1;
                        b->bf=0;
                        break;
                    }
                    case -1:
                    {
                        a->bf=0;
                        b->bf=1;
                        break;
                    }

                    case 0:
                    {
                        a->bf=0;
                        b->bf=0;
                        break;
                    }
        
                }
                c->bf=0;
                b=c;   //b is new root

                
            }
            //else
            //    cout<<"Balanced \n";

        }
    
        if(d==-1)
        {
            if(b->bf==-1)
            {
        //        cout<<"RR rotation"<<endl;    
                /*a->right=b->left;
                b->left=a;
                a->bf=b->bf=0;*/
                RRrotation(a,b);
            }
            else// if(b->bf==1)
            {
                c=b->left;
        //        cout<<"RL rotation"<<endl;        
                a->right=c->left;
                b->left=c->right;
                c->left=a;
                c->right=b;
                switch(c->bf)
                {
                    case 1:
                    {
                        a->bf=0;
                        b->bf=-1;
                        break;
                    }
                    case -1:
                    {
                        a->bf=1;
                        b->bf=0;
                        break;
                    }

                    case 0:
                    {
                        a->bf=0;
                        b->bf=0;
                        break;
                    }
        
                }
                c->bf=0;
                b=c;  //b is new root
                
            }

            //else
                //cout<<"Balanced \n";
        }
        //}
        if(!pa)
            root=b;
        else if(a==pa->left)
            pa->left=b;
        else
            pa->right=b;
        cout<<"AVL tree created!! \n";
        //cout<<"AVL \n";
        //inorder(root);
    

}
void dictionary::search(string key)
{
    cout<<"ENTER SEARCH \n";
    loc=NULL;
    par=NULL;
    if(root==NULL)
    {
        cout<<"Tree not created  "<<endl;
        //    root=key;
        loc=NULL;
        par=NULL;
    }

    //par=NULL;loc=NULL;
    avlnode *ptr;
    ptr=root;
    while(ptr!=NULL)
    {
        if(ptr->keyword==key)
        {

            //flag=1;
            loc=ptr;
            break;                                    //imp for delete1 else it doesnt exit while loop
        }
        else if(key<ptr->keyword)
        {
            par=ptr;
            ptr=ptr->left;
        }

        else
        {
            par=ptr;                           //edit this in previous code
            ptr=ptr->right;
            
        }
    }
    
    if(loc==NULL)
    {
        cout<<"Not found "<<endl;
    }
    
}

void dictionary::update(string oldkey,string newmean)
{
    search(oldkey);
    loc->meaning=newmean;
    cout<<"UPDATE SUCCESSFUL \n";
}
void dictionary::deletekey(string key)
{
    
}
void dictionary::inorder(avlnode *root)
{
    if(root)
    {
        inorder(root->left);
        cout<<root->keyword<<" "<<root->meaning<<endl;
        inorder(root->right);
    }
}

int main()
{
    string k,m;
    dictionary d;
    int ch;
    string key,mean;
    
    do
    {
    cout<<"1.Insert \n2.Update \n3.Ascending \n4.Descending \n5.Display \n6.Quit \n";
    cin>>ch;
    switch(ch)
    {
        case 1:
        {
            d.accept();
            break;
        }
        case 2:
        {
            cout<<"Enter key whose meaning to update \n";
            cin>>key;
            cout<<"Enter new meaning\n";
            cin>>mean;
            d.update(key,mean);
            break;
        }
        case 3:
            d.inorder(d.root);
            break;
        
        case 4:
            cout<<"Descending \n";
            d.descending(d.root);
            break;
        
        case 5:
            d.inorder(d.root);
            break;
        default:
            break;
    }    
    }while(ch!=6);    /*cout<<"Enter word and its meaning"<<endl;
        cin>>k>>m;
        d.insert(k,m);*/
    //    d.accept();
        //cout<<"Enter another word and its meaning \n";
    //    cin>>k>>m;
    //    d.insert(k,m);
        
    
        //cout<<"MAIN \n";
        
        
    
return 0;
}




#include <iostream>
#define SERIOUS 10
#define NONSERIOUS 5
#define GENERAL 1
const int MAX_SIZE = 100;
using namespace std;

class PriorityQueue 
{
  public:
      string N[MAX_SIZE];
      int P[MAX_SIZE];
      int front, rear;

    PriorityQueue() 
    {
          front = -1;
          rear = -1;
      }

    bool isFull() {
        return rear == MAX_SIZE - 1;
    }

    bool isEmpty() {
        return front == -1 || front > rear;
    }

    void enqueue(string name,int value) {
        if (isFull()) {
            cout << "Queue is full" << endl;
            return;
        }

        if (isEmpty()) {
            front++;
            rear++;
            N[rear]=name;
            P[rear] = value;
        } 
    else {
            int i;
            for (i = rear; i >= front; i--) { //i=1
                if (value > P[i]) { //10 > 5
                    P[i+1] = P[i]; //p[2] 5
                    N[i+1] = N[i]; //N[2] abc2
                } else {
                    break;
                }
            } 
            N[i+1] = name; // abc 10 abc3 10 abc2 5
            P[i+1] = value;
            rear++;//2
        }
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return -1;
        }

        int value = front;

        if (front == rear){
            front = -1;
            rear = -1;
        } 
    else {
            front++;
        }

        return value;
    }

    void display() {
        if (isEmpty()) {
            cout<<"\nQueue is empty" << endl;
            return;
        }

        cout<<"\nQueue elements are : \n";
        cout<<"\n\tName \t Priority";
    cout<<"\n____";
        for (int i = front; i <= rear; i++) 
    {
            cout<<"\n\t "<<N[i]<<" \t "<<P[i];
        }
        cout << endl;
    }
};

int main() {
    PriorityQueue PQ;
    string data;
    int ch = 0, p;

    while(ch != 4){
        cout<<"\n\n----- PRIORITY QUEUE -----\n\n";
        cout<<"\t1. Insert data\n\t2. Display data\n\t3. Delete data\n\t4. Exit\n";
        cout<<"\n____\n";
    cout<<"Enter your choice: ";
        cin>>ch;

        switch(ch)
    {
            case 1:
                cout<<"\nEnter patient name: ";
                cin>>data;
                cout<<"\nEnter priority of patient(1 - Serious, 2 - Non-serious, 3 - General checkup): ";
                cin>>p;

                switch (p){
                    case 1: 
                        PQ.enqueue(data, SERIOUS);//abc 10 //abc3 10
                        break;
                
                    case 2:
                        PQ.enqueue(data, NONSERIOUS);// abc2 5
                        break;

                    case 3:
                        PQ.enqueue(data, GENERAL);
                        break;

                    default:
                        cout<<"Enter valid priority value!\n";
                        break;
                }
                
                break;

            case 2:
                PQ.display();
                break;

            case 3:int x;
                x=PQ.dequeue();
                if(x!=-1)
                    cout<<"\nPatient "<<PQ.N[x]<<" having priority "<<PQ.P[x]<<" is dequeued..\n";
                break;

            case 4:
                cout<<"\n\n** Thank you **\n";
                break;

            default:
                cout<<"Enter valid option!\n";
                break;
        }
    }
    return 0;
}

#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

typedef struct stud
    {
        int roll;
        char name[10], div,add[10];
    }stud;
    stud rec;

class student
  {
    public:
      void create();
      void display();
      int search();
      void Delete();
  };

void student::create()
  {
    char ans;
    ofstream fout;
    fout.open("stud.dat",ios::out|ios::binary);
    do
      {
        cout<<"\n\tEnter Roll No of Student    : ";
        cin>>rec.roll;
        cout<<"\n\tEnter a Name of Student     : ";
        cin>>rec.name;
        cout<<"\n\tEnter a Division of Student : ";
        cin>>rec.div;
        cout<<"\n\tEnter a Address of Student  : ";
        cin>>rec.add;
        fout.write((char *)&rec,sizeof(stud))<<flush;
        cout<<"\n\tDo You Want to Add More Records: ";
        cin>>ans;
      }while(ans=='y'||ans=='Y');
    fout.close();
  }

void student::display()
  {
    ifstream fin;
    fin.open("stud.dat",ios::in|ios::binary);
    fin.seekg(0,ios::beg);
    cout<<"\n\tThe Content of File are:\n";
    cout<<"\n\tRoll\tName\tDiv\tAddress";
    while(fin.read((char *)&rec,sizeof(stud)))
      {
        if(rec.roll!=-1)
            cout<<"\n\t"<<rec.roll<<"\t"<<rec.name<<"\t"<<rec.div<<"\t"<<rec.add;
      }
    fin.close();
  }

int student::search()
  {
    int r,i=0;
    ifstream fin;
    fin.open("stud.dat",ios::in|ios::binary);
    fin.seekg(0,ios::beg);
    cout<<"\n\tEnter a Roll No: ";
    cin>>r;
    while(fin.read((char *)&rec,sizeof(stud)))
      {
        if(rec.roll==r)
          {
            cout<<"\n\tRecord Found...\n";
            cout<<"\n\tRoll\tName\tDiv\tAddress";
            cout<<"\n\t"<<rec.roll<<"\t"<<rec.name<<"\t"<<rec.div<<"\t"<<rec.add;
            return i;
          }
        i++;
      }
    fin.close();
    return 0;
  }

void student::Delete()
  {
    int pos;
    pos=search();
    fstream f;
    f.open("stud.dat",ios::in|ios::out|ios::binary);
    f.seekg(0,ios::beg);
    if(pos==0)
      {
        cout<<"\n\tRecord Not Found";
        return;
      }
    int offset=pos*sizeof(stud);
    f.seekp(offset);
    rec.roll=-1;
    strcpy(rec.name,"NULL");
    rec.div='N';
    strcpy(rec.add,"NULL");
    f.write((char *)&rec,sizeof(stud));
    f.seekg(0);
    f.close();
    cout<<"\n\tRecord Deleted";
  }
    
int main()
  {
    student obj;
    int ch,key;
    char ans;
    do
      {
        cout<<"\n\t*** Student Information ***";
        cout<<"\n\t1. Create\n\t2. Display\n\t3. Delete\n\t4. Search\n\t5. Exit";
        cout<<"\n\t..... Enter Your Choice: ";
        cin>>ch;
        switch(ch)
          {
            case 1: obj.create();
                break;
            case 2: obj.display();
                break;
            case 3: obj.Delete();
                break;
            case 4: key=obj.search();
                if(key==0)
                  cout<<"\n\tRecord Not Found...\n";
                break;
            default:
                break;
          }
        cout<<"\n\t..... Do You Want to Continue in Main Menu: ";
        cin>>ans;
      }while(ans=='y'||ans=='Y');
    return 1;
  }



/***********************************************************************
Program for performing various operations on
Index Sequential File organisation.
************************************************************************/
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;

typedef struct employee {
    int empIdNo;
    char name[50];
    char designation[50];
    int salary;
} employee;

class employeeDatabase {
    string fileName = "employee_data.dat";

   public:
    employeeDatabase() {
        fstream fileObj(fileName);
        if (fileObj.fail()) {
            fileObj.open(fileName, ios::out);
            cout << "New File Created" << endl;
        } else {
            cout << "Existing File Found" << endl;
        }
        fileObj.close();
    }

    void addEmployee();
    void searchEmployee();
    void deleteEmployee();
    void displayAll();
};

void employeeDatabase::searchEmployee() {
    int empId;
    employee emp;
    bool status = false;

    // take input of empId number to search
    cout << "Enter Employee Id to search:";
    cin >> empId;

    // opening files to search a record
    ifstream readFile;
    readFile.open(fileName, ios::in | ios::binary);

    // looking for record
    while (readFile.read((char*)&emp, sizeof(employee))) {
        if (emp.empIdNo == empId) {
            status = true;
            break;
        }
    }
    readFile.close();

    if (status) {
        cout << "Found record with details" << endl;
        cout << "Employee ID:" << emp.empIdNo << endl;
        cout << "Name:" << emp.name << endl;
        cout << "Designation:" << emp.designation << endl;
        cout << "Salary:" << emp.salary << endl;
    } else {
        cout << "No record found" << endl;
    }
}

void employeeDatabase::deleteEmployee() {
    int empId;
    employee emp;
    bool status = false;

    // take input of empId number to delete
    cout << "Enter Employee Id to delete:";
    cin >> empId;

    // opening files to delete a record
    ifstream readFile;
    readFile.open(fileName, ios::in | ios::binary);
    ofstream writeFile;
    writeFile.open("~" + fileName, ios::out | ios::binary);
    writeFile.clear();

    // looking for record
    while (readFile.read((char*)&emp, sizeof(employee))) {
        if (emp.empIdNo == empId) {
            status = true;
        } else {
            writeFile.write((char*)&emp, sizeof(employee)) << flush;
        }
    }
    readFile.close();
    writeFile.close();

    // moving temp file back to original file
    if (status) {
        readFile.open("~" + fileName, ios::in | ios::binary);
        writeFile.open(fileName, ios::out | ios::binary);
        writeFile.clear();

        writeFile << readFile.rdbuf();
        readFile.close();
        writeFile.close();

        // remove("~"+fileName);
        cout << "Deleted record" << endl;
    } else {
        cout << "No record found" << endl;
    }
}

void employeeDatabase::addEmployee() {
    employee emp;
    cout << "Enter Employee Id of employee:";
    cin >> emp.empIdNo;
    cout << "Enter Name of employee:";
    cin.ignore();
    cin.getline(emp.name, 50);
    cout << "Enter Designation of employee:";
    // cin.ignore();
    cin.getline(emp.designation, 50);
    cout << "Enter Salary of employee:";
    cin >> emp.salary;
    // cin.ignore();
    ofstream file(fileName, ios::out | ios::binary | ios::app);
    // file.seekp(ios::end);
    file.write((char*)&emp, sizeof(employee)) << flush;
    if (file.fail()) {
        cout << "Failed to add record" << endl;
    } else {
        cout << "Employee record added successfully" << endl;
    }
    file.close();
}

void employeeDatabase::displayAll() {
    ifstream file;
    employee emp;
    int count = 0;
    file.open(fileName, ios::in | ios::binary);
    while (file.read((char*)&emp, sizeof(employee))) {
        count++;
        cout << count << ") ";
        cout << emp.empIdNo << "|";
        cout << emp.name << "|";
        cout << emp.designation << "|";
        cout << emp.salary << endl;
    }
    if (count == 0) {
        cout << "No records Found" << endl;
    }
    file.close();
}
int main() {
    int ch;
    employeeDatabase db;

    do {
        cout << endl;
        cout << "MENU" << endl;
        cout << "1. Add Record" << endl;
        cout << "2. Delete Record" << endl;
        cout << "3. Search Record" << endl;
        cout << "4. Display All Records" << endl;
        cout << "0. Exit" << endl << endl;
        cout << "Enter Your Choice :";
        cin >> ch;
        switch (ch) {
            case 0:
                cout << "Thank You" << endl;
                break;
            case 1:
                db.addEmployee();
                break;
            case 2:
                db.deleteEmployee();
                break;
            case 3:
                db.searchEmployee();
                break;
            case 4:
                cout << "Records in File are" << endl;
                db.displayAll();
                break;

            default:
                cout << "Enter a valid Choice" << endl;
                break;
        }
    } while (ch != 0);

    return 0;
}