help me to check ans:
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. 
�
�1(𝑛) = 4000𝑛2                                       
�
�2(𝑛) = 100 √(𝑛 −10)
 𝑓3(𝑛) = 2𝑛log(𝑛)                                    
�
�4(𝑛) = 10 𝑙𝑜𝑔(𝑛3)                                
�
�5(𝑛) = 12𝑛3 +100𝑛2log(𝑛)            
�
�6(𝑛) = 3𝑛 +1000𝑛                               
�
�) 𝜃(𝑛)          
log(𝑛)           
�
�) 𝜃(1)          
�
�)𝜃(𝑛2)     𝑐) 𝜃(𝑛3)                    
�
�)𝜃(1) 
�
�)𝜃(𝑛0.5)   𝑐) 𝜃(𝑛0.5 log(𝑛))    𝑑)𝜃(log(𝑛))    
�
�) 𝜃(2𝑛)       𝑏)𝜃(𝑛)       𝑐) 𝜃(2𝑛log(𝑛))       𝑑)𝜃(log(𝑛)) 
�
�) 𝜃(𝑛3)        
�
�) 𝜃(𝑛2)        
�
�) 𝜃(𝑛)          
�
�)𝜃(𝑛)       
�
�)𝜃(𝑛)       
�
�) 𝜃(log(𝑛))            
�
�) 𝜃(𝑛2log(𝑛))       
�
�)𝜃(𝑛3)     𝑐) 𝜃(𝑛(3𝑛))              
�
�)𝜃(2𝑛) 
�
�)𝜃(𝑛3) 
�
�)𝜃(3𝑛) 
[5 marks] 
(b) Arrange the functions (𝑓𝑖) in ascending order of running time and write your 
answer on the answer sheet. 
[5 marks] 
Q2) 
Consider the following two functions: 
�
�1(𝑛) = 𝑎 𝑙𝑜𝑔10 (𝑛) 
�
�2(𝑛) = 𝑏 𝑛𝑐 
Where 𝑎, 𝑏 are non-zero positive constants, and 𝑐 > 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. 𝑓2 is a linear function) that it will eventually take a value such 
that 𝑓2 is permanently greater than 𝑓1. 
(a) If 𝑎 = 15, 𝑏 = 4 and 𝑐 = 0.4, for what value of 𝑛 would  𝑓2 permanently exceed 
that of 𝑓1? Fill in the blank on the answer sheet.  
[5 marks] 
(b) For values of 𝑐 > 0, but < 1, explain whether you think it is possible for the 
long-term value of 𝑓1 to exceed that of 𝑓2. Fill in the blanks and check the correct 
box on the answer sheet. 
[5 marks] 
Q3)  
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 ((𝑎1,…,𝑎𝑛)): 
�
� ←0 
for 𝑖 ← 1 to 𝑛 −1 do 
if 𝑎𝑖 ≥ 𝑎𝑛 
�
� ←𝑥+ 𝑎𝑖 
return 𝑥 
Specify the running time.                                                  
Specify the return value (final 𝑥) of Algorithm Ex1 (11, 7, 1, 15, -5, 5).        
(b) 
[3 marks] 
[2 marks] 
Algorithm Ex2 ((𝑎1,…,𝑎𝑛),(𝑏1,…,𝑏𝑛),(𝑐1,…,𝑐𝑛)): 
�
� ←0 
for 𝑖 ← 1 to 𝑛 do 
for 𝑗 ← 1 to 𝑛 do 
for 𝑘 ← 1 to 𝑛 do 
�
� ←𝑥+ (𝑎𝑖×𝑏𝑗 ×𝑐𝑘) 
return 𝑥 
Specify the running time.                                                 
[3 marks] 
Specify the return value (final 𝑥) of Algorithm Ex2 ((1, 0), (2, -1), (3, 9)).    [2 marks] 
(c) 
Algorithm Ex3 ((𝑎1,…,𝑎𝑛),(𝑏1,…,𝑏𝑚)): 
�
� ←0  
�
� ←1 
while 𝑖 < 𝑛 and 𝑎𝑖 > 0 do 
for 𝑗 ← 𝑖 to 𝑚 do 
�
� ←𝑥+ 𝑎𝑖×𝑏𝑗 
�
� ←𝑖+1 
return 𝑥 
Specify the running time. Note: If 𝑖 > 𝑚, 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 product 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, -2, -2) would return 1 
• Sequence (1, 2, 3, 6) would return 1 
• Sequence (1, 2, 2, 4) would return 2 (the sequences (1, 2, 2) and (2, 2, 4)) 
• Sequence (1, 2, 2, 0, 2, 4, 8, 32) 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. 
Problem size n Program 
A 
Program 
(seconds) 
1 
2.5 
(seconds) 
B 
6.0 
6 
20.0 
16.0 
11 
62.5 
26.0 
16 
130.0 
36.0 
21 
222.5 
46.0 
26 
340.0 
56.0 
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. 
Q4) 
[8 marks] 
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? 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 𝑛. The decryption 
process is quite complex. Assume it takes 5 seconds of processing time on a 
PC to apply a key (regardless of 𝑛 and 𝑎 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.1% 
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 𝑛 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.025𝑎 × 𝑛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.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 𝑛 that 
the key must be composed of. 
[10 marks] 
Q5) 
This question is about the design and analysis of a hash map function based 
data storage system. Hash maps work by computing a hash code for some input. 
That input is then used to determine where that input belongs in a hash table. If 
the computed space location is free, the input item is stored there, otherwise 
another strategy has to be used to find a nearby space to store the input. The 
most common approach is to use a linear probe that looks at the next available 
free space in the table. The “size of the problem” when discussing hash maps 
relates to the size of the table i.e. the number of elements that need to be 
investigated to get an input in place in the hash table. 
As an example, consider a hash table with just 10 slots (positions 0 to 9 
inclusive). So the size of the problem 𝑛 is 10. The inputs are simple words. The 
hash function uses a simple hashing function that sums letter values as follows: 
• A is 1 
• B is 2 
• C is 3 
… and so on, up to Z. There are only 26 symbol values available for inputs. So if 
we want to store an input we compute the hash code, and then use that value 
modulo 10 (the remainder after integer division by 10) and use the remainder to 
determine the position in the table, assuming a linear probe is used. You may 
assume that the computation of the hashcode for any input (regardless of length) 
happens in constant time. 
For example: 
• Hashcode(CAB) = 6:  6%10 = 6, so CAB goes in position 6 
• Hashcode(CABBAGE) = 21: 21%10 = 1, so CABBAGE goes in position 1 
• Hashcode(ABC) = 6: 6%10 = 6, but CAB Is already in position 6, so ABC 
goes in position 7 (a linear probe length of 1). 
The linear probe also wraps around the hash map table. I.e. if you want to utilise 
position 9, but it is already in use, try position 0 next).  
The best case for any addition to the hash table occurs when the input hashes to 
a space that is free, so the input can be stored where the hash code determines it 
should. The worst case is any other situation, where a probing scheme has to be 
used. When the table is full, no more items can be added. 
a) Determine the best and worst case running times, using the full range of 
notation appropriately. You should give two examples of inputs that would 
correspond to the best and worst cases (two example for each) to support 
your answer. 
[7 marks] 
b) What practical step could you take to ensure that the worst case did not 
occur as often it might? 
[2 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. 
30 
B -2 
A 
5 
C 
version 1 
B 
30 -10 
D 
20 
A 
5 
version 2 
D 
20 
C 
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.   Answer Sheet 
Please fill in the blanks and submit this answer sheet (only) in a PDF format via 
Canvas. 
 
 
Q1) 
(a)  𝑓1 c, 𝑓2 b, 𝑓3c, 𝑓4d, 𝑓5d, 𝑓6c[5 marks] 
 
 (b)  f₄  < f₂ <  f₁ < f₅ < f₃ < f₆ [5 marks] 
 
 
Q2) 
 (a) Only after 𝑛=236, 𝑓2 permanently exceeds 𝑓1. [5 marks] 
 
 (b) First, we can calculate the gradients of each function: 
 
�
�1′(𝑛)= 15 / (n ln(10)),  𝑓2′(𝑛)= 4c n^(c-1). [4 marks] 
 
So, as 𝑛→∞, so as long as 𝑐>0, it   
 𝐢𝐬 𝐧𝐨𝐭 𝐩𝐨𝐬𝐬𝐢𝐛𝐥𝐞
  for the long-term  
value of 𝑓1 to exceed that of 𝑓2. [1 mark] 
 
 
Q3)  
 (a) 
Performance in the best case (lower bound):     (n) [1 mark] 
Performance in the worst case (upper bound):  O(n) [1 mark] 
Tight bound (if it does not exist, type “none”)   (n) [1 mark] 
The return value (final x): 33 [2 marks] 
 
 (b) 
Performance in the best case (lower bound):     ( n³) [1 mark] 
Performance in the worst case (upper bound):  O(n³) [1 mark] 
Tight bound (if it does not exist, type “none”)   ( n³) [1 mark] 
The return value (final x): 12 [2 marks] 
 
(c) 
Case 1: if m > n: 
Performance in the best case (lower bound):    (1) [1 mark] 
Performance in the worst case (upper bound):  O(nm) [1 mark] 
Tight bound (if it does not exist, type “none”)   (none) [1 mark] 
 
Case 2: if n > m: 
Performance in the best case (lower bound):    (1) [1 mark] 
Performance in the worst case (upper bound):  O(m²) [1 mark] 
Tight bound (if it does not exist, type “none”)   (none) [1 mark] 
 
            
(d)     Input:   𝐴=(𝑎1,…,𝑎𝑛)  
Output:  Number of times 𝑎𝑖∗𝑎𝑖+1=𝑎𝑖+2, for all valid 𝑖 until a  
          sequence (𝑎𝑖,𝑎𝑖+1,𝑎𝑖+2) contains an element with value 0.  
 
 
Algorithm: 
 
Algorithm PatternAnalyzer(A = (a₁,…,aₙ)): 
    count ← 0 
    for i ← 1 to n - 2 do 
        if aᵢ = 0 or aᵢ₊₁ = 0 or aᵢ₊₂ = 0 then 
            return count  // Terminate immediately if an element is zero 
        if aᵢ × aᵢ₊₁ = aᵢ₊₂ then 
            count ← count + 1 
    return count 
[8 marks] 
 
Performance in the best case (lower bound):     (1) [1 mark] 
    Performance in the worst case (upper bound):   O(n) 
    Tight bound (if it does not exist, type “none”)    (none) [1 mark] 
 
 
 
 (e) If a bound does not exist, type “none” to get the mark. 
 
Program A: 
Lower bound:    (n²)) [1 mark] 
Upper bound:   O(n²) [2 marks] 
Tight bound:   ( n²)  [1 mark] 
 
Program B: 
Lower bound:   (n) [1 mark] 
Upper bound:   O(n) [2 marks] 
Tight bound:   ( n)  [1 mark] 
 
 
Q4) If a bound does not exist, type “none” to get the mark. 
 
 (a)  
Lower bound:              ( 2ⁿ) [2 marks] 
Upper bound:             O(2ⁿ) [2 marks] 
Tight bound:      (2ⁿ) [1 mark] 
 
(b) 
    𝑁𝑜
  
  [1 mark]. 
The probability of doing so is 1 / 2ⁿ. [3 marks], 
and this value is      𝑠𝑚𝑎𝑙𝑙
  
 when 𝑛 is large  [1 mark]. 
 
 
(c) 
The key has 𝑛 binary bits. So, the number of combinations is 2ⁿ [1 mark]. For 
a 0.1%  chance of cracking the problem,  we need to try 0.001 * 2ⁿ of the 
combinations [1 mark]. We can calculate that in 30 days, there are 292,000 
seconds [2 marks]. Each try takes 5 seconds. So, in 30 days, that would 
allow 518,400combinations to be tried [2 marks]. 
Therefore the minimum number of bits 𝑛 required will be 29 [4 marks]. 
 
(d) 
The key has 𝑛 binary bits. So, the number of combinations is 2n. For a 0.25% 
chance of cracking the problem, we need to try 0.0025×2n of the 
combinations [2 marks]. We know that in 30 days, there are 2,592,000 
seconds. Each try takes 5𝑛2 seconds [2 marks]. Therefore, in 30 days, that 
would allow 2,592,000/ 5𝑛2 combinations to be tried [2 marks].  
Therefore the minimum number of bits 𝑛 will be 0.0025×2n ≤ 2,592,000/ 5𝑛2 
[4 marks]. 
Q5) If a bound does not exist, type “none” to get the mark. 
(a) Best case: 
Lower bound:              
Upper bound:             
Tight bound:     
(1)  
O(1)  
(1) [1 mark for stating all bounds] 
Inserting "A" into an empty table:  
Hash code: (A = 1)  
Hash position: (1 mod 10 = 1) 
Outcome: Position 1 is free. "A" is placed in position 1 without any probing.  
Inserting "ZOO" into a nearly empty table:  
Assume only position 3 is occupied. 
Hash code: (Z + O + O = 26 + 15 + 15 = 56)  
Hash position: (56 mod 10 = 6)  
Outcome: Position 6 is free. "ZOO" is placed in position 6 without any probing. 
[2 marks for the two examples] 
Worst case: 
Lower bound:              
Upper bound:             
Tight bound:     
(n) 
O(n) 
(n) [2 marks for stating all bounds] 
Inserting "FULL" into a Full Table: 
Initial condition: All positions from 0 to 9 are occupied. 
Hash code: ( F + U + L + L = 6 + 21 + 12 + 12 = 51 ) 
Hash position: ( 51 \mod 10 = 1 ) 
Probing sequence: Positions 1, 2, 3, ..., 9, 0 
Outcome: All positions are checked (total of 10 probes), and no empty slot is found. Insertion fails 
after ( n ) attempts. 
Inserting "ECHO" When Only One Slot is Empty: 
Initial condition: Positions 0 to 8 are occupied; position 9 is empty. 
Hash code: ( E + C + H + O = 5 + 3 + 8 + 15 = 31 ) 
Hash position: ( 31 \mod 10 = 1 ) 
Probing sequence: Positions 1, 2, 3, 4, 5, 6, 7, 8, 9 
Outcome: Positions 1 to 8 are occupied; position 9 is finally found empty after 9 probes (almost ( n ) 
attempts). 
[2 marks for the two examples] 
(b)  
Q6) 
Increasing the size of the hash table: Ensure that the table is larger than the number of items you 
expect to store  
Rehashing: When the table reaches a certain capacity threshold, create a new, larger table and re
insert all existing items using the hash function. 
[2 marks] 
�
� 𝐵 𝐶 𝐷 
iteration 
0    
1 
0 30 5  
2 
0 30 5 25 
3 
0 30 5 25 
4 
0 30 5 25 
�
� 𝐵 𝐶 𝐷 
iteration 
0    
1 
0 30 5  
2 
0 30 5 25 
3 
0 30 5 25 
4 
0 30 5 25 
version 1 
Which result is correct?  𝒗𝒆𝒓𝒔𝒊𝒐𝒏 𝟏   
⬚
 Why?  [2 marks]. 
version 2 
[2 marks] 
[1 mark]. 
[2 marks] 
In Version 1, even though there's a negative edge weight, the algorithm's key invariant—that once 
a node's shortest path is determined and added to the settled set, it won't be improved—is 
maintained. The edge with weight -2 doesn't provide a shorter path to D than the one already found.