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; }SOLVED CS301 GDB 1 Solution and Discussion
-
Re: CS301 GDB 1 Solution and Discussion
Total Marks 5
Starting Date Monday, February 08, 2021
Closing Date Tuesday, February 09, 2021
Status Open
Question Title Graded Discussion Board
Question Description
GDB Scenario:Your friend is developing a maze puzzle game and already designed a module which can generate a random maze. The maze has one entry and one exit point. Now he needs to develop the module which will find the path from entry to exit points for randomly generated maze. Your friend wants the path searching should be quickest. He can use only Stack or Queue data structures to store maze’s visited locations for path generation. He is unable to decide the selection of data structure and asked you to help him.
GDB Question:
From Stack and Queue data structures which data structure you will suggest using for entry to exit path finding module? Select a data structure and give comments in favour to justify your selection. Also mention why you are not selecting the other data structure?
Instructions:
A concise, coherent and to the point answer is preferred over lengthy comment having irrelevant details. Answers, posted on regular Lesson’s MDB or sent through email will NOT be considered in any case.
Best of Luck!
-
@zaasmi said in CS301 GDB 1 Solution and Discussion:
From Stack and Queue data structures which data structure you will suggest using for entry to exit path finding module? Select a data structure and give comments in favour to justify your selection. Also mention why you are not selecting the other data structure?
I Would suggest Stack data structure over Queue. This is because in solving a maze problem, we need to explore all possible paths. Along with that, we also need to track the paths visited.
If we were to use Queue, then after finding an unsuccessful path, we’ll have to start again from the entry point as queue only supports deletion from the front (FIFO property). This would not be useful in our case, as we need to trace back the unsuccessful path until we find another way.
Using Stack, what we can do is, while moving into the maze, we can push the index of the last visited cell and when reached the end of the maze(not exit-point), just keep popping elements from the stack until the cell at stack Top has another way to move.
Using this approach (particularly stack), you can find the correct path in the shortest possible time. -
@zaasmi said in CS301 GDB 1 Solution and Discussion:
From Stack and Queue data structures which data structure you will suggest using for entry to exit path finding module? Select a data structure and give comments in favour to justify your selection. Also mention why you are not selecting the other data structure?
I Would suggest Stack data structure over Queue. This is because in solving a maze problem, we need to explore all possible paths. Along with that, we also need to track the paths visited.
If we were to use Queue, then after finding an unsuccessful path, we’ll have to start again from the entry point as queue only supports deletion from the front (FIFO property). This would not be useful in our case, as we need to trace back the unsuccessful path until we find another way.
Using Stack, what we can do is, while moving into the maze, we can push the index of the last visited cell and when reached the end of the maze(not exit-point), just keep popping elements from the stack until the cell at stack Top has another way to move.
Using this approach (particularly stack), you can find the correct path in the shortest possible time.


-
UNSOLVED CS301 Final Term Current Paper
CS301 – Data Structures • • zareen
100% Off on Your FEE Join US! Ask Me How?


