This lab is worth 10 points and accounts for 12.5 percent of your laboratory grade. The points will be subjectively assigned by your TA based upon whether they believe you made a good faith effort toward complete the tasks that are assigned. Showing up on time, respecting your fellow classmates learning environment, and adherance to laboratory policies also factor into the determination of your score.
The following is an outline of the tasks for you to attempt during the lab period.
A framework containing the files and folders you will need can be found here. Download the .tgz file and decompress it in your account using the command:
tar -xzvf <file_name>
By now you should have received an email in you student ( XXX@student.ucr.edu ) email account. If you have not already, please follow the link in that email to fill out the online Teaching Assistant Evaluation Form.
In the folder iteration write a program that declares a list of integers and then fills it with the numbers 1 through 20. Then write a function print_list which takes a list of integers and prints them out as a space separated list in the order of the list. Call the function with the list that you have created as a parameter to verify that it works correctly.
Working on the same program for the previous exercise, write a function print_list_reverse which takes a list of integers and prints them out as a space separated list in the reverse order of the list. Call the function with the list that you have created as a parameter to verify that it works correctly.
The notes page for this lab contains a description of the bubble sort algorithm. In the folder bubble write a function which performs bubble sort on a list of integers. Create a list of random integers between 0 and 100,000 and give it to your algorithm to sort. Use the print_list function that you wrote earlier to verify that your bubble sort algorithm works.
NOTE: To implement the bubble sort algorithm you may want to use the swap function by including <algorithm>. The swap method of the list class doesn't do what you might expect it to.
Do a systematic analysis of how long it takes your algorithm to sort a list of integers. To do this, run your program on a list of 1,000 integers, 2,000, 3,000 and so on. Do you notice a trend in the amount of time that it takes your algorithm to sort larger and larger lists? Would you classify the relation between the number of items being sorted and the time that it takes to sort them as linear? quadradic? cubic?
NOTE: In order to determine how long your program is taking you can use the program time. For more information on the time program read its man page. To calculate the time taken by your program sum the User time and System time.
Many optimizations can be done on bubble sort to make it perform better. Find a way to improve the performance of your bubble sort algorithm and see what impact that optimization had by comparing it with the results that you recorded in the previous exercise.