CSE 101 Assignment 3
Due date, July 17, 2003, 9: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 or to the graduate assistant at the beginning of class
on the due date.
There will be a 10% penalty if the homework is turned in during office hours
on the due date. Homework turned in later than that will not be accepted.
-
Starting with the array UNSORTED, show the array after every
exchange of heapsort. The final array will be DENORSTU.
-
A traveller must walk from A to his home at B, along a road of length
m miles.
There are n inns on the road.
The ith inn is di miles
from A and costs ci to stay at.
The traveller can walk at most w miles per day.
How can he get home at minimum cost, if he must stay at an inn every
night until he gets to B?
-
Design a dynamic programming algorithm that answers this question, given
the arrays c and d as inputs.
Give pseudocode for your algorithm, and estimate the time complexity,
in terms of n.
-
Walk through the algorithm, showing all work, for the example given
here.
Back to
Course Page