1. Let A[0...n 1] be an array of n distinct numbers. If i < j and A[j] > A[i], then the pair (i, j) is called an inversion of A.

(a) List the five inversions of the array [2, 3, 8, 6, 1]. Note: the inversion is specified by indices.

(b) What array with elements from the set {1, 2, ..., n} has the most inversions? How many does it have? (c) Describe the relationship between the running time of insertion sort and the number of inversions in the input array. Justify your answer.

2. Assuming that Alice is attending a conference. There are many exciting talks Alice would like to attend, some of which may be scheduled at the same time or have some overlaps. Alice has a list of talks to attend in mind and want to see if she can attend all of them. Note that if Alice attends a talk, she will not leave until the end of that talk.

The starting time and ending time of the talks that Alice wants to attend are stored in an array denoted by time, where time[i] = [start i, end i] is the schedule of the i-th talk. We want to design an algorithm to see if Alice could attend all talks specified in the time array.

Example 1:

Input: time = [[0,40],[45,90],[80,120]]

Output: false

# In this example, Alice cannot attend both the second and the third talk as they are partially overlapped.

Example 2:

Input: time = [[0,40],[45,90],[100,140],[150,180]]

Output: true

# In this example, Alice can attend all the talks.

# If the starting time of one talk and the ending time of another talk are the same, we say there is a time conflict and Alice cannot attend both talks.

(a) There is a straightforward algorithm that admits a running time of O(n 2 ), where n is the length of time. Describe this algorithm and explain why it has time complexity O(n 2 ). Hint: try to compare every pair of talks time. Provide pseudocode for your algorithm, a clear English description of what your algorithm is doing and why it is correct, and a brief runtime analysis. You do not need to prove that your algorithm is correct.

(b) There exist more efficient algorithms that have running time O(n log n). Describe such an algorithm. The criterion is same as (a). Hint: first sort the talks by their starting time and then iterate through the sorted list