CSC 477/677 Assignment 5

Due date, October 17, 2002, 5:30 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper. Write your name on each sheet, and do not fold the pages or crimp the corners. Turn the pages in to me or to the graduate assistant on the due date.


In this class, if I ask you to "design an algorithm" I do not mean for you to write code in any computer language. Your algorithm description should be handwritten (not typed or printed from a computer file) and need not even be written in pseudocode.
  1. Work problems 7.2 and 7.3 on page 250 of your textbook.
  2. You are given a sorted list of 4 items, and two additional items that must be inserted into the list in sorted order. You can easily perform this task using 6 comparisons, inserting them one at a time. But, are 6 comparisons necessary?
    1. Prove that the items cannot be inserted using fewer than 5 comparisons.
    2. Either prove that they can be inserted using 5 comparisons, or that they cannot be inserted using 5 comparisons.

Back to Course Page