Maximum weight independent set (WIS) graph problem using DP
Posted on November 5, 2013
(Last modified on August 7, 2020)
| 7 minutes
| Kinshuk Chandra
Input - A path graph G = (V,E)
with non - negative weights on vertices
eg.Consider the graph with vertex weights - 1,4,5,4
Desired output - subset of non-adjacent vertices - an independent set of maximum total weights.
Solutions
Brute force
polynomial time, so lets do better.
greedy approach
Greedy algos are easy to implement but are sometimes not correct. To apply greedy approach here we have to iteratively choose the max-weight vertex not adjacent to any previously chosen vertex.
[Read More]Sequence Alignment using Dynamic Programming
Posted on November 5, 2013
(Last modified on August 7, 2020)
| 7 minutes
| Kinshuk Chandra
Problem :
Input :
2 strings or sequence of characters i.e. X = x1x2…xm, Y = y1y2…yn
Goal - To define the similarity matrix between the 2 sequences with best alignment. This is based on penalty score, called Needleman/Wunsch score.
Eg. consider the sequence - AGGGCT and AGGCA , best alignment here is:
AGGGCT
| | | |
AGG - CA
Penalty
Penalty = penalty of match+penalty of difference + penalty of space
[Read More]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]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]Binary Tree Level-Order Traversal Using Depth First Search (DFS) [Not to USE BFS]
Posted on October 5, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed. We have already seen how to do level order traversal here.
Example
So consider the tree:
1
/ \
2 3
/ \ / \
4 5 6 7
The BFS or level order traversal here is :
[Read More]Binary Tree Post-Order Traversal - Recursive and Iterative Solution
Posted on October 5, 2013
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Consider the tree:
To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
Therefore, the Postorder traversal of the above tree will outputs:
[Read More]Binary Tree In-Order Traversal - Recursive and Iterative Solution
Posted on October 5, 2013
(Last modified on August 7, 2020)
| 5 minutes
| Kinshuk Chandra
Consider the tree
Inorder traversal prints the binary tree in increasing order in case of Binary Search Tree, but here we are discussing any binary tree.
To traverse a binary tree in Inorder, following operations are carried-out :
Traverse the left most subtree starting at the left external node, Visit the root, and Traverse the right subtree starting at the left external node. Therefore, the Inorder traversal of the above tree will outputs:
[Read More]Find the rank w.r.t K - Number of nodes with value less than K
Posted on October 5, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
If the rank of the BST is k, it implies how many nodes/keys are less than k.
So, it boils down to 3 easy recursive calls
In the simplest case if K==node value, then whole of the let is rank of the node if K < node.value then we know that rank depends on the size of left sub tree and its less than sub tree’s length If K > node.
[Read More]Iterators - Allowing iteration over data structures (in java)
Posted on September 10, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Many times we need to iterate over the data structures. But should we allow our clients to know the internal details of the data-structure like whether it is using array or linked list and then iterate themselves.
Here’s where java gives us the power called iterators which allows us to iterate over data structure.
Design Challenge
Consider the stack data structure and we want to support iteration over it on client side.
[Read More]Generic data structures in java
Posted on September 10, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Suppose we have a stack of string, but later we want to use it for integers. We have to re-write the code again and again for every data type. So how can we solve this.
Attempt 1 - Creating the stack for every data type, which is very exhaustive and needs code changes again.
**Attempt 2 - **Implement a stack using Object class.
Example
Downside -
- Discover type mismatch errors at run time
- Casting has to be done at client side
- Code looks ugly because of so many castings
Attempt 3 - Java generics