算法代写 | 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.