Problem 4: Let S = {s1, s2, . . . , sn} and T = {t1, t2, . . . , tm}, n ≤ m, be two sets of integers. (i) Describe a deterministic algorithm that checks whether S is a subset of T. What is the running...

Problem 4: Let S = {s1, s2, . . . , sn} and T = {t1, t2, . . . , tm}, n ≤ m, be two sets of integers.

(i) Describe a deterministic algorithm that checks whether S is a subset of T. What is the running time of your algorithm?

(ii) Devise an algorithm that uses a hash table of length n to test whether S is a subset of T. What is the expected running time of your algorithm?