Master Method for Solving Recurrences
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Why Master method ? - Master method helps us analysing algorithms with their running time.
So, lets consider the integer multiplication - here.
Now we get equation 1.
The way we reason about recursive algorithm like these is with the help of recurrence. Recurrences
What is recurrence?
T(n) = max number of operations this algorithm needs to multiply 2 n digit numbers. Recurrence is to express T(n) in terms of recursive calls.
[Read More]Strassen's Subcubic Matrix Multiplication Algorithm
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
A Review on Matrix Multiplication
Given two 2 nxn matrices X, Y and their product matrix Z,
X.Y = Z
we know that Zij = (ith row of X) . (jth column of Y). So, we take row from X, and column from Y.
zij = ∑xik . ykj where k is 1 < k < n.
For eg. : Let
X = a b and Y = e f
[Read More]Inversions
Posted on August 4, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
This was taught in Algorithms: Design and Analysis Part I on coursera - how to count inversions.
What is an inversion? An inversion is a pair of objects that are out of order. If we are given an array and our goal is to sort from low to high, an inversion would be two items ai and aj such that ai > aj, but i < j. We can see that they are misplaced.
[Read More]Operation time complexity for a LINKED LIST
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The time complexity of handling the operations in a data structure like a LINKED LIST are as follows:
i. Most of the operations are O(n) [i.e. omega times n]
ii. Remove/Insert operations that handles element between elements require O(1) [i.e. omega times one] this is due to references/pointers on both the ends of the list, hence the elements don’t require to be shifted. However, due to the references/pointers this data structure requires additional memory!
[Read More]Operation time complexity for an ARRAY
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The time complexity of handling the operations in a data structure like an ARRAY are as follows:
i. Almost all the operations are O(1) [i.e. omega times one]
ii. Remove/Insert operations that handles element between elements require O(n) [i.e. omega times n] because the elements need to be shifted.
Note! Hence, an array as a data structure is used where remove/insert operations are not required.
Time complexity - Omega of algorithms
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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]
[Read More]Time complexity of algorithms - In particular Big Omega of algorithms
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
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.
[Read More]String Searching Algorithm - Knuth Morris Pratt or KMP Algorithm
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Knuth-Morris-Pratt 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
[Read More]Priority Queue
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
What is priority queue?
A data structure for maintaining items or elements in a queue of priorities, which is usually implemented using an array. A queue of this nature helps to insert every item with an assigned priority and these inserted items could be deleted if required.
Minimum number of queues needed to implement the priority queue?
Two. One queue is used for actual storing of data and another for storing priorities.
[Read More]What is a non-linear datastructure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A non-linear datastrucutre is a datastructure in which the data items in the memory are not allocated contiguously i.e. the data items are dispersed in the memory. The first data item will have a link to the second data item and second data item will have a link to the third data item and so on.
Pros
Uses memory efficiently that the free contiguous memory in not an requirement for allocating data items The length of the data items is not necessary to be known prior to allocation Cons
[Read More]