5. Below are five computational tasks. For each one, choose the data structure o

Question

5. Below are five computational tasks. For each one, choose the data structure or abstract data type you feel best suited to the task from the following list: Stack, Queue, Hashtable, AVL Tree, Priority Queue, Union-Find. In addition, list the basic operations for the data structure or ADT that you chose and give asymptotic worst-case running times for those operations. No additional explanation is required. (a) While processing a list of objects, check if you have processed a particular object before. (b) Store a list of students and their grades. You must also provide an efficient way for a client to see all students sorted in alphabetical order by name. Give the running time for this operation as well. (c) Process a digital image to divide the image up into groups of pixels of the same color. (d) Compute a frequency analysis on a file. That is, count the number of times each character occurs in the file, and store the results (e) Store the activation records (i.e. objects containing the return address and local variable associated with a function call) for nested function calls.

Explanation / Answer

5 (a). To process the list of objects and we must make sure that before that it was processed or not.

For the above situation we can use the Hash-Table data structure,

Hast-table store the object based on the hash code, if hash code is already present in hash-table we will get to know the object is processed. For every object their will, be unique hash-code.

We must write a hash function which return unique hash value of different objects.

Worst case: O(n).

(b). To store the student details and their grade we can use either AVL tree or HASH-table,

Both the data structure will perform well. But worst-case complexity of AVL tree better that Hash table. We can use AVL tree for above scenario.

If we use AVL tree (which is kind of balanced binary tree) it's easier to iterate tree nodes (forward and backward). In each tree node has the name and grade of student, we must write a function which store the data in tree based on the names.

worst case complexity in case of AVL tree is O (log N).

(c) To store the image, we can use the 2Dimension array. In second part of the question we have asked to group the pixel based on the colour. For second part we can use the Hash-table, based on the colour we can calculate the hash-code and do the grouping for the pixel. For each colour we have different hash code, which help us to grouping the pixel of similar types. Worst case complexity in our case would be same as best case which is O(1).

(d) for frequency analysis the best was to use hash table, which store the data in

<key, value >format (map is one of the data structure which store the data in key value form), key is the hash code for each character and value part will count the occurrence.

For 2 different character hash code is always different, so there is no chance of collision.

So worst case complexity in this case is same as the best case complexity O(1).

(e) To store the local variable and object containing the return address,

      For the above situation we can use STACK data structure. As we know that in all     

programming languages complier uses the stack to store the local function variable. The situation given the section (e) is analogues to the compiler situation. Stack would be the best choice.

      Worst case complexity is O(N).

           

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.