HW 1: Algorithm Design

Bart Massey

Deadline

Due Thursday 17 April 2014 before class.

Description

Consider a sequence a of n non-negative integers. We will reverse subsequences of this array in some order, with the end goal being to sort the sequence in nondecreasing order.

For example, given the sequence

        2 5 0 6 0

we might proceed

        2 6 0 5 0
        2 6 5 0 0
        0 0 5 6 2
        0 0 2 6 5
        0 0 2 5 6

There are, of course, shorter ways.

Problems

1. Write down a formal definition of this problem (call it "SUBSEQUENCE REVERSAL SORTING") in the style shown in class and in the text.
2. Give an algorithm that solves this problem. It need not be efficient, but should be guaranteed to complete in all cases.
3. What is the asymptotic worst-case complexity of your algorithm?
4. Can you find an algorithm requiring at most O(n) reversals? At most O(n lg n) reversed elements? [Optional]

Format

Your writeup may be in plain text. It is preferable to produce PDF or HTML. Try to make your writeup clear and readable. Document formats such as Word or OpenOffice are unacceptable. LaTeX is awesome, and you should learn how to use it anyhow, so PDF produced from that is best of all.

Submission

Submissions need to be done in crossgrade.