Algorithm Analysis Objective CODE IN C++ The objective of this programming assignment is to present the student with a C++ introduction assignment with a more challenging problem to solve than the basic practice tasks given in regular homework assignments. This assignment also attempts to illustrate the differences in running times for algorithms that perform the same task: finding prime numbers smaller than a given integer. Instructions Implement a program that asks the user for an integer n, which method (trial division or sieve of Eratosthenes) to use, and whether the prime numbers should be printed to the screen. The program should then find all of the prime numbers smaller than n using the selected method and print the time taken by the algorithm. There is a timer class and example program attached to this assignment. During testing of your program use the option to print the prime numbers found by the algorithms to the screen for verification. Finding prime values by Trial Division To decide if a number is prime using trial division, try dividing the number by all integers between 2 and the square root of the number. If there is a remainder from all of the division operations, the number is prime. You will test each integer less than n using this process to create a list of all the prime numbers less than n. Finding prime values by Sieve of Eratosthenes The following excerpt for finding prime numbers using the Sieve of Eratosthenes algorithm is from http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes (it is important that you view this page to get a better idea on what the algorithm does): To find all the prime numbers less than or equal to a given integer n by Eratosthenes' method: 1. Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n). 2. Initially, let p equal 2, the first prime number. 3. Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked. 4. Find the first number greater than p in the list that is not marked; let p now equal this number (which is the next prime). 5. If there were no more unmarked numbers in the list, stop. Otherwise, repeat from step 3. When the algorithm terminates, all the numbers in the list that are not marked are prime. Run your program for different values of n (at least 10) and record the times taken for finding the prime numbers smaller than n. Recorded times should be distinct and non-zero. For the analysis questions below, use the timings of your program execution that does not print the prime values to the screen. CSE2383 Programming Assignment 1, version 1.2 Page 2 Choose values of n such that valid timings (greater than 0 seconds) are found and choose an increment between the values of n such that your times for each n are not the same. You must report timings for 10 different values of n for each method of finding prime numbers. NOTE: for the sake of debugging your code, choose trivial values of n (e.g. 25 to 32 or smaller) so that your code can finish its search quickly. For actual timing runs, choose larger values of n such that a difference in execution between the two algorithms can be observed. Be aware that some values of n may result in very long execution times (i.e., several minutes to hours). Therefore, it is important for you to complete writing the program in enough time to allow for adequate timing analysis runs. Files and starter code Below is a list of files and/or starter code that is provided with this assignment. If these files are not provided, notify your instructor immediately. The list below may also include a small description on what each files does (or provides); the list may elect to refer you to the comments provided within the file itself. The following files are included in the compressed file, student_files.zip: timer.h and testTimer.cpp A timer class that you will use to perform your timing analysis. The file testTimer.cpp provides an example of how to include this file into you program, create an object of the timer class, and then use its timing methods to perform a timing analysis prime.cpp Starter code that includes the dynamic allocation of an array (using a pointer), and the signatures of the functions that will implement your two algorithms; the functions receive an array as an argument. You do not need to know the details on how to use dynamic memory, pointers, or how arrays are passed to functions to complete this assignment. See code comments for further details. Analysis Questions 1. What are the specifications of your computer (CPU and clock speed, operating system, amount of RAM)? 2. What were your values of n and program timings for the trial division method of finding primes? 3. What is the asymptotic complexity (in O notation) of the trial division method? Justify your answer using your timings. 4. What were your values of n and program timings for the sieve of Eratosthenes method of finding primes? 5. What is the asymptotic complexity (in O notation) of the sieve of Eratosthenes method? Justify your answer using your timings. In addition to answering the questions 3 and 5, include a line graph of the recorded times taken by the algorithms to find the five (or more if you chose) different n values; it should be a single graph with a line for each algorithm. This graphs is visual representation and not a substitute for answering questions 3 and 5. CSE2383 Programming Assignment 1, version 1.2 Page 3 Deliverables Source code prime.cpp and any other *.cpp files written by you associated with this assignment that is necessary (other than the provided timer code) to compile and run your program. The code should follow the style guidelines presented in the web links for the class. Lab Report in pdf format which includes: o Title Page and problem specification o Answers to the Analysis Questions with graph o Conclusions of what you learned from this assignment o References used (see section at the end of this assignment) and Appendx The report format guidelines are located in the Programming Assignments folder in myCourses All deliverables must be submitted on myCourses Grading This assignment is worth 100 points distributed according to the categories outlined below. The programming assignment will show a grading rubric when assigned. The rubric will be the standard for grading this assignment. Below is a brief of the most significate (but not all) details. Program completed (60 points total) If the program fails to compile, the program will be considered incomplete and 0 points will be assigned for this category. Otherwise: Program Functionality: 50 pts (20 for trial division, 25 for Sieve of Eratosthenes) Programming Style: 10 pts Program functionality and criteria: Code compiles. Otherwise a zero grade will be assigned for Program Functionality. Code asks for a number and whether or not to print the prime numbers. (5 pts of the 50) All algorithms must execute and generate numbers. If an algorithm fails to execute and generate numbers, the points for that algorithm will be zero. All numbers presented must be a prime number. If a number provided is not prime, points will be deducted from the algorithm's score relative the total numbers found that were not prime. A potential deduction may be, if three numbers found arent prime, the algorithm score is a zero. The prime numbers printed, includes the number given by the user if it is prime. The execution time for the algorithms must not exceed 3 minutes of execution, for finding prime numbers, given the number provided by the user is at most 3 digits (e.g., 100, 211, and 300). CSE2383 Programming Assignment 1, version 1.2 Page 4 Report and Analysis Questions (40 points total) If all required sections are not provided, the report is considered incomplete and 0 points will be assigned as the grade for the report. Otherwise Title page consistent with what is presented in the Lab Report Format documentation: 10 pts The following required sections of the lab report are graded assuming the standard of a "goodfaith" effort for completing the lab report. A student making a "good-faith" effort presents that a genuine effort was made to meet the criteria outlined in each required section and to provide correct and accurate answers to any assigned question. o Problem specification: 2.5 pts o Analysis: 20 pts if all questions are answered o Conclusions: 5 pts o References: 2.5 pts Program Style Your code should be readable. Use comments to provide details on what actions your implemented methods are taking and to describe the overall task your code (e.g. classes, main program, etc.) is executing. Indent the blocks of loops, decision structures, methods etc. At the top (i.e. header) of all of your code files put in comments, the name of the file, your name, date of the code written, and a description of what the code in that file does. You may use the ProgramStyleExample.pdf as a reference for how to write the header comments, indentation, and how to comment the main body of your code. DO NOT JUST COPY AND PASTE THE COMMENTS IN THE PDF, otherwise you will get a zero for this part. The ProgramStyleExample.pdf file is provided as a link in the Programming Assignments section in myCourses. References You may use code from your textbook, or sources other than the textbook only if you give proper attribution (both as code comments and in your assignment report). If you use code from other sources and provided proper references but is unable to explain how it works if asked, you will get a zero for the reference section of the report and your submission is subject to additional deductions in the grade if warranted by the instructor. If you used code and or material from any source other than the instructor or TA and failed to reference these sources, you will be considered in violation of the MSU honor code and reported to the MSU Honor Code Office, even if you forgot to fill in the references. References in Code Comments Provide a comment at the beginning of the code that states the authors name (if known) and where you obtained the code. CSE2383 Programming Assignment 1, version 1.2 Page 5 C++ Example: /************************************************************* * The following implementation of Red-Black Trees * was written by John Morris and is available at * http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html *************************************************************/ References in the Report Format your references in the department's standard style (based on the IEEE Computer Society style). Examples are available at http://cse.msstate.edu/academics/gradstud/references.php Example: J. Morris, "Red-Black Trees," Data Structures and Algorithms, http://www.cs.auckland.ac.nz/software/AlgAnim/red_black.html (accessed Jun. 2, 2010)