CS301 Assignment 3 Solution and Discussion


  • Cyberian's Gold

    Assignment No. 03
    Fall 2019
    CS301 - Data Structures
    Total Marks: 20

    Due Date: 21-1-2020
    Instructions
    Please read the following instructions carefully before solving & submitting assignment:
    It should be clear that your assignment will not get any credit (zero marks) if:
    o The assignment is submitted after due date.
    o The submitted assignment is other than C++ file (.cpp).
    o The submitted assignment does NOT open or file is corrupted.
    o The assignment is copied (from other student or ditto copy from handouts or internet).
    Uploading instructions
    You are required to upload / submit .CPP file.
    Use Dev-C++, Version 5.11 or above.

    Objective
    The objective of this assignment is ;

    o To make you familiar with Huffman Encoding technique.
    o To learn how to write a program for Huffman Encoding in C++.

    For any query about the assignment, contact at [email protected]

    GOOD LUCK

    Problem Statement

    As you know, Huffman Encoding is a technique developed and used for data compression. It is widely used algorithm for JPEG images. Incomplete code of Huffman Encoding is given below. You are required to complete the missing code.

    In the given code we are using two classes and two functions. The first class HeapNode_Min will consist of data members and a constructor. The second class Analyze will consist of a function which will compare two heap nodes and will return the result. We are also using display function to print the codes of Huffman tree from the root. HCodes function is used to build a Huffman tree, this function is using two while loops and at the end it calls display_Codes function. In main function we are using two arrays, one for frequency and the second one for alphabets. We are using size_of variable to store the size of data types after their division. At the end of the main function we will call HCodes function.

    Note: Just add the missing code. Don’t change the given code. Instructions are highlighted with red color.

    // Huffman Coding program in c++
    
    #include <bits/stdc++.h> 
    using namespace std; 
      
    
    class HeapNode_Min { // Tree node of Huffman      
      
      public:
        
    //Add data members here.  
     
        HeapNode_Min(char d, unsigned f) 
        { 
              //Complete the body of HeapNode_Min function
        } 
    }; 
      
    class Analyze {  // two heap nodes comparison
      
      public:
        bool operator()(HeapNode_Min* l, HeapNode_Min* r) 
        { 
             (l->f > r->f); //Complete this statement
        } 
    }; 
      
    void display_Codes(HeapNode_Min* root, string s) // To print codes of huffman tree from the root. 
    {   
        if (!root) 
            return; 
      
        if (root->d != '$') 
            cout << root->d << "\t: " << s << "\n";
      
        display_Codes(root->l, s + "0"); 
        display_Codes( ); //Complete this statement by passing arguments
     
    } 
      
    
    void HCodes(char data[], int freq[], int s) // builds a Huffman Tree
    { 
        HeapNode_Min  *t,*r, *l ;  // top, right, left
    
      
        priority_queue<HeapNode_Min*, vector<HeapNode_Min*>, Analyze> H_min; 
      
        int a=0;
    	while (a<s){H_min.push(new HeapNode_Min(data[a], freq[a])); ++a;}
    	
      
        while (H_min.size() != 1) { 
      
            l = H_min.top(); H_min.pop(); 
            r = H_min.top(); H_min.pop(); 
      
            t = new HeapNode_Min('$',  r->f + l->f); 
      
            t->r = r; t->l = l; 
           
      
            H_min.push(t); 
        } 
      
        display_Codes(H_min.top(), ""); 
    } 
      
    int main() 
    { 
        int frequency[] = { 3, 6, 11, 14, 18, 25 };  char alphabet[] = { 'A', 'L', 'O', 'R', 'T', 'Y' };  
      	int size_of = sizeof() / sizeof(); //Complete this statement by passing data type to both sizeof operators 
      
      cout<<"Alphabet"<<":"<<"Huffman Code\n";
      cout<<"--------------------------------\n";
    
       //Call Huffman_Codes function.  
      
        return 0; 
    }
    

    Sample Output of the above program is given below.
    9aab7e1d-84a7-4700-a725-d558070fc0b6-image.png

    Important Note: Use Dev-C++, Version 5.11 or above.
    Deadline: Your assignment must be uploaded/submitted at or before 21-1-2020.


  • Cyberian's Gold

    Solution Idea!

    #include <bits/stdc++.h> 
    using namespace std; 
    
    
    class HeapNode_Min { // Tree node of Huffman 
    
    public:
    //Add data members here. 
    char d;
    unsigned f;
    HeapNode_Min *l, *r;
    
    
    HeapNode_Min(char d, unsigned f = -1) 
    { 
    //Complete the body of HeapNode_Min function
    this->d = d;
    this->f = f ;
    this->l = NULL;
    this->r = NULL;
    } 
    }; 
    
    class Analyze { // two heap nodes comparison
    
    public:
    bool operator()(HeapNode_Min* l, HeapNode_Min* r) 
    { 
    //add return before statement and statement is completed. 
    return (l->f > r->f); //Complete this statement
    } 
    }; 
    
    void display_Codes(HeapNode_Min* root, string s) // To print codes of huffman tree from the root. 
    { 
    if (!root) 
    return; 
    
    if (root->d != '$') 
    cout  root->d  "\t: "  s  "\n";
    
    display_Codes(root->l, s + "0"); 
    display_Codes(root->r, s + "1"); //Complete this statement by passing arguments
    
    } 
    
    
    void HCodes(char data[], int freq[], int s) // builds a Huffman Tree
    { 
    HeapNode_Min *t,*r, *l ; // top, right, left
    
    
    priority_queue<HeapNode_Min*, vector<HeapNode_Min*>, Analyze> H_min; 
    
    int a=0;
    while (a<s){H_min.push(new HeapNode_Min(data[a], freq[a])); ++a;}
    
    
    while (H_min.size() != 1) { 
    
    l = H_min.top(); H_min.pop(); 
    r = H_min.top(); H_min.pop(); 
    
    t = new HeapNode_Min('$', r->f + l->f); 
    
    t->r = r; t->l = l; 
    
    
    H_min.push(t); 
    } 
    
    display_Codes(H_min.top(), ""); 
    } 
    
    int main() 
    { 
    int frequency[] = { 3, 6, 11, 14, 18, 25 }; char alphabet[] = { 'A', 'L', 'O', 'R', 'T', 'Y' }; 
    //Complete this statement by passing data type to both sizeof operators 
    int size_of = sizeof(alphabet) / sizeof(*alphabet);
    
    cout"Alphabet"":""Huffman Code\n";
    cout"--------------------------------\n";
    
    //Call Huffman_Codes function. 
    HCodes(alphabet, frequency, size_of);
    return 0; 
    }
    

  • Cyberian's Gold


  • Cyberian's Gold



Quiz 100% Result
| |