Algorithms 3027 Assignment 2 The University of Sydney 2019 Semester 1 School of Computer Science
Task 1: 1-dimensional case Description [5 marks]
• Concatenate both sets into a single list.
• Sort the list in increasing x order, breaking ties by ordering people before beds. • Set a counter to 0
• Iterate over the list:
– If the element is a person, increment the counter.
– If the element is a bed, add (bed name, counter) to the output.
Correctness [4 marks]
Every bed is visited (and thus output) during the loop. When a bed is visited, all people of size not larger than the bed have already been visited, but none that were larger than it, because of the ordering used. Therefore the counter is exactly the number of people compatibile with the bed. Therefore the output is correct.
Time Complexity [3 marks]
• The sort can be performed in O(n log n) (e.g. with mergesort)
• The loop takes O(n) time, because there are 2n iterations which take O(1) time each. • In total this is O(n log n)
Task 2a: 2-dimensional case (merge)
Description [13 marks]
I will prove a slightly more general algorithm, which will be more useful in task 2b.
• Input: P1, P2 are two lists of people; B1, B2 are two lists of beds; of total size 2n. • Preconditions:
– All beds in B1 are annotated with their compatiblity with all people in P1
– All beds in B2 are annotated with their compatiblity with all people in P2
– All lists are sorted in “increasing y, increasing x” order.
– No element in P1 ∪ B1 is strictly greater than any element in P2 ∪ B2 when considering “increasing x, people before beds” order.
• Output: Lists P, B of people and beds respectively, such that:
– P = P1 ∪ P2 and B = B1 ∪ B2 are sorted in “increasing y, increasing x” order
– All beds in B are annotated with their compatiblity with all people in P • Algorithm:
– Merge the sorted lists into a single sorted list in “increasing y, increasing x, people before beds” order (using the linear time merge shown in lectures).
– Set a counter to 0
– Let P, B be empty lists
1
– Iterate over the list:
∗ If it is a person from P1, append the person to P and increment the counter
∗ If it is a person from P2, append the person to P
∗ If it is a bed from B1, append the bed to B with compatibility unchanged
∗ If it is a bed from B2, append the bed to B with compatibility increased by the value of
the counter – Return P and B
Correctness [12 marks]
It is clear that the input to task 2a obeys the pre-conditions of this algorithm, and the output of this algorithm satisfies the requirements of task 2a. So we just need to prove that the algorithm works.
• Claim: P = P1 ∪ P2 and B = B1 ∪ B2 are sorted in “increasing y, increasing x” order. Proof:
– The input lists are in “increasing y, increasing x” order and each contains exclusively beds or people, therefore they are in “increasing y, increasing x, people before beds” order. Therefore, we can merge the lists in that order, in linear time with the merge part of the mergesort algorithm (shown in lectures).
– Every person and bed is visited in “increasing y, increasing x, people before beds” order, and is thus appended to P or B (as appropriate) in that order.
• Claim: All beds in B are annotated with their compatiblity with all people in P. Proof:
– The compatibility of a bed in B1 with people in P2 is zero.
∗ Subproof: Let b be any bed in B1 and p be any person in P2. No element of P1 ∪B1 can be greater than any element of P2 ∪B2, considering the order “increasing x, people before beds”. Therefore p(x) > b(x), which implies b is not compatible with p.
– Therefore the compatibility of beds in B1 is exactly the compatibility with the people in P1 (already known), which is the compatibility output by the algorithm.
– The overall compatibility of a bed in B2 is the compatibilty with the people in P2 (already known) plus the compatibility with the people in P1. By the definition of P1, B2 we know that for all p ∈ P1 , b ∈ B2 , it is the case that p(x) ≤ b(x). Therefore b is compatible with all elements p such that p(y) ≤ b(y). This is exactly the subset of P visited prior to visiting b, because we will visit in increasing y, increasing x, people first, order. Therefore the compatibility is the counter plus the existing compatiblity, which is the compatibility output by the algorithm.
Complexity [5 marks]
• Combine the lists in O(n). (There are 2n elements, and we can merge sorted lists in linear time).
• The loop takes O(n). (Each iteration is constant time (one comparison, one output, possibly one
addition), and there are 2n iterations).
• In total this is O(n) time.
Task 2b: 2-dimensional case (whole algorithm) Description [8 marks]
• Preprocess the data, by arbitrarily combining the lists into a single list of length 2n, which is then sorted by “increasing x, people before beds” order.
• Use this list as input to the following divide and conquer algorithm, which takes a single list of length N:
– If the list contains 1 person and 0 beds, return a list containing only that person, and an empty list. Otherwise:
– If the list contains 0 people and 1 bed, return an empty list, and a list containing only that bed (annotated with compatibility 0). Otherwise:
2
– Let P1,B1 be the result of applying this algorithm to the first ⌈N/2⌉ elements of the list.
– Let P2,B2 be the result of applying this algorithm to the remaining ⌊N/2⌋ elements of the
list.
– Return the two lists P, B resulting from applying P1, B1, P2, B2 to the generalised merge algorithm described in task 2a.
Correctness [10 marks]
Theorem:
The lists P,B returned by the algorithm contain all the people and beds from the input list, are
ordered in “increasing y, increasing x” order, and all beds in B are annotated with their compatibility with all the people in P.
Proof (by induction on the length of the input list):
• Let N denote the length of the (combined) list input to the recursive algorithm. • Base Case:
– Suppose N = 1, then there are two cases:
∗ Case 1: One person, no beds. The solution is a list P containing that person, and an empty list B.
∗ Case 2: No people, one bed. The solution is an empty list P, and a list B containing that bed with compatibility 0 (there are no people for it to be compatible with.)
– Lists with one or no elements are sorted by definition, and these lists are what the algorithm outputs. So the theorem holds for N = 1.
• Inductive hypothesis: Suppose the theorem holds for all instances of size N < k. • Inductive step:
– Consider an input list of size k > 1.
– The algorithm divides the input into two subproblems of size at most ⌈k/2⌉ < k. Therefore,
by the inductive hypothesis:
∗ P1, B1, P2, B2 are all ordered in “increasing y, increasing x” order ∗ All beds in B1 are annotated with their compatibility with P1
∗ All beds in B2 are annotated with their compatibility with P2
– Furthermore, because P1,B1 are based on input from the left (lower) half of a list split on “increasing x, people before beds” order, and P2, B2 are from the remaining portion of the list, and no part of these algorithms modify, introduce, or remove elements, we can deduce that no element in P1 ∪ B1 is greater than any element in P2 ∪ B2 (considering that ordering).
– Therefore P1, B1, P2, B2 satisfy all preconditions for the merge algorithm given in 2a
– Therefore P = P1 ∪ P2 and B = B1 ∪ B2 are sorted in “increasing y, increasing x” order, and
all beds in B are annotated with their compatibility with all the people in P. • Therefore, we can deduce by induction that the theorem holds for all N ≥ 1.
It is obvious that this algorithm can be used to solve the original problem, which has two lists of size n each, after trivially merging and then sorting them to create a list of length N = 2n to be used input to this algorithm.
Complexity [10 marks]
• Preprocessing step:
– Combining two lists of length n can be done in O(n)
– Sorting a list of length 2n can be done in O(2n log 2n) = O(n log n) (e.g. mergesort). • Divide and conquer algorithm:
3
– The input is divided into two subproblems of half the size (±1).
– The divide is just splitting a list at the midpoint, which can trivially be done in O(N) time.
– The merge is proven to take O(N) time in task 2a.
– Therefore we have the recurrence T(N) = 2T(N/2) + O(N), which we already know is Θ(N log N ) (this is the same recurrence as mergesort).
• The input to the divide and conquer algorithm has size 2n, so this takes Θ(2n log 2n) = Θ(n log n) • Therefore the overall time is O(n log n)
4