Question

Provide pseudo-code to compute the difference of two sets, S - T, using:

a. sets represented by linked-lists of characters.

b. sets represented by bit strings. (hint - what is "exclusive or?")

Answer 1

If the sets are represented as sorted linked lists. The running time is O(|S|+|T|)O(|S|+|T|).

We don't need to compare every element of AA against every element of BB, pairwise. That would lead to a runtime of O(|S|×|T|)O(|S|×|T|), which is much worse. Instead, to compute the symmetric difference of these two sets, we can use a technique similar to the "merge" operation in mergesort, suitably modified to omit values that are common to both sets.

In more detail, we can build a recursive algorithm like the following to compute S∖TS∖T, assuming SS and TT are represented as linked lists with their values in sorted order:

1. difference(S, T):
2.     if len(T)=0:
3.         return S
4.     if len(S)=0:
5.         return S
6.     if S[0] < T[0]:
7.         return [S[0]] + difference(S[1:], T)
8.     elsif S[0] = T[0]:
9.         return difference(S[1:], T[1:]) # omit the common element
10.     else:
11.         return [T[0]] + difference(S, T[1:])

Thank you.