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 indicate an algorithm to find the position where to insert \(x\) while keeping the array sorted?
What is the 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 duration of the jobs is 5,8,3,4 and the jobs are carried out in this order, the end times will be 5,13,16,20 and therefore the average end 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 in place sorting algorithm? For all the algorithms presented in the reference book, indicate whether they are in place (or not) or stable (or not).
Answer to the small Inginious MCQ
Exercise 2.1.4 (Inginious)¶
How would you sort increasingly a pile of cards 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 those are the ith biggest ones. Then at each iteration try to make this invariant true for one more card (i+1).
Write the pseudo code of your algorithm on paper and give the complexity.
Once it is done, implement your solution on the inginious task
Exercise 2.1.5¶
How to sort a doubly linked list (which therefore does not allow access to a position by its index) efficiently? How complex is your algorithm?
Which algorithm is used by the sort method of the Collections class 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 pairs of disordered 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 pseudo code.
Astuce
Assume two arrays \(A\) and \(B\), let \(A.B\) be the array result of 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 to calculate \(|\{(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) but also Student objects by their (age, grade, year), how to avoid duplicating the sorting algorithm specifically for these classes?
Explain why the notions of Comparable and Comparator of 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 get the 3rd smallest value in an array of one million int? How complex is your algorithm?
Exercise 2.1.10 (Inginious)¶
How would you get the median of an array of values (so 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 \(v\) value in Quick-Sort 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 java.util.Sort on an array of 10000000 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 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)¶
Complete (without reading the book since you won’t have it at the exam) the implementation of Merge Sort
