Class Notes: Data Structures and Algorithms

Summer-C 1998 - M WRF 2nd Period CSE/E119

Instructor: M.S. Schmalz -- TAs: Tom Davies , James Jeffers

Project 7 Assignment

• Goal. The purpose of this project is to test the performance of code you or others have developed for Projects 3 through 6, for example, DFS, BFS, sorting, and hash tables. You may use code you developed, or code that will be posted on the Web. The key concepts are (a) the correct insertion of timing calls and (b) the correct analysis of timing data.

• Features. Hitherto, you have implemented various types of ADTs without checking their performance, other than perhaps investigating why a program ran for an abnormally long or short time. In this assignment, you will first marshall code you or others have developed, then insert timing calls to measure algorithm performance against several different criteria.

• Functionality. The program Proj7 will be instantiated in its own main() program that will (1) read in a given method specification (e.g., DFS, BFS, sorting algorithm name), (2) read the appropriate input file for each method as specified on the command line, and (3) will measure and analyze timing data for each of the bodies of code to be tested. Output will be produced to the screen and to a diskfile, as follows:
  1. Print your name, SSN, due date of project, and the string 'COP3530-C98-P7' to the screen.

  2. From the command line, read the method type method-type (equal to "DFS-AVL", "BFS-AVL", "DFS-BIN", "BFS-BIN", "MERGE-SORT", "QUICK-SORT", "BIN-SORT", or "INSERTION-SORT" for this assignment), as well as input file name finput, and output file name foutput, using the following command-line format:

     Proj7 -m method-type -i finput -o foutput

     where method-type denotes the String that is the name of the method whose performance you will measure.

     Then, open the input file finput for reading and the output file foutput for writing. The input file must be appropriate for the given method and should be included in the project submission and should be documented for each method used, in the README file that you customarily submit. You can find input file specifications for each of the assigned Projects 3 through 6 listed on the Web home page for this class.

  3. Read the input specification in the first line of finput and construct the appropriate ADT.

  4. Apply the ADT operations (that you or others have coded as Java methods) to the ADT to implement the storage, retrieval, and deletion commands that may be associated with the input file. Measure the total time, kernel time, and time consumed by function calls for each method with some different ADTs (six methods total) that you choose, and compute the screen/file output, as follows.

  5. Example Output. Assuming that you want to analyze DFS for AVL and binary search trees, as well as insert and delete for hash tables, together with Merge-Sort and Bin-Sort, the following output could be generated:

     John Smith     SSN: 123-345-6789
     2 July 1998   COP3530-C98-Proj7
     
                 -- EXECUTION TIMES (ms), NORMALIZED PER DATUM --
     
                      TOTAL TIME          KERNEL TIME         FUNCALL TIME
     METHOD	      Mean Stdev Median   Mean Stdev Median   Mean Stdev Median
     ------------ ---- ----- ------	  ---- ----- ------   ---- ----- ------
      DFS-AVL      0.22  0.07  0.24    1.3   0.6   1.7     0.11  0.04  0.12
     
      DFS-BinTree  0.34  0.15  0.28    1.8   0.9   1.4     0.12  0.03  0.19
     
      INS-Hash     0.03  0.01  0.04    0.37  0.21  0.42    0.16  0.05  0.15
     
      DEL-Hash     0.07  0.03  0.10    0.98  0.16  0.87    0.14  0.03  0.16
     
      Merge-Sort   0.05  0.02  0.07    2.6   0.54  2.7     0.19  0.08  0.18
     
      Bin-Sort     0.02  0.01  0.03    1.5   0.09  1.3     0.17  0.06  0.19
     
     - End Output -
     
     

     Note that this output would consist, for each moethod, of only one line of performance data, for example,

     John Smith     SSN: 123-345-6789
     2 July 1998   COP3530-C98-Proj7
     
                 -- EXECUTION TIMES (ms), NORMALIZED PER DATUM --
     
                      TOTAL TIME          KERNEL TIME         FUNCALL TIME
     METHOD	      Mean Stdev Median   Mean Stdev Median   Mean Stdev Median
     ------------ ---- ----- ------	  ---- ----- ------   ---- ----- ------
      DFS-AVL      0.22  0.07  0.24    1.3   0.6   1.7     0.11  0.04  0.12
     
     - End Output -
     
     

     However, you are to concatenate the output into a report file, which will include discussion of results, as specified below.

     To implement normalization per datum, divide the measured time(s) by the input size. For example, if you measure 17.1 milliseconds elapsed time for sorting 10 input data, then the normalized time would be 0.171 ms. Be careful not to have the number of significant figures exceed the measurement accuracy you can achieve!!!

• Algorithm. Use the following technique (illustrated at a high level) for total timing, kernel timing, and function call timing:

    main():
       ...declarations...
  
       total-time = 0                 ## Zero the timing accumulators
       total-funcall-time = 0
       NTt = 0                        ## Zero the timing counters
       NTf = 0
  
       start-total-timer(Tts)
       ...start executable statements in main program...
                 :
       start-funcall-timer(Tfs)
       ...a function call...
       end-funcall-timer(Tfe)
       total-funcall-time = total-funcall-time + (Tfe - Tfs)
       NTf = NTf + 1
                 :
       end-total-timer(Tte)
       total-time = total-time + (Tte - Tts)
       NTt = NTt + 1
  
    end-main.
  
    subordinate-procedure():
       ...declarations...
  
       total-kernel-time = 0
       NTk = 0
  
       ...start executable statements in subordinate procedure...
  
       start-kernel-timer(Tks)
       ...kernel code of the procedure...
       end-kernel-timer(Tke)
       total-kernel-time = total-kernel-time + (Tke - Tks)
       NTk = NTk + 1
                 :
    end-procedure.
  

• Java Programming Procedure. Use the following steps to guide your implementation of the Java version of the preceding program. Use the code example in the next bulleted item as a guide.

  Step 1. Get started early!!! It will be helpful if you design your main program and time measurement strategy methods before you start programming, or (better still) if you start early on defining these. You may work in groups, but do not copy your timing code directly between individuals or study groups.

  Step 2. Use the timing methods and techniques that we discussed in class, as well as techniques listed in the preceding pseudocode. Timing call insertion is discussed in this clickable link prepared for Dr. Crummer's class.

  Step 3. Test your timing incrementally (i.e., one method at a time), using inputs of known size and statistics.

  Step 4. Try your program on different kinds of output (e.g., large and small files). If your code breaks, fix it until it works on all inputs of finite size, within memory constraints.

  Step 5. Code a man page documentation sheet (one page only, formatted with the troff or HTML language). The generic HTML-format documentation page is shown below:

  Proj7              User Commands              Proj7

  NAME
  Proj7 - {description of what it does -- one line}

  SYNTAX

  Proj7 -m method-type -i finput -o foutput
  {with a description of what each parameter means}

  AVAILABILITY

  {directory to which you submitted, or in which you stored, your program}

  DESCRIPTION

  {what the program does -- 1 or 2 sentences}

  {what each command-line argument means}

  EXAMPLE

  {example of command-line syntax, with a 1- or 2-sentence description of what each different invoke does}

  SEE ALSO

  {some references on Timing Calls}

  PROBLEMS

  {any problems you encountered while testing your code}

  NOTES

  {anything else you want to say -- keep the man page to one page = 55 lines or less}

  {Your-Name}           Last change: {last date you changed this}

  Hint: On your Web browser, use the View menu entry Page Source to find display the source code for this page, including the source code (formatted above) for the HTML-format man page.

  Step 6. Try your program on different kinds of input (e.g., different input sizes, and answer the following questions for each method (on paper):

  • What is the theoretical performance of this method as a function of input size n? Use theory and a brief explanation (e.g., one paragraph) to illustrate your assertions.

  • How did the measured data differ (if at all) from the theoretical prediction? Explain in detail to obtain full credit, and use a graph of T(n) versus n.

  • What is the effect of normalizing the various times (e.g., total time, kernel time, and function call time) on a per-datum basis? Does this render the performance data more uniform? Explain your answer in detail, with supporting analysis.

• Java Programming Example. Here follow links to code used by Dr. Crummer's class that will help you get started. Note the in-line comments, which you should have in your program:
  • Dr. Crummer's Java Tutorial , with example introductory code for array objects

  • Example code for a partial ADT sequence

  • Example code for timing call insertion

• Documentation. Illustrate your program with in-line comments, so the TAs know what you are doing. Consult your textbook and other Java programming references for style guides. Use the man page format given above for an HTML page. If you want to use the troff language, there is a publically-available version at this clickable link.

• Evaluation. Maximum score = 150 points, as follows:

    Insert timing calls (10 pts per method) . . . .  60 points
    Compute statistics  ( 5 pts per method) . . . .  30 points
    Generate tabular report . . . . . . . . . . . .  20 points
    Documentation: man page in troff or HTML
       plus in-line comments in Java code . . . . .  10 points
    Report explaining measurements and behavior
       compared with theory in detail . . . . . . .  30 points
    ----------------------------------------------------------
    TOTAL SCORE                                     150 points
  

  Do not neglect good software engineering or Java programming style, as you were taught in lab sessions and in class.

• Submission. Follow the project submission instructions and the instructions at the Project #7 Instructions Page to achieve correct project submission. Incorrect submissions will not be graded, as they may or may not be received or dated properly by the homework submission server.

• Due Date. Submit the completed project by 11:00am on 6 August 1998. Projects submitted a day late will be penalized -10%; two days late: -20%, three days late: -30%, and four days late: -40% . Projects turned in more than four days late will not be accepted unless accompanied by a documented excuse (e.g., note from your physician or advisor).