String Searching Algorithm - KMP Algorithm

Knuth-Morris-Partt string searching algorithm:
- This algorithm searches a word->w within the main string text->s
- Such a search must employ the following observation:
i) A given match determines where the next match could begin
ii) The above intelligence is obtained for the search word itself that contains sufficient information for making such a discussion (i.e. determine where the next match begins)

Advantage of this string searching algorithm: Helps to avoid the re-examination of already matched characters

Step1:

returns: No match found!
Search algorithms observation: We notice no string->'s'(i.e. word position->i[0]) occurs between position w[0] & w[8] in the main string text except at w[5]. Hence, the next character matching operation begins at w[5].

Step2:

returns: Match found!
Search algorithms observation: We notice all strings of the word occurs between position w[5] & w[3] in the main string text. The next character matching operation begins at w[4].

Step3:

returns: No match found!
Search algorithms observation: We notice no string->'s'(i.e. word position->i[0]) occurs between position w[4] & w[9] in the main string text. The character matching operation ends here.

Exercise-Radix Sorting

a) Given elements for radix sorting = {92,66,74,81,76,52,93,16,12,20}

Sorted sequence = {12,16,20,52,66,74,76,81,92,93}


b) Given elements for radix sorting = {24,16,63,42,47,30,29,32,27,55,52}

Sorted sequence = {16,24,27,29,30,32,42,47,52,55,63}

Exercise-Reverse Polish Notation (RPN)

a) 2+3+4
=> 34+
=> 234++

b) (2+3)*4
=> 23+
=> 423+*

c) 2*(5+2*3)
=> 23*
=> 23*5+
=> 223*5+*

d) (3+4)*(20-(3*4+2))
=> 34*
=> 34*2+
=> 2034*2+-
=> 34+2034*2+-*

e) 5*(3+4)-(2*(2+2*(1+2)))
=> 12+
=> 212+*
=> 2212+*+
=> 22212+*+*
=> 34+22212+*+*-
=> 534+*22212+*+*-

Sorting Algorithm - HeapSort & Heapify

HeapSort(A)
---------------------------------
01 BuildMaxHeap(A)
02 For i <- A.Length to 2 do
03 Exchange A[1] <-> A[i]
04 A.HeapSize <- A.HeapSize-1
05 PercolateDown(A,1)
06 end for
---------------------------------

BuildMaxHeap(A) (i.e. Max-Heapify)
---------------------------------
01 A.HeapSize <- A.Length
02 For i <- (A.Length/2) to 1 do
03 PercolateDown(A,i)
04 end for
---------------------------------

Algorithm that returns the middle element of a double linked list

FindTheMiddleElementofDoubleLinkedList(L)
01 i <- head
02 j <- tail
03 while i != j do
04 i <- i.next
05 j <- j.previous
06 return i

Time complexity - Omega of algorithms

a) if statement - O(n) [Omega times n]
b) for loop - O(n) [Omega times n]
c) for loop with a for loop - O(n*n) [Omega times n squared]
d) for loop within a if loop, this if loop is within a for loop - O(n + n*n) [n plus n squared omega]
e) while loop - O(n) [Omega times n]
f) MergeSort - O(nlogn) [Omega n time logarithmic n]
g) HeapSort - O(nlogn) [Omega n time logarithmic n]
h) KMP algorithm - O(m+n) [m plus n omega]

Checklist before selecting the right data structure for a given problem

(i) Analysis the problem in order to determine resource constraints
(ii) Determine the basic operations that need to be supported, such as Insert/Remove/Search
(iii) Now, select the data structure that has minimum cost/benefits to support the required operations

Algorithm to print-all-pairs in the tables (X, Y)

PrintAllPairs(X[0, 1, 2, ..., n-1], Y[0, 1, 2, ..., m-1])
01 for i<-0 to n-1 do
02 for j<-0 to m-1 do
03 Print(X[i], Y[j])
04 end for
05 end for

Algorithm to Sum-up n number of items in the table

Sum-up n number of items in the table and return the computed Sum

SumUp(X[0, 1, 2, ..., n-1])
01 Sum<-0
02 for i<-0 to n-1 do
03 Sum <- Sum + X[i]
04 end for
05 return Sum

Time complexity of algorithms - In particular Big Omega of algorithms

Big Omega or so called asymptotic upper bound of algorithms such as Sequential statements, If statements and Looping construct

(i) Sequential statements:
Big Omega of this algorithm equals to maximum time complexities of all individual statements (i.e. sum of maximum time complexities of the individual statements)
Therefore, O[g(n)] = O{f1(n)+f2(n)+ ... +fk(n)}
Conclusion: Overall complexity of this algorithm equates to O[g(n)]

(ii) If statements:
Big Omega of this algorithm equals to maximum time complexities of either one of the alternative statements i.e. then branch -> f(n)/else branch -> g(n)
Therefore, O[h(n)] = O{f(n), g(n)}
Conclusion: Overall complexity of this algorithm equates to O[h(n)]

(iii) Looping construct:
Big Omega of this algorithm equals to aggeration of the maximum time complexities of the following: (a) execution time (i.e. elementary operations execution in a given iteration) -> f(n) and (b) the number of iterations -> g(n)
Therefore, O{f(n) * g(n)}
Conclusion: Overall complexity of this algorithm equates to O{f(n) * g(n)}

Selection Sorting An Array

Selection sorting an array A[0, 1, 2, ..., n-1]

01 SelectionSort(A[0, 1, 2, ..., n-1])
02 for (j <- 0) to (n-2) do
03 m <- j
04 for (i <- j+1) to (n-1) do
05 if A[m] > A[i] then
06 m <- i
07 end if
08 end for
09 exchange A[m] <-> A[j]
10 end for

Bubble Sorting An Array

Bubble sorting an array A[0, 1, 2, ..., n-1]

01 BubbleSort(A[0, 1, 2, ..., n-1])
02 i <- 0 03 repeat 04 exch <- False 05 for (j <- 0) to (n-2-i) do 06 if A[j] > A[j+1] then
07 exchange A[j] <-> A[j+1]
08 exch <- True
09 end if
10 end for
11 i <- i+1
12 Until exch = False

Click here for explanation on what is bubble sort?