Project l: Algorithm Design and Time Complexity Analysis for Operations on the D
ID: 3745951 • Letter: P
Question
Project l: Algorithm Design and Time Complexity Analysis for Operations on the Dynamic Array Implementation of the List ADT Due: September 11th, 2018 by 11.59 PM You are given the code for the implementation of the List class using dynamic arrays. The code has been written in such a way that it can calculate the actual run time (in milliseconds) for the two functions (reverseList and segregateEvenOdd) you will be adding to the List class. As mentioned in the code, you will be getting three inputs from the user: (i) the list size (ii) the maximum value for an element in the list and (iii) the number of trials to run your program. The list size is varied from 1000000 to 10000000 (i.e., 0to in increments of 1000000 (i.e., 10). That is, the values for the list size are: 1000000, 2000000, 3000000... 9000000, 10000000. For all values of list size, the maximum value for an element in the list is 5000000 i.e., 5*10) and the number of trials to run the program for each value of list size is 50. The code is structured as follows: After getting the input for the above three variables, the code will create a random array of integers of the specified list size (with values ranging from 1.. maximum value). You will then call the reverseList) function (the code for which is to be implemented by you) on the created integer list and reverse the list. On the reversed integer list, you will call the segregateEvenOdd function and rearrange the values in the list in such a way that it has all the even integers appearing first followed by the odd integers. Each time you run the code (with a particular value of list size), it will run for all the trials and give you the average run time (in milliseconds) for the reverseList and segregateEvenOdd operations on the list. Your algorithms for both reverseList) and segregateEvenOdd) should each run in O(n) time with O(l) additional memory used (i.e., a constant amount of additional memory that is independent of the size of the list). More details about the reverseList) and segregateEvenOdd) functions are as follows: The reverseList() member function for the List class should reverse the contents of the list. For example if the contents of the List are (before reverse): 10 12 5 7 19 21, then after calling the reverseList function, the contents of the List should be updated as: 21 19 7 5 12 10. You should implement the reverseList function without using any additional memory or temporary array that is proportional to the size of the list. Just one temporary variable should be sufficient. void reverseList I The segregateEvenOdd member function for the List class should segregate the contents of the list into a sequence of even integers followed by odd integers. The order of appearance of the even integers (and odd integers) could be different from that in the original list. For example, if the contents of the List are (before segregation into even and odd): 12 34 45 9 8 90 3, then the contents of the List after calling the segregateEvenOdd function could be: 12 34 90 8 9 45 3. Again, you should implement the segregateEvenOdd function by using only O(I) additional memory void segregateEvenOddOExplanation / Answer
1)
// code for the class
class List
{
private:
int *array;
int maxSize;
int endOfArray;
public:
List(int size)
{
maxSize = size;
array = new int[maxSize];
endOfArray = -1;
}
void deleteList()
{
delete[] array;
}
bool isEmpty()
{
return endOfArray==-1;
}
void resize(int s)
{
int *tempArray = array;
array = new int[s];
for(int i = 0;i<min(s,maxSize);i++)
{
array[i] = tempArray[i];
}
maxSize = s;
}
void insertAtIndex(int x,int val)
{
if(x<0||x>endOfArray+1)
x = endOfArray+1;
if(endOfArray==maxSize-1)
resize(2*maxSize);
for(int i = endOfArray;i>=x;i--)
{
array[i+1] = array[i];
}
array[x] = val;
endOfArray++;
}
int read(int i)
{
return array[i];
}
void reverseList()
{
// array elements 0 to endOfArray
// 0 1 2 3 4 5 index 0,5 1,4 2,3 0 1 2 3 4 5 6. 0,6 1,5 2,4 3,3
for(int i = 0;i<=endOfArray/2;i++)
{
//exchange ith and endOfArray - i th element
int temp = array[i];
array[i] = array[endOfArray-i];
array[endOfArray-i] = temp;
}
}
void segregateEvenOdd()
{
int left = 0, right = endOfArray;
while (left < right)
{
/* Increment left index while we see 0 at left */
while (arr[left]%2 == 0 && left < right)
left++;
/* Decrement right index while we see 1 at right */
while (arr[right]%2 == 1 && left < right)
right--;
if (left < right)
{
/* Swap arr[left] and arr[right]*/
int temp = array[left];
array[left] = array[right];
array[right] = temp;
left++;
right--;
}
}
}
void modifyElement(int index,int data)
{
array[index] = data;
}
void deleteElement(int x)
{
for(int i = x;i<endOfArray;i++)
{
array[i] = array[i+1];
}
endOfArray--;
}
int countList()
{
return endOfArray+1;
}
void print()
{
for(int i = 0;i<=endOfArray;i++)
cout<<array[i]<<" ";
cout<<endl;
}
};
2) reverseList()
if given list is a[0]....a[n] we have to return a[n]....a[0]
so it is enough to swap a[i] and a[n-i] once i.e upto halfmark
e.g if list is 2,5,7,8,9,11,13
our program proceeds this way
swap(2,13)
swap(5,11)
swap(7,9)
swap(8,8)
end
Algorithm: segregateEvenOdd()
1) Initialize two index variables left and right:
left = 0, right = endOfArray
2) Keep incrementing left index until we see an odd number.
3) Keep decrementing right index until we see an even number.
4) If lef < right then swap arr[left] and arr[right]
In this way we send all the left numbers to the right and all right to the left
3)reverseList()
if size = n
we do n/2 swaps and each swap takes constant time
T(n) = n/2*O(1) = O(n)
segregate left and right
initially left = 0 and right = n-1
algo would stop at left = n/2
and for each left and right operations you may perform are incrementing them or swapping left,right element each of em are constant operations
T(n) = n/2*O(1) = O(n)
4)in reverselist only extra variables we have used are i,temp i.e 2 => O(1) extra space
in segregation only extra variables we used are left right and temp i.e 3 => O(1) extra space
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.