Alorithms

Topics in this chapter

• Fundamentals and Properties of Algorithms
• Asymptotic Analysis and Time Complexity
• Searching Techniques (Linear and Binary Search)
• Sorting Algorithms (Bubble, Selection, Insertion, Merge)
• Array and String Processing Algorithms
• Mathematical and Number-Theoretic Algorithms
• Advanced Algorithm Design and Divide-and-Conquer

Cheat sheet

Practice questions

1. Question 1Q-203DC4

   Which condition is necessary before applying binary search to an array?

   1. A.The array must contain only integer values.
   2. B.The array must be sorted.
   3. C.The array must have an even number of elements.
   4. D.The array must not contain duplicate values.
   See the answer and solution
2. Question 2Q-1AA8E4

   Explain why binary search cannot generally be applied directly to an unsorted array. Also state the worst-case time complexity of linear search and binary search for an array of n elements.

   See the answer and solution
3. Question 3Q-D77CE7

   What is the array after the first complete pass of selection sort in ascending order on [29, 10, 14, 37, 13]?

   1. A.[10, 29, 14, 37, 13]
   2. B.[29, 10, 13, 37, 14]
   3. C.[10, 14, 13, 29, 37]
   4. D.[13, 10, 14, 37, 29]
   See the answer and solution
4. Question 4Q-E5BE84

   Which statement correctly describes the worst-case time complexity of insertion sort and the situation in which it performs efficiently?

   1. A.Its worst-case time complexity is O(log n), and it is efficient for randomly arranged data.
   2. B.Its worst-case time complexity is O(n), and it is efficient for reverse-sorted data.
   3. C.Its worst-case time complexity is O(n²), and it is efficient when the data is already or nearly sorted.
   4. D.Its worst-case time complexity is O(n²), and it is efficient only when all elements are identical.
   See the answer and solution
5. Question 5Q-5AFFB3

   Explain why merge sort is generally preferred over selection sort for sorting a large collection of data. State the time complexity of both algorithms in the average or worst case.

   See the answer and solution