# 算法代写 | Program Analysis G6017 Coursework 1

这个作业是完成算法分析

Program Analysis G6017

Coursework 1

Q1) Consider the following six functions. They are the running times

of six algorithms. Determine, with clear reasoning, and state the asymptotic

running time of these functions and then arrange them in ascending order of

running time.

𝑓1

(𝑛) = 15𝑛

3 + 𝑛

2

log (𝑛)

𝑓2

(𝑛) = 55 √(𝑛 − 3) + log(𝑛)

𝑓3

(𝑛) = 150000𝑛

2

𝑓4

(𝑛) = 3 𝑙𝑜𝑔(𝑛

3

)

𝑓5

(𝑛) = 3

𝑛 + 175𝑛

𝑓6

(𝑛) = 2

𝑛

log(𝑛)

[15 marks]

Q2)

Specify the running time of each of the following algorithms. You must fully

explain your answer to receive full marks. You should clearly state the

performance in the best and worst cases, and you should consider in each case

the upper and lower bounds and whether a tight bound exists. You should also

explain the significance of the return value (i.e. what problem does that algorithm

solve).

(a)

Algorithm Ex1 ((𝑎1, … , 𝑎𝑛

), 𝑏):

𝑥 ← 0

for 𝑖 ← 1 to 𝑛 do

if 𝑎𝑖 < 𝑏 𝑥 ← 𝑥 + 𝑎𝑖 return 𝑥 [7 marks] (b) Algorithm Ex2 ((𝑎1, … , 𝑎𝑛 ), (𝑏1, … , 𝑏𝑚)): 𝑥 ← 0 for 𝑖 ← 1 to min (𝑛, 𝑚) do if 𝑎𝑖 > 𝑏𝑖

𝑥 ← 𝑥 + 𝑎𝑖

return 𝑥

[7 marks]

(c)

Algorithm Ex3 ((𝑎1, … , 𝑎𝑛

), (𝑏1, … , 𝑏𝑛

), (𝑐1, … , 𝑐𝑛

)):

𝑥 ← 0

for 𝑖 ← 1 to 𝑛 do

for 𝑗 ← 1 to 𝑛 do

for 𝑘 ← 1 to 𝑛 do

𝑥 ← 𝑥 + (𝑎𝑖 × 𝑏𝑗 × 𝑐𝑘

2

)

return 𝑥

[7 marks]

(d)

Algorithm Ex4 ((𝑎1, … , 𝑎𝑛

), (𝑏1, … , 𝑏𝑚)):

𝑥 ← 0

𝑖 ← 1

while 𝑖 < 𝑛 and 𝑎𝑖 > 0 do

for 𝑗 ← 𝑖 to 𝑚 do

𝑥 ← 𝑥 + 𝑎𝑖 × 𝑏𝑗

𝑖 ← 𝑖 + 1

return 𝑥

[7 marks]

The last part is concerned with the concept of proof by contradiction. Providing a

clear statement of your steps, show using proof by contradiction that:

(e) The sum of two odd numbers is always even.

[7 marks]

Q3) You are helping to design an encryption algorithm. The decryption phase of

the algorithm takes two inputs, a message of length 𝑎 digits and a key made up

of 𝑛 binary bits. The decryption phase performs a mathematical process on the

message using the key to produce the plain text decoded message. You are very

aware that there are hackers that would wish to be able to decode your

messages. However, the workings of the algorithm have been kept secret so the

only hack available for decoding the message is a brute force approach where

each possible key is tried one at a time until the correct one is found, when a

decoded message in English is produced. There are no known cribs,

weaknesses or other techniques to assist in hacking the cipher.

(a) What is the running time for a brute force method to decode a message?

[5 marks]

(b) Should the lower bound you identified in part (a) concern us in terms of

the safety and security of our encryption technique?

[5 marks]

(c) The security of the encryption process depends on the value 𝑛. The

decryption process is quite complex. Assume it takes 30 seconds of

processing time on a PC to apply a key (regardless of the values of 𝑛 and

𝑎) to the message (regardless of whether it’s the correct key). The

algorithm may be regarded as sufficiently secure provided that, using a

brute force method, there is no more than a 1% chance that the message

would be decoded correctly in 30 days (working 24 hours a day).

Calculate the minimum number of bits 𝑛 that the key must be composed

of.

[10 marks]

(d) In reality, the time it takes to apply the key depends on the lengths of 𝑛

and 𝑎. If the key is short, the application time is quick. If the key is long, it

takes longer to apply. We discover that the time to apply the key to the

message is given by the formula 𝑡 = 0.01𝑎 × 𝑛

2 where 𝑛 is the number

of bits in the key, 𝑎 is the length of the message and 𝑡 is the time in

seconds. This time the algorithm may be regarded as sufficiently secure

provided that, using a brute force method, there is no more than a 0.5%

chance that the message of 100 characters would be decoded correctly in

30 days (working 24 hours a day). Determine the minimum number of bits

𝑛 that the key must be composed of.

[10 marks]

Q4) This question concerns Dijkstra’s algorithm which is reproduced overleaf:

You will be considering what happens when the algorithm is run on the following

graph where the source vertex is 𝑣1. Note that this graph contains a negatively

weighted edge.