SOLVED ECE36800 Programming Assignment #1

This assignment covers learning objective 1: An understanding of basic data structures, including stacks, queues, and trees; learning objective 3: An ability to apply appropriate sorting and search algorithms for a given application. This assignment is to be completed on your own. You will implement Shell sort on an array and Shell sort on a linked list. In both cases, you will use the following sequence for Shell sort: {1,2,3,4,6,...,2 p 3 q ,...}, where every integer in the sequence is of the form 2p3 q and is smaller than the size of the array to be sorted. Note that most of the integers in this sequence, except perhaps for some, can always be used to form a triangle, as shown in Lecture slides on insertion sort and Shell sort. There may be incomplete rows of integers in the sequence below the triangle. For example, if there are 15 integers to be sorted, the corresponding sequence {1,2,3,4,6,9,8,12} would be organized as follows, with an incomplete row containing the integers 8 and 12 in the sequence: 1 2 3 4 6 9 8 12 You are not allowed to pre-compute the sequence and store them in your program. The sequence has to be generated as part of your Shell sort functions. Moreover, you have to generate the sequence such that the numbers in the sequence are sorted. For the sequence generated for sorting 15 numbers, the sorted sequence is {1,2,3,4,6,8,9,12}. Your Shell sort will perform 12-sorting, 9-sorting, 8-sorting, ..., 2-sorting, and 1-sorting. Functions to be written We provide you three .h files: sequence.h, shell array.h, and shell list.h. You will develop the functions declared in these .h files in the corresponding .c files: sequence.c, shell array.c, and shell list.c. These .c files and pa1.c are the only files you will submit for this assignment. For this assignment, you are not allowed to define additional structures (struct). If your submission contains additional structures, your submission will receive a grade of 0. You are also not allowed to use mathematical functions declared in math.h and defined in the math library. If your submission includes math.h or calls math functions declared in math.h and defined in the math library, your submission will receive a grade of 0. ECE36800   However, you are allowed to define additional helper functions. These helper functions should be declared as static so that the scope of each helper function stays within that of the .c file that contains the helper function. Do not modify the provided .h files because you are not submitting them. Any modifications you have made to the provided .h will not be reflected in the .h files that we use to evaluate your submission. Function you will write for sequence.c: long *Generate 2p3q Seq(int n, int *seq size) Here, n is the number of long integers to be sorted. You should determine the number of elements in the sequence and store that number in *seq size. For example, if n is 0 or 1, the sequence should contain 0 elements. Therefore, *seq size should store 0. For n = 16, the sequence should contain 8 elements. Therefore, *seq size should store 8. The function should allocate space to store the elements of the sequence as long integers. Even when the sequence is empty, you should allocate a space of 0 elements. Moreover, these elements must be stored in ascending order. The address of the long array is returned. If malloc fails, you should return NULL and store 0 in *seq size. This function will be called by the Array Shellsort and List Shellsort functions. It is important that the caller function, e.g., Array Shellsort or List Shellsort function, has an integer variable to store the size of the sequence, and pass the address of this variable into long *Generate 2p3q Seq(int n, int *seq size) using the seq size parameter. Any helper functions for Generate 2p3q Seq, if any, must reside in sequence.c. These helper functions should be declared as static. Functions you will write for shell array.c: There are three functions that deal with performing Shell sort on an array. The first two functions Array Load From File and Array Save To File, are not for sorting, but are needed to transfer the long integers to be sorted from and to a file in binary form to and from an array, respectively. long *Array Load From File(char *filename, int *size) The size of the binary file whose name is stored in the char array pointed to by filename should determine the number of long integers in the file. The size of the binary file should be a multiple of sizeof(long). You should allocate sufficient memory to store all long integers in the file into an array and assign to *size the number of integers you have in the array. The function should return the address of the memory allocated for the long integers. You may assume that all input files that we will use to evaluate your code will be of the correct format. Note that we will not give you an input file that stores more than INT MAX long integers (see limits.h for INT MAX). If the input file is empty, an array of size 0 should still be created and *size be assigned 0. You should return a NULL address and assign 0 to *size only if you could not open the file or fail to allocate sufficient memory. It is important that the caller function, e.g., the main function, has an int variable to store the size of the array, and pass the address of this variable into long *Array Load From File(char *filename, int *size) using the size parameter. int Array Save To File(char *filename, long *array, int size) ECE36800 The function saves array to an external file specified by filename in binary format. The output file and the input file have the same format. The integer returned should be the number of long integers in the array that have been successfully saved into the file. If array is NULL or size is 0, an empty output file should be created. Note that this function asks you to save an array to a file. It does not ask you to free the array. void Array Shellsort(long *array, int size, long *n comp) The function takes in an array of long integers and sort them (using the Shell sorting algorithm). size specifies the number of integers to be sorted, and *n comp should store the number of comparisons involving items in array throughout the entire process of sorting. This function will have to call Generate 2p3q Seq to obtain the sequence of numbers to be used for Shell sort. You may choose to use insertion sort or bubble sort to sort each sub-array. (If you use selection sort to sort each sub-array, your program may have high run-time complexity if you do not take advantage of the properties of the sequence.) A comparison that involves an item in array, e.g., temp < array[i] or array[i] < temp, corresponds to one comparison. A comparison that involves two items in array, e.g., array[i] < array[i-1], also corresponds to one comparison. Comparisons such as i < j where i or j are indices are not considered as comparisons for this programming assignment. It is important that the caller function, e.g., the main function, has a long integer variable to store the number of comparisons, and pass the address of this variable into void Array Shellsort(long *array, int size, long *n comp) using the n comp parameter. Any support functions for these three functions, if any, must reside in shell array.c. These helper functions should be declared as static. Functions you will have to write for shell list.c: There are also three functions that deal with performing Shell sort on a linked list. In this assignment, you will use the following user-defined type to store long integers in a linked list: typedef struct Node { long value; struct Node *next; } Node; This structure has been defined in shell list.h. Given the definition of the structure Node, these are the three functions you have to write to deal with performing Shell sort on a linked list: Node *List Load From File(char *filename) The load function should read all (long) integers in the input file into a linked list and return the address pointing to the first node in the linked list. The linked list must contain as many Nodes as the number of long integers in the file. You should not have additional nodes in the linked list. Moreover, the long integers should be stored in the same order in the linked list as they are stored in the file. In other words, the first (last) long integer in the input file is the long integer stored in the first (last) node of the list. You should return an empty list if you could not open the file or fail to allocate sufficient memory. int List Save To File(char *filename, Node *list) The save function should write all (long) integers in a linked list into the output file in the order in which they are stored in the linked list. This function returns the number of integers successfully written into the file. ECE36800   Note that this function asks you to save a list to a file. It does not ask you to free the list. Node *List Shellsort(Node *list, long *n comp) The Shell sort function takes in a list of long integers and sort them. To correctly apply Shell sort, you would have to know the number of elements in the list and generate the sequence used for sorting accordingly (by calling Generate 2p3q Seq). The address pointing to the first node of the sorted list is returned by the function. Similar to the case of an array, a comparison here is defined to be any comparison that involves the field value in the structure Node. Note that if you are given a list of n Nodes, you should return a sorted list of n Nodes. 100 addr: 30 104 addr: 40 12 addr: 50 99 addr: 20 9 addr: 10 NULL (a) Original list (b) Sorting by manipulating addresses of Nodes 100 addr: 30 104 addr: 40 12 addr: 50 99 addr: 20 9 addr: 10 NULL 40 value next 50 20 10 0 40 0 20 30 50 The List Shellsort function must perform sorting by manipulating the next fields of the Nodes. Figure (a) shows an original list that is unsorted. Figure (b) shows how the list is sorted by storing the correct addresses in the next fields. The long integers stored in the value fields remain in the original Nodes. For example, the integer 99 is stored in a Node with an address 20 in the original list. The field of the same Node stores the address 10, allowing it to point to the Node storing the value 9. After sorting, 99 is still stored in the value field of the Node with address 20. However, the next field of the Node now stores 30, allowing it to point to the Node storing the value 100. In other words, each long integer must reside in the same Node in the original list before and after sorting. The only array that appears in this function is the sequence generated by Generate 2p3q Seq. You are not allowed to have other arrays (of any types) in this file. Therefore, you cannot divide a list into sub-lists and use an array to store these sub-lists. This restriction also applies to all helper functions of List Shellsort. Any additional helper functions should be defined in shell list.c file. These helper functions should be declared as static. It is important that the linked list returned from and/or passed into these three functions in shell list.c contain only nodes that store valid values. main function you will write in pa1.c: You have to write another file called pa1.c that would contain the main function to invoke the functions in shell array.c and shell list.c. Note that the function in sequence.c is invoked indirectly by the two Shellsort functions in shell array.c and shell list.c. ECE36800  You should be able to obtain the executable pa1 with the following command: gcc -O3 -std=c99 -Wall -Wshadow -Wvla -pedantic sequence.c shell array.c shell list.c pa1.c -o pa1 The flags used are a subset of the flags used in ECE26400. Note that the -Werror flag has been taken out. Also, the optimization flag -O3 is used. It is recommended that while you are developing your program, you use the “-g” flag instead of the “-O3” flag for compilation so that you can use a debugger if necessary. It is your responsibility to make sure that your submission can be complied successfully on eceprog. Just to be sure, you should type in alias gcc at the command line and check whether your gcc uses the correct set of flags. When the following command is issued, ./pa1 -a input.b output.b the program should load from input.b the long integers to be sorted and store them in an array, run Shell sort on the array, and save the sorted long integers in output.b. The program should also print the number of comparisons performed to the standard output with the following format: "%ld\n" ./pa1 -l input.b output.b the program should load from input.b the long integers to be sorted and store them in a linked list, run Shell sort on the linked list, and save the sorted long integers in output.b. The program should also print the number of comparisons performed to the standard output with the following format: "%ld\n" What should the main function do when an empty file or an invalid file is given? For the -a option, the load function (Array Load From File) returns a NULL address if you could not open the file or fail to allocate sufficient memory. The main function should exit with EXIT FAILURE when the returned address of the load function is NULL. For an empty input file, the load function should return a valid array of size 0. Therefore, an empty output file should be created. For the -l option, the current setup does not allow you to distinguish between an empty file, an invalid input filename, or failure in memory allocation (they all result in an empty linked list from the load function (List Load From File) for linked lists). Therefore, you should always continue to perform sorting and writing (an empty output file). You may declare and define other static help functions in pa1.c. Submission and Grading: The assignment requires the submission (electronically) of a zip file called pa1.zip through Brightspace. The zip file should contain sequence.c, shell array.c, shell list.c, and pa1.c. We do not expect you to turn in a Makefile because we are going to evaluate your functions individually. Any other files in the zip file will be discarded. Your zip file should not contain a folder (that contains the source files). Assuming that your folder contains sequence.c, shell array.c, shell list.c, and pa1.c (and no other .c files), you can create pa1.zip as follows: zip pa1.zip sequence.c shell_array.c shell_list.c pa1.c ECE36800   It is important that if the instructor has a working version of pa1.c, it should be compilable with your sequence.c, shell array.c and shell list.c to produce an executable. Similarly, if the instructor has a working version of sequence.c, it should be compilable with your pa1.c, shell array.c and shell list.c to produce an executable. For evaluation purpose, we will use different combinations of your submitted .c files and our .h and .c files to generate different executables. If a particular combination does not allow an executable to be generated, you do not get any credit for the function(s) that the executable is supposed to evaluate. The loading and saving functions will account for 20%. The sequence generation function will account for 20%. The Shell sort function for arrays will account for 20%. The Shell sort function for lists will account for 40%. The main function does not account for any points. However, if your main function does not work properly, we will deduct up to 5 points. Be aware that we set a time-limit for each test case based on the size of the test case. If your program does not complete its execution before the time limit for a test case, it is deemed to have failed the test case. We will not announce the time-limits that we will use. You should instead analyze whether your implementation has the expected time complexity through the numbers of comparisons or the runtimes for various test cases. You can obtain the runtime using the command time, e.g., time ./pa1 -l input.b output.b. It is important all the files that have been opened are closed and all the memory that have been allocated are freed before the program exits. A caller function that receives heap memory should be responsible for freeing it. For example, if the instructor’s main function calls the Array Load From File function, it is the responsibility of the main function to free the returned array. It is not the responsibility of the Array Shellsort or Array Save To File to free the array. Memory issues will result in 50-point penalty. Given: We provide .h files, namely, sequence.h, shell array.h, and shell list.h. We also provide sample input files in pa1 examples.zip. (Use the command unzip pa1 examples.zip to unzip the zip file.) All “.b” files are binary files. The number in the name refers to the number of long integers the file is associated with. For example, 15.b contains 15 long integers, 15sa.b contains 15 sorted long integers from 15.b. In particular, 15sa.b is created by pa1 by the following command: ./pa1 -a 15.b 15sa.b My implementation of pa1 prints the following output to the screen when the above command is issued: 67 (The count of 67 is based on an implementation that uses insertion sort as the basic sorting algorithm in Shell sort. If we implement Shell sort with bubble sort as the basic sorting algorithm, the count is 80.) My implementation of pa1 prints the following output to the screen when the following command is issued: ./pa1 -l 15.b 15sl.b 104 My implementation of pa1 also created 1Ksa.b and 1Ksl.b. Of course, 15sa.b and 15sl.b are identical and 1Ksa.b and 1Ksl.b are also identical. For the input files 10K.b, 100K.b, and 1M.b, the output files of my implementation of pa1 are not included. ECE36800  Your implementation should not try to match the number of comparisons that my implementation reported. That is not the purpose of the assignment. Getting started: Download all files associated with the assignment from the Brightspace website. As the link to the assignment will disappear after the due date, you would not be able to access any of these files from Brightspace after the deadline. Any updates to these instructions will be announced through Brightspace. Given that the input files are in binary format, you probably want to write some helper functions to print the array of long integers before and after sorting in text (instead of binary) for debugging purpose. Keep in mind that fread and fwrite for binary files are analogous to fscanf and fprintf for text files. You probably want to write and test the load and save functions together because if you call the load and save functions without sorting the array or linked list, the output file should match the input file. The main challenge of this assignment is to perform Shell sort on a linked list. When we perform Shell sort on an array, we do not have to divide the array in sub-arrays. This assignment challenges you to perform Shell sort on a linked list without dividing the list into several sub-lists. This is a rare example when bubble sort is more useful than insertion sort. My suggestion is that you first implement Shell sort of an array using bubble sort as the basic sorting algorithm. It is important that the bubble sort routine terminates early when it detects that an array is sorted. (In the case of Shell sort, the bubble sort should terminate early when it detects that all sub-arrays are sorted.) The following algorithm implements bubble sort on an array of n integers. sorted = false last_exchange = n while (not sorted) sorted = true last_element = last_exchange - 1 for i = 1 to last_element if array[i - 1] > A[i] exchange A[i-1] and A[i] last_exchange = i sorted = false The algorithm employs two techniques to gain some efficiency. It uses a flag sorted to detect sortedness of an array. It also uses last exchange to record the index at which the most recent last exchange occurs. As all elements at and after the last exchange index are already at their correct positions at the end of the for-loop, the next iteration of while-loop should not examine those elements again. Therefore, last element is assigned last exchange - 1. Your Shell sort of an array based on bubble sort should add an outer-loop to account for the sequence. The body of the loop should be very similar to the bubble sort provided above, just like how Shell sort of an array based on insertion sort is developed in class. You probably also want to implement the above bubble sort algorithm on a linked list. Once you have these implementations, you may be able to identify a better connection between Shell sort of an array and Shell sort of a linked list. This assignment is about performing Shell sort. If you implement other sorting algorithms, your submission does not meet the specifications of the assignment, and it will receive a grade of 0. ECE36800  Other than the required output to stdout as specified, do not print other messages to stdout. If you want to print error messages for debugging purposes, use fprintf to print the messages to stderr. If your program produces messages that are not expected, your submission does not meet the specifications of the assignment and it will not earn the relevant credits. We will use valgrind to check for memory issues. While you are most familiar with memory leaks, valgrind can be useful in helping you find the cause of a segmentation fault and identify allocated memory locations that have not been initialized properly. The tool is useful only when you pay attention to all messages that valgrind reports. One useful programming habit is to keep your code valgrind-clean at any stage of programming. In other words, do not leave any memory issues unresolved at any stage of programming. Another good habit to cultivate is to pay attention to the number of memory allocations made by your program. Does the number of memory allocations reported by valgrind match your expectation? For example, I expect my pa1 to make 4 or more allocations for Shell sorting an array, and 18 or more allocations for Shell sorting a list of 15 integers. Why do we need 4 or more allocations and 18 or more allocations, respectively?