Computer Algorithms design & analysis: 2 works : 48 hours
paigelamb
module_5-homework.rtfCIS 330: Algorithm Design and Analysis 1
Running head: Algorithm Design and Analysis, Module 5, Homework
Directions: Please complete each of the following exercises. Please read the instructions carefully.
For all “short programming assignments,” include source code files in your submission.
- The following refer to mergesort.
- Show, in the manner of figure 8.2, how top-down mergesort would sort S O R T M E.
Show, in the manner of figure 8.4, how bottom-up mergesort would sort S O R T M E.
Short programming assignment. Implement a bottom-up mergesort that first sorts blocks of M elements using insertion sort. Test your program with large sets of random data and determine what value of M works best.
- The following refer to linked list mergesort.
- Explain why mergesort is more suitable for linked lists than other sorting methods.
Consider a file that is “mostly sorted.” Explain how the principles of linked-list merge could be used to quickly produce a sorted file.
- For each of the following priority-queue operations, give a implementation in which the operation is optimal (that is, O(1)), and an implementation in which the operation is worst-case (that is, O(N)). Briefly explain how the operation is performed under the implementation you have chosen.
- Insert
Remove maximum
Change priority
Join
- Explain how the insert and getmax heap operations use the fixUp and fixDown functions.
Short programming assignment. Implement heapsort. For variously-sized arrays of random integers, determine what percentage of the total sort time is spent in the heap-building phase. Construct a table showing the results.
- Programs 9.9 and 9.10 implement a priority queue using a doubly-linked list, with dummy head and tail nodes. Discuss the effect each of the following changes would have on priority queue operations (that is, list the operations that would be affected, and explain the performance effect).
- Using a singly-linked list instead of a doubly-linked list
Not using dummy nodes
Not maintaining a tail pointer.
- Complete each of the following. You should have four drawings, one for each part of the question; do not simply give the queue that results after step d.
- Construct the binomial queue that results from inserting the keys H A L T into an initially empty binomial queue.
Construct the binomial queue that results from inserting the keys O M N I B U S into an initially empty binomial queue.
Execute the remove the maximum operation from the queue of part b.
Join the queues of parts a and c.
- Consider the two power-of-2 heaps shown below. Join the two heaps into one and show the resulting heap.
