Assignment 0

Divide-Conquer

In this warmup assignment, we consider the fundamental problems of searching and sorting in the comparison-based model. In this model, we charge an algorithm one unit cost for every comparison that involves two elements of the input array (this holds even if the array elements has been transferred out of the array). Every other operation is free (has zero cost).

Part I: MINMAX

The task

1. Implement a divide-and-conquer algorithm (using recursion) for the above problem.
   
2. Implement an iterative algorithm (using loop) for the same problem.
   
3. Prepare a plot of the cost (number of comparisons involving array elements) of your two algorithms as a function of the array size. Use a size range of 1 to 1000. On the plot, also superimpose the functions 1.5N-2 and 2N-3 as N varies.

What to Hand-in

1. Source:
   Email a single compressed file by email (zip or tgz). If you use C/C++, please ensure that your program compiles and runs on our AFS polaris.clarkson.edu.
2. Plot:
   Submit a single plot (as PDF or JPG) showing the costs of the recursive versus nonrecursive algorithms.
   (True/False) Your algorithms make no more than 1.5N-2 comparisons on an input array of size N.

Part II: ALL SORTS OF SORTS

The task

1. Provide your own implementations of the following sorting algorithms:
   • Insertion sort
   • Selection sort
   • Merge sort
   • Quicksort (with a fixed pivot)
   • Quicksort (with a median pivot)
     Note: implement the linear-time algorithm for median finding.
   • Heapsort
2. Prepare a single plot that compares the costs of the above sorting algorithms as a function of the array size.
   That is, sort your sorting algorithms based on their costs.

What to Hand-in

1. Source:
   Submit by email your source in a single compressed file (zip or tgz). If you use C/C++, please ensure that your program compiles and runs on our AFS polaris.clarkson.edu.
2. Plot:
   Submit the following two plots (as PDF or JPG).
   1. A plot showing the costs of all sorting algorithms as a function of varying input sizes (from 1 to 128). Rank your sorting algorithms from best to worst. Does this agree with the theoretical analyses? Yes/No.
   2. A plot showing the cost of your median finding algorithm versus the function 10N (where N is the array size). Does this agree with the theoretical analysis? Yes/No.

• For each experiment (search or sort), prepare an integer array A of size N which contains the integers 1 through N (in increasing order). Next, shuffle A randomly and uniformly. Use this to test all the algorithms and record their costs (so it is a fair comparison and easy to verify correctness). Now vary N to range from 1 to a sufficiently large value.
• You may work in groups of up to three people.