Homework 1 CSc 4520/6520 Design and Analysis of Algorithms Fall 2017 Due: 5:00pm
ID: 3111602 • Letter: H
Question
Homework 1 CSc 4520/6520 Design and Analysis of Algorithms Fall 2017 Due: 5:00pm, Sept. 6, 2017 1. An integer matrix is all n x array of integers; for example: 3 10 1 112-18 A- 312-101 67 0 -23 3 10 5 A row is a series af umbers fron left to right and a column is the series from top to bottom. Here, we will modify inscrtion sort to sort the roxa of a matrix, with respect to their colums. For the above example, thi yields: 1 1012 -18 3-12-10 A-3 10 4 3 10 5 67 23 (a) (15 pts) Write pseudocode for this modified version of insertion sort ( MATRIXINSERTIONSORT) (b) (20 pts) Prove the best- and worst-cnse complexity of MATRIx- INSERTIONSOr. For simplicity, assume that the matrices are square e. they are nx n matrices, in which the number of rows is equal to the number of colus)Explanation / Answer
Here I am assuming you know the algorithm for InsertionSort
a. Array <--- array[m][n] //declare 2D array of size m and n and later initialize
insertionSort(array[m][n]) //pass array in real insertion sort algorithm
/**********************in InsertionSort*****************/
sort by columnwise // instead of swapping elements swap row arrays
now find where column elements are same and sort it according second column if elemnts of second column are same sort according to subsequent column
tip: // use insertion sort algorithm for above, in that algorithm change 1D array with 2D array and single elements with row array
b. best case is when all the elements in first column are different so we will not have to worry about second column so time complexity only n2
worst case is when all the elements in first n-1 columns are same and only last column elements are different(optional because if same not much difference it will make), here we will have to sort columnwise so for every column we will get n2 time so we will have to sort all n columns due to that time complexity will be n3
c. It will not be same, in this case , worst-case complexity of MATRIX- INSERTION-SORT, is better than the regular insertion sort.
Hope this Helps!!
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.