Find the longest oscillating subsequence

 Posted on April 11, 2014  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

Given the sequence of numbers find the longest oscillating subsequence Solution The oscillating sequence is the sequence, when the 2 adjacent numbers are either greater than or smaller than the current number. So, for example following is the oscillating sequence: 1, 7, 4, 6, 2 So, 7 is greater than both 1 and 4, 4 is less than both 4 and 6 and so on. Now, given the sequence of number we have to find the longest oscillating subsequence. [Read More]
kodeknight  companies  morgan-stanley  greedy Algo 

Application of clustering

 Posted on October 21, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Informal goal - given n points [web pages images, genome fragments, etc] classify into “coherent groups” People in machine learning must have heard of unsupervised learning. Assumption As input, given a (dis) similarity measure 2 symmetric examples - euclidean distance, genome similarity goal - same clusters => nearby So, coherent group has smaller distance. Objective function to do clustering - there are many objective functions, but we are reading max-spacing k-clusterings. [Read More]
kodeknight  greedy Algo 

Minimum Spanning tree MST

 Posted on October 19, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

MST is used to connect a bunch of points to each other as cheaply as possible. Applications clustering networking Blazingly fast greedy algorithms There are many greedy algorithm, but we will talk about 2: Prim’s algo [1957, also djikstra’ 1959] or Jarnic found it in 25 years earlier. Kruskal’s algo[1956]. Will be using union find data-structure. They are blazingly fast as they are almost close to linear time of number of edges: [Read More]
tree  kodeknight  greedy Algo  minimum-spanning-tree  MST  spanning tree  graph-search 

Prim's Algorithm

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

This algorithm was first propsed by Jarnik, but typically attributed to Prim. It starts from an arbitrary vertex (root) and at each stage, add a new branch (edge) to the tree already constructed, much like a mould. The algorithm halts when all the vertices in the graph have been reached. To understand the problem statement refer here. This is similar to djikstra’s algorithm where we were clear where to begin with as we were given the source vertex, but here we have to choose arbitrarily. [Read More]
Graph  Algorithms  kodeknight  greedy Algo 

Kruskal's Algorithm

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

In kruskal’s algorithm the selection function chooses edges in increasing order of length without worrying too much about their connection to previously chosen edges, except that never to form a cycle. The result is a forest of trees that grows until all the trees in a forest (all the components) merge in a single tree. graph Example In Kruskal’s algorithm, we sort the edges according to their edge weights and start counting them and including them in MST, if they are not forming any cycle. [Read More]
Graph  Algorithms  kodeknight  greedy Algo  incomplete 

An Activity Selection Problem ( Greedy Approach)

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

An activity-selection is the problem of scheduling a resource among several competing activity. Statement: Given a set S of n activities with and start time, Si and fi, finish time of an ith activity. Find the maximum size set of mutually compatible activities. Compatible Activities Activities i and j are compatible if the half-open internal [si, fi) and [sj, fj) do not overlap, that is, i and j are compatible if si ≥ fj and sj ≥ fi [Read More]
Algorithms  kodeknight  greedy Algo 

Dijkstra's Algorithm (Shortest Path)

 Posted on July 5, 2010  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Consider a directed graph G = (V, E). Problem Determine the length of the shortest path from the source to each of the other nodes of the graph. This problem can be solved by a greedy algorithm often called Dijkstra’s algorithm. The algorithm maintains two sets of vertices, S and C. At every stage the set S contains those vertices that have already been selected and set C contains all the other vertices. [Read More]
Algorithms  kodeknight  greedy Algo  distance