Q1)Suppose you are given an array A of n elements. Your task is to sort n numbers stored in array A by reading the first element of A and placing it on its original position (position after sorting). Then read the second element of A, and place it on its original position. Continue in this manner for the first n-1 elements of A. What type of sorting is this? Write the algorithm and also mention the name of this sorting algorithm. What loop invariant does this algorithm maintain? Give the best-case and worst-case running times of this sorting algorithm.
Q1)Suppose you are given an array A of n elements. Your task is to sort n numbers stored in array A by reading the first element of A and placing it on its original position (position after sorting). Then read the second element of A, and place it on its original position. Continue in this manner for the first n-1 elements of A. What type of sorting is this? Write the
Q2)Consider an array consisting of the following sequence: 1, 4, 9, 16, 25, 49, …, n
Suppose a number in the sequence is missing.
- Write the mathematical process to find the missing number, i.e. some equation.
- What is the time complexity of finding the missing number in the sequence?
Q3)Sort the text “SARHAD UNIVERSITY” in ascending order using the insertion sort algorithm. Discuss also the best, worst and average case complexity of the algorithm.
Q4)Arrange the Big-Oh complexities specified in Question 3 according to the order of their growth.
Q6)Consider an empty stack STK of size 5 (array-based implementation). What will be the output after applying the following stack operations? Draw a diagram in support of your answer. How many elements are there in the stack at the end of the processing?POP(), PUSH(9), PUSH(11), PUSH(25), POP(), POP(), PUSH(42), POP(), PUSH(3), PUSH(7), PUSH(30), PUSH(15), PUSH(54),POP(), PUSH(50)
Step by step
Solved in 2 steps