COP 3530, Discrete Data Structures and Algorithms, Summer 1999, Homework 1 :: UFL Florida Computer Programming Homework

Class Notes: Data Structures and Algorithms Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344 Homework #1 -- Solutions (in blue type) Note: There have been many questions about this homework assignment. Thus, clarifications are posted below in red type. When you answer these questions, bear in mind that each one only counts four points out of 1000 total points for the course. Thus, each one should have a concise answer. No need to write a dissertation. * Question 1. Suppose you want to find the maximum of a sequence or vector a of n distinct integers. Write an algorithm to do this in O(n) time, for any sequence of n distinct integers. max = very large negative number input(a) for i = 1 to n do if a[i] > max then max = a[i] endfor output(max) * Question 2. You could assume that you know the maximum value of a before you search for it. That is, if a has values in the interval [0,101], then the maximum would be 101. The best case (least work) in the preceding algorithm would occur when the maximum of the n-element sequence is the first element of the sequence. Where is the maximum located for the (a) worst case, and (b) average case? Support each answer with a proof, not just an example. Alternatively, you could assume that the maximum was not known beforehand, and a)-b), above might be easier...Either assumption is o.k. o Case 1: Maximum unknown a priori -- You have to search through the entire array to find the maximum. Thus, there is no worst case or best case if you consider the work as comparisons (dominant cost) only. o Case 2: Maximum known a priori -- This becomes a linear search problem (find the maximum).