CSE2320-001                                          Fall2001                                        J.C.M.Tiernan

 

Lab Assignment #1

 

Due date: Monday, September 10, 2001, 12:30pm

 

Pseudocode the algorithm for the Sieve of Erastosthenes(discussed in class at the time of this assignment).  Analyze the algorithm line by line as in the INSERTION_SORTon p. 24 of the textbook (p. 8 in the first edition text), then find theappropriate order for the running time using big-O notation discussed insection 3.1, p. 44.

 

 

 

An entertaining and

only mildly factualintroduction to

the Sieve of Erostosthenes

 

 

Erostosthenes was an ancientGreek mathematician (as were so many.) In particular, Erostosthenes was fascinated with discovering primenumbers.  Many primes were alreadyknown at that time but there was not a straightforward, well-known way ofdiscovering primes as the numbers grew larger.  The contribution that Erostosthenes made to the work infinding primes was to come up with an algorithm that could be easily applied tofind larger and larger primes. 

 

The name for his algorithm comes fromthe myth that Erostosthenes was inspired by the sight of fishermen hauling inhuge nets.  The nets were woven insuch a way that the fishermen would catch the fish that they wanted to keep butunwanted fish would fall through the nets.  The net, or sieve, would thus separate the fish.  The algorithm Erostosthenes designedseparates numbers into non-primes and primes.

 

The Sieve of Erastosthenes hasreally only a starting point, two steps, and an ending condition.  The starting point is to take any sizecontinuous group of integers starting with 2, e.g. the group from 2 to 100,from 2 to 10,000,000, etc.  Then tofind all the prime numbers within that group you repeatedly apply two steps.  First, circle the smallest unmarkednumber (of course, this is 2 for the first iteration).  Second, mark out every number in orderthat is a multiple of the circled number within the group (so the firstiteration marks out every multiple of 2 starting with 4 going up to the largesteven number in the group.)  Repeatthe two steps and end when every number in the group is either circled ormarked out.

 

 

 

 

1

2

3

4

5

 

6

7

8

9

10

 

11

12

13

14

15

 

16

17

18

19

20

 

21

22

23

24

25

 

 

 

This assignment will be graded on the following:

 

30%     Algorithm is clearly pseudocode

                  {Isthe algorithm pseudocode or code in some specific language?}

15%     Algorithm follows specifications

                  {Doesthe algorithm correctly use the Sieve to find the prime numbers?}

20%     Correctness ofalgorithm

                  {Doesit find the prime numbers?}

20%     Correctness of the lineby line analysis for 'times'

                  {Iseach line correctly labeled for the number of times it will be executed?}

15%     Correctness of O-notation upper bound 

                  {Hasthe worst case performance been correctly determined?}