Exercises B

Note

You must complete these exercises by Wednesday of W5.

Exercise 2.2.1 (Inginious)

Write a method that takes an array of intervals as input and returns the union of those intervals as an array of disjoint intervals. We consider that the input intervals are given in the form of two arrays int[] min, int[] max; where the ith interval is given by (min[i],max[i]) . Example input min=[5,0,1,6,2] max=[7,2,2,8,3] would output min=[0,5] ,max=[3,8]. Write the pseudocode. How complex is your method?

Solve the corresponding taks on Inginious Union intervals

Exercise 2.2.2

You need to sort a large array that has the property that it only contains values in the set {0,1,2}. What sorting algorithm do you suggest? Write the code. How complex will it be to sort the array? Discuss this complexity with respect to the lower bound of a sorting algorithm (Proposition 1 pages 280-281).

Exercise 2.2.3

The mode of a table of numbers is the number that appears most frequently in the table. For example (4,6,2,4,3,1) has mode 4. Give an efficient algorithm to calculate the mode of an array of \(n\) numbers. What if we know that the array only contains values from 0 to \(k\)?

Exercise 2.2.4

Given two sets \(S_1\) and \(S_2\) (each of size \(n\)), and a number \(x\). Describe an efficient algorithm to find if there is a pair \((a,b)\) with \(a \in S_1,b \in S_2\) such that \(a+b=x\). What is the time complexity of your algorithm? What if the sets are in already sorted arrays?

Exercise 2.2.5

Same question as the previous one but for a single set. What if the set is in an already sorted array?

Exercise 2.2.6

Give an algorithm to calculate the union of two sets \(A\) and \(B\). Suppose in a second step that the already sorted set \(A\) has a size \(n\) and the also sorted set \(B\) has a size \(n^2\) . What would be the time complexity of you algorithm, does your algorithm change?

Exercise 2.2.7

Given a matrix of integers that are sorted along rows and columns, how do you find a given number in the matrix efficiently? Hint: There is a \(\mathcal{O}(n+m)\) time algorithm for a \(n\times m\) matrix. To do this, start in the upper right corner and compare with the number you are looking for. Which parts of the matrix can you prune in your search based on the result?

Exercise 2.2.8 (Inginious)

Design an algorihtm to compute the number of entries larger or equal to a given value \(v_1\) in n x n matrix of integers. What if you need to recompte it for a different value \(v_2\)? Do you need to redo the computation from scratch or some pre-computation can be done do it more efficiently?

Inginious task: Global Warming