2.4.1 application

• Machine Scheduling, sort all task according to start time, and minheap of machine end time.
• Container Loading and 0/1 knapsack problem are different. For 0/1 knapsack problem, we consider the value and weight together, For greed algorithm, it change time complexity from 2ⁿto n.log(n), but 583/600 is withing 10%, so it’s very practical algorithm. Don’t underestimate it.
• Topological sorting:
  1) Select any one among  vertices having no incoming edge  
  2) Put the node into the solution &  Remove the node and its outgoing edges from the graph  
  4) Repeat the above steps until no nodes remain  
   
  You need to InDegree[n] array to save and update all the vetex InDegree, and stack to store all the vetex which indegree is 0.

• Bipartite-cover problems are NP-hard
  A greedy method to develop a fast heuristic  
  Construct the cover AâĂŹ in stages  
  Select a vertex of A  using the greedy criterion:  
  Select a vertex of A that covers the largest # of uncovered vertices of B

• Dijkstra algorithm.
  
  
  1. The greedy idea lies in line 8
  2. In line 8, it must shortest path to this vetex, Because if it’s not, There is shorter path, then, according to we select min in line 8, shorter one will be selected first, and this value HAS BEEN updated before.
  3. O(n²)
  4. the shortest value is saved, it’s also idea of dynamic programming.
  5. Just like vertabi, you can think that they are the same.