Exercises A#
Note
You must complete these exercises by Wednesday of W4.
Exercise 2.1.1#
Given an array containing \(n\) sorted integers, and a number \(x\) to insert into the array, can you describe an algorithm to find the position where \(x\) should be inserted while keeping the array sorted?
What is the time complexity of this algorithm? Does your algorithm also work for a sorted linked list? With what complexity?
Exercise 2.1.2#
We consider the very general problem where we have \(n\) jobs to perform for clients and each job \(j\) takes \(t_j\) seconds to complete. Only one job can be performed at a time.
The goal is to complete all jobs while maximizing customer satisfaction. Maximizing customer satisfaction means building a schedule that minimizes the average job completion time.
For example, if the durations of the jobs are 5, 8, 3, 4 and the jobs are carried out in this order, the completion times will be 5, 13, 16, 20 and therefore the average completion time will be \(\frac{5+13+16+20}{4}=13.5\).
Prove (with a written proof!) that sorting the \(n\) jobs in ascending order of \(t_j\) generates an optimal solution to the problem.
Exercise 2.1.3#
What is meant by a stable and an in-place sorting algorithm? For all the algorithms presented in the reference book, indicate whether they are in-place (or not) and whether they are stable (or not).
Answer the short INGInious MCQ.
Exercise 2.1.4 (INGInious: Card Sorter)#
How would you sort a pile of cards in ascending order with the restriction that the only permitted operations are:
compare the first two cards,
exchange the first two cards,
move the first card to the back of the pile?
Astuce
Try to maintain the invariant that the last i elements of the pile are sorted and are the i largest ones. Then at each iteration try to make this invariant true for one more card (i+1).
Write the pseudocode of your algorithm on paper and give its time complexity.
Once it is done, implement your solution on the INGInious task.
Exercise 2.1.5#
How can you sort a doubly linked list (which does not allow access to a position by index) efficiently? What is the time complexity of your algorithm?
Which algorithm is used by the sort method of the List interface below?
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = n; i >= 0; i++) {
list.add(i);
}
list.sort(Integer::compare);
Exercise 2.1.6#
Design an efficient algorithm for counting the number of inverted (out-of-order) pairs of values. For example, in the sequence \(1,3,2,5,6,4,8\), there are the pairs \((3,2), (5,4), (6,4)\) which are unordered. Justify the complexity of your algorithm and give its pseudocode.
Astuce
Assume two arrays \(A\) and \(B\), let \(A.B\) be the array resulting from the concatenation of \(A\) and \(B\). Let \(nUnsorted(A)\) be the number of unsorted pairs in an array \(A\).
We have the following property that you can prove:
What is the complexity of calculating \(|\{(i,j) : A[i]>B[j]\}|\)? Can this complexity be improved if \(A\) and \(B\) are sorted? Could you compute \(nUnsorted\) based on some adaptation of a well-known sorting algorithm that runs in \(\mathcal{O}(n \cdot \log(n))\)?
Exercise 2.1.7#
Imagine that we want to sort a collection of Person objects lexicographically by their (weight, age, height) and also Student objects by their (age, grade, year). How can you avoid duplicating the sorting algorithm specifically for these classes?
Explain why the Comparable and Comparator interfaces in Java are useful for this. Explain how you would implement an efficient Comparator for String.
Exercise 2.1.8#
Is it possible to get a stable sort starting from an unstable sorting algorithm? How?
Exercise 2.1.9#
How would you find the 3rd smallest value in an array of one million int values? What is the time complexity of your algorithm?
Exercise 2.1.10 (INGInious: Median)#
How would you get the median of an array of values (i.e., the \(\frac{n}{2}\)-th value)? What is the time complexity of your algorithm?
Solve the related INGInious task Median.
Astuce
What can you infer regarding the position of the median after the partitioning operation around a pivot value \(v\) in the QuickSort algorithm?
Exercise 2.1.11#
What is Autoboxing and Unboxing in Java? How can this impact the performance of a sorting algorithm?
Compare the performance of Arrays.sort on an array of 10,000,000 entries consisting of int and
the same array with Integer.
Exercise 2.1.12#
What is a code profiler? What information provided by a profiler could you use to improve the performance of your algorithms and data structures in general (speed, memory, GC)?
A good free profiler is VisualVM.
Use VisualVM on your code for the previous question.
Exercise 2.1.13 (INGInious: Merge Sort)#
Complete (without reading the book since you won’t have it during the exam) the implementation of Merge Sort.
Exercise 2.1.14 (INGInious: A Photographer problem)#
Help the photographer arrange players of two soccer teams so that everybody is visible in the picture (exam 2022): Photo.
Exercise 2.1.15 (INGInious: An Olympic Problem)#
Help the Olympic Games organizers compute the number of training rooms (exam 2024): TrainingSessions.
Exercise 2.1.16 (INGInious: Fix QuickSort)#
It seems that this QuickSort implementation does not always have the expected time complexity. Help us improve it: FixQuickSort.