# Test 1 #3 (Version A)

(a) Use pseudocode to describe an algorithm for finding the largest and second largest elements in a list of integers.

procedure largest_and_2nd_largest $(a_1, a_2, \dots, a_n)$
if $a_1 > a_2$
then $max1:=a_1$
$max2:=a_2$
else $max1:=a_2$
$max2:=a_2$
for $i=3$ to $n$
if $a_i > max 1$
then $max2:=max1$
$max1:=a_i$
else if $a_i > max2$
then $max2:=a_i$
return $(max1, max2)$
{$max1$ is the largest element in the list; $max2$ is the second-largest element in the list}

(b) Show each step of your algorithm from (a) when it is applied to the set {1, 6, 4, 2, 5}

Step 1: compare $a_1$ and $a_2$:
Is $a_1=1 > a_2=6$? No, so the initial value of $max1$ is $a_2=6$ and the initial value of $max2$ is $a_1=1$.

Step 2: $i=3$:
Is $a_3= 4 > max1=6$? No.
Is $a_3=4> max2=1$? Yes, so we redefine $max2$ as $a_3=4$.

Step 3: $i=4$:
Is $a_4= 2 > max1=6$? No.
Is $a_4=2> max2=4$? No.

Step 4: $i=5$:
Is $a_5= 5 > max1=6$? No.
Is $a_5=5> max2=4$? Yes, so we redefine $max2$ as $a_5=5$.

The algorithm then returns $(max1, max2) = (a_2=6, a_5=5)$.

(c) Determine the number of comparisons used by your algorithm in (a). Explain your answer. (You may ignore comparisons needed to determine whether the end of a loop has been reached.)

There is one comparison before the loop: $a_1$ versus $a_2$.
There are $n-3+1=n-2$ values of $i$ inside the loop.
Each value of $i$ includes at most two comparisons: $a_i$ versus $max1$ and $a_i$ versus $max2$.
Therefore there are $1 + 2(n-2)= 2n-3$ comparisons overall. (Note that this ignores comparisons needed to determine whether the end of a loop has been reached.)

This entry was posted in Test #1 Solutions. Bookmark the permalink.

### 3 Responses to Test 1 #3 (Version A)

1. Kate Poirier says:

Part (a) was a challenge for many of you. Some of you had algorithms that returned the largest element in the list twice, some of you had algorithms that returned the largest and smallest elements in the list, some of you had algorithms that worked only if all elements were positive. The algorithm above isn’t the only one that works; many of you had correct answers that looked completely different.

As in #2, you’ll want to make to use “return” only once at the end when you’re ready to spit out the outputs.

2. Kate Poirier says:

Part (b) was another tricky question where many of you didn’t appear to look at your answer for (a). Again, the point of (b) was so you could check your answer for (a). Some of you included unexpected notation in your answer for (b) and didn’t state clearly what each of your steps were, so it was hard for me to tell whether what you were doing for (b) actually matched what your algorithm in (a) told you to do or not.

3. Kate Poirier says:

Again, for part (c), many of you looked at your answer for (b) instead of (a) and/or included a big-O estimate for the complexity of your algorithm. Don’t forget to read the question carefully and answer what is asked for.