CS 415 Signature Project

When transitioning from an array of integers (or other primitive data type) to more complex data elements, it is natural to declare an object with multiple data fields. For this project, a Person will have fields for an individual's first name and surname, city, state (or territory), and telephone number.

At the level of coding, the non-numeric fields within a Person could be stored as a C++ string or a C-style char *. Further, if Person fields will be initialized with a constructor, but never changed, these fields might (or might not) be specified with const. In software development, natural questions arise as to whether/how such implementation details might impact code readability, maintenance, operability, and efficiency.

When ordering an array of Persons, at least seven case-sensitive orderings seem natural:

• by first name (comparison of strings)
• by surname (comparison of strings)
• by combined surname and first name (use surnames, but if surnames match, then compare first names)
• by city (comparison of strings)
• by state/territory (comparison of strings)
• by state/territory and city (use state/territory, but if state/territory names match then compare cities)
• by telephone number (stored and ordered as long integers)

For these orderings equality and ordering are handled by different methods within the Person class, where each method examines only one or two fields, and ignores the others.

Although constructors and public methods for variations in the Person class need not impact the use of the class in applications, variations in private fields lead to two different header files. For the purposes of this assignment, two versions of a Person class are considered for this project:

• Implementation with some fields involving C++ String objects: a header file Person.hpp and [partial] implementation file Person.cpp.
• Implementation with some fields involving C-style strings (with const char * pointers and char arrays): a header file PersonAlt.hpp and [partial] implementation file PersonAlt.cpp.

Note: Behind the scenes, both programs sortAlgsForPersons.cpp and ortAlgsForPersonsAlt.cpp use files first-names.c, surnames.c, and states.c, each of which is available for download.

Work for this project component:

• Download these header and implementation files, and complete any unimplemented code.
  • Note: The header files must not be changed for this project.

  • Before editing any programs, compile and run Person.cpp and PersonAlt.cpp (and save the output). Then answer these questions (which likely will be the same for both programs). As a Signature Project, answers to each question must involve several complete sentences. (Expect point penalties for sentence fragments.)

    • ** Method equalName compares first names and surnames separately. Another approach might concatenate the surname followed by the first name, and then compare the concatenated strings. Why might this second approach yield incorrect results in some cases?
    • ** Explain how the testing is done in the main procedure of these two programs. For example, what is the purpose of each of the 2-dimensional arrays, equalNameResults, etc.?
    • ** Do the test cases in this main procedure fully cover the possible cases that might arise for the methods in this class? If some cases seem unnecessary, identify them, and explain why they are superfluous. If all cases are essential, justify your conclusion.
    • ** Describe the output obtained by running Person.cpp. For example, the output is structured into parts. Identify each part, and indicate what, if any, summary statements are made.
    • ** Does the output from PersonAlt.cpp differ from that obtained from Person.cpp? Describe any differences found, if any.

  • Complete Person.cpp and PersonAlt.cpp, by expanding the method stubs in each program.

    • Expanded code will be needed in each program for methods
      equalFirstName, equalSurname, equalCity, equalStateTerritory, equalLocation, equalTelephone, comesBeforeFirstName, comesBeforeSurname, comesBeforeName, comesBeforeCity, comesBeforeStateTerritory, comesBeforeLocation.

      Notes:

      • In most cases, the completed methods can serve as a starting reference to complete the stubs.
      • For each stub, the 2 lines of the method body can be replaced by no more than 6 nicely formatted lines—and most can involve just 1 or 2 simple lines of code!
      • Thus, the overall time for completing the stubs can be rather modest— and this work may provide a reasonable review of both C++ and C-based strings.)
    • Although the main procedure of each program contains thorough testing for most methods, code is not included for testing comesBeforeSurname or comesBeforeName. Expand the current testing with code to test these two additional methods. (Once you have completed this testing code in one program, it likely can be added to the second program with a cut-and-paste.)

  • Run each program and save the output obtained.

    • Note the header of both Person.cpp and PersonAlt.cpp provides instructions regarding how to compile and run the program in a terminal window, and how to compile to an object file which can be used in applications.
    • ## Explain how the structure of the program supports both this testing and the use of the program. For example, why/how can command-line statements yield two different types of compiled files?

  • ## Based on your testing output, explain (in at least a few sentences) why you believe your program is correct!

Note: Be sure your completed code for this project component is correct, as it will be used in other components.

• a full listing of programs Person.cpp and PersonAlt.cpp, with all stubs completed in each program, and with thorough testing. (Testing should involve all methods, including the two additional tests you wrote.)
• output from the completed program.

For each student, the final report should contain sections for the following:

• answers to questions asked regarding the initial programs (before stubs were completed)(For clarity, these questions are identified with double asterisks **)
• complete answers (in English sentences) for the questions about compiling the programs for different purposes and about the correctness of both programs. (For clarity, instructions for this material are identified with double number signs ##)

Program sortAlgsForInts.c provides C code for several sorting algorithms applied to integers, and for testing those algorithms. This component of the Signature Project explores what changes might be needed to translate these algorithms to arrays of objects of the Person class, and also to explore the extent to which adding procedures for clarity and readability might impact run-time efficiency.

Program sortAlgsForPersons.cpp contains a framework for timing versions of the Insertion Sort and two other sorting algorithms for random Person arrays. To help make this work manageable, students will have different assignments (A, B, C, or D), as specified on Canvas.

1. This assignment focuses on the tradSelectionSort from sortAlgsForInts.c:
   • Translate the code to sort arrays of Person objects, placing the resulting code as the implementation of sortAlgA in sortAlgsForPersons.cpp
   • Modify this code to obtain an implementation of sortAlgB, by writing your own swap procedure and calling that in the selection sort to swap a[smallestIndex] and a[i]
2. This assignment focuses on the SelSortWInsertion from sortAlgsForInts.c:
   • Translate the code to sort arrays of Person objects, placing the resulting code as the implementation of sortAlgA in sortAlgsForPersons.cpp
   • Modify this code to obtain an implementation of sortAlgB, by writing your own procedure that inserts the max element into the last position by sliding other elements down and calling that in the selection sort to at the end of the outer loop.
3. This assignment focuses on the traditional, recursive merge sort, involving a basic traditionalMergeSort method and a helper traditionalMerge procedure from sortAlgsForInts.c:
   • Translate the code to sort arrays of Person objects, naming the resulting code for the traditionalMergeSort as sortAlgA and including an appropriate helper (perhaps still named traditionalMergeSort).
   • The traditionalMerge procedure ends with two loops which copy larr and rarr back to array. Write your own procedure that copies a segment of one array to a designated position in another array, and the use your procedure in a revised newMerge procedure that replaces the copying of extra elements by procedure calls. Then copy the traditionalMergeSort to a new sorting merge sort method sortAlgB that uses newMerge rather than traditionalMerge.
4. This assignment focuses on an iterative version of the Merge sort tradIterMergeSort, which uses a traditionalMerge procedure as defined in sortAlgsForInts.c:
   • Translate the code to sort arrays of Person objects, placing the resulting code as the implementation of traditionalMerge, and tradIterMergeSort in sortAlgsForPersons.cpp (Within sortAlgsForPersons.cpp, tradRecMergeSort should take the place of sortAlgA.)
   • The traditional merge procedure ends with two loops which copy larr and rarr back to array. Write your own procedure that copies a segment of one array to a designated position in another array, and the use your procedure in a revised newMerge procedure that replaces the copying of extra elements by procedure calls. You will need to copy your tradIterMergeSort to a new sortAlgB method that then calls this newMerge

When you have completed your assigned work on the sorting algorithms (just handling one of case A, B, C, or D, as specified on Canvas), follow these instructions.

• Within sortAlgsForPersons.cpp, four constants/expressions, defined after the opening program header, may need to be adjusted to give meaningful results on your local computer.

            // range of simulations
            const int minDataSetSize = 40;
            const int maxDataSetSize = 640;
            //int maxDataSetSize = 40960000;
            //int maxDataSetSize = 81920000;
            //int maxDataSetSize = 327680000;
  
            // expression for incrementing size variable in simulation outer loop
            #define sizeIncrement  size *= 2
  
            // number of iterations for simulation/timing of each sorting size
            const int numSimIterations = 1500;
          

  When you first run the program, follow these guidelines:
  • Adjust numSimIterations, so the elapsed time for the size of the first data sets is between 2.0 and 4.0 seconds. If needed, minDataSetSize also could be adjusted.
  • Adjust minDataSetSize and maxDataSetSize, so that the output includes about 4 sizes of data. (Note, however, that in my experience, it is not uncommon to get a segmentation fault from time to time. If this happens to you, try running the program several times.)
  • Efficiency analysis can be relatively straight forward, when the size of experiments doubles for each set of experiments. However, if experiments consistently yield segmentation faults, try changing the sizeIncrement defintion (e.g., to size += 50).
  • Before proceeding in this assignment, continue adjusting these variables/definitions until you obtain four sets of non-zero timings—at least for some runs.
• Since ordering by phone involves a simple comparison of long integers, timing for this sorting will largely correspond to our sorting experiments using integers (perhaps with some overhead for the class structure). However, ordering either by name or by location involves comparisons of strings. Run the program to obtain timings for sorting by phone, by name, and by location.
  • ## When you run the program, to what extent does the nature of the data for comparison seem to impact sorting times for random data? For example, is the sorting time about the same, about 10% longer for strings, about 20% longer, etc.? Justify your answer.
  • ## Compare timings and data set size for sortAlgsForInts.c and sortAlgsForPersons.cpp. One program sorts int data and the other objects containing string and integer data. Describe any differences you observe, and provide some reasons that might be behind these results.
  • ## In reviewing output of this program, compare the times required for both versions of the sorting algorithms (with and without the swapping or shifting procedures). To what extent does using the swap/shift procedure change the overall sorting time for each algorithm? Are the times the same with or without the swap procedure? If not, which is faster and how much so (e.g., 5%, 10%, 15%, etc.)? Overall to what extent does coding for readability in this case seem to impact code run times?

• A listing of the extended SortingAlgForPersons.cpp program and the output it produces.

For each student, the final report should contain a section for the following:

• Discussion of both the relative readability of the code with and without swap procedures, and analysis of the extent to which utilizing the swap procedure impacts run time. (For clarity, instructions for this material are identified with double number signs ##)

This component examines the relative efficiency of recursive versus iterative implementations of code by comparing two versions of the same sorting algorithm. For this component, all students will start by considering program sortAlgsForInts.c, which provides C code for several sorting algorithms applied to integers, and for testing those algorithms. Further, program sortAlgsForPersons.cpp contains a framework for timing versions of the Insertion Sort and two other sorting algorithms for random Person arrays. To spread the workload over members of small groups, students will have different assignments (A, B, or C) as specified on Canvas, as follows:

1. This assignment focuses on the tradSelectionSort from sortAlgsForInts.c:
   • Translate the code to sort arrays of Person objects, placing the resulting code as the implementation of sortAlgA in sortAlgsForPersons.cpp (This is the same work that is part of assignment A for Project Component 2.)
   • Using your code in sortAlgA as a base, rework the algorithm by replacing the outer loop by a recursive procedure to obtain an implementation of sortAlgB. (If needed, feel free to utilize a husk and kernel approach, with sortAlgB as the husk and a helper method as the kernel.)
   • Note: For the recursive version of this code, you might consult Is it possible to have recursive Selection Sort? by Quora.
2. This assignment focuses on the SelSortWInsertion from sortAlgsForInts.c:
   • Translate the code to sort arrays of Person objects, placing the resulting code as the implementation of sortAlgA in sortAlgsForPersons.cpp (This is the same work that is part of assignment B for Project Component 2.)
   • Using your code in sortAlgA as a base, rework the algorithm by replacing the outer loop by a recursive procedure to obtain an implementation of sortAlgB. (If needed, feel free to utilize a husk and kernel approach, with sortAlgB as the husk and a helper method as the kernel.)
   • Note: For the recursive version of this code, you might consult Selection Sort Algorithm – Iterative & Recursive | C, Java, Python by Techie Delight.
3. This assignment focuses on both the recursive and iterative versions of the merge sort from sortAlgsForInts.c: In particular, translate the code for traditionalMergeSort as sortAlgA, tradIterMergeSort as sortAlgB, and traditionalMerge as a separate private method. (This work is similar to parts of assignments C and D for Component 2.)

When you have completed your assigned work on the sorting algorithms (just handling one of case A, B, or C, as specified on Canvas), follow these instructions.

• As in component 2, adjust variables/definitions for minDataSetSize, maxDataSetSize, sizeIncrement, and numSimIterations (found just after the program header), so that the elapsed time for running the first data set is between 2.0 and 4.0 seconds, and so that the program does not yield segmentation faults (at least for some runs).
• Program sortAlgsForInts.c (from above) shows both recursive and iterative implementations of a Merge Sort.
  • ** Review the two implementations carefully. Except for the difference form (recursion versus iteration), to what extent do these implementations perform exactly the same work. Of course, recursion and iteration may perform tasks in different orders, but is the overall work the same, or does one implementation perform some work that the other does not? Explain.
  • ** Run sortAlgsForInts.cpp, and compare the run times of the recursive and iterative implementations. Are the times similar, or is one approach more efficient than the other (and by about how much 5%, 10%. etc.)? Explain.
• ** Now focus on the iterative and recursive methods that you wrote within sortAlgsForPersons.cpp
  • With your addition of the recursive implementation for your assigned sorting algorithm, run the program and compare the timings of the recursive and iterative versions of the sorting procedure.
  • Is the time roughly the same, or is one implementation more efficient? And if there is a noticeable difference, how much more (e.g., 5%, 10%, etc.)?
• ** Looking at the results you obtained for this component of this project, and considering results shared by others in your group, can you make a preliminary conclusion regarding the likely impact of utilizing recursion versus iteration in implementing an algorithm? Does one approach have a clear efficiency advantage? Does one approach have a clear advantage regarding clarity? Overall, what guidelines might you suggest regarding the use of recursion versus iteration? Explain.

• A listing of the extended SortingAlgForPersons.cpp program and the output it produces.

For each student, the final report should contain a section for the following:

• Discussion of both the relative readability of the code with and without swap procedures), and analysis of the extent to which utilizing the swap procedure impacts run time. (labelled **)

As introduced in component 2, program sortAlgsForPersons.cpp runs versions of three sorting algorithms, Selection Sort, Insertion Sort, and Merge Sort for several Person array. The code also checks that each algorithm sorts correctly by name, by location, and by phone. This component considers whether the sorting algorithm is stable.

For this Project component, check the Project page on Canvas to determine which sorting algorithm you should utilize and whether you should consider sorting by name or by location. Your assigned sorting algorithm utilizes the following letter code:

1. Selection Sort
2. Insertion Sort
3. Merge Sort

• ** Describe how code might be tested to determine if the implementation of a sorting algorithm is stable.
  • One possible approach would involve two steps: First sort the array by telephone number and then by either name or location.
  • Will this approach provide a solid test to determine stability? If so, explain carefully. If not, suggest a different testing strategy and explain why it works.
• Add a method testStability to program sortAlgsForPersons.cpp to implement your stability test.
• ** Run your program to determine if your designated algorithm for this Project component is stable.
  • If the sorting algorithm is stable, explain why.
  • If not, but the code can be refined (in no more than a couple lines) to yield a stable algorithm, describe those changes, then test your code to demonstrate the adjusted algorithm is stable.
  • If the code cannot be easily changed to yield a stable algorithm, explain why such an adjustment is not possible.
• ** If you can obtain a stable sort procedure, run the following experiments.
  • ** Experiment 1:
    • Modify your program to perform a sort by name and save the results in an array or vector.
    • For a copy of the original array or vector, first sort by firstName and then by surname.
    • To what extent is the result of these two sorts identical?
  • ** Experiment 2: Repeat the previous experiment, except in the second step sort by surname and then by FirstName. Again, to what extent is the result of these two sorts identical?
• ** To what extent do these experiments confirm or contradict your conclusions about designing tests for stability, as discussed at the start of this Project component?

• A listing of the sortAlgForPersons.cpp program and the output it produces.

In class on Tuesday, April 29, each student should be able to discuss the following:

• An algorithm to test whether an algorithm is stable, and an argument why this test works.
• If the original sorting algorithm (as translated from sortAlgForInts.cpp) was not stable,
  • what modest revision of the code resulted in a stable algorithm, and an explanation why the revision works, or
  • why a modest adjustment is not possible to obtain stability.

For each student, the final report should contain a section for the following:

• A description of an algorithm to test whether an algorithm is stable, and an argument why this test works. (answering questions labeled **)
• If the original sorting algorithm (as translated from sortAlgForInts.cpp) was not stable,
  • both the revised code that yields a stable algorithm, and an explanation why the revision works (labelled **, if relevant), or
  • a discussion of why a modest adjustment is not possible to obtain stability. (labelled **, if relevant)
• A discussion of the results and conclusions of the two experiments described toward the end of this Project component (labelled **)