Experiment 1: linear Search
Q1. What is best case efficiency of linear search?
Ans. The best case efficiency of linear search is O(1).
Q2. Linear search is special case of which search.
Ans. Linear search is special case of brute-force search.
Q3. What are the various applications of linear search?
Ans. Linear search is usually very simple to implement, and is practical when the list has only a
few elements, or when performing a single search in an unordered list. When many values have
to be searched in the same list, it often pays to pre-process the latter in order to use a faster
method.
Q4. What is worse case?
Ans. In the worse case, the no. of average case we may have to scan half of the size of the array
(n/2)
Q5. During linear search, when the record is present in first position then how many
comparisons are made ?
Ans. Only one comparison.
Experiment No.-2 Binary Search
Q1. What is the worst case complexity of binary search using recursion?
Ans. O(logn)
Q2. What is the average case time complexity of binary search using recursion?
Ans. O(logn)
Q3. What are the applications of binary search?
Ans. Union of intervals
Q4. Binary Search can be categorized into which of the following?
Ans. Divide and conquer
Q5. What is the time complexity of binary search with iteration?
Ans. O(logn)
Experiment No.-3. Selection Sort
Q1. What is the worst case performance of selection sort?
Ans. The worst case performance of selection sort is O(n2).
Q2. Selection sort is suitable for which type of list.
Ans. Selection sort is suitable for small list.
Q3. What is the best case performance of selection sort?
Ans. The best case performance of selection sort is O(n2).
Q4. What is the worst case space complexity of selection sort?
Ans. The worst case space complexity of selection sort is O(n) total, O(1) auxiliary.
Q5. How many comparisons are performed in the second pass of the selection sort
algorithm?
Ans. n-2 comparisons are performed in the second pass of the selection sort algorithm.
Experiments No.-4. Insertion Sort
Q1. What is the best case complexity for insertion sort algorithm
Ans. O(n)
Q2. What is the worst case complexity for insertion sort algorithm
Ans. O(n*n)
Q3. Total number of comparisons for insertion sort is
Ans. n(n-1)/2
Q4. In which cases are the time complexities same in insertion sort?
Ans. Worst and Average
Q5. For insertion sort, the number of entries we must index through when there are n
elements in the array is
Ans. n-1 entries
Experiment No.-5 Bubble Sort
Q1. How do we define bubble sort?
Ans. Bubble sort repeatedly scan the list, comparing adjacent elements swapping them if they are
in wrong order.
Q2. How can the efficiency of bubble sort algorithm be determined?
Ans. The efficiency of bubble sort algorithm can be determined in terms of the number of
comparisons.
Q3. What is the complexity of the bubble sort algorithm?
Ans. The complexity is O(n2). The time required to execute the bubble sort algorithm is
proportional to (n2), where n is the number of input items.
Q4. What are the basic criteria for selecting appropriate algorithm?
Ans. Execution Time, Storage Space, Programming Effort
Q5. What is the advantage of bubble sort over other sorting techniques
Ans. Detects whether the input is already sorted
Experiment No.-6 Merge Sort
Q1. Merge sort uses which of the following technique to implement sorting?
Ans. divide and conquer
Q2. Which of the following method is used for sorting in merge sort?
Ans. Merging
Q3. Which of the following is not a variant of merge sort?
Ans. linear merge sort
Q4. Merge sort is preferred for arrays over linked lists. Is it True or False ?
Ans. False
Q5. What will be the best case time complexity of merge sort?
Ans. O(n log n)
Experiment No.-7 Quick Sort
Q1. Quick sort is also known as
Ans. Pointer sort and External sorting
Q2. In which cases are the time complexities same in quick sort?
Ans. Best and Average
Q3. What pattern of splits gives the worst-case performance for quick sort?
Ans. Descending order.
Q4. In quick sort the pivot value is usually the
Ans. Any Element
Q5. What is the Best case, Average case and worst case complexity for quick sort algorithm
Ans. Best Case- O(nlogn) Average Case- O(nlogn) Worst Case- O(n*n)
Experiment No.-8 Strassen’s Matrix Multiplication
Q1. Strassen’s algorithm is a/an_____________ algorithm.
Ans. Recursive
Q2. Strassen’s matrix multiplication algorithm follows ___________ technique.
Ans. Divide and Conquer
Q3. Running time of Strassen’s algorithm is better than the naïve Theta(n3) method.
Ans. True
Q4. What is the recurrence relation used in Strassen’s algorithm?
Ans. 7T(n/2) + Theta(n2)
Q5. Strassen’s Matrix Algorithm was proposed by _____________
Ans. Volker Strassen
Experiment No.-9 Matrix Chain Multiplication
Q1. Which methods can be used to solve the matrix chain multiplication problem?
Ans. Dynamic programming, Brute force, Recursion
Q2. Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively.
What is the number of multiplications required to multiply the two matrices?
Ans. 10*20*30
Q3. Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices
respectively. What is the minimum number of multiplications required to multiply the three
matrices?
Ans. 18000
Q4. Consider the brute force implementation in which we find all the possible ways of
multiplying the given set of n matrices. What is the time complexity of this implementation?
Ans. Exponential
Q5. What is the time complexity of the above dynamic programming implementation of the
matrix chain problem?
Ans. O(n3)
Experiment No.-10 Longest Common Subsequences
Q1. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the
longest common subsequence?
Ans. 7
Q2. Longest common subsequence is an example of ____________
Ans. 2D dynamic programming
Q3. What is the time complexity of the above dynamic programming implementation of the
longest common subsequence problem where length of one string is “m” and the length of the
other string is “n”?
Ans. O(mn)
Q4. Which of the following is the longest common subsequence between the strings
“hbcfgmnapq” and “cbhgrsfnmq” ?
Ans. hgmq, cfnq, bfmq
Q5. What is the time complexity of the brute force algorithm used to find the longest common
subsequence?
Ans. O(2n)
Experiment No.-11 0-1 Knapsack Problem
Q1. The Knapsack problem is an example of ____________
Ans. 2D dynamic programming
Q2. Which methods can be used to solve the Knapsack problem?
Ans. Brute force algorithm, Recursion, Dynamic programming
Q3. You are given a knapsack that can carry a maximum weight of 60. There are 4 items with
weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items
you can carry using the knapsack?
Ans. 160
Q4. What is the time complexity of the brute force algorithm used to solve the Knapsack
problem?
Ans. O(2n)
Q5. The 0-1 Knapsack problem can be solved using Greedy algorithm.
Ans. False
