Angličtina pro matematiky II
COURSE MATERIALS WEEK IX.
Lecture 16 Greedy algorithms
Decide whether the statements are true or false.
- Greedy algorithms are one distinct kind of algorithms.
- Digraph is an abbreviation for directed graph.
- The plural form of vertice is vertices.
- The word vertices comes from old English.
- It appeared in the 15th century.
- Directed graph contains unordered pairs.
- In asymptotic notation, we leave out vertical bars.
- In connected graph, the number of edges is bigger than the number of vertices.
9. In connected graph, you can connect all vertices in the graph.
Listen again and try to find words which are wrong
Transcript - Lecture 16
A)-- valuable experience. OK, today we're going to start talking about a particular class of algorithms called greedy algorithms. But we're going to do it in the context of graphs. So, I want to review a little bit about graphs, which mostly you can find in the textbook in enclosure B. And so, if you haven't reviewed in appendix B recently, please sit down and review appendix B. It will pay off especially during our get -home quiz. So, just reminder, a digraph, what's a digraph? What's that short for? Directed graph, OK? Directed graph, G equals (V,E), OK, has a set, V, of vertices.
B)And, I always get people telling me that I have one vertice. The singular is not vertice; it is vertex, OK? The plural is vertices. The singular is vertex. It's one of those strange English words. It's probably originally like French or something, right? I don't know. OK, anyway, and we have a set, E, which is a subset of V cross V of edges. So that's a digraph. And undirected graph, E contains unordered pairs.
C)OK, and, sorry? It's Latin, OK, so it's probably very old, then, in English. I guess the vertex would be a little bit of a giveaway that maybe it wasn't French. It started to be used in 1570, OK. OK, good, OK, so the number of edges is, whether it's directed or undirected, is O of what? V^2, good. OK, and one of the conventions that will have when we're dealing, once we get into graphs, we deal a lot with sets. We generally drop the vertical bar notation within O's just because it's applied. It just makes it nicer. So, once again, another abuse of notation. It really should be order the size of V^2, but it just messes up, I mean, it's just more stuff to write down. And, you're multiplying these things, and all those vertical pubs.
D)Since they don't even have a sense to the vertical bar, it gets messy. So, we just drop the vertical bars there when it's in asymptotic notation. So, E is order V^2 when it's a set of pairs, because if it's a set of pairs, it's at most n choose two, which is where it's at most n^2 over 2, here it could be, at most, sorry, V^2 over 2, here it's at most V^2. And then, another property that sometimes comes up is if the G is connected, we have another limit, implies that the size of E is at least the size of V minus one. OK, so if it's connected, meaning, what does it mean to have a graph that's connected?
E)Yeah, there's a path from any vertex to any other vertex in the graph. That's what it means to be connected. So if that's the case, that a number of edges is at least the number of vertices plus one, OK? And so, what that says, so one of the things we'll get into, a fact that I just wanted to tell you, is that in that case, if I look at log E, OK, log of the number of edges, that is O of log V.
Transcript - Lecture 16
-- valuable experience. OK, today we're going to start talking about a particular class of algorithms called greedy algorithms. But we're going to do it in the context of graphs. So, I want to review a little bit about graphs, which mostly you can find in the textbook in appendix B. And so, if you haven't reviewed in appendix B recently, please sit down and review appendix B. It will pay off especially during our take-home quiz. So, just reminder, a digraph, what's a digraph? What's that short for? Directed graph, OK? Directed graph, G equals (V,E), OK, has a set, V, of vertices.
And, I always get people telling me that I have one vertice. The singular is not vertice; it is vertex, OK? The plural is vertices. The singular is vertex. It's one of those weird English words. It's probably originally like French or something, right? I don't know. OK, anyway, and we have a set, E, which is a subset of V cross V of edges. So that's a digraph. And undirected graph, E contains unordered pairs.
OK, and, sorry? It's Latin, OK, so it's probably pretty old, then, in English. I guess the vertex would be a little bit of a giveaway that maybe it wasn't French. It started to be used in 1570, OK. OK, good, OK, so the number of edges is, whether it's directed or undirected, is O of what? V^2, good. OK, and one of the conventions that will have when we're dealing, once we get into graphs, we deal a lot with sets. We generally drop the vertical bar notation within O's just because it's applied. It just makes it messier. So, once again, another abuse of notation. It really should be order the size of V^2, but it just messes up, I mean, it's just more stuff to write down. And, you're multiplying these things, and all those vertical bars.
Since they don't even have a sense to the vertical bar, it gets messy. So, we just drop the vertical bars there when it's in asymptotic notation. So, E is order V^2 when it's a set of pairs, because if it's a set of pairs, it's at most n choose two, which is where it's at most n^2 over 2, here it could be, at most, sorry, V^2 over 2, here it's at most V^2. And then, another property that sometimes comes up is if the G is connected, we have another bound, implies that the size of E is at least the size of V minus one. OK, so if it's connected, meaning, what does it mean to have a graph that's connected?
Yeah, there's a path from any vertex to any other vertex in the graph. That's what it means to be connected. So if that's the case, that a number of edges is at least the number of vertices minus one, OK? And so, what that says, so one of the things we'll get into, a fact that I just wanted to remind you, is that in that case, if I look at log E, OK, log of the number of edges, that is O of log V.