Scribd
Upload
20 views

GLA University, Mathura Design and Analysis of Algorithms Tutorial-1 B.Tech-V Semester

The document discusses algorithms and their analysis. It provides pseudocode for selection sort and asks to modify insertion sort to sort in non-increasing order. It proves that max(f(n), g(n)) = Θ(f(n) + g(n)) for asymptotically nonnegative functions f(n) and g(n). It asks questions about the time complexity of algorithms like linear search, merge sort on strings, and master theorem for divide and conquer algorithms. It also asks about the tightest upper bound for the number of swaps in selection sort and the time complexity of a given function.

Uploaded by

Gaurav Yadav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
20 views

GLA University, Mathura Design and Analysis of Algorithms Tutorial-1 B.Tech-V Semester

The document discusses algorithms and their analysis. It provides pseudocode for selection sort and asks to modify insertion sort to sort in non-increasing order. It proves that max(f(n), g(n)) = Θ(f(n) + g(n)) for asymptotically nonnegative functions f(n) and g(n). It asks questions about the time complexity of algorithms like linear search, merge sort on strings, and master theorem for divide and conquer algorithms. It also asks about the tightest upper bound for the number of swaps in selection sort and the time complexity of a given function.

Uploaded by

Gaurav Yadav
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

GLA University, Mathura

Design and Analysis of Algorithms


Tutorial-1
B.Tech-V Semester
1.

Consider sorting n numbers stored in array A by first finding the smallest element
of A and exchanging it with the element in A[1]. Then find the second smallest
element of A, and exchange it with A[2]. Continue in this manner for the first n - 1
elements of A. Write pseudocode for this algorithm. Give the best-case and worstcase running times of selection sort in -notation.

2.
Write the INSERTION-SORT procedure to sort into nonincreasing instead of
nondecreasing.
3.
Let f(n) and g(n) be asymptotically nonnegative functions. Using the basic
definition of -notation, prove that max(f(n), g(n)) = (f(n) + g(n)).
4.
5.
6. List of n strings, each of length n, is sorted into lexicographic order using the mergesort algorithm. The worst case running time of this computation is
O (n log n) (B) O (n2 log n) (C) O (n2 + log n) (D) O (n2)
7. Which of the
n^(1/2)

following functions has the largest growth rate?


(B) n^100

(C) 2^(n/2)

8. The complexity of linear search algorithm is


(A) O(n)
(B) O(log n)
(C) O(n2)

(D) 2^(n!)

(D) O(n log n)

9. Which of the given options provides the increasing order of


asymptotic complexity of functions f1, f2, f3 and f4?
f1(n) = 2^n, f2(n) = n^(3/2), f3(n) = nLogn, f4(n) = n^(Logn)
(A) f3, f2, f4, f1
(B) f3, f2, f1, f4
( C) f2, f3, f1, f4
(D) f2, f3,
f4, f1
10. The Merge sort is what kind of algorithm?
(A) divide and conquer; (B) greedy; (C) brute force; (D) dynamic
programming; (E) probabilistic
11. The Master Theorem (Main Recurrence Theorem)
(A) is used to prove correctness of algorithms; (B) gives general solutions to
time recurrences for divide-andconquer algorithms; (C) gives intractability
results;
(D) is proven by temporal logic; (e) none of these
12. Input comprises a sorted list of n integers with many duplications
such that the number of distinct integers in the sequence is O (log n), the
time complexity to find an element in the list is given by,

(A) O(n)
(1)

( B) O(log n)

(C) O(log log n)

( D)

13. Which one of the following is the tightest upper bound that
represents the number of swaps required to sort n numbers using selection
sort?
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D)
O(n2)
14. Consider the following function:
The return value of the function is
(A) (n2)
(B) (n2log n)
(D)(n3logn)
15.

(C) (n3)

You might also like