Homework Answers
In Dijkstra algorithm, the time complexity is always computed as the function value of :
( ( Number of vertices ) * ( Number of extractMin operations ) ) + ( ( Number of edges ) * ( Number of insert or decrease operations ) ) .
Given,
The number of vertices in the graph = Size of the heap = n
Let, the number of edges be E.
In fibonacci heap,
It takes Ѳ ( log n ) time to perform an extractMin operation
It takes Ѳ (1) time to do an insert or decrease operation.
So, the total time complexity of Dijkstra algorithm = Ѳ ( n*log n + E ).
a)
If a graph is dense, then the maximum number of edges is ( n*(n-1)/2 ) which in asymptotic notation is Ѳ ( n ^2 ).
So, in a dense graph, the number of edges E = Ѳ ( n ^2 ).
The asymptotic time complexity of Dijkstra algorithm in a dense graph is = Ѳ ( n*log n + E )
= Ѳ ( n*log n + ( n^2) )
= Ѳ ( n^2 ).
Thus, the asymptotic time complexity of Dijkstra algorithm iin a dense graph s Ѳ ( n^2 ).
b)
In a sparse graph, the number of edges E = Ѳ ( n ).
The asymptotic time complexity of Dijkstra algorithm in a sparse graph is = Ѳ ( n*log n + E )
= Ѳ ( n*log n + n )
= Ѳ ( n*log n ).
Thus, the asymptotic time complexity of Dijkstra algorithm in a sparse graph is Ѳ ( n*log n ).
Add Answer to:
please justify.
A Fibonacci heap is a fancy priority queue data structure. For a heap of...
In prim’s algorithm, if a graph G(V,E) is represented by its adjacency list and the priority...
In prim’s algorithm, if a graph G(V,E) is represented by its adjacency list and the priority queue is implemented using min-heap data structure, find the time complexity of the algorithm using big-oh asymptotic notation. Justify your answer in detail how you get the time complexity
Please be sure to justify the running times you claim using what you know about the...
Please be sure to justify the running times you claim using what you know about the cost of Dijkstra’s algorithm and the meaning of dense and sparse graphs. We know that our input graph G = (V,E) is sparse. What is the asymptotic running time in terms of |V|?
I need help writing java code for the Binary Heap Priority Queue assignment. Task: // Deletes all...
I need help writing java code for the Binary Heap Priority Queue assignment. Task: // Deletes all instances of the parameter obj from the PQ if found, and returns true. Returns false if no match to the parameter obj is found. public boolean delete(E obj); // provided ADT How can I write this in O(logn)? assuming you are using Sink/Swim (insert/remove) operations Additional info: Each method must be as efficient as possible. That is, an O(n) is unacceptable if the...
In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the...
In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the element of the heap with the smallest key is the root of the binary tree. On the other hand, a max-heap has as root the element with the biggest key, and the relationship between the keys of a node and its parent is reversed of that of a min-heap. We also discussed an array-based implementation of heaps. In this assignment, your task is to...
Computer Algorithm question 8) Give an algorithm for building a heap in O(n) 9) Prove the...
Computer Algorithm question
8) Give an algorithm for building a heap in O(n)
9) Prove the algorithm given in 8) runs in O(n) time.
10) What is the asymptotic runtime of an algorithm represented
by the following recurrence equation?
11) Suppose you have the following priority queue implemented as a (max) heap. What will the heap look like when the max node is removed and the heap is readjusted? Assume on each heapify operation the largest child node is selected...
Write a program in Java to implement the max-priority queue using max-heap data structure. Implement the...
Write a program in Java to implement the max-priority queue using max-heap data structure. Implement the max-heap data structure using an integer array of 10 cells. (Do not use Java in-built PriorityQueue class.) [In a max-heap, the root node and the intermediate node vales are always greater than their children.] First, take 10 integer values from the user and insert them in the max-priority queue. Then print the elements of the queue. After that, delete two elements from the queue...
Professor Strongmind has developed a hardware priority queue device for his computer. This de- vice can...
Professor Strongmind has developed a hardware priority queue device for his computer. This de- vice can store up to p records, each containing a key and a small amount of satellite data (such as a pointer). With this device, INSERT and EXTRACT-MIN operations on the priority queue can be performed in O(1) worst-case time each, as long as the records are stored in the device. Your task is to develop a sorting algorithm using the device. Suppose there are n...
Using C++, data structures, C++ STL, inputs and expected outputs are shown below. Max Heap Heap...
Using C++, data structures, C++ STL, inputs and expected
outputs are shown below.
Max Heap Heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either > (in a max heap) or s (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node. In binary-tree based heap, it...
Provide an O(k log k) algorithm that uses a heap data structure to find the kth...
Provide an O(k log k) algorithm that uses a heap data structure to find the kth largest element from the heap of n elements where n > k. Sketch your algorithm. (Hint: You may need to use an additional heap) Use the example data below to demonstrate the process. (e.g. Find the 7 largest element from this heap and it should be 45) Justify the running time. Heap H 100 80 70 40 50 65 60 20 40 10 30...
5. A three-heap with n elements can be stored in an array A, where A[O] contains...
5. A three-heap with n elements can be stored in an array A, where A[O] contains the root of the tree. a) Draw the three-heap that results from inserting 5, 2, 8, 3, 6, 4, 9, 7, 1 in that order into an initially empty three-heap. You do not need to show the array representation of the heap. You are only required to show the final tree, although if you draw intermediate trees. b) Assuming that elements are placed in...
In class, we discussed the priority queue (PQ) ADT implemented using min-heap. In a min-heap, the element of the heap with the smallest key is the root of the binary tree. On the other hand, a max-heap has as root the element with the biggest key, and the relationship between the keys of a node and its parent is reversed of that of a min-heap. We also discussed an array-based implementation of heaps. In this assignment, your task is to...
Computer Algorithm question
8) Give an algorithm for building a heap in O(n)
9) Prove the algorithm given in 8) runs in O(n) time.
10) What is the asymptotic runtime of an algorithm represented
by the following recurrence equation?
11) Suppose you have the following priority queue implemented as a (max) heap. What will the heap look like when the max node is removed and the heap is readjusted? Assume on each heapify operation the largest child node is selected...
Professor Strongmind has developed a hardware priority queue device for his computer. This de- vice can store up to p records, each containing a key and a small amount of satellite data (such as a pointer). With this device, INSERT and EXTRACT-MIN operations on the priority queue can be performed in O(1) worst-case time each, as long as the records are stored in the device. Your task is to develop a sorting algorithm using the device. Suppose there are n...
Using C++, data structures, C++ STL, inputs and expected
outputs are shown below.
Max Heap Heap is a specialized tree-based data structure that satisfies the heap property: if P is a parent node of C, then the key (the value) of P is either > (in a max heap) or s (in a min heap) the key of C. The node at the "top" of the heap (with no parents) is called the root node. In binary-tree based heap, it...
Provide an O(k log k) algorithm that uses a heap data structure to find the kth largest element from the heap of n elements where n > k. Sketch your algorithm. (Hint: You may need to use an additional heap) Use the example data below to demonstrate the process. (e.g. Find the 7 largest element from this heap and it should be 45) Justify the running time. Heap H 100 80 70 40 50 65 60 20 40 10 30...
5. A three-heap with n elements can be stored in an array A, where A[O] contains the root of the tree. a) Draw the three-heap that results from inserting 5, 2, 8, 3, 6, 4, 9, 7, 1 in that order into an initially empty three-heap. You do not need to show the array representation of the heap. You are only required to show the final tree, although if you draw intermediate trees. b) Assuming that elements are placed in...
Most questions answered within 3 hours.
-
A chemical equation is balanced by adding coefficients in front
of some formulas so that the...
asked 1 minute from now -
From the literature (reference your sources): What are the
lattice parameters of calcite and aragonite? Why...
asked 38 minutes ago -
Your system is rejecting the question am asking which is
preceded by a case study. It...
asked 43 minutes ago -
3. On January 2, 2000, Larry creates a trust with himself as
trustee. Larry as trustee...
asked 40 minutes ago -
A member of the volleyball team spikes the ball. During this
process, she changes the velocity...
asked 47 minutes ago -
Are adult gamers less likely to use a gaming console (Xbox,
PlayStation, Wii, etc...) than teen...
asked 1 hour ago -
The University of
Texas recently reported that 43% of college students aged 18-24
would spend their...
asked 1 hour ago -
The length of stay at a specific emergency department in
Phoenix, Arizona, in 2009 had a...
asked 1 hour ago -
. Please give the mechanism for this type of problem. Step by
Step
The toxin that...
asked 1 hour ago -
If you have a 1M stock solution and you want to dilute 1 :10
with water,...
asked 1 hour ago -
In a load instruction, the effective address is obtained by
A) Retriving the address from a...
asked 1 hour ago -
Use the following information to answer this question.
Windswept, Inc. 2017 Income Statement ($ in millions)...
asked 1 hour ago