University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page

CSC 715 Assignment 2
Due date: Thursday, February 14, 2008, 11:30 AM.
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me on or before the due date.
-
Work Problem 4-7 a., c. on page 88 of your textbook.
Part d. gives an O(m + n log m) time algorithm for finding all row
minima of an m by n Monge matrix.
Try to find an O(m + n) time algorithm for the same problem.
-
Work Problem 15-2 on page 364 of your textbook.
There are different solutions to this problem, of increasing difficulty
and decreasing time complexity:
-
A simple O(n2)-time algorithm.
-
A very difficult O(n log n)-time algorithm.
-
An O(n)-time algorithm.
-
Work Problem 15-3 on page 364 of your textbook.
Despite the length of the description in the textbook, this problem
is easier than 15-2.

Back to
Course Page