Test 1 #2 (Version A)

Posted on March 27, 2016 by Kate Poirier

(a) Use pseudocode to describe an algorithm that takes a list of n integers \{a_1, a_2, \dots, a_n\} and finds the number of integers greater than 5 in the list.

procedure greater_than_5(a_1, a_2, \dots, a_n\: integers)
count:=0
for i=1 to n
    if a_i > 5
    then count := count + 1
return count

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

Step 1, i=1:
Is a_1=1 > 5? No, so count stays at 0.

Step 2, i=2:
Is a_2=5 > 5? Yes, so count is redefined as 0+1=1.

Step 3, i=3:
Is a_3=4 > 5? No, so count stays at 1.

Step 4, i=4:
Is a_4=2 > 5? No, so count stays at 1.

Step 5, i=5:
Is a_5=5 > 5? No, so count stays at 1.

Therefore algorithm returns count = 1.

(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.)

The algorithm in (a) has a loop which uses n values of i. Each value of i gives one comparison: a_i versus 5. Since there are no comparisons outside the loop, the algorithm uses n comparisons. (Notice 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 #2 (Version A)

  1. Kate Poirier says:
    March 27, 2016 at 4:50 pm

    For the most part, part (a) was either completely correct or completely incorrect. A few of you missed that the output was supposed to be a count…not a location and not a list. Keep in mind that when you say “return” you’re saying what the output of the algorithm is…so it stops there. A few of you had “return” written as part of your loop; this exits the loop so your algorithm didn’t get a chance to examine all of the elements on the list before it stopped and returned an output.

    Reply
  2. Kate Poirier says:
    March 27, 2016 at 4:52 pm

    For part (b), I tried my best to analyze whether you had applied your algorithm in part (a) correctly, even if your answer for (a) was not correct. It looked like, for some of you, you didn’t look at your answer for (a) when you were answering (b), so there was a mis-match. The point of asking you (b) was really to get you to test whether your algorithm in (a) worked. Keep in mind, whenever you’re writing an algorithm like the one you wrote for (a), you can test it on a small set of inputs to see if it does what you want it to do, even if you’re not asked explicitly to do so.

    Reply
  3. Kate Poirier says:
    March 27, 2016 at 4:55 pm

    The biggest issue with part (c) was that some of you appeared to look at your answer for (b), when (c) was asking about your algorithm in (a). This was probably just an oversight, so make sure you always read test questions slowly and carefully so that you’re actually answering the question that’s being asked.

    A few of you included a big-O estimate for the complexity of your algorithm as well, even though it wasn’t asked for, so it was hard to see if you really knew what you were doing. In general, ask the question that is asked, not a related question.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *