Reference no: EM132428606

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

i. 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 (ⁿ_k), factorials n!, and/or the floor and ceiling functions [x] and [x].

(a) A(n) = A(n - 1) + 1, where A(0) = 0.
              {0 if n < 5     if n < 5
(b) B(n)=  {B(n-5) + 2   otherwise
(c) C(n)= C(n -1)+ 2n -1, where C(0) = 0.
(d) D(n) = D(n -1) + (ⁿ₂), where D(0) = 0.
(e) E(n)= E(n - 1) + 2ⁿ, where E(0) = 0.
(f) 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.]

Project

Create any program based from Algorithms with the following properties developed by Richard Jonhsonbaugh and Marcus Schaefer (2004):

Input. The algorithm receives input

Output. The algorithm receives output

Precision. The steps are precisely stated

Determinism. The intermediate results of each step of execution are unique and are determined only by the inputs and results of the preceding steps.

Finiteness. The algorithm terminates; that is it stops after finitely many instructions have been executed.

Correctness. The output produced by the algorithm is correct

Research and present an algorithm and consider the following in the Analysis of Algorithms. Correctness. Does the given algorithm solve the problem?

Termination. Does the algorithm always stop after a finite number steps? · Time Analysis. How many instructions does the algorithm execute? Discuss in detail each properties of the researched algorithm.

Attachment:- Project Data Structures.rar