Marks. This assignment has in total 15 marks and is worth 15% of the total subject mark.

Objectives. To improve your understanding of the time complexity of algorithms and recurrence relations. To develop problem-solving and design skills. To improve written communication skills; in particular, the ability to present algorithms clearly, precisely, and unambiguously.

Difficulty. The number of * indicates the difficulty of a problem: (*) means a bit challenging, and (**) means very challenging. There is no (**)-problem in this assignment.

About Analysis.  When solving problems in this assignment, you can directly use  any known theoretical results that are taught in class as facts with no need to prove them. For example, you can claim sorting n integers can be done in O(n · log n) worst-case time without proofs.

Problem  1.   (2  Marks) Consider two English documents D1  and D2; denoted by S(D1) and S(D2) as the sets of English  words in them, respectively, where each word has O(1) length, i.e., each word consists of only a constant number of characters.

The similarity between D1 and D2 is defined as the Jaccard Similarity between the sets of words in them, i.e., S(D1) and S(D2). Specifically, the similarity between D1  and D2  is computed as:

Sim(D1,D2 ) = |S(D1) ∩ S(D2)|

For simplicity, we assume that the sets of words in D1 and D2 have the same size, namely, |S(D1)| = |S(D2)| . And we let n = |S(D1)| = |S(D2)| .

Design an algorithm to compute Sim(D1,D2 ) in O(n) expected time.  You will need to justify the time complexity of your algorithm with appropriate analysis.   [1 mark for the algorithm

and 1 mark for the analysis]

Solution.  In Lecture 17, we discussed hashing.  We can solve this problem by using universal

hashing.

We first insert each word in S(D1) into a hash table, which takes O(n) time. Define a counter sI . For each word in S(D2), we check if it is in the hash table. If it is in the hash table, sI  = sI + 1. Sim(D1,D2 ) can then be calculated as  = 2nsI . To check if a key exists in a hash

table take expected O(1) complexity, so the total complexity for n keys is expected O(n).

Problem 2.  (2 Marks) Consider an undirected connected graph G = ⟨V,E⟩ with n nodes and m edges; define a special source node s ∈ V in the graph G.  Describe a data structure which can achieve the following:

• the data structure can be constructed in O(n + m) worst-case time;

• the space consumption of the data structure (excluding the graph G) is O(n) in the worst case;

• for any query node q ∈ V other than s, it can report the shortest distance between s and q in the graph G in O(1) worst-case time, where the shortest distance between s and q is defined as the length, (i.e., the number of edges) of the shortest path from s to q in G.

You will need to justify the above complexities of your algorithm with appropriate analysis.   [1 mark for data structure and the algorithm, and 1 mark for the analysis]

Solution.   In Lecture 8, we discussed the Breadth First Search  (BFS) algorithm to traverse a graph. We can run a modified BFS algorithm on graph G starting at node s to obtain the shortest distances between s and all the other nodes v  ∈  V .  We can use an array with size n to store those distances, where the index of the array is the node’s IDs.  The modified BFS based on the pseudocode in the slides is described below:

• initialize an array A with size n; A[s] ← 0;

• mark every node in V as unvisited; initial a queue Q;

• Q.enqueue(s); mark s as visited

• while Q is not empty, do the following:

·  u ← Q.dequeue();

·  for each u’s unvisited neighbor v ,

·  Q.enqueue(v); mark v as visited; A[v] = dist[u] + 1;

The space of array A is O(n), and the BFS can be done in O(n + m). When given a query node q , we can obtain its shortest distance between q and s by reading A[q] in O(1).

Problem 3.  (*)(3 Marks) Consider the following problem:

Given an (unsorted) sequence S of n integers from a constant-size universe {1, 2, . . . , 100} (i.e., the universe size is 100, a constant), find the longest strictly ascending sub-sequence (not necessarily contiguous) of integers from the original sequence S such that all these integers in this sub-sequence are in a strictly ascending order.

For example, consider the following sequence of integers:

S = {1, 20, 14, 7, 9, 30, 77, 15, 20, 60} ,

where  s1   =  {1, 20, 30, 77}  and  s2   =  {1, 7, 9, 15, 20, 60}  are two possible  strictly  ascending  sub- sequences  of S .   While there exist more other strictly ascending sub-sequences of S, it can be verified that s2  is the longest strictly ascending sub-sequence of S .

You are asked to design an algorithm that can solve the above problem in O(n) worst-case time. You will need to justify the time complexity of your algorithm with appropriate analysis.  [2 marks for the algorithm and 1 mark for the analysis]

Solution. We solve this problem by dynamic programming (Lecture 18).

Define L(i,cap) as the length of the longest strictly ascending sub-sequence of the first i integers that are less than cap.

Then, we have the following optimality structure:

L(i,cap) = max{L(i − 1,vi) + 1,L(i − 1,cap)}         if vi  < cap

L(i,cap) = L(i − 1,cap)        if vi  ≥ cap

And the base case is L(0, · ) = 0. Our goal is to obtain L(n,101).

To achieve this, we can initialize a table of n rows and 101 columns, where the value in the ith row and the jth  column corresponds to L(i,j).

We can simply calculate the value of every cell in this table row-by-row.  Clearly, for the first row, L(1,j) = 0 for all j ≤ v1  and L(1,j) = 1 for all j > v1 . For the second row, by recurrence, we have:

• for all j ≤ v2 , L(2,j) = L(1,j), each of which can be obtain in O(1) time;

• for all j > v2 , L(2,j) = max{L(1,v2 )+1,L(1,j)}; as all the values in the first row are already computed, each of this value can be obtained in O(1) time.

Since the cell in the ith  row only depends on the values in the (i − 1)th  row in the table, and when computing the values in row i, all these values in row (i − 1) are computed, each value in row i can be obtained in O(1) time.  Moreover, as there are only 101 = O(1) columns, the computation for each row is O(1). And there are n rows, the overall time complexity is bounded by O(n).

After computing the table, L(n, 101) is the length of the longest strictly ascending sub-sequence. To obtain the actual sub-sequence with respect to this length, we can “backtrack” the computation of L(n, 101) by going through the table.   Specifically, if we choose to take vi  when considering L(i,cap) for some cap, record this value.

Therefore, the actual longest strictly ascending sub-sequence can be obtained in O(n) time after the table is constructed.

Problem 4.  (8 Marks) Consider a set S of n integers; given a query integer q, the predecessor of

q in S is defined as the largest integer in S that is no more than q . For example, consider S = {1, 14, 7, 9, 30, 77, 15, 20, 60} ;

the predecessor of q = 7 in S is 7, and that of q = 28 in S is 20.

By symmetry, the successor of q in S is defined as the smallest integer in S that is no less than q . Continuing to the previous example, the successor of q = 7 in S is still 7, and that of q = 28 in S is 30.

•  (a) Design a data structure that achieves the following:

– it can be constructed in O(n · log n) worst-case time;

– it consumes O(n) worst-case space;

– it can find the predecessor in S for every given query integer q in O(log n) worst-case time.

You will need to describe:  (i) the data structure,  (ii) the construction algorithm of the data structure, (iii) the predecessor query algorithm of the data structure; and you will also need to justify the construction time complexity, space consumption and query time complexity of your data structure with appropriate analysis.  [1 mark for the data structure, 1 mark for the algorithm, and 1 mark for the analysis]

•  (b) Suppose that you have a data structure that meets the requirements in Problem (a). More- over, in addition to the predecessor queries, suppose also that your data structure can find the successor in S for every given query integer q in O(log n) worst-case time.

Describe an algorithm with the above data structure such that, given any range [a,b] with integers a < b, it can report all the integers x in S such that a ≤ x ≤ b, in O(k + log n) time in the worst case, where k is the number of integers in S that are in the range [a,b]. You will need to justify the time complexity of your algorithm with appropriate analysis.

Continuing the previous example, given a range [4, 19], you algorithm should report {7, 9, 14, 15} as they are the integers in S that are in the given range.  [1.5 marks for the algorithm and 1.5 marks for the analysis]

•  (c) Further strengthen (if necessary yet still with O(n) worst-case space) the data structure in Problem (b), and describe an algorithm such that given any range [a,b] with integers a < b, it can return the number of integers in S that are in the range [a,b], in O(log n) time in the worst case. You will need to justify the time complexity of your algorithm with appropriate analysis.

Continuing the example in Problem (b), your algorithm should return 4 for the range [4 , 19] as there are 4 integers in S in this range.   [1 mark for the algorithm and  1 mark for the analysis]

Solution.

(a) We  can  store the  elements  in  an  array  and  apply  merge  sort  (Lecture  11),  which takes

O(nlog n) time complexity and O(n) space.   To get the predecessor of a query integer q in S, we can use a slightly modified binary search (Lecture 4).  The idea is when we cannot find the key (when lo > hi), we return the index hi which will refer to the largest integer smaller than the key.

function FindPredecessor(A,lo,hi,key)

if lo > hi then return hi

mid ← lo + (hi − lo)/2

if A[mid] = key then return mid

else

if A[mid] > key then

return FindPredecessor(A,lo,mid − 1,key)

else

return FindPredecessor(A,mid + 1,hi,key)

The whole algorithm can then be done in the steps below:

– if a < A[0], the predecessor does not exist in S .

– otherwise, return A[FindPredecessor(A,0,n − 1,a)]

The complexity of FindPredecessor is the same as a binary search which takes O(log n).

(b) We use the same data structure (sorted array) for Problem (b).  FindSuccessor is similar to

FindPredecessor, but we return the index lo when the key is not found.  The algorithm can then be done in the steps below:

– if a > A[n − 1] or b < A[0], return an empty array

– if a < A[0],start = 0, otherwise start = FindSuccessor(A,0,n − 1,a)

– if b > A[n − 1],end = n − 1, otherwise end = FindPredecessor(A,0,n − 1,b)

– get elements from index start to index end in array A.

The first step takes O(1). The second and third steps take O(log n) as the same in Problem (a). In terms of the third step, it scans only the elements that satisfy a ≤ x ≤ b, which takes O(k). Therefore, the total complexity is O(k + log n).

(c) We can modify the algorithm in (b) to solve Problem (c). In the last step, instead of getting elements from index start to index end, we return end−start+1, which takes O(1). Without scanning the k elements, the total complexity is O(log n).

Submissions

You should lodge your submission for Assignment 2 via the LMS (i.e., Canvas).   You must iden- tify  yourself in  your file.  Poor-quality scans of solutions written or printed on paper will not be accepted. There are scanning facilities on campus, not to mention scanning apps for smartphones etc. Solutions generated directly on a computer are of course acceptable. Submit one file:

• A assignment2.pdf file, comprising your solutions to the questions in the assignment.

Administrative Issues

When is late? What do I do if I am late? The due date and time are printed on the front of this document. The late penalty for non-exam assessment is two marks per day (or part thereof) overdue. Requests for extensions or adjustments must follow the University policy (the Melbourne School of Engineering “owns” this subject), including the requirement for appropriate evidence.

Late submissions should also be lodged via the LMS, but, as a courtesy, please also email the subject coordinator, Junhao Gan, when you submit late.  If you make both on-time and late sub- missions, please consult the subject coordinator as soon as possible to determine which submission will be assessed.

Individual  work.   You are reminded that your submission for this Assignment is to be your own individual work.  Students are expected to be familiar with and to observe the University’s Academic Integrity policy http://academicintegrity.unimelb.edu.au/.   For the purpose of ensuring academic integrity, every submission attempt by a student may be inspected, regardless of the number of attempts made.

Students who allow other students access to their work run the risk of also being penalized, even if they themselves are the sole authors of the submission in question.  By submitting your work electronically, you are declaring that this is your own work.  Automated similarity checking software may be used to compare submissions.

You may re-use code and materials provided by the teaching staff, and you may refer to resources on the Web or in published or similar sources.  Indeed, you are encouraged to read beyond the standard teaching materials.  However, all such sources must be cited fully and, apart from code and materials provided by the teaching staff, you must not copy code or any materials.