Assignment No. 04 SEMESTER Fall 2013 CS301- Data Structures Total Marks: 25 Due Date: 29/01/2014

	Assignment No. 04 SEMESTER Fall 2013 CS301- Data Structures		Total Marks: 25 Due Date: 29/01/2014
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: Ø  The assignment is submitted after due date. Ø  The submitted assignment file is not in .doc or .docx format. Ø  The submitted assignment file does not open or corrupted. Ø  The assignment is copied (from other student or ditto copy from handouts or internet). Uploading instructions For clarity and simplicity, You are required to Upload/Submit only one MS word file which will contain solutions of all the questions. Ø  Don’t wait for grace day. Grace Day is given only if there is problem with LMS on due date. Submit your solution within due date. Ø  Note that no assignment will be accepted through email if there is any problem on grace day. Note: It is recommended to use Microsoft Word for solution of assignment. Objective The objective of this assignment is o   To make you familiar with traversing AVL tree, threaded binary tree and construction of (min and max) heap. For any query about the assignment, contact at cs301@vu.edu.pk GOOD LUCK
		Marks: 25
Question 1(a):                                                                                                                                    Marks 2 Find the pre-order traversal of AVL tree given in solution of assignment 3. Question 1(b):                                                                                                                                    Marks 8 Construct min heap from data traversed in question 1(a). Question 2(a):                                                                                                                                    Marks 2 Find the post-order traversal of AVL tree given in solution of assignment 3. Question 2(b):                                                                                                                                    Marks 8 Construct max heap from data traversed in question 2(a).     Question 3: An AVL tree is given in the solution file of assignment 3. Convert that AVL tree into a threaded binary tree and also use dummy node in this threaded binary tree.                                                                            Marks 5 Solution Guidelines: Use assignment 3 solution file for AVL tree while finding pre-order, post-order traversal or constructing threaded binary tree. In question 1(b) show final tree of min heap and status of array. In question 2(b) show final tree of max heap and status of array. While building max or min heap tree, read traversed values from left to right.
Lectures Covered:  This assignment will covers lectures #  23 - 31 Deadline:           Your assignment must be uploaded / submitted on / before, Wednesday January 29, 2014.