COMS30041 Advanced Algorithms 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
January/February 2022
Faculty of Engineering
Examination for the Degrees
of
Bachelor of Science
Master of Engineering
COMS30041
Advanced Algorithms
1. Suffix tree/array question:
(a) (6 points) Draw the compact suffix tree for the string “bookkeepee” .
(b) (2 points) How many leaves, internal nodes and edges does the compact suffix tree of the string “bookkeepee” have?
(c) (4 points) A repeat in string S is a substring of S that occurs at least twice in S. A repeat is maximal if it occurs in at least two locations where it is not extensible on either side. That is if you were to extend it to the right or left it would no longer be a repeat. Which parts of its compact suffix tree do the maximal repeats of the string “bookkeepee” correspond to and what are those maximal repeated substrings?
(d) (2 points) What is the suffix array of “mississippis”? Recall that the string “ab” islexicographically earlier than the string “abc” .
(e) (2 points) Consider the linear time construction algorithm for suffix arrays called the DC3 method. In this algorithm we first look at the indices that are non-zero mod 3. For the string “mississippis”, what is the suffix array of the suffixes corresponding to indices that are non-zero mod 3?
(f) (4 points) For the string S =“mississippis”, assume that we are given the suffix array of the suffixes corresponding to indices that are non-zero mod 3. Show how in the DC3 algorithm we can in linear time find the ordering of the suffixes whose indices are 0 mod 3.
2. (a) Consider a set H = {h1 , h2 } of hash functions. Each function in H maps a key from the set {1, 2, 3, 4} to a hash value in {1, 2, 3}. The explicit definitions of the hash functions are given below:
h1 (1) = 4, h2 (1) = 2
h1 (2) = 3, h2 (2) = 1
h1 (3) = 2, h2 (3) = 3
h1 (4) = 2, h2 (4) = 3
i. (2 points) What is the probability that h(1) = h(4), i.e. Pr(h(1) = h(4)), when h is picked uniformly at random from H?
ii. (2 points) Is H a weakly universal set of hash functions? Justify your answer.
(b) (4 points) Suppose that we have a set of n fixed keys from a universe U . We want to be able to look up these keys in constant time and O(n) space using the static perfect hashing scheme of Fredman, Koml´os & Szemer´edi. Describe how to achieve this. You may assume that we have access to a weakly universal set of hash functions h : U → {0,..., n − 1}.
(c) Consider the following variant on cuckoo hashing where we use two tables T1 and T2 of the same size and hash functions h1 (x) = x mod 4 and h2 (x) = 2x mod 4.
. Both tables have size 4.
. The hash function h1 is used to insert elements into T1 and hash function h2 is used to insert elements into T2 .
. When inserting a new key x, we first try to put x at position h1 (x) in T1 . If this leads to a collision, then the previously stored key y is moved to position h2 (y) in T2 .
. If this leads to another collision, then the next key is again inserted at the appropriate position in T1 , and so on.
At the start T1 = (4, 
, 14, 
) and T2 is empty (underscore indicates that entry is currently empty). i. (2 points) What is the result of inserting 12 and 10 into the hash table.
ii. (2 points) If 12 is inserted first into the initial tables as given in this question, what is the smallest non-negative key that causes a potentially infinite loop if inserted after 12?
(d) (2 points) What are the space requirements for a van Emde Boas tree in terms of the size of the universe u?
(e) (2 points) If one were to really create a van Emde Boas tree that used this much space, what is the smallest number n of integers the tree would have to contain so that insert, lookup and delete
operations took Θ(log log u) time (where u is the universe size).
(f) (4 points) Construct a Cartesian tree for the input 1 , 7, 3, 0, 8, 2.
3. (a) (8 points) For this question we will use only weighted, undirected graphs. In graph theory, the Hamiltonian Cycle problem for a graph G asks if there exists a cycle in G that passes through each vertex in G exactly once. A cycle is a path that start and ends at the same vertex. This problem is known to be NP-complete and we therefore assume for the purposes of this question that there is no polynomial time solution for it.
The Travelling Salesman Problem asks us to find the shortest distance tour (or cycle) that passes through each vertex of the graph exactly once.
Given a weighted undirected graph G, we say that G satisfies the triangle inequality if for all connected vertices i,j,k , wi,j ≤ wi,k + wk,j .
This question asks you to give a proof of the following statement by showing a reduction from Hamiltonian Cycle. “Assuming P
NP, then for any constant ρ ≥ 1, there is no polynomial time ρ-approximation for the Travelling Salesman Problem that applies to all graphs without the triangle inequality.”
To start you off in the reduction, let G′ = (V, E′ ) be the complete graph of V , so that every vertex is connected to every other vertex. We will assign weights to the edges in E′ as follows:
Consider the travelling salesman problem with this new graph:
APPROX-TSP(G′ )
By choosing a suitable value for the blank box above together with this new graph, give a proof of the claim.
(b) (6 points) Show how in polynomial time we can transform any instance of the travelling salesman problem on a graph which does not satisfy the triangle inequality into another instance whose edge weights do satisfy the triangle inequality. The two instances must have the same set of optimal tours.
(c) (6 points) Explain why such a polynomial time transformation does not contradict the statement in the first part of this question, assuming P ≠ NP.
2024-01-04