python

CPSC 335 Project 3: sorting three ways  Summer 2015  Prof. Kevin Wortman, CSU Fullerton  [email protected] 

Introduction    In this project you will implement and analyze three string sorting algorithms:   

1. an  ‐time algorithm implemented in Python;(n )O 2   2. the same algorithm, this time implemented in a faster programming language such as C++; 

and  3. an  ‐time algorithm implemented in Python.(n  )O logn  

  The goal is to compare the performance impact of changing implementation choices, such as which  programming language to use, against the impact of switching to a different algorithm with a  theoretically‐faster efficiency class. 

The hypotheses    This experiment will test three hypotheses:   

1. A mathematically‐derived efficiency class for an algorithm will accurately predict the run  time of the algorithm’s implementation, regardless of which programming language is used. 

2. Lower‐level languages such as C++ are faster than higher‐level languages such as Python, by  some multiplicative constant. 

3. ‐time algorithms outperform  ‐time algorithms for large  , regardless of(n  )O logn (n )O 2 n   the implementation choices that are made. 

Sorting strings    This project involves implementing three algorithms, each of which sorts a list of strings. To  simplify matters I have provided you with an input file  beowulf.txt . The file contains the words  from the Project Gutenberg edition of Beowulf, limited to only ASCII letter characters, and newline  characters separating the words. The first few lines look like this:    The  Project  Gutenberg  EBook  of 

Beowulf  This  eBook  is  for  the  use  of  anyone    To form an input of size  , use first   words in the file. The file has   wordsn n 0, 074 7   so we are limited to  0, 07.  n ≤ 4 7  

Implementation 1: an  ‐time sort in Python(n )  O 2     First, implement an  ‐time sorting algorithm in Python. You are welcome to use the(n )O 2   out‐of‐place or in‐place selection sort covered in class. If you prefer, you may implement a different 

‐time sorting algorithm, such as insertion sort or bubble sort.(n )O 2     As with the prior projects, your algorithm should be a component of a complete program. The  program should:   

1. load the input file;  2. print the first 10 words (unsorted);  3. sort  words, where   is input as either a command line argument or from standard input;n n   4. measures the elapsed time of the sorting algorithm,  5. print the first 10 words (sorted), as a quick check that the sort is correct;  6. print the elapsed time to standard output. 

  You may reuse the code for measuring elapsed time that was given for project 1. 

Implementation 2: the same  ‐time sort in a faster(n )  O 2   language    Next, implement the same  sort algorithm in a “fast” lower‐level language. Python has a(n )O 2   reputation for being “slow,” so we expect this implementation 2 to be faster than implementation 1.  I expect most groups will use C++, but you are also authorized to use C, Go, Java, or C#. If you would  prefer to use a different fast language, you must get my permission first, and it must be a compiled  and statically typed language.    You will also need to implement the same kind of timing harness so that we can collect empirical  timing data and confirm this implementation’s correctness. I have provided you with sample high 

resolution timing code in C++11. If you choose to use a different language, you are responsible for  figuring out how to do high resolution timing in that language.    If you develop your implementation in Visual Studio, make sure to compile in Release Mode.  Programs compiled under Visual Studio’s Debug Mode are quite slow, sometimes slower than  interpreted Python code.   

Implementation 3:  ‐time sort in Python(n  )  O logn     Finally, implement merge sort, heap sort, out‐of‐place randomized quick sort, or in‐place  randomized quick sort in Python. As usual you will need a timing harness. 

Sample output    The output of my C++ selection sort implementation:    requested n = 200  loaded 200 lines from ’beowulf.txt’  first 10 words:  [The][Project][Gutenberg][EBook][of][Beowulf][This][eBook][is][for]  selection sort...  first 10 words:  [AN][ANGLOSAXON][Act][An][AngloSaxon][Author][BEOWULF][BEOWULF][BOSTON ][BY]  elapsed time: 0.00051 seconds 

Elapsed time crossover point    According to our mathematical analyses, the  ‐time algorithms will be faster for small values(n )O 2   of   while the  ‐time algorithm will be faster for large values of  . We expect there to ben ( n )O logn n   a crossover point which is an input size   such that the  ‐time algorithms are faster whennc (n )O 2  

and the  ‐time algorithm is faster when  .n < nc ( n )O logn n > nc    

    Determining the crossover point between your implementation 2 and 3 is part of the project. 

Deliverables    Produce a written project report  in PDF format . Your report should include the following: 

1. Your name(s) , CSUF‐supplied email address(es), and an indication that the submission is 1

for project 3.  2. Two scatter plots: 

a. One showing the run time of all three implementations, zoomed out so that the  quadratic curves are clear. 

b. One zoomed in to show the crossover point.  3. An output for   for all three implementations.00n = 2   4. Your complete Python source code for implementations 1 and 3.  5. Your complete source code (in C++ or similar) for implementation 2.  6. Answers to the following questions, using complete sentences. 

a. Which  ‐time algorithm did you choose to implement, and why?(n )O 2   b. Which  ‐time algorithm did you choose to implement, and why?(n  )O logn   c. Which of the three implementations did you find most difficult, and why?  d. Are your empirical results consistent or inconsistent with hypothesis 1? In other 

words, do the run times of both implementation 1 and 2 fit quadratic curves? 

1 Recall that, as stated on the syllabus, you may work in a group of up to three students. 

e. Are your empirical results consistent or inconsistent with hypothesis 2? In other  words, are the run times of your implementation 1 greater than those of  implementation 2 by a constant factor? If so, approximately what is that factor, as a  percentage? Does this result surprise you? 

f. Are your empirical results consistent or inconsistent with hypothesis 3? In other  words, is there a crossover point   for which implementation 3 is faster thannc   implementations 1 and 2? If so, what is the approximate value of  ? How muchnc   faster is implementation 3 over implementation 2, as a percentage, for the full 

 Does this result surprise you?0, 07?n = 4 7   g. Based on these results, which approach do you think is a better way of 

implementing algorithms efficiently: implementing a slow algorithm in a fast low  level language (implementation 2), or implementing a fast algorithm in a slow high  level language (implementation 3)? Why? What are the implications on software  development in general? 

  Your document  must be uploaded to TITANium as a single PDF file. 

Deadline    The project deadline is Monday, 6/29, 11:55 pm. Late submissions will not be accepted.   

License 

  This work is licensed under a  Creative Commons Attribution 4.0 International License .