2. (10 points) Repeats (A[1...n]: integer array) count = 0 number =-00 1 3 ori-1

Question

2. (10 points) Repeats (A[1...n]: integer array) count = 0 number =-00 1 3 ori-1..(n-1) do 4 if Alj--Ali+1 then count-count+1 if number i] then 7 print number number Alij 9 print count Does the algorithm above correctly solve the problem of counting the total number of all integers that repeat consecutively in the input array A correct? (E.g., if A contains 1 2 3 33 4566788881233 then count must be 11)? Answer yes or no. If your answer is yes, provide an explanation (no formal proof is required). If your answer is no, provide a counter example with input, correct answer, algorithm's output and a short explanation of why algorithm's output is different from the correct answer.

Explanation / Answer

Answer is "NO"

Algorithm does not give the right answer : Lets see why ?

A = 1 2 3 3 3 4 5 5 => Correct count should be 5 [3 3's and 2 5's]

=> count = 0 , 1 is not equal to 2 count remains 0
=> count = 0 , 2 is not equal to 3 count remains 0
=> count = 1 , 3 equal to 3 count becomes 1
=> count = 2 , again 3 equal to 3 count becomes 2
=> count = 2 , 3 is not equal to 4 count remains 2

In this way if we see , count will give us 3 at the end which is wrong

Correct Algorithm

Repeat (A[1..n]: Integer Array )

sum = 0
count = 1
for i = 1..(n-1)
   if A[i] = A[i+1]
   count = count +1
   else
   if count != 1
   sum = sum + count
   count = 1


if count != 1 //Out of for loop for last elements, Loop will terminate
sum = sum + count
return sum

Explanation: count is initialised to 1 and sum is initialised to 0 [Our answer will be in sum]
=>
A = 1 2 3 3 3 4 5 5 => Correct count should be 5 [3 3's and 2 5's]

=> sum = 0 , count =1 , 1 is not equal to 2 count remains 1 and sum. = 0
=> count = 1 , 3 equal to 3 count becomes 2 and sum = 0
=> count = 2 , again 3 equal to 3 count becomes 3 , sum =0
=> count = 2 , 3 is not equal to 4 sum becomes 3 because count is not equal to 1 and count is initialised to 1
Then when we get 5 5 , count will be 2 and sum will be 5

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.