Exercises B¶
Note
You must complete these exercises by Wednesday of W5.
Exercise 2.2.1 (Inginious: Union of Intervals)¶
Write a method that takes an array of intervals as input and returns the union of those intervals as an array of disjoint intervals. What is the time complexity of 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: Global Warming)¶
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
Exercise 2.2.9 (Inginious: Radix Sort)¶
Every integer is encoded on 32 bits in Java. An integer can thus be seen as a string of 32 bits. The radix-sort algorithm is version of string sort that start with the least significant bit rather than the most sigfificant bit (as for MDS pp. 710).
Complete the partial implementation for sorting an array of integers using radix sort.
Inginious task: Radix Sort
While implementing this algorithm try to answer the following questions:
What is the time-complexity of this algorithm?
Would the radix sort algorithm as implemented also work by starting from the most signficant bit rather than from the least significant bit?
What stable sort algorihtm did you choose in your implementation? What it its time complexity? Do you know another algorithm that could be used without requiring an auxiliary array?
How to adapt the radix-sort implementation to sort number that may be positive or negative (be carefull about the way an negative number is represented bitwise)?
