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

Class Notes Data Structures and AlgorithmsSummer-C Semester 1999 - M WRF second Period CSE/E119, Section 7344Home feat 1 -- Solutions (in blue type)Note there contrive been many questions about this homework assignment. Thus, clarifications are posted downstairs in red type. When you answer these questions, bear in mind that all(prenominal)(prenominal) one only counts four points out of 1000 total points for the course. Thus, each one should have a concise answer. No need to spell out a dissertation. * Question 1. Suppose you want to find the maximum of a range or vector a of n pellucid integers. create verbally 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 ai max then max = ai endfor output(max) * Question 2. You could lead that you know the maximum value of a before you search for it. That i s, if a has values in the interval 0,101, then the maximum would be 101. The trump out elusion (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 draw 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).