Assignment Task 1: Sort the sequence 4 6 8 2 9 5 1 7 3 with:
- Insertion sort
- Selection sort
- Quick sort (picking the first element as the pivot)
- Quick sort (using the median-of-three pivot)
- Merge sort
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 Task 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 (nk), 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) + (n2), where D(0) = 0.
(e) E(n)= E(n - 1) + 2n, 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.]
Assignment 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.
Our professional Sorting Algorithm Assignment Help tutors always do a thorough research before drafting any assignment paper and always write the paper from the scratch, so that, students always get the most authentic, error-free and plagiarism free assignment paper every time.
Tags: Sorting Algorithm Assignment Help, Sorting Algorithm Homework Help, Sorting Algorithm Coursework, Sorting Algorithm Solved Assignments, Insertion Sort Assignment Help, Insertion Sort Homework Help, Selection Sort Assignment Help, Selection Sort Homework Help, Quick Sort Assignment Help, Quick Sort Homework Help, Merge Sort Assignment Help, Merge Sort Homework Help
Attachment:- Data Structures & Algorithms.rar