Algorithms Answers

Consider the following two variants of the pseudo code for the Insertion Sort algorithm. Using each variant, sort the array: 51 52 53 54 55. Note that 51, 52, ..., 55 are five different instants of integer 5 and need to be treated as separate elements (that are of the same numerical value). Determine the number of comparisons encountered with each of the two variants of the algorithm to sort the above array and what is the final sorted array (include the suffixes of the elements throughout your work).


Pseudo Code - I Pseudo Code - II

Use pseudocode to describe an algorithm that displays the last occurrence of each element in an input sequence a_0,a_1,…,a_n. In other words, if an element appears more than once in the sequence, only the last occurrence is displayed.

Example:

4, -5, 3, 2, 3, -1, 4, 3  displays -5, 2, -1, 4, 3

Determine the running time of your algorithm as a function of n (in the worst, best and average case) and then use asymptotic notation to simplify it.