-
Notifications
You must be signed in to change notification settings - Fork 54
/
DPVideo.html
67 lines (62 loc) · 2.55 KB
/
DPVideo.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
<html>
<!-- THIS FILE WAS GENERATED BY A SCRIPT: DO NOT EDIT IT! -->
<head>
<link href="style.css" rel="stylesheet" type="text/css"/>
<title>
Dynamic Programing Video
</title>
</head>
<body>
<div id="header">
<div id="logo">
<img src="graphics/Julia.png">
</div>
<div id="user-tools">
<a href="index.html">Home</a>
<a href="about.html">About</a>
<a href="feedback.html">Feedback</a>
</div>
</div>
<h1>
Dynamic Programing Video
</h1>
<p>
A brief lecture discussing a dynamic programming problem, and the
conditions under which one can and cannot use a greedy
algorithm.
<br />
The context of this presentation assumes that students have already
been introduced to both dynamic programming and greedy algorithms,
but are puzzled as to when one or the other
technique applies (something I have found is a common problem).
<br />
And the idea that opportunity cost is the differentiator here needs
to be refined a bit: I only arrived at this today while preparing
this lecture. The refinement is needed because even in the activity
selection problem, there is <i>some</i> opportunity cost: you still
forego some activities in taking the greedy choice. But the
opportunity cost does not "spillover" into other choices. I have
begun work on trying to formalize this notion, and will produce a
paper stating this relationship more precisely.
</p>
<figure>
<iframe width="560" height="315"
src="https://www.youtube.com/embed/4l3pXjEXDp0"
frameborder="0" allowfullscreen>
</iframe>
<figcaption>
A dynamic scheduling problem.
</figcaption>
</figure>
</body>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-97026578-2', 'auto');
ga('send', 'pageview');
</script>
</html>