Python代写 | Divide-And-Conquer Algorithms

本次澳洲代写是Python分治算法相关的assignment

This assignment requires you to write three efficient divide-and-conquer algorithms that processes in- teger sequences. It is worth 5% of your total course marks.

All three programs have the same input and output format. The input consist of two white-space separated sequence S₁ and S₂ of positive integers (each sequence is given on one line). The length of S₁ is n₁ and the length of S₂ is n₂; note these are not necessarily the same.  The output will be a n₂ lines, each consisting of a single integer. For the following three problems we index elements in each sequence start at 0 and end at n₁ − 1 or n₂ − 1.

This simple warm-up problem will check if you can read the input correctly (from stdin). For each integer x in S₂, output/print (to stdout) the value n₁ + x.

1 3 0 2 3 4

We assume the first input sequence S₁ is sorted. Determine the highest index each item x in S₂ within S₁. If x does not appear, then output −1 for that case. To solve this task one is expected to write a traditional O(log n₁) binary-search function, called n₂ times

1 3 10 21 23 23 24

3 12 23 24

This is the same as Problem 1, except the input S₁ is a sorted and rotated array. That is, S₁ = s₀, s₁, s₂, . . . , s_i, . . . , s_n1−1, where for some 0 <  i  <  n,  s_i  is the smallest element,  and modulo n, s_j ≤ s_j+1 for all j ≠ i – 1.

23 24 1 3 10 21 23

3 12 23 24