Tonks Gabriel

Greenhorn

Posts: 15

posted 5 years ago

The runtime of the Prim-Jarnik MST algorithm depends on what implementation is chosen for

the priority queue Q. For a graph with n vertices and m edges, what is the asymptotic runtime of

the algorithm if Q is implemented as a binary heap? What asymptotic runtime can be achieved if

Q is implemented using an array? Describe the array-based implementation of all priority queue

operations required by the algorithm. Are there graphs for which the array-based

implementation is asymptotically faster than the binary heap implementation?

Answer: a) O(m log n)

b) O(n^2) via selection sort or insert sort

c & d) do no know

Suppose you must compute the MST for simple undirected graphs G with edge weights of 1 or

2. How fast can you make the Prim-Jarnik MST algorithm for such graphs? Give the

pseudocode of the modified algorithm and describe all data structures needed to support your

algorithm.

Algorithm with Prim-Heaps(G)

1. Make a heap of values(vertex,edge,wt(edge))

2. for I is equal to 1 to |V|-1 do

3. let(v,e,wt(e)) have the smallest weight in the heap

4. add u1 and e to V

5. for each edge e=(v,u1) do

6. if u1 is not already in V

7. find value (u1,f,wt(f)) with (u1,e,wt(e))

8. return E

Using a min-heap each vertex, the smallest edge connecting V with that vertex.

Perform |V|-1 steps in which we remove the smallest element in the heap in which we examine an edge e=(v,u1). For each step, we replace a value on the heap which will reduce its weight. Using a adjacency linked list and min-heap(priority queue) the running time is O(elogv)

True or false, with brief justification.

If f(n) and g(n) are both O(h(n)), then f(n) + g(n) is O(h(n)). true

The worst-case height of a binary search tree is O(log n). false, only if it is balance

A preorder traversal of a heap yields the keys in non-decreasing order. false, pre order traversal visit the root first then to the left child

Running depth-first search on a tree with n vertices takes O(n) time. true, m-1

If e is a minimum-weight edge of a connected undirected graph G, then Kruskal's algorithm will always include e in the MST it constructs. true, you cant create the first cycle without e

the priority queue Q. For a graph with n vertices and m edges, what is the asymptotic runtime of

the algorithm if Q is implemented as a binary heap? What asymptotic runtime can be achieved if

Q is implemented using an array? Describe the array-based implementation of all priority queue

operations required by the algorithm. Are there graphs for which the array-based

implementation is asymptotically faster than the binary heap implementation?

Answer: a) O(m log n)

b) O(n^2) via selection sort or insert sort

c & d) do no know

Suppose you must compute the MST for simple undirected graphs G with edge weights of 1 or

2. How fast can you make the Prim-Jarnik MST algorithm for such graphs? Give the

pseudocode of the modified algorithm and describe all data structures needed to support your

algorithm.

Algorithm with Prim-Heaps(G)

1. Make a heap of values(vertex,edge,wt(edge))

2. for I is equal to 1 to |V|-1 do

3. let(v,e,wt(e)) have the smallest weight in the heap

4. add u1 and e to V

5. for each edge e=(v,u1) do

6. if u1 is not already in V

7. find value (u1,f,wt(f)) with (u1,e,wt(e))

8. return E

Using a min-heap each vertex, the smallest edge connecting V with that vertex.

Perform |V|-1 steps in which we remove the smallest element in the heap in which we examine an edge e=(v,u1). For each step, we replace a value on the heap which will reduce its weight. Using a adjacency linked list and min-heap(priority queue) the running time is O(elogv)

True or false, with brief justification.

If f(n) and g(n) are both O(h(n)), then f(n) + g(n) is O(h(n)). true

The worst-case height of a binary search tree is O(log n). false, only if it is balance

A preorder traversal of a heap yields the keys in non-decreasing order. false, pre order traversal visit the root first then to the left child

Running depth-first search on a tree with n vertices takes O(n) time. true, m-1

If e is a minimum-weight edge of a connected undirected graph G, then Kruskal's algorithm will always include e in the MST it constructs. true, you cant create the first cycle without e

posted 5 years ago

Hi Tonks Gabriel,

Welcome to CodeRanch!

Frankly speaking, I stopped reading after first 10 lines or so.

Please TellTheDetails. What is the problem? Which part did you not understand? I didn't get what is the exact problem here.

Also, please ShowSomeEffort and DoYourOwnHomework. If you get stuck, and you ask proper questions, you'll get help here, but please do not expect to get your homework done here

I hope this helps.

All the best!

Welcome to CodeRanch!

Frankly speaking, I stopped reading after first 10 lines or so.

Please TellTheDetails. What is the problem? Which part did you not understand? I didn't get what is the exact problem here.

Also, please ShowSomeEffort and DoYourOwnHomework. If you get stuck, and you ask proper questions, you'll get help here, but please do not expect to get your homework done here

I hope this helps.

All the best!

Regards,

Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)

Tonks Gabriel

Greenhorn

Posts: 15

posted 5 years ago

I'm sorry if I wasn't clear I want to ask for help on the questions since I do not know how to do them. They are NOT homework questions to be graded it is an sample exam given that the professor didn't give a solution for. I apologize for the misunderstanding. -.- See attachment for proof. Hope that helps

Anayonkar Shivalkar wrote:Hi Tonks Gabriel,

Welcome to CodeRanch!

Frankly speaking, I stopped reading after first 10 lines or so.

Please TellTheDetails. What is the problem? Which part did you not understand? I didn't get what is the exact problem here.

Also, please ShowSomeEffort and DoYourOwnHomework. If you get stuck, and you ask proper questions, you'll get help here, but please do not expect to get your homework done here

I hope this helps.

All the best!

I'm sorry if I wasn't clear I want to ask for help on the questions since I do not know how to do them. They are NOT homework questions to be graded it is an sample exam given that the professor didn't give a solution for. I apologize for the misunderstanding. -.- See attachment for proof. Hope that helps

posted 5 years ago

Well, Tonks, you don't have to give a proof - your word is fine for me This homework policy is simply to discourage people from using this forum for ready-made answers to their homework.

What I'm trying to say is - I'm just not getting what the problem is.

Also, could you provide a little background about what you've tried so far?

After reading about this MST and Prim and Jarnik, it seems more of an algorithmic problem than a Java problem.

What I'm trying to say is - I'm just not getting what the problem is.

Also, could you provide a little background about what you've tried so far?

After reading about this MST and Prim and Jarnik, it seems more of an algorithmic problem than a Java problem.

Regards,

Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)

Campbell Ritchie

Sheriff

Posts: 55351

157

posted 5 years ago

In fact, I think it is too difficult for this forum; it would fir better elsewhere, so I shall move it.

Patience, patience. You may have a long wait; that is a difficult question.Tonks Gabriel wrote:Anyone care to contribute?

In fact, I think it is too difficult for this forum; it would fir better elsewhere, so I shall move it.

Tonks Gabriel

Greenhorn

Posts: 15

posted 5 years ago

That would be great. thanks

Campbell Ritchie wrote:Patience, patience. You may have a long wait; that is a difficult question.Tonks Gabriel wrote:Anyone care to contribute?

In fact, I think it is too difficult for this forum; it would fir better elsewhere, so I shall move it.

That would be great. thanks

Tonks Gabriel

Greenhorn

Posts: 15

posted 5 years ago

I know. I just posted an evidence to let people see I'm not lying, so in case there is someone who can answer it he won't hesitate to help me.

Anayonkar Shivalkar wrote:Well, Tonks, you don't have to give a proof - your word is fine for me This homework policy is simply to discourage people from using this forum for ready-made answers to their homework.

What I'm trying to say is - I'm just not getting what the problem is.

Also, could you provide a little background about what you've tried so far?

After reading about this MST and Prim and Jarnik, it seems more of an algorithmic problem than a Java problem.

I know. I just posted an evidence to let people see I'm not lying, so in case there is someone who can answer it he won't hesitate to help me.