Class Notes: COP3530

Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: Hongyu Guo , Lloyd Noronha, Jagadha Sivan

Homework #1 -- Due Fri 21 May 1999 : 09.30am

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.
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.
Question 3. Given the algorithm you developed in Question 1 including whatever assumptions on which you based your development and analysis for the best, worst, and average cases, what is the computational work requirement W for finding the maximum in the (a) best, (b) worst, and (c) average case? Show your work for each case - it is best to compute W for each step of the algorithm, then sum W over all steps to get the total work requirement W_tot .
Question 4. If you have a sequence of n distinct integers, what is the probability that (a) the maximum of the sequence will occur as the first element of the sequence, or (b) as the last element of the sequence? Show your work, and give an example, using a 5-element sequence.
Question 5. Given a sequence of n distinct integers, what is the probability that the maximum of the sequence will occur as the i-th element of the sequence, where i = 1..n? For Question 6, denote this probability as Pr(max @ i). Show your work, and express the probability as a function of the index i.
Question 6. Taking the result you obtained in Question 5, derive a technique for determining the average probability of occurrence of the maximum of an n-element sequence. Hint: Sum the probability Pr(max @ i) over i = 1..n, then divide the sum by n.
To get credit for Question 6, you must (a) show an example worked out by hand, in detail, for a 5-element sequence; and (b) compare this probability with the probability of the average work requirement W_ave. Hint: You were asked to deduce W_ave in Question 3.

Note: Ask the TAs if you have questions about the homework. You must complete the homework by yourself, but you can work together on general approaches to solving the homework problems. Show your work to get full credit. Any copying will be construed as cheating.