 | Assignment No. 05 SEMESTER fall 2011 CS301- Data Structures | Total Marks: 20 Due Date: 23rd January 2012 | ||||||||||||
| 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 does NOT open or file corrupt. o The assignment is copied (from other student or ditto copy from handouts or internet). Objective The objective of this assignment is to give you some practice exercise of o Max heap and Min Heap o Union For any query about the assignment, contact at cs301@vu.edu.pk GOOD LUCK | ||||||||||||||
| | Marks: 20 | |||||||||||||
| Question No.1 (5+5 Marks) Consider the following array as input
I) Prove that it is a heap and also explain what type of heap it is.? II) Add 16 and 3 into the heap and convert it into Max heap. Question No: 2 Marks: 10 Perform the following sequence of Union operations on the set of elements {1,2,3,4,5,6,7,8,9,10,11} using Union by Size. Union(1,2) Union(3,5) Union(3,6) Union(1,4) Union(3,9) Union(10,11) Union(1,10) Union(7,8) Union(10,7) Union(1,3) . | ||||||||||||||
| Lectures Covered: This assignment will covers 29 to 36 Lectures Deadline: Your assignment must be uploaded/submitted at or before 23rd January 2012. | ||||||||||||||
Search with our Site
Custom Search
Friday, January 20, 2012
Assignment # 5 CS301 Fall 2011 Due Date 23 jan 2011
Subscribe to:
Post Comments (Atom)
Answer 1.
ReplyDeleteFirst I define, Heap.
“ Heap is a complete binary tree that confirms to the heap order”.
The heap order is a property that states that in a minimum heap for every node X, the key in the parent is smaller than or equal to the key in X. In simple word it can be said that parent nod has key smaller than the values on its children nodes. That’s the proof that we implement the heap by complete binary tree.
Heap is the data structure of big use and benefit. It is used in priority queue. If we put the events that are going to happen in a special queue, like priority queues. This priority queue does not follow the FIFO (First in First out) rule. We have to put elements in the queue at the end but after that we get the element with respect to its priority. We get element that is going to occur first in the future. The event with minimum time of occurrence becomes at first position in the sorted array. We get the event with minimum time first. After removal of the element, a programmer shifts the array elements to left. And if we insert a new element , the array is sorted again.
Try this link for solution
ReplyDeleteAssignment No. 05
SEMESTER fall 2011
CS301- Data Structures
http://vustudents.ning.com/group/cs301datastructures/forum/topics/assignment-5-cs301-fall-2011-due-date-23-jan-2011