ARIZONA STATE UNIVERSITY
CSE 310, All Sections | Data Structures and Algorithms | Fall 2015
Available Wednesday, 09/16/2015; due electronically Friday, 10/09/2015
This assignment covers Chapters 6 (Heaps), 7 (Quicksort), and 9 (Medians and Order Statistics) of the text
[100 marks total].
Submit electronically, before midnight on Friday, 10/09/2015 using the submission link on Blackboard for
Assignment #2, a le named [url removed, login to view] containing your solution to this assignment
(a .doc or .docx le is also acceptable, but .pdf is preferred).
1. Heaps. [10 marks total]
(a) What are the minimum and maximum number of elements in a heap of height h? [2 marks]
(b) Show that an n-element heap has height blog nc. [2 marks]
(c) Show that in any subtree of a max-heap, the root of the subtree contains the largest value occurring
anywhere in that subtree. [4 marks]
(d) Is the sequence h23; 17; 14; 6; 13; 10; 1; 5; 7; 12i a max-heap? Why or why not? [2 marks]
2. Heaps. [10 marks total]
(a) Illustrate the operation of Max-Heapify(A; 3) on the array A = h27; 17; 3; 16; 13; 10; 1; 5; 7; 12; 4; 8; 9; 10i.
(b) Illustrate the operation of Build-Max-Heap(A) on the array A = h5; 3; 17; 10; 84; 19; 6; 22; 9i.
(c) You are given a list of numbers for which you need to construct a min-heap. How would you use
an algorithm for constructing a max-heap to construct a min-heap? [5 marks]
3. Heapsort. [10 marks]
Argue the correctness of Heapsort using the following loop invariant.
At the start of each iteration of the for loop, the subarray A[1 : : : i] is a max-heap containing
the i smallest elements of A[1 : : : n], and the subarray A[i+1 : : : n] contains the n
2 freelanceria on tarjonnut keskimäärin 339 ₹/tunti tähän työhön
Hi I am from an ISC/ICSE background and currently 4th Year BE student and I am perfect candidate to do the job. I have almost 5 years of experience learning and practicing java. Thank You Yash