aspose file tools*
The moose likes General Computing and the fly likes Help me review for final (Java with Data Structures) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Engineering » General Computing
Bookmark "Help me review for final (Java with Data Structures)" Watch "Help me review for final (Java with Data Structures)" New topic
Author

Help me review for final (Java with Data Structures)

Tonks Gabriel
Greenhorn

Joined: Feb 23, 2012
Posts: 15
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
Greenhorn

Joined: Feb 23, 2012
Posts: 15
Anyone care to contribute?
Anayonkar Shivalkar
Bartender

Joined: Dec 08, 2010
Posts: 1456
    
    5

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!


Regards,
Anayonkar Shivalkar (SCJP, SCWCD, OCMJD, OCEEJBD)
Tonks Gabriel
Greenhorn

Joined: Feb 23, 2012
Posts: 15
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





[Thumbnail for SampleFinal2.png]

[Thumbnail for SampleFinal1.png]

Anayonkar Shivalkar
Bartender

Joined: Dec 08, 2010
Posts: 1456
    
    5

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
Sheriff

Joined: Oct 13, 2005
Posts: 36478
    
  16
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
Greenhorn

Joined: Feb 23, 2012
Posts: 15
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
Greenhorn

Joined: Feb 23, 2012
Posts: 15
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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Help me review for final (Java with Data Structures)
 
Similar Threads
July Newsletter Puzzle (Maze Solver)
Undirected graph help - using ArrayLists and Maps.
"Position" Concept as it applies to Data Structures
Big O notation & Recursion
How to detect circle in a directed graph?