Lecture Notes for SE 598, Data Structures and Algorithms

26 July 2000, Set and Multiset Applications

1. the seive of eraosthenes

   1. a prime number p has only itself and 1 as factors - prime numbers are important for cryptography

   2. problem - find all the prime numbers in the set { 2, 3, ..., n } for some integer n

   3. the greek mathematician eraosthenes solved this in 300 b.c.e.

      1. put 2 through n in s

      2. find the smallest integer i in s - i must be prime

      3. remove from s all multiples of i - n/i iterations

      4. repeat the previous two steps with the next smallest integer in s

      5. keep repeating until there is no next smallest integer in s

      6. everything left in s is prime

         1. static void sieve(int n) {
            
              set s;
              for (int i = 2; i <= n; i++)
                s.insert(i);
            
              for (set::iterator p = s.begin(); p != s.end(); p++)
                for (int i = (*p)*2; i <= n; i += *p)
                  s.erase(i);
            
              copy(s.begin(), s.end(), ostream_iterator(cout, " "));
              cout << "\n";
              }
            

2. histograms

   1. assume a set s of values defining a range (min, max)

   2. a histogram partitions the range into equally spaced (usually) subranges

   3. each subrange contains the values of s

   4. the count of values in each subrange is plotted against the subrange min and max - a bar graph

   5. n-tile ranges in statistics.

      1. static void hist(const set<double> & ds, int n) {
         
           if (ds.size() < 1) return;
         
           const double 
             min = *(ds.begin()),
             max = *--ds.end(),
             range = (max + 0.1) - min,
             subrange = range/((double) n);
           
           vector<set<double> > buckets(n);
           for (int i = 0; i < n; i++)
             buckets.push_back(set<double>());
         
           for (set<double>::iterator i = ds.begin(); i != ds.end(); i++)
             buckets[(int) ((*i)/subrange)].insert(*i);
           }
         

This page last modified on 25 July 2000.