1) Write down a pseudo code for deleteMax(p) of a max heap. Prove that the heap satisfies the heap property when your algorithm terminates. Also show that it runs in O(log n) time where n is the current number of elements in the heap.

2) We are given a communication network that is an edge-weighted graph G=(V, E). The weight on each edge is at least 0 and at most 1, representing the reliability of the communication channel: it is the probability that the communication between the two endpoints will not fail. Design an O(|E|log|E|) time algorithm to find the most reliable path between two given nodes. Describe its pseudo code, correctness proof and running time proof.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

Problem 1
As explained in the lecture, in order to deleteMax element, we first replace the max (which resides in the root since the original data structure is a Max Heap) with the element from the last position, namely p[n]. Then we remove the max element from the heap and decrease the size n by 1. In order to make sure the remaining data structure preserves the heap property, we repeatedly call the heap_property procedure to arrange the remaining elements. Practically, at each call, if the swapped element is larger than both its children, the algorithm stops. Otherwise we swap it with the largest child. The procedure continues until the former p[n] element either becomes a leaf node or more swaps with one of its children is necessary. In pseudo-code, this can be written as below:...

By purchasing this solution you'll be able to access the following files:

for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats