You are given a set of n points x$1,...,$ xn and a set of n segments $[$a$1,$ b$1]...[$an$,$ bn$]$ on a line, where xi$,$ ai$,$ bi are all integers. We want to output k$1,$ k$2...,$ kn$,$ where ki is the number of segments that contain xi$.$ More formally, let X$[1,...,$ n$]$ be the array storing the points. Moreover, let I$[1,...,$ n$]$ denote an array storing the segments such that each entry I$[$i$]$ stores two values I$[$i$].$left and I$[$i$].$right. We want to write an algorithm that computes K$[1,...,$ n$]$ with K$[$i$]$ being the number of segments containing the point X$[$i$].$ In the following, assume that all the points, starting points, and endpoints are distinct.

$($a$)$ Assume you solve the problem using a naive algorithm which iterates through all point$-$segment pairs, what is the running time?

In the following, we develop a more clever algorithm. To this end, we first create an auxiliary array C$[1,...,3$n$]$ that stores the points as well as start and end points of the intervals. Each entry C$[$j$]$ stores three values: C$[$j$].$value that is an integer, C$[$j$].$type that is either of the literals $$left$,$right$,$ or $$point$,$ and a value C$[$j$].$pointer that stores an index between $1$ and n into one of the original arrays.

$($b$)$ Write the pseudocode of a procedure GenerateC$($X$,$I,n$)$ that fills the above described array C based on the arrays X and I.

$($c$)$ Assume now that the above described array C has been generated and then sorted according to the value field, i$.$e$.,$ such that C$[$i$].$value $<$ C$[$i $+1].$value for all i from $1$ to $3$n $1.$ Write a procedure ComputeK$($C$,$ n$)$ which computes the array K$[1,...,$ n$]$ in time $\backslash$Theta $($n$)$ by iterating over the array C once.

$($d$)$ Assume you use the best sorting algorithm you know from the lecture so far, what is the overall running time when combining the solutions from parts $($b$)$ and $($c$)$ to solve the overall problem?

$($e$)$ Argue the correctness of part $($c$)$ using a suitable loop invariant.

$($f$)$ Now assume that collisions between points and start or endpoints of the intervals can happen, as well as collisions between multiple intervals. For instance, we could have that X$[$i$]=$ I$[$j$].$left, that I$[$i$].$left $=$ I$[$j$].$right, or that I$[$i$].$left $=$ I$[$j$].$left for some i and j$.$ Show that if we do not make any assumptions on how the sorting algorithm breaks ties, that then our algorithm is incorrect. To this end, provide an example input X and I and a sorted corresponding C such that your algorithm from part $($c$)$ produces the wrong result

$($g$)$ Generalize your algorithm from part $($b$)$ in such a way that the combined algorithm, with unmodified part $($c$),$ correctly works even in the presence of collisions. The format of the array C should remain unchanged and we still do not make any assumption on how the sorting algorithm breaks ties. $($Hint: You may consider tweaking the values stored in C$[$i$].$value.$)$