代写program编程、代写Python，Java程序

日期：2022-03-30 11:32

Question 1 [2 Marks]

We know, from lectures, the following facts. For 0 < ε < 1 < c,

where f(n) ? g(n) means both f(n) ∈ O(g(n)) and g(n) 6∈ O(f(n)) (i.e. g(n) is not in O(f(n))).

For the following pairs of functions, f(n),g(n), determine if f(n) ∈ Θ(g(n)), f(n) ∈ O(g(n)), or f(n) ∈

?(g(n)), making the strongest statement possible. That is, if both f(n) ∈ O(g(n)) and f(n) ∈ ?(g(n))

are true, you must answer with the form f(n) ∈ Θ(g(n)). You must answer with f(n) on the left and

g(n) on the right, for example, you may not answer g(n) ∈ O(f(n)).

You must show all working. A correct answer that does not show your working will result in 0 marks.

Question 2 [2 Marks]

A string of characters is called a palindrome if reading the characters from left to right gives the same

sequence as reading the characters from right to left.

For example: abccba, ahgiigha and abgllggllgba are all palindromes while abcdabcd, lghddgl and

abcd are not.

Write the pseudocode for an algorithm which, given a string and its length n, can identify a palindrome

using only one scan from left to right (which means you can only access each letter once). Your

algorithm must employ the use of either a queue or a stack, and you must justify your choice.

If you use a stack myou must use PUSH() and POP(), and if you use a queue you must use ENQUEUE()

and DEQUEUE().

Assume for simplicity every input will be of even length.

Page 3 of 5

Question 3 [3 Marks]

The following graph represents a road network where each edge presents a road segment. The costs of

the road segments are given in the figure below. There are three hospitals at nodes B, D, and E, and an

accident occurs at node H.

(a) Which algorithm would you use to find the nearest hospital from the accident. Explain how and

why you would use this algorithm.

(b) Which is the nearest hospital, which path would you take and what is the cost of this path? You

must show the execution of the algorithm described above.

(c) List the order of the nodes visited from H in the graph when a breadth-first search is used.

You should break ties in alphabetic order.

Page 4 of 5

Question 4 [3 marks]

Consider the following recursive function, which takes an unordered array of integers, A, and an integer,

k, and returns TRUE if k appears in A and FALSE otherwise.

function THIRDSSEARCH(A[0..n-1], k)

if n == 0 then

return FALSE

else if n == 1 then

return (A[0] == k)

else

a ← THIRDSSEARCH(A[0..n/3?1], k)

b ← THIRDSSEARCH(A[n/3..n×2/3?1], k)

c ← THIRDSSEARCH(A[n×2/3..n?1], k)

return (a OR b OR c)

For simplicity, you may assume the input array is of length n = 3

m for some positive integer m, so that

each recursive call gets an exact third of the input array.

(a) Write down, and solve, a recursive formula W(n) = ... which describes the number of steps taken

by THIRDSSEARCH on an array of length n, for the worst case input. Make sure you include the

base case(s). Keep in mind that the basic operation is usually the most frequent or most expensive

operation. Remember the formula for the geometric series states that.

(b) Use the language of ?,O,Θ to bound the time complexity of THIRDSSEARCH, using T(n) for its

runtime. You must include an upper and lower bound. Full marks are awarded only to the tightest

possible bounds.

(c) Explain how THIRDSSEARCH could be slightly modified to improve its efficiency in the best case,

and repeat the analysis from part (b), with justification.

END OF TEST

Page 5 of 5