Help me review for final (Java with Data Structures)

[Tonks Gabriel]

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

[Tonks Gabriel]

Anyone care to contribute?

[Anayonkar Shivalkar]

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!

[Tonks Gabriel]

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

[Anayonkar Shivalkar]

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.

[Campbell Ritchie]

Tonks Gabriel wrote:Anyone care to contribute?

Patience, patience. You may have a long wait; that is a difficult question.
In fact, I think it is too difficult for this forum; it would fir better elsewhere, so I shall move it.

[Tonks Gabriel]

Campbell Ritchie wrote:

Tonks Gabriel wrote:Anyone care to contribute?

Patience, patience. You may have a long wait; that is a difficult question.
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]

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.