Program Analysis – 2019 Assignment 1 University of Sussex Program Analysis G6017 Coursework 1 Due: Semester 1 Week 6 Thursday 5 November 2020 by 4PM Format: Electronic submissions only by Canvas. Your...

1 answer below »
1. Answer all the questions. 2. Show your workings where appropriate. You can still get credit for a question with an incorrect final answer if your workings show that you understood what the problem was and how to solve it. 3. Do not copy the work of another student. Plagiarism is a very serious matter. Discussion between students is to be encouraged – copying is an academic disciplinary matter


Program Analysis – 2019 Assignment 1 University of Sussex Program Analysis G6017 Coursework 1 Due: Semester 1 Week 6 Thursday 5 November 2020 by 4PM Format: Electronic submissions only by Canvas. Your submission does not need to be typed, although handwritten scripts must be legible. If you do the work in a handwritten form, please scan it and upload the work as a single PDF document. No paper copies of this submission will be accepted. Weighting 50.0 % of the coursework element for this module 12.5 % of the overall module mark General instructions 1. Answer all the questions. 2. Show your workings where appropriate. You can still get credit for a question with an incorrect final answer if your workings show that you understood what the problem was and how to solve it. 3. Do not copy the work of another student. Plagiarism is a very serious matter. Discussion between students is to be encouraged – copying is an academic disciplinary matter. 4. Check that you provide any working or information that the question asks for. 5. Hand your submission in on time. There are penalties for late submission. 6. If I cannot read your submission, I cannot mark it. It is your responsibility to ensure that the presentation of your submission is appropriate for a University student. 7. Do not forget to state units if they are relevant and apply to a question. 8. You should use any calculating aids your feel appropriate to help you solve the problems including, although not limited to, calculators, spreadsheets such as Excel and MATLAB. 9. If you do not understand the questions, you can get help at the workshop sessions. 10. This assignment is marked out of a total of 100. 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 + ?2log⁡(?) ?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 state under what circumstances the algorithm will return true. (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. (a) Complete the following table: • The top row shows the values of  after initialisation. • In each of the subsequent rows, you should give the values of  that all 8 vertices have at the end of that iteration of the algorithm’s while loop. • In the row for iteration ? you should circle the value ⁡(?) (which you will have put in the column for the vertex ?) for the vertex ? that is selected in the first line of the while loop during the i-th iteration. • Also, in the row for iteration ?, you should show in bold (or with an underline) any value of  that has changed on that iteration. Then state whether you think that the answer is correct. ?1 ?2 ?3 ?4 ?5 ?6 ?7 ?8 iteration 0        1 2 3 4 5 6 7 8 [10 marks] (b) Give concise descriptions of the situations where giving Dijkstra’s algorithm a graph with one or more negatively weighted edges will result in a valid and an invalid output. You should use a diagram and an example to assist in your description. [10 marks] Dr Kingsley Sage [email protected] September 2020 mailto:[email protected]
Answered Same DayOct 07, 2021

Answer To: Program Analysis – 2019 Assignment 1 University of Sussex Program Analysis G6017 Coursework 1 Due:...

Kushal answered on Oct 14 2021
137 Votes
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.
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 state under what circumstances the algorithm will return true.
a) Algorithm Ex1 ((?1, … , ?? ), ?):
? ← 0
for ? ← 1 to ? do
if ?? < ?
? ← ? + ??
return ?
⇒ Since it is a the sum of all the numbers of an array which are less than b, so the complexity will be O(Ex1)=O(n)
So the upper bound will be Theta O(n) because that will be the worst case complexity and the loop will always run from 1 to n for comparison so the tight bound will exist which is always <=O(n).
b) Algorithm Ex2 ((?1, … , ?? ), (?1, … , ??)):
? ← 0
for ? ← 1 to min (?, ?) do
if ?? > ?i
? ← ? + ??
return x
⇒ The worst case complexity of the above algorithm will be O(min(n,m)), so the upper bound will be O(min(n,m)), the lower bound can be when n or m=1 , so it will O(1) and hence a tight bound exists between the upper and lower bounds.
c) Algorithm Ex3 ((?1, … , ?? ), (?1, … , ?? ), (?1, … , ?? )):
? ← 0
for ? ← 1 to ? do
for ? ← 1 to ? do
for ? ← 1 to ? do
? ← ? + (?? × ?? × ??^2 )
return ?
⇒ Since the loop is running three times so the worst complexity is O(n^3). When n is 1, then the lower bound will be O(1), hence a tight bound exists between the upper and lower bounds.
d) Algorithm Ex4 ((?1, … , ?? ), (?1, … , ??)):
? ← 0
? ← 1
while ? < ? and ?? > 0...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here