See the General Guidelines for homework assignments.

This assignment must be done individually.

For each question below, design an algorithm that satisfies the stated requirements. Express your answer using the pseudocode notation covered in the course notes on Algorithms. Use descriptive names for your variables, and include comments as necessary. Note: if you do not use the pseudo-code notation from the course notes, we will not grade your submission.

1. [50 points] Design an algorithm that will efficiently find the largest difference between any two elements (not necessarily adjacent) in a list of numbers.

# Find maximal list difference.
#
number N                  # variable for list size
list number List          # variable for the list of values
get N                     # N = number of values in the list
get List                  # get values for the list
# This part is up to you; you may use as many variables as you like,
# and whatever seems to you to be the best algorithm (as described in
# the comments above. Note that part of the score will depend on how
# efficient is your solution.

halt                      # done!

2. [50 points] Suppose you are given a list of N values, each of which is either a 0 or a 1, initially arranged in random value. You need to modify the values in the list so that it consists of a sequence of 0s (possibly empty) followed by a sequence of 1s (also possibly empty), with the same number of both as were originally in the list. For example:

      0111010010 -> 0000011111
      1000111000 -> 0000001111
      0000000000 -> 0000000000

Now this problem could be solved by any of the common sorting algorithms, but the special nature of the values in the list makes it possible to devise a particularly efficient solution. (Here, efficiency would refer partly to how many times you need to reset a value in the list, and partly to how many times you would have to change list position variables in
your algorithm.) Design an efficient solution by completing the following algorithm:

# Sort bi-valued list.
#
number N                   # variable for list size
list number List           # variable for the list of values
get N                      # N = number of values in the list
get List                   # get values for the list
# This part is up to you; you may use as many variables as you like,
# and whatever seems to you to be the best algorithm (as described in
# the comments above. Note that part of the score will depend on how
# efficient your solution is.

halt                       # done!