Solution 1:
For computing the highest probability of a path,we need to find the product of probabilities of each path between s and t nodes. Because the probabilities are independent, the probability that a path will not fail is the product of the probabilities that its edges will not fail.We want to
| | | ||||
| find a path from s to t such that ∏(u,v)∈pr(u,v) is maximized. This is equivalent to maximizing | |||||
| | | | | | |
| log(∏(u,v)∈pr(u,v)) = ∑(u,v)∈plog r(u,v), which in turn is maximizing ∑(u,v)∈p | -log r(u,v). |
Thus, for finding the highest probability path we need to run Shortest path algorithm for DAG i.e, topological ordered graph. We need to consider edge weights w(u,v) as -log p(e).Since logarithm will not change the monotonicity, and a minus logarithm will convert a minimization problem into a maximization problem, a shortest path p on the converted graph satisfying
| p = arg min ∑k | log w(v | | , v ) | |||||
| | | | | |||||
| i=1 | i-1 | i | ||||||
| will satisfy | | | | | | |||
| p = arg max ∏k | p(e)(v | i-1 | , v ) | |||||
| i=0 | i | |||||||
SPDAG(G,s):
Initialize the weights of each edge to -log(p(e))
Dist[u] = ∞ for all u ∈ G – s
Dist[s] = 0
For each v ∈ V – s in topological order :
Dist[v] = min dist[u] + (-log p(u,v)) // for (u,v) ∈ E (Edges) and p(u,v) probability of edge
return dist
The initialization of weights take O(E) time and visiting each node takes O(V) time in topological order. Thus, the time complexity of the algorithm is O(|V| + |E|).
Solution 2:
We need to consider a directed graph G = (V,E) with a node for each course and an edge (v,w) whenever course v is a prerequisite for course w. The courses we can take in the rest semester are precisely the sources of this graph; we might as well take them all. We can then remove them from the graph, and in the subsequent semester, take the sources of the remaining graph; and so on.
We need to compute incomingEdges in[.] and let sourceNodesList be the list of source nodes.
Algo:
noOfSemesters = 0
repeat until sourceNodesList is empty:
noOfSemesters = noOfSemesters + 1
nextL = empty list
for all u in sourceNodesList :
for all neighbors w of u in E:
in[w] = in[w] -1
if in[w] is 0:
add w to nextL
sourceNodesList = nextL
return noOfSemesters
The first part is the linear time incomingEdge computation and source identification. Then the main loop begins, with the integer variable time containing the current semester number and sourceNodesList containing the current list of courses. When these courses are removed from the graph, the incomingEdges of the nodes they point to are reduced; the main body of the loop performs the corresponding reductions and identifies the next set of source nodes, nextL.
Each course u is on sourceNodesList during exactly one semester; at that point, its incomingEdge is already zero and thus we never again consider edges into u. While u is on the the current list, all the edges out of it are examined. Thus in the repeat loop, over the entire execution of the algorithm, all edges in the graph are examined exactly once. Therefore, the total time taken by the loop is O(|V| + |E|).
Solution 3:
We need to find the minimum amount of time spent at the gas stations during the trip from San Francisco to Stony Brook. The idea is to calculate the minimum time spent at the gas station within every 100 miles of coverage of the trip. An optimal way to do that is to calculate the OPT(i) which is given by :
OPT(i) = c+ min OPT (j)
i
- j ; j < i, dist(j,i) ≤ 100
ci= time spent at station xi for filling
j = any previous station before current station i
c = 0 for San Francisco and Stony Brook as we start with a full tank at San Francisco and don’t to need to fill up at Stony Brook as we reach the destination.
The main idea is that the time to get to xi, including the time to fill up at xi, is equal to the shortest time spent getting to an earlier gas station (within 100 miles) plus the time spent filling
up at x.
i
Because there are only n + 2 stops, including SF and SB, the function is called with a maximum of O(n) unique arguments. This means that the amount of storage required – either for memoization or for iteratively nding the answer – is O(n); and similarly, since the function is only called O(n) times and does O(n) comparisons on each call (in a naive implementation), the total running time is no worse than O( n2).
Now, Let there are n number of stations, and array X of size n contains time spend at stations, and D be a n+2 size array that contains distances of stations from SF with first entry as 0, distance of SF from SF and last entry is the distance of SB from SF , let us represent
Algo:
let T be array of n elements, initialised to -1 and T(n) =0 Time = CalcTime(1)
CalcTime(k):
if T(k) != -1
return T(k)
else
smallest = infinity
i1=1
while((D(k+i1) – D(k)) < 100)
temp = X(k+i1) + CalcTime(k+i1)
if temp < smallest
smallest = temp
end
end
T(k) = smallest
return T(k)
end
Solution 4:
We’ll solve this problem first by going backwards. We’ll loop from n down to 1 and determine the cheapest way of placing books i through n if we start a new shelf with book i. We store the best cost in COST [i]. Assume that W represents the width of the shelves, and that H is an array containing the heights of the books. We will let COST [i] be the best possible cost of placing book i through n. For each i, m can be determined by satisfying the inequality,
∑m T[q] ≤ W.
q =i
COST [i] = min COST [i+k] + max H[i],……., H[ i+k-1 ]
1 ≤ k ≤ m
The base case is COST [n] = H[n].
The algorithm would look something like the following:
Inputs:
An array of heights H and an array of thicknesses T, both indexed from 1 to n, containing positive real numbers. The width of each shelf is assumed to be a global constant. We further assume that T [i] ≤ L for each i, 1 ≤ i ≤ n (no fat books that won’t fit on any shelf)
Outputs:
An array COST, indexed from 1 to n. COST[i] indicates the total cost of shelving books i through n starting on a new shelf. Also, a list of numbers indicating which books should mark the first book on the shelf
PLACEBOOKS (H; T) :
COST : array(1..n) of real;
currentshelf : real;
i; j; start : integer;
Begin
COST[n] := H[n];
for i := n 1 downto 1 loop
currentshelf := T [i];
Append start to left end list.
for j := i + 1 to n loop
currentshelf := currentshelf + T [j];
if currentshelf ≤ W and maxH[i],……,H[j] + COST[j +1] ≤ COST[i] then
COST [i] = max H[i],……,H[j] + COST [j + 1]
NextShelf [i] = j + 1
end if;
end for loop;
end for loop;
end PLACEBOOKS;
The outer loop goes through the different subproblems in reverse order. For each subproblem, the inner loop iterates through the books to be placed on the shelf.
The if statement on the inside checks two things: First, if there is room to place the next book on the shelf. If there isn’t, then there is no point in even attempting to place the book on the shelf. If there is, then we need to check to see if it will be cheaper to place the current book on the shelf we’re on, or to start a new shelf. If we want to place the book on the current shelf, then we add to the current size of the shelf we’re working on and increment the loop counter. Again, if not, then we have to add to the cost of the current subproblem and start a new shelf.
Performance:
The execution of the inside of the innermost for loop is bounded by a constant amount. The number of times the innermost loop is executed is bounded by a n, and the outer loop is executed n-1times, so the performance will be O(n2).
Solution 5:
- Considering convoy as an array and ship as an index of the convoy array. To find the maximum net profit, the idea is to find the maximum sum of the values possible in the array of convoy.
Algo:
- Initialise convoy as an array of ship having values of profit or loss at each ship. Let n be the size of the array,i.e., no. of ships.
- Initialise maxNetProfit = convoy[0] and currentValue, index to zero.
- for each ship s in convoy[n]: // iterating from s=0
currentValue = currentValue + convoy[s]
If currentValue > maxNetProfit :
index =s
maxNetProfit = currentValue
end if.
end for.
- Output index, maxNetProfit
The algo loops for n size of array of convoy. Hence, the running time of the algorithm is O(n).
- The interception point means that an expert navigator knows what ships he needs to consider from which Jack can get maximum profit,i.e, he can even intercept in the middle of convoy and break off in the middle to get maximum net profit.
We will use divide and conquer algorithm for getting O(n log (n) ) complexity.In short what it does is that it returns the maximum of the following three
- Maximum subarray sum of left half of array
- Maximum subarray sum of right half of array
- Maximum sum subarray that passes through middle
We can easily find the crossing sum in linear time. The idea is simple, find the maximum sum starting from mid point and ending at some point on left of mid, then find the maximum sum starting from mid + 1 and ending with sum point on right of mid + 1. Finally, combine the two and return.
Maxl = Maximum subarray sum of the left half
Maxli = the left index corresponding to maxl
Maxlj = the right index corresponding to maxl
Maxr = Maximum subarray sum of the right half
Maxri = the left index corresponding to maxr
Maxrj = the right index corresponding to maxr
Cenmax = Maximum subarray sum which passes through middle cenmaxl= sum corresponding to the left half of cenmax cenmaxr= sum corresponding to the right half of cenmax cenmaxi=the left index corresponding to cenmax cenmaxj=the right index corresponding to cenmax
The findMaxSubArraySum() function returns the maximum subarray sum, its left index and also its right index.It is called with findMaxSubArraySum(arr,1,n).
Algo:
Begin
Read arr[n]
return findMaxSubArraySum(arr,1,n)
FindMaxSubArraySum SubRoutine :
findMaxSubArraySum(arr,i,j) :
mid=(i+j)/2
[maxl,maxli,maxlj]=findMaxSubArraySum(arr,i,mid)
[maxr,maxri,maxrj]=findMaxSubArraySum(arr,mid+1,j)
cenmaxl=0
for p= mid -> i :
if(cenmaxl+arr[p]<0)
break
else
cenmaxl=cenmal+arr[p]
cenmaxi=p
cenmaxr=0
for p= mid+1 -> j :
if(cenmaxr+arr[p]<0)
break
else
cenmaxr=cenmaxr+arr[p]
cenmaxj=p
cenmax=cenmaxl+cenmaxr
if maxl is greater than cenmax and maxr
return maxl,maxli and maxlj
if maxr is greater than cenmax and maxl
return maxr,maxri and maxrj
else
return cenmax,cenmaxi,cenmaxj