CSCI 362 — Lab 7a

Divide and Conquer (and Combine) Algorithms

Due: July 3, 2019 @ 11:59PM

Handout

Grab the handout tarfile from here: http://cs.millersville.edu/~wkillian/2019/summer/files/csci362/lab7a-divide-and-conquer.tar

Overview

You've been tasked with implementing a few divide, conquer, and combine algorithms! Some are also just useful utilities in solving more complex problems.

Algorithms

Note: when you call a function, please be sure to use its fully qualified name from SortUtils. For example, nth_element will call partition. You will want to say SortUtils::partition rather than just partition.

Required Functions

namespace SortUtils
{

// Given a RandomAccessRange [first, last), determine where the "midpoint"
// would be and perform the following steps:
// order *first, *mid, *std::prev(last) in such a way such that
//   *first <= *mid <= *std::prev(last)
//
// returns an iterator to mid -- a.k.a. the median
//
template<typename Iter, Requires (concepts::RandomAccessIterator, Iter)>
Iter
median3 (Iter first, Iter last);

// Takes two sorted ranges [first1, last1) and [first2, last2)
// and "merges" them by copying values into the iterator starting
// at "out". Uses operator< for comparing values
//
// Returns the iterator of one-past-the-last where we wrote to out
//
template<typename Iter1, typename Iter2, typename OIter,
         Requires (concepts::ForwardIterator, Iter1),
         Requires (concepts::ForwardIterator, Iter2),
         Requires (concepts::ForwardIterator, OIter)>
OIter
merge (Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2, OIter out);

// Takes a RandomAccessRange [first, last) and partitions the data into
// three groups -- this should be accomplished in a SINGLE PASS Big-O: O(N)
//
// Group 1: all values in [first, last) < pivot
// Group 2: all values in [first, last) == pivot
// Group 3: all values in [first, last) > pivot
//
// [ ... Group 1 ... | ... Group 2 ... | ... Group 3 ... ]
//                   ^                 ^
//                   p1                p2
//
// Returns a pair of iterators pointing to "p1" and "p2" above
//
template<typename Iter, typename Value,
         Requires (concepts::RandomAccessIterator, Iter)>
std::pair<Iter, Iter>
partition (Iter first, Iter last, Value const& pivot);

// Given a RandomAccessRange, recursively call partition on either the
// left half or right half until you have found the nth largest element
//
// A call to nth_element (v.begin(), v.end(), 0) will return the min
// A call to nth_element (v.begin(), v.end(), v.size() - 1) will return the max
// A call to nth_element (v.begin(), v.end(), v.size() / 2) will return the median
//
// Precondition:
//   std::distance (begin, end) > n
//
// Hints:
//  - n will change if you need to recurse on the right half
//  - No recursion happens if "index of" n is between "index of" p1 and p2
//    remember: p1 and p2 are the return values to partition.
//  - call median3 to get a pivot value
//  - when calling partition, remember to dereference the iterator returns by median3
//
template<typename Iter, Requires (concepts::RandomAccessIterator, Iter)>
Iter
nth_element (Iter first, Iter last, size_t n);

// Finds an approximate median value (recursively) of the range [first, last)
//
// Divide-and-conquer until there are <= 5 values in a range, then
// sorts the small range (hint: use insertion sort).
//
// Build this from the pseudocode we went over in class.
// NOTE: this is probably the most difficult problem due to
//       the requirement of using iterators and no extra space
//
// Hint: you will want to call "chunk" and "insertion_sort"
template<typename Iter, Requires (concepts::RandomAccessIterator, Iter)>
Iter
median5 (Iter first, Iter last);

} // end namespace SortUtils

Running the autograder

Invoking make should create the autograder.

There can be a lot of output shown from the autograder. Some of it could be overwhelming at times. I recommend adding a couple of arguments to the autograder to help ease the pain.

./autograder -a

Will run the autograder and stop as soon as the first FAILURE is found

./autograder -t

Will list all of the tags for each of the tests. If you want to run a specific subset of tags you can do so by stating the following:

./autograder [access],[iterator]

Will run all tests that have the access and iterator tags

./autograder --failed

Will list all failed tests at the end of the autograder output

./autograder --passed

Will list all passed tests at the end of the autograder output

Style

Use good programming style:

Submission

Since this consists of multiple files, a tarball will be required for submission.

invoking make handin should create handin.tar

Please submit handin.tar to autolab

Grading

This lab is graded out of 75 points.