Homework 2 (due 4/14)
CSC 321

We talked about asymptotic notation (Section 2.3, 2.4), insertion sort (Section 6.1), mergesort (Section 5.2) and lower bounds for comparison-based sorting (Section 6.3). Next week, we will talk about quicksort (Section 6.2),heapsort(3.5), linear time sorts (6.4) and selection (6.5). I also mentioned the game planarity (available as phone app as well).

Submission: Submit to the d2l dropbox. Use some standard format for your homework (Word or pdf, for example), and make sure to include your name and assignment number. Include screenshots for code and testruns. You do not need to include the code (or any executables).

1. (Reading Assignment) Read Sections 6.1, 5.2, 6.3, and Section 2.4 on recurrence relations up to page 60.

2. (Hybrid Sorting, 18pt) We mentioned in class that while asymptotically, mergesort beats insertion sort (so as n grows larger), there are cases when insertion sort is better, including few elements out of place, or just short lists. Here we want to test this claim in a bit more detail.

  1. [2pt] Show that n log n = O(n2). Hint: work with definition, find a factor c that will do.

  2. [2pt] Show that n2 ≠ O(n log n). Hint: again, work with definition; argue that for any choice of c, n2 <= c n log n is wrong for arbitrarily large n.

  3. [5pt] Use implementations of insertion sort and mergesort (you can use your own, or you can use the ones I uploaded to d2l) to do an experimental running time analysis. The hypothesis you are testing is that for small lists, insertion sort beats mergesort, but that from some point on (the crossover point), mergesort will be (and will remain) faster, bearing out the results in a) and b). Use the running time analysis to determine where that crossover point is for the implemernations of insertion sort and mergesort you are using. Include a plot of the running times (similar to the ones we've seen in class, you can use/modify my code as necessary), clearly showing the cross-over point, and what value it has.

  4. [5pt] Implement a hybrid sort, which uses mergesort for long lists, but as soon as the length of the lists go below the crossover point you determined in c) switches to using insertion sort. You can extend/modify the code I gave you, or work with your own code.

  5. [4pt] Do a running-time analysis comparing: insertion sort, mergesort, the hybrid sort from d), and a built-in sort in your programming language (in Python, .sort() is based on Timsort). Include (a clearly labeled) screenshot of the running times. Are the results in keeping with what you expected?

3. (Inversions, 22pt) For a given list of values, lst, an inversion is a pair of numbers that are in the wrong order (if we wanted the list sorted). More formally, an inversion consists of two indices i<j so that lst[i] > lst[j]. For example, [4,3,5,2,1] has 8 inverted pairs: (4,3); (4,2); (4,1); (3,2); (3,1); (5,2); (5,1); (2,1) are all in the wrong order.

  1. [3pt] How many inversions are there in the list [n, n-1, n-2, ..., 2, 1]? Explain your answer.

  2. [4pt] Implement a (simple) algorithm that counts the number of inversions in a list. What is the asymptotic running time of your algorithm? Use the result from a) to test your algorithm.

  3. [10pt] Implement an algorithm that counts the number of inversions in a list in time O(n log n). As usual, include testruns showing the algorithm works correctly on some inputs (e.g., you can use the result from part a). Hint: the easiest solution is to adapt mergesort. Follow the recursive structure of mergesort: as  you divide, and as you conquer, how do you calculate the number of inversions? Before implementing this, I strongly suggest you take a small list (4 or 8 elements), where you know the answer, and trace mergesort on that example by hand. The interesting part here is what happens during the merge.

  4. [5] Determine the number of inversions of the list stored as longlist.txt (or as zip: longlist.zip)

Marcus Schaefer
Last updated: April 9th, 2015.