CS 202 Fundamental Structures of Computer Science II

Assignment 1 – Algorithm Efficiency and Sorting

Due Date: 7 October 2013 (Monday)

 


Question-1 (30 points)
 

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

 

a)      Insertion sort.

b)      Selection sort.

c)      Bubble sort.

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

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

 


Question-2 (60 points) – Programming Assignment

You are asked to implement the sorting algorithms selection sort and quicksort for linked lists of integers and then perform some measurements. For quicksort, take the first element of the linked list as pivot. The details are as follows:

 

  1. Create two identical linked lists with random 20,000 integers using the random number generator function rand. One linked list is for one algorithm.
  2. For each algorithm, write the methods for giving a linked list of integers in ascending order. Add a counter to count the number of pointer changes within the linked list. The counter is only for this purpose and does not participate in sorting. Note that your algorithm should not create a new linked list.
  3. Write a main method to find the time requirements of different algorithms. To measure the time requirement, you can use the library function clock() (and include time.h). Invoke clock() library function before and after each sorting algorithm to measure the elapsed time (in milliseconds). Output the number of pointer changes and the elapsed time for each algorithm.
  4. Repeat the experiment (steps 1 to 3) for at least 5 different input sizes, i.e., 40,000, 60,000, 80,000, 100,000, …. With the help of Matlab, Microsoft Excel, other tools, or manually, present your experimental results graphically.

 

 

Question-3 (10 points)

 

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 October 7, 2013, send an e-mail, with subject title CS202 HW1, to your TA, Mecit Sarı (mecit.sari@bilkent.edu.tr), attaching one zipped file which contains:

Ø  hw01.doc, the file containing the answers to Questions 1 and 3, the sample output of the program and graphical representation of the experiments for Question 2, and

Ø  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 e-mail must be CS202 HW1, otherwise, it may be considered as one of the junk e-mails!

·           In the first lecture on October 7, 2013, turn in the hardcopy of your homework which includes solutions to all questions. The hardcopy should be identical to the files zipped in your e-mail. Make sure that your homework contains your name, student id, and section number; otherwise, it will not be graded.

·           Do not forget to put your name 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 AND CHEATING ARE HEAVILY PUNISHED.