Transcribed TextTranscribed Text

3.20 The notions of 2 0, O can be viewed as binary relations on the set F of (eventually positive) functions f: N R. A (binary) relation R on a set S is any subset of the Cartesian product S x.S. For x, y e S, we say that x is related to y, written xRy, if the ordered pair (x, y) e R. Note that determines a relation on the set F by defining f©g to mean g(n) € ©(f(n)). In a similar way, Qand o determine relations on F. A very important class of relations on a set S are the so-called equivalence relations. Equivalence relations on S correspond precisely to partitions of S into pair-wise disjoint subsets (see Exercise 3.22). Definition A relation R on S is said to be an equivalence relation if the following three properties are satisfied. 1. Reflexive Property: xRx, V € S. 2. Symmetric Property: xRy = yRx, v y € S. 3. Transitive Property: xRy and yRz =xRz, v x, y, Z € S. a) Show that the relation Ois an equivalence relation on F (that is, verify properties (1), (2), and (3) of Proposition 3.1.1). b) Show that relations O and Qare reflexive and transitive but are not symmetric. 4.43 Exercise 4.43. The ChangePriority operation will be necessary later when we use priority queues to implement algorithms like Prim's algorithm for minimum spanning trees and Dijkstra's algorithm for shortest paths. Illustrate your algorithm for the sample min-heap 2 30 17 69 33 23 18 90 77 where the priority of 90 is changed to 1. Another priority queue operation that is sometimes useful is ChangePriority(Q.x.y),whici changes the priority value of an element x in the queue Q to V (and maintains a priority queue). Give pseudocode for ChangePriority when the priority queue is implemented as a min-heap. ChangePriority should have worst-case complexity O(log n), where n is the number of elements in the min-heap.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Problem 2

When the priority of a key is changed, three situations are possible:
- The Min-Heap property is not violated
- The Min-Heap property is violated and the key with the changed priority must be percolated-up for restoring the Min-Heap property.
- The Min-Heap property is violated and the key with the changed value must be percolated-down for restoring the Min-Heap property

In our case we must change the priority of key 90 to 1, so the Min-Heap property is violated and it is needed the new priority to be percolated-up in order to maintain the Min-Heap property.Original value of A[i]> vand the root of the Min-Heap is < the new priority=> the key 1 must become the new root of the Min-Heap.So at each step of the algorithm the parent nodesis moved down one position in the pathand the key 1 is moved one position up in the path.In the end A[0]=1 and that is the final position for the key with the changed priority....

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

for this solution

or FREE if you
register a new account!

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