Refer My Notes

Given a graph of n vertices, determine the minimum cost path to start at a given vertex and travel to each other vertex exactly once, returning to the starting vertex. In some versions, the starting and ending points are different and fixed, and all other points have to be visited exactly once from start to end. A standard way to solve these problems is to try all possible orders of visiting the n points, which results in a run-time of O(n!). To calculate cost using Dynamic Programming, we need to establish recursive relation in terms of sub-problems. Let us define a term C(S, i) be the cost of the minimum cost path visiting each vertex in set S exactly once, starting at 1 and ending at i. We start with all subsets of size 2 and calculate C(S, i) for all subsets where S is the subset, then we calculate C(S, i) for all subsets S of size 3 and so on. Note that 1 must be present in every subset. So the algorithm is like below - If size of S is 2, then S must be {1, i},  C(S, ...

An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum. If the probabilities of searching for elements of a set are known from accumulated data from past searches, then Binary Search Tree (BST) should be such that the average number of comparisons in a search should be minimum. eg. Lets the elements to be searched are A, B, C, D and probabilities of searching these items are 0.1, 0.2, 0.4 and 0.3 respectively. Lets consider 2 out of 14 possible BST containing these keys. Figure 1 Figure 2 Average number of comparison is calculated as sum of level*probability(key element) for each element of the tree. Lets the level of tree start from 1. Therefore, for figure 1 -     Average number of comparison = 1*0.1 +2*0.2 +3*0.4 +4*0.3  = 2.9                                  ...

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible Given a knapsack of capacity m and number of items n of weight w1, w2, w3 ... , wn with profits p1, p2, p3..., pn. Let x1,x2,...,xn is an array that represents the items has been selected or not. If the item i is selected, then xi = 1 If the item i is not selected then x i = 0 In 0/1 knapsack, the item can be selected or completely rejected. The items are not allowed to be broken into smaller parts. The main objective is to place the items into the knapsack so that maximum profit is obtained or find the most valuable subset of items that fits into the knapsack. Constraints: The weight of the items chosen should not exceed the capacity of knapsack. Obj...