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 task on INGInious: Union intervals.

Exercise 2.2.2#

You need to sort a large array containing only values in the set {0, 1, 2}. What sorting algorithm do you suggest? Write the code. What is the time complexity to sort the array? Discuss this complexity with respect to the lower bound for comparison-based sorting algorithms (Proposition 1, pages 280-281).

Exercise 2.2.3#

The mode of an array of numbers is the number that appears most frequently in the array. 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 target 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 already given in sorted arrays?

Exercise 2.2.5#

Same question as above, but for a single set. What if the set is already given in a sorted array?

Exercise 2.2.6#

Give an algorithm to compute the union of two sets \(A\) and \(B\). Suppose next that the already sorted set \(A\) has size \(n\) and the already sorted set \(B\) has size \(n^2\). What would be the time complexity of your algorithm? Would your algorithm change?

Exercise 2.2.7#

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

Exercise 2.2.8 (INGInious: Global Warming)#

Design an algorithm to compute the number of entries greater than or equal to a given value \(v_1\) in an \(n \times n\) matrix of integers. What if you need to recompute it for a different value \(v_2\)? Do you need to redo the computation from scratch, or can some precomputation be done to answer queries more efficiently?

INGInious task: Global Warming.

Exercise 2.2.9 (INGInious: Radix Sort)#

Every integer is encoded using 32 bits in Java. An integer can thus be seen as a string of 32 bits. The radix sort algorithm is a version of string sort that starts with the least significant bit rather than the most significant bit (unlike MSD sort, page 710).

Complete the partial implementation for sorting an array of integers using radix sort.

INGInious task: Radix Sort.

While implementing this algorithm, answer the following questions:

  1. What is the time complexity of this algorithm?

  2. Would the radix sort algorithm as implemented also work by starting from the most significant bit rather than from the least significant bit?

  3. What stable sorting algorithm did you choose in your implementation? What is its time complexity? Do you know another algorithm that could be used without requiring an auxiliary array?

  4. How would you adapt the radix sort implementation to sort numbers that may be positive or negative (be careful about the way negative numbers are represented bitwise)?

Exercise 2.2.10 (INGInious: Aggregate, January 2023)#

INGInious task: Aggregate.