Lecture Notes for SE 598, Data Structures and Algorithms

26 July 2000, Set and Multiset Algorithms

1. set union

   1. union(A, B) - the elements in either A or B

   2. set union - { x | x in A or x in B }

   3. multiset union -

      1. { x | x in A or x in B }

      2. x # union(A, B) = x # A + x # B

   4. the union algorithm is based on merging - sorted lists

      1. set

         1. template 
            static void set_union(const Set & A, const Set & B, Set & AuB) {
            
              Set::iterator ai = A.begin();
              Set::iterator bi = B.begin();
            
              while (ai != A.end() && bi != B.end())
                if (*ai < *bi)
                  AuB.insert(*ai++);
                else {
                  AuB.insert(*bi++);
                  if (*ai == *bi) ai++;
                  }
            
              AuB.insert(ai, A.end());
              AuB.insert(bi, B.end());
              }
            

      2. multiset

         1. template 
            static void multiset_union(const Set & A, const Set & B, Set & AuB) {
            
              Set::iterator ai = A.begin();
              Set::iterator bi = B.begin();
            
              while (ai != A.end() && bi != B.end())
                if (*ai <= *bi)
                  AuB.insert(*ai++);
                else
                  AuB.insert(*bi++);
            
              AuB.insert(ai, A.end());
              AuB.insert(bi, B.end());
              }
            

2. set difference

   1. difference(A, B) - the elements in either A but not in B

   2. set difference - { x | x in A and x not in B }

   3. multiset difference

      1. { x | x in A and x not in B }

      2. x # difference(A, B) = max(x # A - x # B, 0)

   4. the difference algorithm is based on merging - sorted lists

      1. set

         1. template 
            static void set_difference(const Set & A, const Set & B, Set & AdB) {
            
              Set::iterator ai = A.begin();
              Set::iterator bi = B.begin();
            
              while (ai != A.end() && bi != B.end())
                if (*ai < *bi)
                  AdB.insert(*ai++);
                else if (*ai == *bi) {
                  ai++;
                  bi++;
                  }
                else
                  bi++;
            
              AdB.insert(ai, A.end());
              }
            

      2. multiset - same as set

3. majority

   1. Given a multiset S, an element x of S is the majority of S if S.count(x) > S.size()/2

   2. sort and count - expensive

   3. find the median value, then count - cheaper

   4. reduce the problem to a simpler one

      1. pick x and y from S

      2. if x != y then throw them both out

      3. if (x == y, then they may be in the majority; remember them

      4. when S is empty

         1. if there are no majority candidates, there is no majority

         2. if there is a majority candidate, count the occurrences in S

This page last modified on 26 July 2000.