Algorithms
Sorting
Learning Objectives:
- Recognize the significance of sorting in data analysis, searching, and optimization.
- Learn about comparison-based sorting algorithms, such as bubble sort, selection sort, insertion sort, and merge sort.
- Understand the principles, time complexities, and best-case/worst-case scenarios for each algorithm.
- Bubble Sort: It sorts by comparing each pair of adjacent items and swapping them in the order. This will be repeated until no swaps are needed. The algorithm got its name from the way smaller elements "bubble" to the top of the list. It is not that much efficient, when a list is having more than a few elements. Among simple sorting algorithms, algorithms like insertion sort are usually considered as more efficient. Bubble sort is little slower compared to other sorting techniques but it is easy because it deals with only two elements at a time.
- Insertion Sort It is a simple Sorting algorithm which sorts the array by shifting elements one by one. Following are some of the important characteristics of Insertion Sort.
- It has one of the simplest implementation
- It is efficient for smaller data sets, but very inefficient for larger lists.
- Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.
- It is better than Selection Sort and Bubble Sort algorithms.
- Its space complexity is less, like Bubble Sorting, insertion sort also requires a single additional memory space.
- It is Stable, as it does not change the relative order of elements with equal keys
- Quick Sort Quick sort works by partitioning the array to be sorted.
- each partition is internally sorted recursively.
- As a first Step, this algorithm chooses one elements of an array as a pivot or a key element.
- the array is then partitioned on either side of the pivot.
- elements are moved so that those greater then the pivot are shifted to its right where as the others are shifted to its left.
- two pointers low and up are initialized to the lower and upper boundes of the sub array.
- up pointer will be decremented and low pointer will be incremented as per following condition.
- Increase low pointer until t[low] > pivot.
- Decrease up pointer until t[up] <= pivot.
- If low < up then interchange t[low] with t[up].
- If up <= low then interchange t[up] with t[i].
- Merge Sort
- Select Sort
- Bucket Sort
Solved Example: 9972-01
Let P be a quicksort program to sort numbers in ascending order using the first element as the pivot. Let $t_1$ and $t_2$ be the number of comparison made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?
A. $t_1$ = 5
B. $t_1$ < $t_2$
C. $t_1$ > $t_2$
D. $t_1$ = $t_2$
Correct Answer: C
Solved Example: 9972-02
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64.
Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?A. 256
B. 512
C. 1024
D. 2048
Correct Answer: B
Solved Example: 9972-03
An array of 25 distinct elements is to be sorted using quick sort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is:
A. 0.02
B. 0.04
C. 0.08
D. 0.16
Correct Answer: C
Solved Example: 9972-04
Consider the following array: \[23,32,45,69,72,73,89,97\] Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort above array in ascending order?
A. Insertion sort
B. Selection sort
C. Quicksort using the last element as pivot
D. Merge sort
Correct Answer: A
Solved Example: 9972-05
Which of the following is a type of sorting algorithm?
A. Binary search
B. Quick sort
C. Depth-first search
D. Breadth-first search
Quick sort is a popular sorting algorithm used for sorting arrays and lists in ascending or descending order.
Correct Answer: B
Searching
Learning Objectives:
-
Recognize the importance of searching in data retrieval, data analysis, and problem-solving.
- Learn the linear search, binary Search algorithm and its basic principles and their time complexity.
Searching algorithm is an algorithm made up of a series of instructions that retrieves information stored within some data structure, or calculated in the search space of a problem domain.
Search algorithms:
- Linear search
- Step I: Start with the leftmost element of array and one by one compare x with each element of the array.
- Step II: If x matches with an element, return the index.
- Step III: If x doesn't match with any of elements, return -1.
- Binary search: Can be performed only on a sorted list. Uses divide and conquer technique to search the list.
- Step I:Search element is compared with the midlle of the list.
- Step II: If search item < middle element of the list, search is restricted to the first half of the list.
- Step III: If search item > middle element of the list, search is restricted to the second half of the list.
- Step IV: If search item = middle element of the list, search is complete.
- Jump search
- Interpolation search
- Exponential search
- Ternary search
Solved Example: 9240-01
Finding the location of the element with a given value is:
A. Traversal
B. Search
C. Sort
D. None of the options
Correct Answer: B
Solved Example: 9240-02
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?
A. $\dfrac{97^3}{100^3}$
B. $\dfrac{99 \times 98 \times 97}{100^3}$
C. $\dfrac{97 \times 96 \times 95}{100^3}$
D. $\dfrac{97 \times 96 \times 95}{3! \times 100^3}$
Correct Answer: A
Solved Example: 9240-03
A _______ is an ordered collection of finite, homogeneous data elements.
A. Linked List
B. Graph
C. Tree
D. Hash Table
Correct Answer: A
Complexity
The complexity of an algorithm is a way to classify how efficient an algorithm is, compared to alternative ones. The focus is on how execution time increases with the data set to be processed.
We are usually interested in the worst case complexity: What are the most operations that might be performed for a given problem size.
Classes of Complexity:
- Constant time (C): The time necessary to perform the algorithm does not change in response to the size of the problem.
- Linear time (n): The time grows linearly with the size (n) of the problem.
- Quadratic time (n$^2$): The time grows quadratically with the size (n) of the problem.
Worst case complexities of common Sorting algorithms:
- Slection Sort: (n$^2$)
- Insertion Sort: (n$^2$)
- Merge Sort: (n $\log$ n)
- Quick Sort: (n$^2$)
Asymptotic Notations:
Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.- O notation
- $\Omega$ notation
- $\theta$ notation
Solved Example: 9239-01
There are n unsorted arrays: A$_1$, A$_2$ , ..., A$_n$. Assume that n is odd. Each of A$_1$, A$_2$, ..., A$_n$ contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A$_1$, A$_2$, ..., A$_n$ is:
A. O(n)
B. O(n log n)
C. O(n$^2$)
D. $\Omega$(n$^2$ log n)
Correct Answer: C
Solved Example: 9239-02
Consider the following C function.
int fun(int n) {
int i, j;
for (i = 1; i < = n; i++) {
for (j = 1; j < n; j + = i) {
printf (‘’ %d %d’’, i, j);
}
}
}
Time complexity of fun in terms of Θ notation is
A. $\Theta (n \sqrt{n})$
B. $\Theta (n^2)$
C. $\Theta (nlog n)$
D. $\Theta (n^2 log n)$
Correct Answer: C
Solved Example: 9239-03
Let $f(n) = n$ and $g(n) = n^{(1 + sin n)}$, where n is a positive integer. Which of the following statements is/are correct?
I. $f(n) = O(g(n))$
II. $f(n) = \Omega(g(n))$
A. Only I
B. Only II
C. Both I and II
D. Neither I nor II
Correct Answer: D
Solved Example: 9239-04
What is the complexity of the following code?
sum=0;
for (i=1; I <= n; i*=2)
A. O(n$^2$)
B. O(n log n)
C. O(n)
D. O(n log n log n)
Correct Answer: B
Big-O
- Big O notation (with a capital letter O, not a zero), also called Landau's symbol, is a symbolism used in complexity theory, computer science, and mathematics to describe the basic behavior of functions. Basically, it tells you how fast a function grows or declines.
- Landau's symbol comes from the name of the German mathematician Edmund Landau who invented the notation.
- The letter O is used because the rate of growth of a function is also called its order.
- What is Big O notation??? It describes:
- Efficiency of an Algorithm
- Time Factor of an Algorithm
- Space Complexity of an Algorithm It is represented by O(n) where n is the number of operations.
Solved Example: 9152-01
What is the space complexity of insertion sort? (Consider input size and additional storage)
A. O(n)
B. O(n^2)
C. O(n log n)
D. O(1)
Correct Answer: A