## ← 15-01 Dave's Problem

• 1 Follower
• 51 Lines

### Get Embed Code x Embed video Use the following code to embed this video. See our usage guide for more details on embedding. Paste this in your document somewhere (closest to the closing body tag is preferable): ```<script type="text/javascript" src='https://amara.org/embedder-iframe'></script> ``` Paste this inside your HTML body, where you want to include the widget: ```<div class="amara-embed" data-url="http://www.youtube.com/watch?v=cplURaPK5i0" data-team="udacity"></div> ``` 1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

1. So Alice is now super, super happy, but what about the others?
2. So I suggest that we take a look at Dave here,
3. and Dave, as you remember, was working on a logistics problem,
4. so what he was trying to solve was shortest tour.
5. And actually, last time we left off,
6. Dave wasn't too happy,
7. because we found out it is not very easy to find
8. a good search tree or a pre processing strategy
9. for his problem.
10. On the other hand, of course, we mentioned that in practice
11. shortest tour is usually very easy to solve,
12. but from a theoretical perspective,
13. maybe we were a bit lucky for Dave;
14. if we're not looking for the best possible solution,
15. but except an approximation,
16. and then if we should find an approximation,
17. Dave can get a little happier here
18. and of course he doesn't have to be as jealous that
19. Alice has such an NP complete problem
20. and he seems to have a harder one.
21. Now lucky for Dave,
22. there is a constant factor approximation algorithm
23. for shortest tour,
24. but since Dave is not that proficient in theoretical computer science,
25. I think he doesn't really stand a chance
26. of coming up with this algorithm himself,
27. so you will have to pay close attention now
28. to be able to explain it to Dave.
29. The concept that we will use is that of a
30. spanning tree, and if you've had an algorithm course before,
31. you will know what a spanning tree is,
32. but I'm quickly going to explain it to you just to make sure.
33. A spanning tree is a part of a graph
34. or actually it's a selection of edges
35. in a graph so that the result looks
36. like a tree.
37. Well, what that means is that you select edges
38. so that you still keep the whole graph connected,
39. but you don't have any cycles,
40. so a cycle would be something like this
41. where you can leave a vertex and then come back to it
42. another way, so you select edges
43. so that the whole graph is still connected,
44. but there can be no cycles, so
45. to have you figure it out, let's do a quick quiz here.
46. This is the thing that worked 3 times.
47. I'm going to give you 3 choices of what a spanning tree could be,
48. and the red edges are always those that
49. I'm selecting here.
50. I would like you to tell me in which of these cases
51. the red edges from a spanning tree for the graph.