Scribd
Upload
61 views2 pages

CPSC 502 Problem Set 3: Heaps & BSTs

This document contains the problems for Problem Set 3 that is due on September 20, 2016 for CPSC 502 at the University of Bridgeport. It includes 6 problems related to heaps, sorting algorithms, binary search trees, and converting a binary search tree into a min heap. The problems range from 5 to 15 marks and involve tasks like drawing heap and binary search tree representations, carrying out heapsort steps, analyzing sorting algorithms, and providing algorithms.

Uploaded by

skdfks
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
61 views2 pages

CPSC 502 Problem Set 3: Heaps & BSTs

This document contains the problems for Problem Set 3 that is due on September 20, 2016 for CPSC 502 at the University of Bridgeport. It includes 6 problems related to heaps, sorting algorithms, binary search trees, and converting a binary search tree into a min heap. The problems range from 5 to 15 marks and involve tasks like drawing heap and binary search tree representations, carrying out heapsort steps, analyzing sorting algorithms, and providing algorithms.

Uploaded by

skdfks
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CPSC 502: Problem Set 3

University of Bridgeport
Due September 20, 2016
HEAPS
Problem 1 [5 marks]

Problem 2 [15 marks]


Consider) the) numbers) 23, 18, 12, 14, 9, 7, 10, 6, 5, 8) in) successive)
locations)A[1], A[2], ..., A[10])of)an)array)A.)
)
a) Write) the) array) and) its) numbers) as) a) complete) binary) tree) as) is) done) for)
heaps.)Explain)carefully)why)these)numbers)already)form)a)heap.))
b) Carry)out)the)first&two)steps)of)the)heapsort)algorithm)on)these)numbers,)that)
is,) produce) two) numbers) in) the) proper) final) locations) and) restore) the) heap)
property) for) the) remaining) numbers) each) time.) Be) careful) to) show) all) your)
work)in)a)readable)form.)
c) Using)the)same)10)numbers)as)in)the)previous)problem,)show)how)to)insert)
the) number) 20) into) this) heap) as) a) new) entry.) You) must) restore) the) heap)
property)and)show)the)resulting)heap)of)11)numbers.)
Problem 3 [5 marks]
Given an unsorted array. The array has this property that every element in array is at most
k distance from its position in sorted array where k is a positive integer smaller than size
of array. Which sorting algorithm can be easily modified for sorting this array and what is
the obtainable time complexity? Explain your answer.
a)
b)
c)
d)

Insertion sort with time complexity O(kn)


Heap sort with time complexity O(nlogk)
Quicksort with time complexity O(klogk)
Merge sort with time complexity O(klogk)

BINARY SEARCH TREES


Problem 4 [5 marks]
Which of the following is not a binary search tree? Explain why.

Problem(5([15(marks](
The)order)in)which)values)are)inserted)determines)what)BST)is)built)(inserting)the)
same)values)in)different)orders)can)result)in)different)final)BSTs).)Draw)the)BST)that)
results)from)inserting)the)values)1)to)7)in)each)of)the)following)orders)(reading)from)
left)to)right):)
1.
2.
3.

5376214
1234567
4352617

Problem 6 [10 marks]


Given a Binary Search Tree, briefly give a descriptive algorithm to convert it into a MinHeap containing the same elements in O(n) time.

You might also like