math代写|算法代写|algorithm代写 : 典型的一个算法代写题目
1. [15 marks] Consider the following data structure for representing a set. The elements of the set are
stored in a singly linked list of sorted arrays, where the number of elements in each array is a power
of 2 and the sizes of all the arrays in the list are different. Each element in the set occurs in exactly
one array. The arrays in the linked list are kept in order of increasing size.
To perform SEARCH, perform binary search separately on each array in the list until either the desired
element is found or all arrays have been considered.
To insert a new element x into the set (given the precondition that x is not already in the set),
create a new array of size 1 containing x
insert this new array at the beginning of the linked list
while the linked list contains 2 arrays of the same size
merge the 2 arrays into one array of twice the size
(a) [1 mark] Draw the data structure that results after inserting the following sequence of elements
into an initially empty set:
2, 63, 1, 32, 77, 8
(b) [2 marks] What is the worst case time, to within a constant factor, for performing SEARCH
when the set has size n? Justify your answer.
(c) [2 marks] What is the worst case time, to within a constant factor, for performing INSERT when
the set has size n? Justify your answer.
(d) [5 marks] Use the aggregate method to prove that the amortized insertion time in a sequence of
n insertions, starting with an initially empty set, is O(log n).
(e) [5 marks] Use the accounting method to prove that the amortized insertion time in a sequence of
n insertions, starting with an initially empty set, is O(log n).
2. [10 marks] Using the tree implementation of disjoint sets:
(a) [5 marks] Describe a sequence of make-set and union operations that builds a tree such that the
longest path has length 3 (3 edges on the path). Use the fewest number of elements possible.
Also draw the resulting tree.
(b) [3 marks] In general, what is the minimum number of nodes needed for the longest path length
to be k?
(c) [2 marks] What is the maximum number of nodes possible in a tree for the longest path length
to be k?
(No proof necessary in all three parts.)
3. [10 marks] East Turbofan is a newly founded low-price cheapo airlines company. They have just
completed research and accounting to determine, for every pair of cities, whether the company is
allowed to operate bidirectional flights between the two cities (may be disallowed for political reasons
or being bullied by bigger airlines), and what would be the operating cost per day if yes.
1
(Definition: Operate on a pair [of cities] means: Operate bidirectional flights between the two cities.)
East Turbofan is in luck: While they are not allowed to operate on some pairs, the allowed pairs are
enough to reach every city from/to every city, possibly through intermediate cities.
East Turbofan is low-price cheapo, so clearly they don’t really want to operate on all allowed pairs.
They want to choose just enough pairs to operate on, so that every city is reachable from/to every city
by 0 or more East Turbofan flights, and the total operating cost per day is minimized.
Implement an algorithm that computes the minimum total operating cost per day. The input is a list
of allowed pairs and costs, in which each item is a tuple (city1
, city2
, cost).
Example input (the answer is 5):
[(“Toronto”, “Chicago”, 1), (“Toronto”, “Montreal”, 3), (“Toronto”, “London”, 2),
(“Montreal”, “London”, 2), (“Chicago”, “London”, 5)]
Chicago Toronto London
Montreal
1
2
3 2
chosen 5
not chosen
So yeah East Turbofan is so cheapo, if you need to go from Chicago to Montreal, they’ll happily fly
you over the Atlantic twice because it’s cheaper for them. Don’t forget that you pay for your meals
and washroom visits during those 16 hours. Thank you for coding for East Turbofan!
How you can test The tester uses Python’s standard unittest library. You can use it like any other
Python unit-testers. Some examples:
python3 testeastturbofan.py
python3 testeastturbofan.py TestETF.test_handout
Marking scheme If your code looks like a general algorithm (as opposed to customizing for my
test cases), you get 3 marks to start. In addition:
• If your code compiles: 1 more mark per test passed. But watch this: Each test case gets 2.5
seconds only on the Mathlab server. Timing out is a failure. Each test case is timed separately.
• If your code does not compile: 0 more marks.
If your code does not look like a general algorithm, 0 to 3 marks depending on how far off it is.
2