Reference no: EM132401066
Assignment 1
Sort the sequence 4 6 8 2 9 5 1 7 3 with:
• Insertion sort
• Selection sort
• Quicksort (picking the first element as the pivot)
• Quicksort (using the median-of-three pivot)
• Mergesort
A sorting algorithm is stable if equal elements always remain in the same relative order before and after sorting. Which of our sorting algorithms are stable? Why?
Write a method or function that removes all duplicate elements from a Java array or Haskell list in O(n log n) time. Hint: sort the array first (you may use the sorting function from the standard library).
Assignment 2
For each of the following recurrences, first guess an exact closed-form solution, and then prove your guess is correct. You are free to use any method you want to make your guess-unrolling the recurrence, writing out the first several values, induction proof template, recursion trees, annihilators, transformations, 'It looks like that other one', whatever-but please describe your method. All functions are from the non-negative integers to the reals. If it simplifies your solutions, express them in terms of Fibonacci numbers Fn, harmonic numbers Hn, binomial coefficients (kn), factorials n!, and/or the floor and ceiling functions [x] and [x].
(a) A(n) = A(n -1) + 1, where A(0) = 0.
(b) B(n) = 0 if n < 5; B(n - 5) + 2 otherwise
(c) C(n)= C(n -1)+ 2n -1, where C(0) = 0.
(d) D(n) = D(n -1) + (n/2), where D(0) = 0.
(e) E(n) = E(n -1) + 2n, where E(0) = 0.
(0 F(n)= 3.F(n -1), where F(0) = 1.
(g) G(n) = G(n-1)/G(n-2), where G(0) = 1 and G(1) = 2. [Hint: This is easier than it looks.]