CS 202 Fundamental Structures of Computer Science II

Assignment 1 – Algorithm Analysis, Sorting and Searching

Due Date: June 21, 2010 (Monday)

Question-1 (30 points)

Trace the following sorting algorithm for sorting the array: 7 1 9 2 3 5 into ascending order. Use the array implementation as described in the textbook/lectures.

a) Insertion sort.

b) Selection sort.

c) Bubble sort.

d) Mergesort. Also list the calls to mergesort and merge in the order in which they occur.

e) Quicksort. Also list the calls to quicksort and partition in the order in which they occur. Assume that the first item is chosen as pivot.

Question-2 (60 points) – Programming Assignment

You are going to implement the following sorting algorithms for linked-lists of integers, and empirically test them. First, write the methods for the following sorting algorithms for linked-lists of integers. Make sure that your methods sort the given linked lists of integers in DESCENDING order.

• Insertion Sort
• Quick Sort – selects the first item as pivot
• Radix Sort

Then, write a main method to find the time requirements of your methods for different linked lists of integers. You have to create 9 different linked lists and you have to find the time requirement of each of your methods for each of the linked list. The linked lists that you have to create:

• 3 linked lists with sizes 20000, 40000, 80000. Fill each linked list with the integers in the ascending order (0,1,2,3,4,...).
• 3 linked lists with sizes 20000, 40000, 80000. Fill each linked list with the integers in the descending order (80000,79999,...)
• 3 linked lists with sizes 20000, 40000, 80000. Fill each linked list with random integers using the random number generator function rand .

Make sure that you test your methods with the same linked lists.

To measure the time requirement of your method use clock() library function (include time.h). You should invoke the clock() library function before and after the invocation of your sorting method, the difference between these two returned values is the time requirement for your method (in miliseconds).

Your program should print 27 time requirements (9 for each sorting algorithm).

Finally, add the code that does the following at the end of your main function. This code prompts the user to enter a set of integers (together with number of integers in the set), creates a linked list from those integers, sorts these integers in the descending order using the aforementioned sorting algorithms, and displays the sorted integers on the screen.

Question-3 (10 points)

With the help of Microsoft Excel or other tools, or manually, present your experimental results graphically. Compare your empirical results with the theoretical one for each sorting algorithm (Explain any differences between the empirical and theoretical results, if any).

Hand-in:

· You should submit both the softcopy and hardcopy of your homework.

· Before 6:00 pm of June 21, 2010, send an email, with subject title CS202 HW1, to your TA, Sefa Kılıç (sefak@cs.bilkent.edu.tr), attaching with one zipped file (named as yournameyourlastname.zip ) which contains:

§ hw01.doc, the file containing the answers of Questions 1 and 3, the sample output of the program in Question 2,

§ hw01.cpp and hw01.h (if needed), the files containing the C++ source code and the non-standard library used in Question 2, and

§ readme.txt, the file containing anything important on the compilation and execution of your program in Question 2.

· The subject field of your email must be CS202 HW1, otherwise, it may be considered as one of the junk emails!

· You are free to write your programs in any environment (you may use either Linux or Windows). On the other hand, we will test your programs on “dijkstra.ug.bcc.bilkent.edu.tr” and we will expect your programs to compile and run on the “dijkstra” machine. If we could not get your program properly work on the “dijkstra” machine, you would lose a considerable amount of points. Therefore, we recommend you to make sure that your program compiles and properly works on “dijkstra.ug.bcc.bilkent.edu.tr” before submitting your assignment.

· In the lecture on June 21, 2010, turn in the hardcopy of your homework which includes the solutions of all of the questions. The hardcopy should be identical to the files zipped in your email. You should not submit the print-outs of your source codes. Make sure that your homework contains your name, student id, and section on them; otherwise, it will not be graded.

· Do not forget to put your name and your section in the header comments in both hw01.cpp and hw01.h.

· Keep all the files before you receive your grade.

.

· DO THE HOMEWORK YOURSELF.

· PLAGIARISM IS A SERIOUS CRIME AND WILL BE HEAVILY PUNISHED.