need some one with good data structure and algorithm knowledge

ARIZONA STATE UNIVERSITY

CSE 310, All Sections | Data Structures and Algorithms | Fall 2015

Assignment #2

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.

[2 marks]

(b) Illustrate the operation of Build-Max-Heap(A) on the array A = h5; 3; 17; 10; 84; 19; 6; 22; 9i.

[3 marks]

(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

C Programmierung C++ Programmierung Ingenieurwesen Java

Projekt-ID: #8653637

Über das Projekt