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]Introduction to Heap
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Definition of a heap
A heap is a data structure that contains objects which have comparable keys.
Uses of Heap
Some uses for a heap include: keeping track of employee records where the social security number is the key, network edges, events where there is a priority, etc.
Such a heap is called descending heap. In an ascending heap, on the other hand, the key value stored in a node is smaller than the keys of its children nodes.
[Read More]What is a Graph data structure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Graphs consist of 2 ingredients :
Vertices (V) , also called nodes and can be pictured as dots Edges (E) , the line connecting the nodes. Types of Graphs
Depending on the edges, there two types of graphs:
Undirected Graphs - A graph that entail edges with ordered pair of vertices, however it does not have direction define. Example of such a graph is the ‘Family tree of the Greek gods’ **Directed Graphs (**aka Arcs) - Directed Graph: A graph that entail edges with ordered pair of vertices and has direction indicated with an arrow.
[Read More]Finding an integer that repeats odd number of times in an array of positive integers
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Question: In an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity?
Solutions
Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0.
[Read More]Huffman Codes
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Background
When we encode characters in computers, we assign each an 8-bit code based on an ASCII chart. But in most files, some characters appear more often than others. So wouldn’t it make more sense to assign shorter codes for characters that appear more often and longer codes for characters that appear less often?
This is exactly what Claude Shannon and R.M. Fano were thinking when they created the first compression algorithm in the 1950’s.
[Read More]Convert integers to roman numbers
Posted on January 5, 2012
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Question: write an algorithm to convert an integer into roman number. For example, 1 -> I, 2 -> II, or 4 -> IV.
Solution: in order to solve this problem, we must know the rules of writing roman numerals. For example, I is 1 and V is 5 but IV is not 6 but 4 (5 -1). Moreover, there is no 0 number in roman numeral system. Here is the link to an article about roman numerals if you are unfamiliar with the system.
[Read More]Karp-Rabin algorithm
Posted on December 25, 2011
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Some points to note about this String matching algorithm:
uses an hashing function; preprocessing phase in O(m) time complexity and constant space; searching phase in O(m__n) time complexity; O(n_+_m) expected running time. Instead of checking at each position of the text if the pattern occurs or not, it is better to check first if the contents of the current string “window” looks like the pattern or not. In order to check the resemblance between these two patterns, a hashing function is used.
[Read More]Find the smallest window in a string containing all characters of another string
Posted on September 30, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Example
S = “ADOBECODEBANC”, T = “ABC”,
Minimum window is “BANC”.
Note:
If there is no such window in S that covers all characters in T, return the emtpy string “”. If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
[Read More]Program to check if two rectangle overlap or itntersect
Posted on May 14, 2011
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Rectangles can be tilted also, what about that cas…
Anonymous - Dec 3, 2013
Rectangles can be tilted also, what about that case?
Program to check if two rectangle overlap or itntersect
Posted on May 14, 2011
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Input - 2 Rectangles with x and y coordinates.
Output - boolean value which states if they overlap or not This is a one of the classic problems in graphics programming and game development. So, let’s see how we can solve it.
Most computer (now cellphone) screens have an invisible coordinate system that is used to identify where graphical objects are on the screen. For example, the iPhone coordinate system has the origin at the top-left corner of the screen.
[Read More]