Program Analysis G6017
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Program Analysis G6017
Coursework 1
|
Due: |
Semester 1 Week 6 Thursday 9 November 2023 by 4PM |
|
Format: |
Electronic submissions only by Canvas. You should write your answers in the blanks on the answer sheet we have provided for you and submit this answer sheet only in a PDF format. If you want to do your work in a handwritten form, please print the answer sheet, fill it in properly, and then again scan and upload your 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 and fill in the blanks on your answer sheet. We will only mark the answers on your answer sheet in a PDF format.
2. If you want to do your work in a handwritten form, please print the answer sheet, fill it in properly, and then again scan it and upload the work as a single PDF document.
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. 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. Finally, we only mark your answers on your answer sheet.
8. If you do not understand the questions, you can get help at the workshop sessions.
9. This assignment is marked out of a total of 100.
Q1)
(a) Consider the following six functions. Choose only one of the following asymptotic running times for each function and write a, b, c, or d in your answer sheet.
[5 marks]
(b) Arrange the functions (fi ) in ascending order of running time and write your answer on the answer sheet. [5 marks]
Q2)
Consider the following two functions:
Where a , b are non-zero positive constants, and c > 0 is a real value. A student is comparing the relative asymptotic running time of these two functions. They can see that if c = 1 (i.e. f2 is a linear function) that the long-term growth rate off2 is greater than f1 .
(a) If a = 10, b = 3.0 and c = 0.5, for what value of n would the long-term growth rate off2 permanently exceed that off1 ? Fill in the blank on the answer sheet. [5 marks]
(b) For values of c > 0, but < 1, explain whether you think it is possible for the long-term growth rate of f1 to exceed that of f2 . Fill in the blanks and check the correct box on the answer sheet. [5 marks]
a3)
Specify the running time of each of the following algorithms. 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. Fill in the blanks and write your answers on the answer sheet.
(a)
|
Algorithm Ex1 ((a1, … , an)): x ← 0 for i ← 1 ton − 1 do if a i > an x ← x + a i return x |
|
|
Specify the running time. Specify the return value (final x) of Algorithm Ex1 (12, 3, 1, 15, -3, 5). (b) |
[3 marks] [2 marks] |
|
Algorithm Ex2 ((a1, … , an), (b1, … , bn), (c1, … , cn)): x ← 0 for i ← 1 ton do for j ← 1 ton do for k ← 1 ton do x ← x + (a i × bj × ck) return x |
|
|
Specify the running time. [3 marks] Specify the return value (final x) of Algorithm Ex2 ((1, 0), (2, - 1), (3, 9)). [2 marks] (c) |
|
|
Algorithm Ex3 ((a1, … , an), (b1, … , bm)): x ← 0 i ← 1 while i < n anda i > 0 do for j ← i tom do x ← x + a i × bj i ← i + 1 return x |
|
Specify the running time. Note: If i > m, you should assume that the for loop does not run (does not iterate backwards). [6 marks]
(d) A data pattern analyser is to be built that can analyse a sequence and detect and count up the number of occurrences of three consecutive integers where the third integer is the sum of the first and second integers. Integers can be positive or negative. The analyser needs to stop counting and terminate immediately if it reaches an element in the sequence with value 0.
So:
• Sequence (1, -1, 0) would return 0 (termination condition)
• Sequence (1, 1, 3) would return 1
• Sequence (1, 1, 3, 4) would return 1
• Sequence (1, 2, 3, 5) would return 2 (the sequences (1, 2, 3) and (2, 3, 5))
• Sequence (1, 2, 3, 0, 1, 4, 5, 1) would return 1 (because it stops counting and terminates immediately after reaching the element with value 0).
In your answer sheet, write a linear algorithm to solve the problem using a pseudo- code style similar to the one shown in parts (a) to (c), and state the running time of your algorithm. Note: As the question asks for a linear algorithm, try to use a single loop only. You are not allowed to use any nested loops which might make the worst case non-linear. [10 marks]
(e) Two programs A and B are developed that solve the same problem. A student conducts an experiment to see how the running time of each program varies with the size of the input problem set. A summary of the data they collect is shown below. We are told that the data the two programs are tested with represents a worst-case scenario of the problem.
Based on the data available, what conclusions may we draw about the running time complexity classes of the algorithms that the two programs implement? Please fill in the blanks on the answer sheet. [8 marks]
Q4)
You are helping to design an encryption algorithm. The decryption phase of the algorithm takes two inputs, a message of length a digits and a key made up of n 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? Fill in the blanks on the answer sheet. [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? Fill in the blanks and check the correct boxes on the answer sheet. [5 marks]
(c) The security of the encryption process depends on the value n. The decryption process is quite complex. Assume it takes 10 seconds of processing time on a PC to apply a key (regardless of n and a values) 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 0.5% chance that the message would be decoded correctly in 30 days (working 24 hours a day). Fill in the blanks on the answer sheet and calculate the minimum number of bits n 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 n and a. 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 t = 0.025a × n2 where n is the number of bits in the key, a is the length of the message and t 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.25% chance that the message of 200 characters would be decoded correctly in 30 days (working 24 hours a day). Fill in the blanks on the answer sheet and determine the minimum number of bits n that the key must be composed of. [10 marks]
Q5)
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 v1. Note that this graph contains a negatively weighted edge.
Please look at the table in your answer sheet and complete it:
• 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 i you should circle the value δ (v) (which you will have put in the column for the vertex v) for the vertex v that is selected in the first line of the while loop during the i-th iteration.
• Also, in the row for iteration i, 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. [9 marks]
Q6)
The diagrams below show two directed graphs. We would like to investigate the effect of negative edge weights when using Dijkstra’s algorithm to find the lowest cost path from A to all other nodes.
Run Dijkstra’s algorithm on both versions and complete their corresponding tables on your answer sheet. In which version do you think the path costs are calculated correctly for all nodes even though one of the edges is negative weighted? Why does a version work properly while another one does not? Your answer should refer to the concept of an invariant. [7 marks]
2023-11-10