Algorithm and Analysis(Develop a formula) 2.1: The Average-Behavior analysis of Algorithm 1.1 (Page 36)

makes several simplifying assumptions; in particular, it is assumed that no value shows up in two different places in the array. The formula (shown on Page 37) is much more complex if the elements are not distinct. In this problem, you are asked to analyze one such scenario: For simplicity, assume that n is even. Assume that every element in the n-element array shows up exactly twice (so there are n/2 distinct values, and each value occurs in two separate places in the array). Assume the array is unsorted (so the elements are 'randomly scattered' throughout the array). Develop a formula for A(n), in terms of n and q (based on the definitions of A, n, and q as on Pages 35, 35, and 37)

Note that under the conditions given in this homework problem, the reasoning in the short paragraph on Page 36 only has to be modified slightly for the new worst case analysis; the worst case scenario is almost the same as it wasbefore. You will find that the average case analysis is substantially more difficult to compute under our new circumstances. Note that I'm only asking you to write down the average case analysis -- you do NOT have to write up the worst case analysis.In this last homework problem, the analysis for each of the elements will be similar to every other element, since every element occurs twice. If K is not found, it will take just as long to discover that, but if K is in the array, then it's slightly more likely that it will be found 'earlier' than before, since it occurs in two spots, not just one. Thus, you will have to present a much more complex argument. For example, consider the chance that it will take 3 attempts before the element K is found in the array. For this to happen, we must have something like 1st: not-K 2nd: not-K 3rd: K 4th, 5th, 6th, ..., nth slots: one of these slots contains the other instance of K (since we were told that if K occurs, it occurs twice). So, to determine the likelihood that it will take exactly three 'basic operations' (comparisons) to find K, you need to find out how likely this situation is. To do that, you have to count the ways this could happen, which amounts to counting how you can distribute the second occurrence of K in the remaining n-3 positions. In effect, you have to choose 1 of the n-3 slots to put the other K value in. Similar calculations have to be done when K shows up in the very first slot, and when it shows up for the first time in the second slot, in the fourth slot, etc. Why don't you have to worry about K showing up for the first time in the very last slot? Expect a big, ugly summation with lots of terms. It is fine to leave your answer that way, as long as it is accurate. Often, these ugly expressions can be simplified, leading to a much more elegant (and compact) expression. You can get a little bit of extra credit if you can [correctly] achieve a dramatic simplification of your original ugly sum. (And you may get a LOT of extra credit if only a few people manage to do this.) You may find the problem is incompletely specified. If so, make sure you state your assumptions that led to the formula you developed.

and Examipl 36 Chapter 1 Analyzing Algorithms and Problems: Principles Algorithm 1.1 Sequential Search, Unordered Input: E. 1, K, where E is an array with n entries (indexed O,... ,n- ), and K is the item sought. For simplicity, we assume that K and the entries of E are integers, as is t found). int seqSearch(intl] E, int n, int K) 1. int ans, index 2. ans1; // Assume failure. 3, for (index = 0; index