## Transcribed 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.

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....