CSCI 1320 - Assignment #9

This assignment is going to test your abilities to use the things that we have recently discussed in class. This includes dynamic memory, structures, sorting, and searching. After each problem description I've given you sample input and output files as well as my executable which you can save into your sol directory and run on the lab machines (you might have to give the file execute rights though "chmod u+x ???", where ??? is the file name).

As a side note, be sure to save the code from all the programs you do. It is quite possible that later in the semester other assignments will include things that overlap with them and your code will be reusable.

Speed Test Problem:

For this assignment I want you to do speed testing on the different sorts that we did. You should write the three sorts (yes, I sent you code, but you should at least try to write them yourself first). You will make two versions of each. One will sort ints like we did in class and the other will sort large structures. The large structures will have one int and an array of 100 doubles. Sorting those will show you the difference of having time consuming copies vs. short copies.

So to get this to work you need to have some numbers to sort. To do this you will use the rand function and fill an array with random numbers. So that your tests are "even" I want you to have one array with 100,000 integers that you fill with random numbers by calling rand. Then have another array of ints and an array of your structures. Copy the ints from your first array into the other arrays and sort them. Do this once using only 100 of the numbers, then 1000, then 10000, and last the full 100000 (this last one might require dynamic memory for the structures). Use the clock command in time.h to keep track of how long the sorts take. Use man clock to look up the description. Put comments at the top of your submitted code with your results.

Some notes on this. It does not matter what values are in the doubles in the structs. You just sort by the ints. The doubles are only there to make the copies take longer. You should only have a total of 3 arrays, two of ints and one of structs. One int one is your "backup copy" so that after you sort some numbers you can restore the original sequence. The second int array is the one that you will use for sorting. While it will be 100,000 elements in size, you can easily tell the sort method to sort a smaller number of those elements, which is what you should do. You will have to copy from your backup array to the sort array before every sort. The struct array should be a dynamic array because 100,000 of those structures would take over 80MB of space and the stack won't be happy with that. A simple malloc at the beginning and free at the end will suffice. You must copy the numbers from your backup array into the int fields of the struct array before each sort of these.

For extra credit, think of a way to get data that is partially ordered and use it in the sort and report the results of that. Also, you can plot up the timing results for the 3 sorts on the 4 different input sizes and hand in a paper copy.

Graphics Problem:

One problem that existed in what you did for assignment 7/8 is that while you told it how far the triangles are from you, you didn't use that information for much of anything. Most importantly, you didn't check to see if one triangle was behind another (at least you didn't have to). Now that you know how to sort, you can fix this. I want you to add one more option to your menu. When this option is selected you should sort the triangles based on the point that is closest tot eh viewer (smallest z value). Do this so that when you draw the triangles you draw the ones that are furthest first. That means you want the array to start with the traingle that has the largest z value (again you are only considering the point in the triangle with smallest z-value). This way, when you draw it things will look correct as long as the triangles don't actually intersect one another.

Grade Book:

For this you will extend what you did in assignment 7/8 and add sorting to it. I want you to add 3 options (8, 9, and 10 with quit becomeing 11). The first one should just display data for the full class. It should show name, assignment average, quiz average, test average, class participation, and class average. The second new option is to sort the students alphabetically by their names. This doesn't display anything, it just reorders the students data in the arrays you use. If you select option 8 after doing this all the students will be shown in alphabetical order. The third new option is to sort the students by their class average.