Algorithm design. We have inherited a data structure for storing non-negative in

Question

Algorithm design. We have inherited a data structure for storing non-negative integers in an array. The array has been pre-allocated and is of size M. However, we don’t always actually use all M slots – the number of elements stored is some N < M.

The original author of the code decided to not explicitly keep track of N, but instead used a “sentinel” approach: all values being stored are in indices [0..N-1] and after that the array is filled with negative 1 (-1 indicating “nothing here”). (Note that N is strictly less than M).

This way if we are searching for something, we know when to stop.
Your job: devise an algorithm which takes such an array and determines N in O(logN) time. Write your algorithm as a C function. Assume that M is a given constant.
Argue the correctness of your algorithm and why it achieves the specified runtime.
NOTE: Partial credit for an O(logM) time algorithm, but in general, a solution that is

O(logM) is not necessarily O(logN)

Explanation / Answer

#include<stdio.h>
#include<conio.h>

void ar()
{
   int a[10]={1,4,7,2,3};
   int i,c=0;

   for(i=0;i<10;i++)
   {
   if(a[i]>0)
   {
       c++;
   }
   else
   {
       a[i]=-1;
   }
   }

   printf("Value of N is %d",c);
   getch();
}

void main()
{
   clrscr();
   ar();
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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