SILLY THINGS
1.Stable sorting algorithms – Merge Sort, Insertion Sort, Bubble Sort Not stable - Quick Sort, Heap Sort All of the sorting algorithms can be made stable by tweaking a little into the comparison schema of the algorithm, taking position a criteria.
2.Every comparison based sorting algorithm has to make – O(nlogn) comparisons Based on the decision tree argument - let x be the height of tree - 2^x leaves
Worst case time complexity of building a heap
Build-Heap(A[]): heapsize = A.length for i from floor(heapsize/2) to 1 do heapify(A,i) end end
Time complexity appears to be - O(nlogn)
| #!/bin/bash | |
| #Steps to run this script | |
| # $ sudo -s | |
| # $ touch script.sh | |
| ## copy paste this file to script.sh | |
| # $ chmod +x script.sh | |
| # $ ./script.sh 2>&1 | tee scriptoutput |
| import java.util.*; | |
| /************************* | |
| * @author rohith peddi | |
| *************************/ | |
| //[refer-http://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/] | |
| public class AhoCorasick { | |
| /*********************************************** | |
| * TRIE DATA STRUCTURE IMPLEMENTATION | |
| * | |
| * TIME : O(logR(N)) | |
| * Space : RN and RNw | |
| * | |
| **********************************************/ | |
| class Alphabet { | |
| /****************************************************** | |
| * BOYER MOORE SUBSTRING SEARCH | |
| * | |
| * Initially computes a skip array which tells us how far | |
| * should we skip in order to match the pattern elements | |
| * | |
| * stores the last occurence of the character in the | |
| * pattern and shifts accordingly | |
| * [BAD CHARACTER HEURISTIC] | |
| * |
| /****************************************************** | |
| * RABIN KARP FINGERPRINT SUBSTRING SEARCH | |
| * | |
| * Performs hash operation to check for match | |
| * Uses horner's method to compute hash value | |
| * | |
| * A total N-M substring hash values are computed | |
| * and matched with the hash function of pattern | |
| * | |
| * Time - O(N) |
| /****************************************************** | |
| * KNUTH MORRIS PRATT SUBSTRING SEARCH | |
| * | |
| * Initially computes a DFA array which tells us the restart | |
| * state of the pattern while the txt goes from left to right | |
| * without any change in the increment | |
| * | |
| * Search plays with the state of the pattern variable | |
| * | |
| * Time: O(N) |
| public class DpMethods{ | |
| /********************************************** | |
| LONGEST INCREASING SUBSEQUENCE | |
| **********************************************/ | |
| int[] Table = new int[N]; | |
| Arrays.fill(Table,1); | |
| for(int i=0; i<N; i++){ | |
| for(int j=0; j<i; j++){ | |
| if(A[j]<A[i] && Table[i]<Table[j]+1){ |
| public class MathMethods{ | |
| /********************************************* | |
| IS3MULTIPLE - | |
| Checks whether a number is 3 multiple or not | |
| much faster - does bitwise operations as follows: | |
| if number is negative make it positive, if it is 0 return 1 | |
| if it is 1 return 0, count number of odd set bits and even set | |
| bits and perform this operation recursively |