Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Programming Assignment — Summer 2022 — CS483

Unbalanced Merge-Sort

You will read the paper by Nardelli and Proietti and implement the algorithm it describes.

It compares its algorithm to another algorithm by Brown and Tarjan. Instead, you will compare the algorithm to the normal Mergesort in the textbook. Do not  focus on the proofs, only the performance.

Efficient Balanced Merge-sort, Information Sciences 176 (2006) 1321-1337 can be found at www.mat.uniroma2.it/~nardelli/publications/InfSci-06.pdf

On page 1134 it describes some inputs used for the empirical comparisons.  In particular the input sequence will be a random permutation of the keys 1, 2, 3, … , n.

Use the standard Fisher-Yates algorithm, see /en.wikipedia.org/wiki/Random_permutation

We will only count key comparisons (not CPU time).

The sorting algorithm has two parts: creating BS-tree and then (p.1333) “The final step will therefore sort Q by means of successive (sorted) merges of the constituting components starting from the smallest ones.” It seems that this final phase converts each tree into an array and leaves the merged arrays as arrays.

NOTE: you should first get the procedure outlined in the proof of Lemma 3.1 working.

WHAT DO YOU DO?

You will code the two algorithms as detailed above.  You will construct various random inputs and run the algorithms on these inputs, and collect averages.

We should be able to run your code on the Mason cluster; use Python, Java, or C++ (or get approval from the TA).

You will then write an analysis of the results  (1 or 2 pages) describing how they agree (or do not agree?) with your expectations, after reading the paper.

You will have tables and/or graphs.

Your code should be sufficiently readable that someone grading it can readily determine how you handled the various unspecified algorithmic details.

NO GROUP WORK PERMITTED. See syllabus.

You may ask any questions of me and the TA— best if during class.

Questions to others must NOT relate to your code or algorithmic details.

Departmental Honor Code guidelines apply.

SUBMISSION:

Submit your files to the TA.

In particular your analysis/summary and the working code.

The TA will decide later if you should submit it on Blackboard or as an email.

Use "CS483 PA" as the subject of your email.