(Solved): [20 marks] Alice and Bob are meeting up at the park. Alice arrives at time \( t \in[1, \ldots, n] ...

[20 marks] Alice and Bob are meeting up at the park. Alice arrives at time \( t \in[1, \ldots, n] \) with probability \( a_{t} \) (where \( \sum_{t=1}^{n} a_{t}=1 \) ). Bob arrives at time \( t \in[1, \ldots, n] \) with probability \( b_{t} \) (where \( \sum_{t=1}^{n} b_{t}=1 \) ). Assume the time \( t \) is in minutes. 4.1 [4 marks] Provide an expression for the probability that Alice arrives \( k \) minutes before Bob (where \( k \) can be negative). 4.2 [10 marks] Design an \( O(n \log n) \) algorithm that computes the probability that Alice arrives before Bob. How might FFT fit into this problem? 4.3 [6 marks] Design an \( O(n) \) algorithm to compute the probability that Alice and Bob arrive an even number of minutes apart.