i. Show the compressed trie containing the strings "soup", "salad", "sorbet"and "saltines".[6 marks] ii. Show the suffix tree for the string "bandana". (b) Describe the hash function commonly used in the Rabin-Karp “rolling hash"method for string matching, and what makes it suitable for this purpose (i.e.,in which sense it can be used for a "rolling" hash and how).[8 marks] (c) The SUBSET SUM problem is the following: Given an input of ʼn integers X = {₁,...,} and a target integer t, determine whether there is a subset S of X such that the sum of the numbers in S equals t. Describe a dynamic programming algorithm for SUBSET SUM and state the running time of your algorithm.[8 marks] (d) SUBSET SUM is NP-complete, which in particular means that every known algorithm for the problem needs exponential time in ʼn in the worst case. How is this consistent with the existence of a dynamic programming algorithm a sin Question 3c?[6 marks]