Assignment 0

A Tale of Two Problems

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 or sequence (this holds even if the array elements has been transferred out of the array). Every other operation is free (has zero cost).

Part I: EXTREMA SEARCHING

The task

1. Implement a divide-and-conquer algorithm (using recursion) for the above problem.
   Your algorithm should make no more than 1.5N-2 comparisons on an input array of size N.

2. Implement an iterative algorithm (using loop) for the same problem.
   Your algorithm should make no more than 1.5N-2 comparisons on an input array of size N.

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). Your code should compile and run (under Linux) on the AFS polaris1.clarkson.edu system.
2. Plot:
   Submit a single plot (as PDF or JPG) showing the costs of the recursive versus nonrecursive algorithms.

Part II: SORT THE SORTS

The task

1. Provide your own implementations of the following sorting algorithms:
   1. Insertion sort
   2. Selection sort
   3. Merge sort
   4. Quicksort (with a fixed pivot)
   5. Quicksort (with a median pivot).
      For this quicksort, provide an implementation of the linear-time algorithm for median finding.
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). Your program should compile and run on the AFS polaris1.clarkson.edu system.
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.

• You may work in groups of up to three people.
• The following is a template for testing the sorts (in C++).