Having discussed the Bellman ford algorithm, let us quickly revisit the classical depth first search. We can apply this to model computational problems using graph.
Graph representations usually involve an adjacency matrix where the matrix rows and columns are vertices and there is an entry in the cell corresponding to (u,v) if and only if the u,v is connected by a direct edge.
An adjacency list adj(v), on the other hand comprises of list of neighbours of v.
In a depth first traversal, we start from a vertex v. For each neighbour w of v that is not explored yet, we recursively explore graph from w. depth first means we explore one vertex as far as possible before moving to the next one.
That is why this algorithm can be considered a decrease and conquer approach.
In a DFS forest, there are tree edges and back edges. Back edges are the missing edges.
One other thing we could do in a depth first tree is that we could keep track of when we enter and exit a vertex.We do this with the help of a stack.
Every back edge leads to an ancestor. A question is in a depth forest, can there be a vertex edge to a vertex that is not an ancestor. The answer in this case is no because if there was an edge between two vertices, then one of the vertices is unexplored and it would be added below not by going up. So all the edges on the top are explored. So a back edge to something other than an ancestor is not possible.
If we were to write a pseudo code for marking the entry and exit point, it would look something like this:
DFS(G)
{
for each v in V do { entryno[v] = 0; exitno[v] = 0 }
entrycount = 0; exitcount = 0;
for each v in V do
{
 if (entrycount(v) == 0) { dfs(v); }
}
}

dfs(v)
{
entrycount = entrycount + 1; entryno[v] = entrycount;
foreach(v,w) in E do
{
if (entrycount[w] = 0) {dfs(w);})
}
exitcount = exitcount + 1; exitno[v] = exitcount;
}
}

We look at Bellman-Ford algorithm today.
Dijkstra's algorithm requires us to have non-negative weights.
This algorithm let us compute the shortest path even when the weights are non-negative. Dijkstra's algorithm does not work with negative edge weights because it does not recompute the costs between vertices as we discover intermediary nodes.
We are now allowing negative edges with the caveat that the negative cycle is not ok.
Shortest path are well defined.
The idea here is that for increasing lengths k, compute shortest paths with at most k edges.
Our observation is that the shortest path can have at most n-1 edges >= n edges-cycle. Non-negative weights are eliminated.
The recurrence is described this way.  The path of length k from v to u breaks up as path of length k - 1 from v to some neighbor w of u. Then we add an edge from w to u.
We use the notation dist-k[u] as the shortest path from v to u using at most k edges.
dist-k[u] = min( dist-k-1[u], distk-1[w] + cost[w,u] for each neighbour w of u )
we know that dist 0 of source vertex v = 0  and dist0[u] = infinity.
So we create  a grid to compute the distances. We grow the path length from the source vertex to all the others so for a seven vertex graph we have path lengths varying from 0 to 6  For each path length we compute the costs and fill the grid.
The pseudo code is like this:
BellmanFord(v, cost, dist, n) {
for i = 1 to n do
    dist[i]  = infinity;
dist[v] = 0;

for k =1 to n-1 do
 for each vertex  u != v do
     distnew[u] = dist[u];  // upto k-1
     for each edge (i,u) do
      distnew[u] = min(distnew[u], dist[i] + cost(i,u));
 for each vertex u != v do
    dist[u] = distnew[u];   // replace
}

Complexity is O(n^3) if we use Adj matrix/
and O(nm) if we use the adjacency list
Optimizations include the following:
At k+1 the only distances that can change are those whose incoming edges have changed in the previous round. So we maintain a queue of those vertices whose distance reduces in iteration k
  Only need to update neighbours of these vertices
We can also terminate if no change is seen for some k.

Today we look at some more lectures from mecr.org. we continue our discussion on dynamic programming we organize the subsets to our advantage there are 2 ^N subsets and the optimal solution has N subsets . In dynamic programming we maintain the principle of optimality by breaking the problem b into sub problems and combining them to format the solution the sub problems may not be disjoint so we cannot apply divide and conquer further the there may not be a single strategy to use so we cannot apply the greedy algorithms. We choose appropriate reordering ti reorganize the sub problems fro m exponential to polynomial. We use memo table to avoid wasteful recomputation. And we iteratively fill table by analyzing dependencies

Today we cover some more discussion on dynamic programming. When we arrange the jobs in terms of their profits and use the dynamic programming, we have a binary tree of jobs to traverse. We have binary because we include and exclude. Some of the nodes will appear in other places as well in this tree. This is what we call overlapping and it costs us re-evaluation which we try to avoid. So the strategy is to store each computed value in a table.  We look up the table before making recursive call.  This look up table is called a memo table
So we improve the algorithm we described earlier with one which uses lookup of this table.
The algorithm looks like this:
function MaxProfitMemo(n) {
if ( n == 1) {
     return(Profit(1));
}
assign j to the last task job that ends before job n begins
if the table look up of (n-1) is not defined
            recursively call MaxProfitMemo on n-1
if the table MaxProfitTable[j] is not defined
            MaxProfitTable[j] = MaxProfitMemo(j)
finally return the max of either MaxProfitTable(n-1) or
                                                  Profit(n) + MaxProfitTable[j]))
}
We can actually do a further improvement. We can analyze the dependency of entries in table.

we iterate of over the entries this way

function MaxProfitIterative(n) {
MaxProfitTable[1] = Profit(1);

for i = 2 to n {
j = last job that ends before job i begins
MaxProfitTable[i] = max(MaxProfitTable[i-1], Profit(i) + MaxProfitTable[j]);
}
return (MaxProfitTable[n]);
}

Note that we don't have to check if i-1 and j are in the table.
And the complexity is )(n) and the assignment of j is only constant time since we keep the jobs in sorted order. However O(nlogn) to sort.

We now look at an important class of algorithms called dynamic programming. These use the principle of optimality which says:
there are subproblems possible for the overall problem
These subproblems can be solved efficiently
These can combine the solutions
This can be done recursively
Note that divide and conquer algorithms were based on the assumption that the subproblems are disjoint.
Also the greedy algorithms differs from the above in that there can be different subproblems possible but it chooses a strategy that does not change for the input.
generally, the sub-problems overlap. This is why we need to find the sub-problem structure.
Secondly, there is no fixed strategy so we may not be able to find a greedy strategy.
This means we have to exhaust all possibilities.
In dynamic programming, we take these constraints as such and try to do it efficiently.
We do this with the following three steps:
1) we come up with a recursive formulation in terms of subproblems
2) we organize the subproblems to make the search efficient.
3) we solve subproblems and keep track of the answers to avoid recomputation.
We will now see an example with the problem of Interval scheduling.
In this problem, we have tasks with predefined start, finish.
We find the subset of non-overlapping tasks and
try to choose the largest such sub-set.
A twist to the above problem is referred to as the weighted scheduling.
In this problem, each task fetches a profit and we try to maximize not the number of jobs but the profit from those jobs.
As we may see, there is no known greedy strategy for this problem. This means we will have to exhaust all combinations and choose the best. This means we have exponentially many combinations.
We will now re-organize the combinations to make the search more efficient.
We will sort the jobs by their finish time where each job ends earlier than the other.
We search based on excluding jobs one at a time. If a job has to be included we look to see what others can be excluded.If we exclude, we look at the remaining sub-problem recursively. The recursion terminates when there is one job and the profit is from that job.
Let MaxProfit(n) denote the max profit for jobs 1 .. n
Let Profit(i) denote the actual profit of job i
Our recursive formulation is as follows:
MaxProfit(k) = max (MaxProfit(k-1), Profit (k) + MaxProfit(j))
J is the latest job that ends before k starts.
and the MaxProfit(1)  is the profit(1)
The first component in the recursive formulation above is from the exclusion of job j and the second component is from the inclusion of job k.

Today we will look at some more discussion on greedy algorithms for job scheduling. Upto now we had established two facts :
1) For any job a with profit pa that is in SI and not in SJ, pa >= pb.
2) For common jobs between SI and SJ, they share the same time slot.
So if we transform SI to SI' and SJ to SJ' where they have the same time reference, then for a job a in SI' we should find an empty slot in SJ' because if there was another job there that would have had a different profit which is not possible. We see why this way. Lets say that there was a job b in that empty slot. If its profit was the same as that of a, then the job is the same as a and we maintained the job with profit pa exists only in SI and not in SJ. If b had a profit more than that of a, it would have had a position earlier than a in SI' since they have the same time reference. However this is not possible. Similarly, it cannot have a profit less than for the same reason. Thus we have eliminated one of the jobs from SI' and SJ' while preserving optimality.
Since we can repeat this step multiple times for jobs with highest profit and  we can preserve optimality at each step. Eventually we can transform J to be the same as I. So J is optimal I is the same as J. Hence I is itself optimal. So greedy solution is optimal.
To conclude, we have established that
J can be executed if and only if J can be executed in deadline order
and
Greedy solution is optimal.

We look further into some of the algorithms for job scheduling today.we discuss feasibility and optimality of scheduling. Feasibility is defined in this way. A schedule of jobs is feasible if and only if the deadlines of the jobs involved are in increasing order and less than the target. This is called deadline order. Suppose J is feasible, J = {1,2,..k} we maintain some order 1,2,...k but J is feasible in some order other than that.
Suppose r1, r2...rk is a feasible solution. we can show that it can be modified to the schedule above. Let us say at some point that the two orders disagree. At that point, we can check and find that 11a job is the same and we have one more point that it agrees. Eventually the given schedules are shown feasible
 A schedule of jobs is optimal such as when  it's greedy. We said the greedy solution is one when the order of profits is in the descending order
Suppose we have two job schedules J and k    there is a job in one that does not belong to the other and vice versa. The claim is the profit from the non optimal schedule is less than the one in the optimal one. We can establish this formally but intuitively we see why the greedy solution is considered optimal since we covered what greedy job scheduling is in the previous post.
To prove that greedy algorithm is optimal we take the greedy solution as I and optimal solution as J
We begin with I is not equal to J i.e. I and J are not comparable. If J belongs to I is not possible, then J is not optimal. If I belongs to J any missing job is compatible.
Let's look at highest profit job in I, not in J. i.e. a belongs to I, a does not belong to J and has the highest profit. b belongs to J and b does not belong to I,
The claim is profit from a is greater than or equal to profit from b.
a arrange J also in descending order of profit.

I ----- a    this schedule has job a with Max profit
J -----b     this schedule has job b with Max profit

If profit of b is more than a,  it would have been included in I since the jobs are compatible but this is not the case because I has listed a as max
This is one proof.
Now lets take SI as schedule for I and SJ schedule for J for symmetrical schedules. We want to make SI & SJ agree on time slots for all common job
If we take a job x and a job z common to both , we show that if x occurs after z on Si, and x occurs before z on Sj, then we walk the events from the rightmost end where we had the least profit and we see that this ordering is a discrepancy. Note that with regard to absolute time the same job in both schedules can be aligned or fixed to the time reference which could be chosen as the original positions of either schedule for that job. Having fixed a job this way, we now repeat for all the common jobs such that they occupy the same time slots
In the above we use I as the reference for our assumptions and findings in j.
We establish the following two facts
If there's a job a with Max profit this in I but not J
Then the profit of any job b in j that is not in I Is lesser than that of a
And common jobs have the same time