Computer Algorithms design & analysis: 2 works : 48 hours
paigelamb
module_6-homework.rtfCIS 330: Algorithm Design and Analysis 2
Running head: Algorithm Design and Analysis, Module 6, 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.
Short programming assignment. Implement the binary quicksort where Item is an integer in the range 0 - 32,767 (that is, fifteen bits). You will need to write a digit function to extract a particular bit from an integer. Test your function on an array of randomly generated integers.
- Consider the following sorting scenarios. Which is more appropriate for a radix sort, and why?
- An input file with 100 records. The records are to be sorted on a 256-bit key.
An input file with 10000 records. The records are to be sorted on a 16-bit key.
- The following refers to the perfect shuffle and unshuffle operations.
- Perform a perfect shuffle on the following: F G T E A H I W A B T D K U Q Z
Perform a perfect unshuffle on the following: J E Y B D A H I Y K E Q B T S L
- Explain how Batcher’s odd-even merge actually merges two subfiles while only exchanging adjacent locations in the array.
- Design a sorting network for a file of five elements. Demonstrate, in the manner of figure 11.4, that your network would correctly sort a file starting in reverse order such as E D C B A.
- Show in the style of figure 11.12 a 4-way balanced merge sort on the following file, with initial sort size of 3. A S O R T I N G P R O B L EM W I T H E N O U G H K E Y S
- How many parallel steps (as defined in property 11.8) would be required to sort 100,000 records using 32 processors?
- For the following set of numbers, perform both a MSD and LSD radix sort. Show the resulting column of numbers after each pass (each digit).
1143
7788
8478
6352
6323
6478
1253
2235
2834
4443
