
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.
-
Work problems 7.2 and 7.3 on page 250 of your textbook.
-
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?
-
Prove that the items cannot be inserted using fewer than 5 comparisons.
-
Either prove that they can be inserted using 5 comparisons, or that
they cannot be inserted using 5 comparisons.

Back to
Course Page