Algorithms Test 1

Concept:

Dijkstra’s algorithm is used to find single source shortest path i.e path between any two vertices in a graph. All edges must have non-negative weights and graph must be connected.

Explanation:

V	a	b	c	d	e	f	g
a	0a	3a	5a	6a	Inf	Inf	Inf
b	0a	3a	5a	5b	Inf	Inf	Inf
C	0a	3a	5a	5b	11c	8c	12c
d	0a	3a	5a	5b	11c	8c	12c
f	0a	3a	5a	5b	11c	8c	9f

So, we get the shortest distance from a to g . (a -> b -> c -> d -> f -> g).

• The worst case of QuickSort occurs when the picked pivot is always one of the corner elements in sorted array. In worst case, QuickSort recursively calls one subproblem with size 0 and other subproblem with size (n-1).
• So recurrence is T(n) = T(n-1) + T(0) + O(n).
• The above expression can be rewritten as T(n) = T(n-1) + O(n) 

void exchange(int *a, int *b) 
{ 
int temp; 
temp = *a; 
*a = *b; 
*b = temp; 
} 

int partition(int arr[], int si, int ei) 
{ 
int x = arr[ei]; 
int i = (si - 1); 
int j; 

for (j = si; j <= ei - 1; j++) 
{ 
    if(arr[j] <= x) 
    { 
    i++; 
    exchange(&arr[i], &arr[j]); 
    } 
} 

exchange (&arr[i + 1], &arr[ei]); 
return (i + 1); 
} 

/* Implementation of Quick Sort 
arr[] --> Array to be sorted 
si --> Starting index 
ei --> Ending index 
*/
void quickSort(int arr[], int si, int ei) 
{ 
int pi; /* Partitioning index */
if(si < ei) 
{ 
    pi = partition(arr, si, ei); 
    quickSort(arr, si, pi - 1); 
    quickSort(arr, pi + 1, ei); 
} 
}

Insertion sort takes linear time when input array is sorted or almost sorted (maximum 1 or 2 elements are misplaced). All other sorting algorithms mentioned above will take more than linear time in their typical implementation.

Binary search algorithm:

Binary search algorithm is used to find an element in an already sorted array.

STEPS 1:

It finds the middle element of the array and compare the element with the element to be searched, if it matches then return true.

STEPS 2:

If not, then divide the array into two halves in which if element to be search is less than middle element then search takes place in left part otherwise search in right half.

STEP 3:

Repeat this process, until you get the element.

Explanation:

For worst case 52

Worst Case: Search 50 in below give array

11

12

15

24

35

50

51

63

 

\({\rm{midde\;index}} = \frac{{0 + 9}}{2} = 4\therefore {\rm{a}}\left[ 4 \right] = 35\)

50 > 32

\({\rm{midde\;index}} = \frac{{5 + 9}}{2} = 7\;\therefore {\rm{a}}\left[ 7 \right] = 63\)

50 < 63

\({\rm{midde\;index}} = \frac{{5 + 6}}{2} = 8\;\therefore {\rm{a}}\left[ 5 \right] = 50\)

matched

T(n) = O(log n)

Also, for average case:

T(n) = O(log n)

Concept:

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent pairs, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

Explanation:

In 1^st iteration: 25, 9, 15, 30, 11, 17 , 22

Output: 9, 15, 25, 11, 17, 22, 30

In 2^nd  iteration: 9 15 25 11 17 22 30

Output: 9 15 11 17 22 25 30

11 is at index 2.

Important Point:

int A = {25, 9, 15, 30, 11, 17 , 22} //index starts with 0

For the first loop it will run n times

for(i = 0; i < n; i ++ ) → complexity is O(n).

For the second loop it will run for ⌈log₂ m⌉

for(int j = m ; j > 0; j= j/2) → complexity is O(log₂m).

Since Outer loop has complexity O(n) and inner loop has complexity O(log₂m)

Time complexity for code block = O(n × log₂m)

•  Huffman Coding uses Greedy approach to solve the problem
• Merge sort is an efficient sorting algorithm that uses a divide-and-conquer approach to order elements in an array.
• Dynamic Programming is used in Coin change problem

7 and 9 both are at their correct positions (as in a sorted array). Also, all elements on left of 7 and 9 are smaller than 7 and 9 respectively and on right are greater than 7 and 9 respectively.

Selection sort makes O(n) swaps which is minimum among all sorting algorithms mentioned above.

Master Theorem: T(n)= aT(n/b)+f(n); a>=1,b>1.

Therefore a = 2, b = 2, f(n) = nlogn

\(n^{log_ba} = n^{log_22}=n\)

\({f(n) > n^{log_ba}}\)

∴  T(n) = O(n(logn)²)

If G is a directed graph, the sum of the lengths of all the adjacency lists is |E|. If G is an undirected graph, the sum of the lengths of all the adjacency lists is 2|E|. For both directed and undirected graphs, the adjacency-list representation has the desirable property that the amount of memory it requires is θ(V+E).

In Heapsort, we first build a heap, then we do following operations till the heap size becomes 1. a) Swap the root with last element b) Call heapify for root c) reduce the heap size by 1. In this question, it is given that heapify has been called few times and we see that last two elements in given array are the 2 maximum elements in array. So situation is clear, it is maxheapify whic has been called 2 times.

Using optimal algorithm (merge sort)

Sequence: 25, 31, 37, 49, 57

Ascending order: 25, 31, 37, 49, 57

Merge(25, 31) → new size (56)

Number of comparisons = 25 + 31 – 1 = 55 

Sequence: 37, 49, 56, 57

Merge(37, 49) → new size (86)

Number of comparisons = 37 + 49 – 1 = 85  

Sequence:  56, 57, 86

Merge(56, 57) → new size (113)

Number of comparisons = 56 + 57 – 1 = 112

Sequence: 86, 113

Merge(86, 113) → new size (199)

Number of comparisons = 86 + 113 – 1 = 198  

Therefore, total number of comparisons, 55+ 85 + 112 + 198 = 450

The only significant advantage that bubble sort has over most other algorithms, even quicksort, but not insertion sort, is that the ability to detect that the list is sorted efficiently is built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only O(n).

The data can be sorted using external sorting which uses merging technique. This can be done as follows: 1. Divide the data into 10 groups each of size 100. 2. Sort each group and write them to disk. 3. Load 10 items from each group into main memory. 4. Output the smallest item from the main memory to disk. Load the next item from the group whose item was chosen. 5. Loop step #4 until all items are not outputted. The step 3-5 is called as merging technique.

1. To sort the array firstly create a min-heap with first k+1 elements and a separate array as resultant array.
2. Because elements are at most k distance apart from original position so, it is guranteed that the smallest element will be in this K+1 elements.
3. Remove the smallest element from the min-heap(extract min) and put it in the result array.
4. Now,insert another element from the unsorted array into the mean-heap, now,the second smallest element will be in this, perform extract min and continue this process until no more elements are in the unsorted array.finally, use simple heap sort for the remaining elements

Time Complexity

1. O(k) to build the initial min-heap.
2. O((n-k)logk) for remaining elements.
3. 0(1) for extract min.

So overall O(k) + O((n-k)logk) + 0(1) = O(nlogk)

Out of the given options quick sort is the only algorithm which is not stable. Merge sort is a stable sorting algorithm.

Any comparison based sorting algorithm can be made stable by using position as a criteria when two elements are compared. Counting Sort is not a comparison based sorting algorithm. Heap Sort is not a comparison based sorting algorithm.

Applying binary search to calculate the position of the data to be inserted doesn't reduce the time complexity of insertion sort. This is because insertion of a data at an appropriate position involves two steps: 1. Calculate the position. 2. Shift the data from the position calculated in step #1 one step right to create a gap where the data will be inserted. Using binary search reduces the time complexity in step #1 from O(N) to O(logN). But, the time complexity in step #2 still remains O(N). So, overall complexity remains O(N²).

Concept:

Keys: 5, 28, 19, 15, 20, 33, 12, 17,

10.

ℎ(k) = k mod 9

Chaining

Maximum chain length = 3 (28 -> 19 -> 10)

Minimum chain length = 0 (0, 4, 7 slot doesn’t have any element)

\({\rm{Average\;chain\;length\;}} = \frac{{0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1}}{9} = \frac{9}{9} = 1\)

Hence option 1 is the correct answer.

The insertion sort will take  time when input array is already sorted.

Data:

T1 = 256 sec = 28 sec

number of elements  = n₁ = (2÷ 2) M =  2²⁰

T2 = 81.92 min = 81.92 × 60 sec

Formula:

Time complexity of merge sort is O(nlog2n),

T = c × n × log2n

where c is constant

Calculation:

T1 = c × n1 × log2 n1

28 = c × 2²0 × log2 220

1 = c × 212 × 20

\(\therefore c = \frac{1}{{{5×2^{14}}}}\)

T2 = c × n × log2n

\(81.92 × 60 = \frac{1}{{{5×2^{14}}}}\;{n_2}{\log _2}{n_2}\)

nLog2n = 24576 × 214

nLog2n = 24 × 224

∴ n = 224

Size = 2× 224 = 32 MB

Concepts:

Initialize the first row and first column with 0.

If there is match, A[i, j] = A[i – 1, j  – 1] + 1

If not match: max(A[i – 1, j], A[i, j – 1])

Table of longest common subsequence:

	M →	a	b	a	b	a	b	b	a	a
N↓	0	0	0	0	0	0	0	0	0	0
b	0	0	1	1	1	1	1	1	1	1
a	0	1	1	2	2	2	2	2	2	2
b	0	1	2	2	3	3	3	3	3	3
a	0	1	2	3	3	4	4	4	4	4
a	0	1	2	3	3	4	4	4	5	5

Length of longest common subsequence = r = 5

5 is repeated 2 times

r + r×n + n2 = 5 + 5×2 + 22 = 19

The value is 19.

The recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving the above recursion, we get θ(nLogn)

1. Array size = min(max(deadline)), number of jobs) = (7, 10) = 7

2. Sort the Jobs in descending order based on profit

3. Fill the array in reverse order of deadline

Array

Job	A	J	D	C	H	G	B
Profit	25	25	30	40	43	33	35

            0         1          2         3          4          5          6         7

Maximum profit = 25 + 25 + 30 + 40 + 43 + 33 + 35 = 231