Due Friday 29th of September at 6pm Sydney time  (week 3)

In this assignment we review some basic algorithms and data structures, and we apply the divide- and-conquer paradigm.  There are three problems  each worth 20 marks, for a total of 60 marks. Partial credit will be awarded for progress towards a solution. We’ll award one mark for a response of “one sympathy mark please” for a whole question, but not for parts of a question.

Any requests for clarification of the assignment questions should be submitted using the Ed forum

We will maintain a FAQ thread for this assignment.                                                                        .

For each question requiring you to design an algorithm, you must justify the correctness of your algorithm.  If a time bound is specified in the question, you also must  argue that your algorithm meets this time bound.  The required time bound always applies to the worst case  unless otherwise specified.

You must submit your response to each question as a separate PDF document on Moodle.  You can submit as many times as you like. Only the last submission will be marked.

Your solutions must be typed, not handwritten. We recommend that you use LaTeX, since: .  as a UNSW student, you have a free Professional account on Overleaf, and

. we will release a LaTeX template for each assignment question.

Other typesetting systems that support mathematical notation (such as Microsoft Word) are also acceptable.

Your assignment submissions must be your own work.

. You may make reference to published course material (e.g. lecture slides, tutorial solutions) without providing a formal citation. The same applies to material from COMP2521/9024.

. You may make reference to either of the recommended textbooks with a citation in any format.

. You may reproduce general material from external sources in your own words, along with a citation in any format.  ‘General’ here excludes material directly concerning the assignment question. For example, you can use material which gives more detail on certain properties of a data structure, but you cannot use material which directly answers the particular question asked in the assignment.

. You may discuss the assignment problems privately with other students.  If you do so, you must acknowledge the other students by name and zID in a citation.

.  However, you must write your submissions entirely by yourself.

– Do not share your written work with anyone except COMP3121/9101 staff, and do not store it in a publicly accessible repository.

– The only exception here is UNSW Smarthinking, which is the university’sofficial writing support service.

Please review the UNSW policy on plagiarism. Academic misconduct carries severe penalties.

Please read the Frequently Asked Questionsdocument, which contains extensive information about these assignments, including:

.  how to get help with assignment problems, and what level of help course staff can give you

. extensions, Special Consideration and late submissions

.  an overview of our marking procedures and marking guidelines

.  how to appeal your mark, should you wish to do so.

Question 1 Asymptotics

Read about asymptotic notation in the review material and determine if f(n) = O(g(n)) org(n) = O(f(n)) or both (i.e., f(n) = Θ(g(n))) or neither of the two, for the following pairs of functions. Justify your answers.

[A] [5 marks]

f(n) =^6n2 − n;    g(n) = log2（n5）

[B] [5 marks]

f(n) = n;    g(n) = (sin(πn) + cos(πn))n

[C] [5 marks]

f(n) = 4n2 log2 (n);    g(n) = (n!)n

[D] [5 marks]

f(n) = n2−cos(πn);    g(n) = n√n

You might find L’Hˆopital’s rule useful:  if f(x), g(x) → ∞ as x → ∞ and they are differentiable, then

x = x .

Remember that when dealing with asymptotics in computer science, we only care about integer values of n (input sizes are integers).

Question 2 Convenience Store

Serge owns and runs a convenience store where he purchases items from m different manufacturers and resells them to his customers.   Each  manufacturer  sells  items  up  to  n  at  a time.   When buying in bulk from a manufacturer, Serge receives a discount.  To find out the cost per item when purchasing i items at a time from manufacturer k, Serge can ask for a quote from the manufacturer, denoted Q(i,k).  The manufacturers will give each quote in constant time, but if Serge asks for more than ⌈log2 n⌉ quotes from the same manufacturer, he will be blocked for spam and shunned from the business community forever.  It is never more expensive to purchase more items from a single manufacturer (that is, Q(i,k) ≥ Q(j, k) for all manufacturers k and all quantities of items i < j).

Serge also has an array S[1..m], where S[k] is the price he sells the items from manufacturer k for in his shop.

Serge can sell items for a profit whenever the cost he pays per item is cheaper than the price he sells them for in his shop.   Serge is interested in determining the smallest number of items he needs to buy from each manufacturer in order to sell the items for a profit.  For each manufacturer 1 ≤  k ≤  m, we denote this quantity M[k].  That is,  M[k] is the smallest number of items that Serge must buy from manufacturer k in order to sell the items for a profit. For all manufacturers, Q(n,k) < S[k], so it is always possible for Serge to make a profit.

2.1    [6 marks] Serge is interested in purchasing from a particular manufacturer k.  Design an algorithm that determines the smallest number of items Serge needs to purchase from manufacturer k in order to sell them for a profit, without asking for more than  ⌈log2 n⌉ quotes.

Example: Suppose manufacturer  k sells 1 item for s2, 2 or 3 items for s1.50 each, and 4 items for s1.25 each. That is, Q(1, k) = $2, Q(2, k) = Q(3, k) = $1.50 and Q(4, k) = $1.25. Serge sells items from manufacturer k for s1.75 each (S[k] = $1.75). The smallest number of items Serge needs to sell to make a profit is 2, so M[k] = 2.

Q(i,k) gives the cost per item when i items are purchased from manufacturer k, and S[k] is the price Serge can sell the items for.

2.2    [14 marks] Each of Serge’s m manufacturers does not produce items of the same quality. In fact, Serge has numbered them in increasing order of quality, so manufacturer 1 produces the lowest quality items and manufacturer m produces the highest quality items.  Serge knows for a fact that when purchasing items from a higher quality manufacturer, he needs to purchase the same or fewer items to sell them for a profit. That is, if k > l, then M[k] ≤ M[l].

Serge would like to compute M[k] for all m manufacturers.  Serge has realised that it is possible to use your method from Q2.1 on each of the m manufacturers for a total time complexity of O(mlog n), but has decided that this is not fast enough.

Assuming m < n, design an algorithm that runs in O(n) time to determine the smallest number of items Serge needs to buy from each manufacturer in order to sell the items for a profit while asking each manufacturer for at most ⌈log2 n⌉ quotes.

Your algorithm should use the fact that M[k] ≤ M[l] for all manufacturers k > l.

Question 3 In the Night  Garden

Alice is planting n1  flowers f1 ,..., fn1   among n2  rectangular gardens G1 , . . . , Gn2 .  Bob’s task is to determine which flowers belong to which gardens.  Alice informs Bob that no two gardens overlap; therefore, if a flower belongs to a garden, then the flower belongs to  exactly  one garden and a garden can contain multiple flowers.  If a flower fi  does not belong to any garden, then Bob returns an undefined garden for fi.

Each garden Gi  is given by a pair of points GBL [i] and GTR [i], representing the bottom left and top right corners of the garden respectively. Each flower is represented by a point F[i] representing its location. Let n = n1 + n2 .

A  collection of n1  = 5 flowers  and n2  = 4 gardens.

More formally, you are given three arrays: . GBL = [(x1 , y1 ), . . . , (xn2 , yn2 )], where GBL [i] = (xi , yi ) represents the bottom left point of garden Gi , . GTR =  [(x1 , y1 ), . . . , (xn2 , yn2 )], where GTR [i] = (xi , yi ) represents the top right point of garden Gi , and . F = [(x1 , y1 ), . . . , (xn1 , yn1 )], where F[i] = (xi , yi ) represents the location of flower fi. You are not guaranteed that a flower belongs to a garden; it is possible that a flower is planted in none of the gardens. Your goal is to return the garden that a flower fi belongs to (if any), for each fi. . For example, in the diagram above, if the flower ordering is sorted by its x-coordinate and the rectangular gardens are sorted by their x-coordinate of GBL , then we return f1 : G1 , f2 : G2 , f3 : G2 , f4 : G4 , f5 : G3 . Your output can be in any form (e.g. array, list, set, dictionary), so long as you maintain the correct pair of flowers and gardens.

3.1    [12 marks] We first solve the special case where all of the gardens intersect with a horizontal line. Design an O(nlog n) algorithm to determine which flowers belong to which gardens (if such a garden exists).

A  collection of n1  = 6 flowers  and n2  = 4 gardens  that  intersect  with  a horizontal line.