Objectives

To improve your understanding of the time complexity of algorithms and data structures. To design com- putational solutions to problems and develop problem-solving skills. To improve written communication skills; in particular the ability to present algorithms clearly, precisely and unambiguously.

Scenario

In this assignment we will consider the following scenario.  Information about hiking trails is stored on a server and is frequently queried by hikers and trail maintenance team.  The queries are sent as search queries from a website.  You are designing the backend for storing and retrieving this information in a useful form.  Your goal is to design algorithms and ways to store trail information in order to answer queries efficiently to ensure that hikers are not strangled in the woods waiting for their web-query to return.

Each hiking trail has a distance, a difficulty level and is associated with a unique number. Each hike spans either one or more regions. Each region is also associated with a unique number.

Notes:

● You can start working on problems 1, 2 and 3 in any order as they are independent of each other.

● For every pseudo-code question, for every variable you define, clearly comment what it is used for.

● If you make use of a function, you need to either define it or refer to where in lectures or textbook it is defined and what is its complexity. You need to explain what it does, what are its inputs and outputs.

1    Hike Search [8 points]

The system stores all trail intersections as a list of tuples T where each tuple is of the form (k, j) where k and j are trail numbers. Numbers in each tuple and T appear in arbitrary unspecified order.

To plan hikes, users are interested in finding what other trails a given trail i crosses with. A naive way to implement this function would be to do a linear scan for i. Since hike searches are frequent, you want to optimise the performance by precomputing the answers and storing them in auxiliary data structures.  Your task in this question is to come up with an implementation of function  CRossEs(i) that, in constant time, returns a list C of all the trails that trail i crosses with.  Your solution should consist of preprocessing and creating data structures that can be queried later by  CRossEs(i),  for any trail number i. That is, you need to write two functions PREpRocEss(T ) and CRossEs(i) where CRossEs(i)

can query data structures created by PREpRocEss(T ). You can assume that PREpRocEss(T ) would be called before any queries to CRossEs(.).

You can use l T  to denote the length of T and ntrails to denote the number of trails. You can assume that trail numbers are sequential, start at 0, and that only valid trail numbers will be used to query your function.

1.  [2 point] Describe your solution in English.  ( ≈ maximum of 2-3 sentences/lines)

2.  [2 point] What is the time complexity of PREpRocEss(T ) and CRossEs(i)?

3.  [4 points] Now write the pseudo-code of both functions.  A solution with non-optimal complexity may receive partial marks. Note:  You can use notation for t f T to iterate over tuples in T and use t.k and t.j to refer to trail numbers stored in tuple t.

2    Cross-Regional Hiking [14 points]

Trails often span across multiple regions. This information is currently stored in an array L where L[r] is an array of trails that go across region r , r f [0, nregions _ 1] and nregions is the number of regions.

This question is split in Part A (4 subtasks) and Part B (2 subtasks). You can work on Part A and Part B in any order.

Part A   The next 4 subtasks relate to the following pseudo-code where Q is an array of region numbers in unspecified order. You can assume that insert(. . .), update(. . .) and length(. . .) below can be answered in constant time.

function FUNcT1oNx(L, Q)

l - [] // empty list of tuples where each tuple is of the form (first, second)

for i f L[Q[0]] do // go over each element in L[Q[0]]

l.insert((i, 0)) // insert a tuple where first element is i and second is 0

for q f Q do

for i f L[q] do

for t f l do

if t.first = i then

l.update((t.first, t.second + 1)) // update the tuple t in l

s - [] // empty list

for t f l do

if t.second = length(Q) then

s.insert(t.first)

return s

1.  [1 point] Let L be [[1, 2, 3], [1, 2], [1, 2, 3, 5, 6, 8], [1, 8, 6, 10, 21], [1, 4, 6, 9]]. Give an instance of Q that includes region 3 (i.e.,  [1,8,6,. . . ]) and is of length 3, on which FUNcT1oNx would have the best performance.

2.  [1  point] Assuming same constraints as in the above subtask, give an instance of Q on which FUNcT1oNx would have the worst performance.

3.  [2 points] Briefly describe, in no more than 3 sentences, the functionality of the above pseudo-code.

4.  [2 points] Briefly describe how you would optimise the above code and what would the performance improvement be.  ( ≈ maximum of 3-4 sentences/lines)

Part  B   You want to help hikers to search across trails with region information.   For the next two subtasks below, you are asked to

(i) provide a brief (1-2 sentences) explanation in English of your solution

(ii) write pseudo-code for each of these functions

(iii) indicate the time complexity of your functions with a one sentence justification

There are naive ways to implement these functions in O((nregions × ntrails)2 ) .  Full marks would be awarded for more efficient solutions .

5.  [3 points] spANMosT(L) Return a trail that passes most number of regions. If there is more than one, return the one with the smallest trail number.

6.  [5 points] D1scoNNEcTEp(L) Return a region that cannot be reached from any other region as no trail goes outside of it. If there is more than one, return the one with the smallest region number.

3    Maintaining Trails [8 points]

Hikes need to be maintained as the more people visit them the more their conditions deteriorate. At the end of each day, smart meters installed at each trail send the number of hikers who have gone through each trail.  The information for day d is sent to you as a list of tuples Ud  where each tuple is of the form (i, h) where i is a trail number and h is the number of hikers who travelled on i today.  The order in Ud  is arbitrary and not specified while the size of Ud  differs day to day. For this part, you can assume that there are ntrails trails numbered from 0 to ntrails _ 1.

Occasionally, the maintenance team sends a query asking for the number of the most travelled trail (if there is more than one, ties are broken arbitrarily). After the query, this trail is repaired.

You propose to support the above query by maintaining the following max-heap H .  Each node in the heap represents a trail and stores a counter of the number of hikers since last maintenance of that trail.  The heap is updated everyday based on information in Ud .  The most-travelled trail can be easily retrieved as it is the root node of the heap. When the maintenance query is sent, the counter of root node is reset to 0 and the heap needs to be “repaired” .

1.  [4 points] Describe an efficient way to update the heap H given Ud .  Write pseudo-code of your solution UppATEHEAp(H, Ud). A solution with non-optimal complexity may receive partial marks.

2.  [4 points] Your colleague argues that using a max-heap is inefficient, and suggests to keep an array of counters indicating the number of hikers since last maintenance of each trail and update it every day using Ud . On each maintenance query, the array is scanned to find the most-travelled trail and its counter is then reset to 0.

Let ld  denote the size of Ud .  Indicate the time complexity of your approach and your colleague’s approach, on the following two operations, respectively:

(a) Update the data structures upon receiving Ud

(b)  Process a maintenance query (i.e., return the most travelled hike since last repair, reset its

counter to 0 and update the corresponding data structures)

Which approach would you prefer? Briefly justify your answer.