#include //... more header as needed

/********* DO NOT CHANGE THESE CONSTANTS IN YOUR FINAL SUBMISSION *********/

#define MAX_SIZE 20 // must be 20 in your final submission #define SUCCESS 0

char order[5]; // global variable, asc or desc

/****************** YOUR CODE STARTS HERE ******************/ /************************************************************/ /* Input: array A with "siz" elements in it and an integer d Output: d is added to the array. Return a non-negative number if the addition is successful. Return a negative number if the addition is unsuccessful. Unsuccessful/Error condition(s): A reaches the MAX_SIZE already. */ int myAdd( int A[], int * siz, int d ) { /* ADD YOUR CODE HERE */ }

/* Input: array A with "siz" elements in it, and an integer d Output: If d is found in the array, return the index of the cell containing d. Otherwise return a negative number if d is not found. Unsuccessful/Error condition(s): d is not found.

note: this must be a 'binary search', and can be either iterative or recursive(i.e., no loops) for recursive, you may need a recursive helper funciton with heading similar to this int myBinarySearch_Recursive_helper( int A[], int d, int start, int end ) */ int myBinarySearch( int A[], int siz, int d ) { /* ADD YOUR CODE HERE */ }

/*

*/

/* Input: array A with "siz" elements in it, and an integer d Output: Return a negative number if d is not found. Otherwise d is removed from the array and return 0. Error condition(s): d does not exist in A. */

int myRemove( int A[], int *siz, int d ) { /* ADD YOUR CODE HERE */ }

/* Input: array A with "siz" elements Output: Display the array on the standard output with one space between every two numbers. Print a new line after the last element. */

void printArray( int A[], int siz ) { int i; printf("[ "); for ( i = 0; i

/* main() function */ int main() { int myArray[MAX_SIZE]; int retCode, data; char action; char a[20];

do{ printf("sort order: ascending (asc) or descending (desc)? "); fgets(order, 10, stdin); } while ( .... ); /******************* YOUR CODE ENDS HERE *******************/ /************************************************************/

/********* DO NOT CHANGE ANYTHING BELOW THIS LINE IN YOUR FINAL SUBMISSION ****/ int size = 0; // local varible do { fgets(a, 20, stdin); sscanf(a, "%c %d", &action, &data ); switch( action ) { case 'a': /* add */ case 'A': retCode = myAdd( myArray, &size, data ); if ( retCode >= SUCCESS ) { printArray( myArray, size ); } else printf( "Failed to add %d. ", data ); break; case 'r': /* remove */ case 'R': retCode = myRemove( myArray, &size, data ); if ( retCode >= SUCCESS ) { printArray( myArray, size ); } else printf( "Failed to remove %d. ", data ); break; case 's': /* search */ case 'S': retCode = myBinarySearch( myArray, size, data ); if( retCode >= 0 ) printf( "Found %d at index %d. ", data, retCode ); else printf( "Not found %d. ", data ); break; case 'q': /* quit */ case 'Q': /* To quit the input, enter an arbitrary integer and character (action) 'q' or 'Q'. This is not elegant but makes the code simpler. */ /* Do nothing but exit the switch statement */ break; default: printf( "Invalid operation %c ", action ); } } while ( action != 'q' && action != 'Q' );

return 0; } // end main

Question 2 Maintaining sorted array arrays, loops, passing pointers, binary search (38 pts) Specification Operate on an array of integers that is initially sorted in ascending or descending order. The array must always be maintained in ascending or decreasing order. The array's capacity is indicated by MAX_SIZE and its current size is indicated by variable 'size'. Implementation Download the partially implemented file sortedArray.c and start from there. The program first prompts the user for the order to maintain the sorted array - either in ascending or descending order. First, complete the do while loop in the beginning of main, so that it keeps on prompting the user for input until either "asc" or "desc" is entered, as shown in the sample output. Given an array arr of integers that is sorted (ascending or descending), and is maintained by its 'size', implement the following functions: - myAdd (arr, *int siz, d) : add an integer d to the array; Parameter siz is an integer pointer that stores the address of size variable defined in main. After adding, the array maintains sorted - ascending or descending as specified by the user at the beginning. Return a number 0 if the operation is successful; return a negative number if the operation is unsuccessful. The adding is unsuccessful if, before insertion, the MAX_SIZE has reached. - myRemove (arr, *int siz, d) : remove integer d from the array; Parameter siz is an integer pointer that stores the address of size variable defined in main. Return a number 0 if the operation is successful; return a negative number otherwise (e.g., d is not found in the array). Assume no duplicate values in the array. After removal, the array remains sorted. - Note that you don't need to remove d from the memory. All you need is to make sure that d is no longer in the valid range of array, and thus does not show in the output of the current 'size' elements. And, all existing elements maintained sorted. - myBinarysearch (arr, int siz, d) : given an integer d, determine if d is in the array arr. Parameter siz is an integer that stores the current size of the array. If d is found in the array, return the index of the cell containing d. Return a negative number otherwise (e.g., d is not found in the array). Assume no duplicate values in the array. - Note that since the array is maintained sorted, instead of using linear search which has complexity O(n), you need to do binary search, which has complexity log(n). You may have learnt binary search in other courses. If not, search the literatures for more 3 information about binary search. A brief introduction is also given at the end of this document. I will also briefly talk about this in recent lecture. You should not use C's library function to do binary search. Write you own binary search. Binary search can be implemented iteratively (using loops) or recursively (using recursion), and you can do it either way. If you implement using recursions, you may want to use a recursive helper function which takes more parameters. Note that these functions need to access and share the current size information of the array, and update the current size information when an element is inserted or deleted from the array. Here for functions myAdd () and myRemove (), we need to pass the address of variable size, whereas for myBinarysearch and printArray, we just pass the size. Think about why. Can we pass size to myAdd () and myRemove (), or pass address of size to mybinarySearch()? Hint: When doing adding and searching, you may want to distinguish ascending and descending order. For removal, depending on your algorithm, bothorders may or may not be able to use the same logic. Sample Inputs/Outputs: Here we assume the MAXSIZE is 5. In your submitted code, the MAXSIZE should be the given value 20 . Also you may want to test more cases. red 307 \& gcc sortedArray.c -o sortA red 308 o sortA sort order: ascending (asc) or descending (desc)? abc sort order: ascending (asc) or descending (desc) ? as sort order: ascending (asc) or descending (desc) ? Asc sort order: ascending (asc) or descending (desc) ? asc a 10 [10 ] a 98 [9810 ] a 5 [98510 ] a 67 [9851067] s 5 Found 5 at index 1 s 10 Found 10 at index 2 a 67 [986751067] a 90 Failed to add 90 r 67 [9867510] r 1 Failed to remove 1 s5 Not found 5 r67 [98510] r 5 [9810] s 5 Not found 5 r 5 Failed to remove 5 r98 4