CS 425: THEORY OF ALGORITHMS DATE: 09/26/2018 TOTAL: 50 points (score will be do

Question

CS 425: THEORY OF ALGORITHMS DATE: 09/26/2018 TOTAL: 50 points (score will be doubled) 1 Short Questions (2 points) a) Explain runtime of an algorithm b) Given the following data set 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26 What would be the runtime to sort these data, if (0) Insertion Sort is used and (i) Selection Sort is used? (2 x 2 4 pts) (c) Name three steps of divide and conquer algorithm (2 pts) (d) Give names of at least two algorithms which are based on Divide and Conquer algorithm. 2 points)

Explanation / Answer

1) Runtime of an algorithm depends on the number of operations executed. More the number of operations the more will be the running time of an algorithm.

2) Runtime to sort the given data

a)Insertion Sort: We know that the runtime for insertion sort for N elements is N2. So for 2N elements it will be 4N2.

From the given data: Number of elements are 13 i.e N=13.

So the runtime for sorting these data will be 132.

b) Selection Sort: For selection sort also runtime is N2

So the runtime for sorting 13 elements is 132.

3) The three steps of divide and conquer algorithm are:

4) Two algorithms based on Divide and Conquer algorithm are:

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---