Home Work 5

This Home work is on Shortest path Algorithms a(Chapter 4 of Das Gupta) and Greedy Algorithms (Chapter 5 of Das Gupta) Optional problems are not to be submitted Do any 6 problems and choose at least one problem from each topic (shortest path algorithm, greedy algorithm) Due on 10/30/2014.
  1. Do Problem 4.13 a (DG)
  2. Do Problem 4.19 (DG)
  3. Do Problem 4.21 a (DG)
  4. Problem 24.3.6 (CLRS Edition 3 Page 603 - the problem is given below) We are given a directed graph G =(V,E) on which each edge (u,v) in E has an associated value r(u,v), which is a real number in the range 0 ≤ r(u,v) ≤ 1 that represents the reliability of a communication channel from vertex u to vertex v. We interpet r(u,v) as the probability that the channel from u to v will not fail and we assume that these probabilities are independent. Give an efficient algorithm to find the most reliable path between two given vertices.
  5. Problem 5.5 (DG)
  6. Problem 5.7 (DG)
  7. Problem 5.9 a-i (DG)
  8. Prolem 5.14 (DG)
  9. Do Problem 5.20 (DG) - find a perfect matching in a tree
  10. Do Problem 5.21 (DG) - find a minimum feedback edgeset in a weighted undirected graph
  11. Optional Do not submit Do Problem 4.2 (DG)
  12. Optional Problem 5.1 (DG)
  13. Optional Problem 5.2 (DG)