MIT 6.006 - Algorithms

Question 1

How many edges (given |V| number of vertices) are possible in a simple graph which is:

1. Directed
2. undirected

Answer 1

a simple graph doesn’t contain self loops, nor duplicate edges from v1 to v2 so:

1. v*(v-1)
2. v choose 2

for Both |E| = O(|v|^2)

Question 2

What’s the out degree of a vertex?

Answer 2

How many edges are going out of that node.

Question 3

What’s the sum of all outgoing degrees over all vertices in an undirected graph?
What about a directed graph?

Answer 3

undirected: 2*|E|
directed: |E|

Question 4

If I solve the problem of “output all of the vertices |V| reachable from a specific vertex t, and for each its shortest path to t,

what would be the space complexity of a naive algorithm?

How can I do it better?

Answer 4

a naive output might be O(v^2).

Shortest paths tree will take only O(v)

Question 5

How do I know that the shortest paths from t to all V is a tree?

Answer 5

1. It has no cycles (otherwise, i would find a shorter path)
2. It is connected (by definition,otherwise there would be no path…)

Question 6

Why does BFS take O(|V|+|E|) time?

Answer 6

We allocate P() data structure of size V, which takes O(V) time, and then we run over all the edges of the graph which is O(E).

Question 7

What’s wrong with the following BFS code if the graph is general? When it will work?

while len(nodesCurrentLevel)>0:
currentNode = nodesCurrentLevel.pop(0)
#Visit the node
currentLevelNodesVisited.append(currentNode.val)
if currentNode.left:
nodesNextLevel.append(currentNode.left)
if currentNode.right:
nodesNextLevel.append(currentNode.right)
ans.append(currentLevelNodesVisited)

Answer 7

In a general graph, there are loops, so this can create an infinite loop.
-> I need to check if a node was already encountered before adding it to the next level.

This will work on a tree since, by definition, a tree has no cycles.

Question 8

What does DFS do better than BFS? (Why do I care about it if BFS already solved reachability and shortest path)

Answer 8

Time complexity of BFS is O(|V| +|E|).

Time complexity of DFS is O(|E|) (we consider the sum of out-degrees).

Notice that DFS solves reachability and not shortest path.

Since P(v) is saved for each node during DFS, and we can have up to V vertices on the stack, Its space requirement is O(v)

Question 9

What does 6006 call a “full DFS”? What’s its output?
What’s its run time?

Answer 9

perform DFS for every node which its parent was not set yet.

This algo find the # of connected components in a graph.

Run time is O(|V| + |E|)

Question 10

What’s a DAG? Give an example for a DAG

Answer 10

Directed acyclic graph.

A tree.

Question 11

What’s a topological order

Answer 11

f(v) such that f(u)<f(v) if (u,v) is an edge.

Question 12

What can I say about finishing order of DFS in a DAG? Why?

Answer 12

The reverse of the finishing order of DFS is a topological order.

If there’s an edge (u,v) I want to prove that f(u)<f(v). Either v was visited before u or not.

If u was visited before v, then u will call DFS on v which will finish first, and so reverse finish will mean that f(v)<f(u).

if u was not visited before we visit v, there must be a s’ node such that there’s a path from our source node s to v, without u.
That means that with u there’s a second path from s to v(just look at p(v)….up to s), which means that the graph is cyclic, but the graph is DAG…

In the lecture he claimed that since graph is acyclic, we can’t reach u from v and therefore visit(v) will finish before visit(u) will finish. It is correct and my claim wasn’t correct BECAUSE IT IS POSSIBLE FOR U TO BE NOT REACHABLE from S. DAG is acyclic but it’s not necessarily connected!

If it’s a DAG -> topological order from reverse time finished DSF

No such topological order -> not a DAG

Question 13

Cycle detection in a directed graph- how?

Answer 13

If it’s a DAG -> topological order from reverse time finished DSF

No such topological order -> not a DAG!

Simply run DFS and check if reverse finishing time is a topological order or not.

DFS will traverse an edge from v to an ancestor of v: take a cycle (v0,v1…vk,v0) and let’s assume that v0 is the first node that DFS will visit (if not, then reorder the cycle such that it does - that is called without loss of generality).

DFS will visit after v0 v1,v2…vk and before finishing v0 will try to visit v0 from vk!

This will also tell me where’s the cycle in G.

Question 14

What’s a weighted graph?

Answer 14

Along with V,E, there’s a weight function w:E->Z (notice that a weight can be negative,positive, or 0).

Question 15

Why do we care about a weighted graph?

Answer 15

This models many things in real life: actual distances for routes, latency in a network, strength of connection in a social network etc etc

Question 16

Why can we assume that we can query a weight in constant time?

Answer 16

We can save the weight of an edge in a hashset, or in the adjacency list of a vertex, which by itself can be a hashset

Question 17

What’s the weight of a path

Answer 17

The sum of weight of its edges…

Question 18

What’s a weighted shortest path

Answer 18

the path between u and v with minium weight (notice that if there’s a cycle with a negative weight this is minus infinity, if no path this is defined as infinity).

Question 19

How can I solve the shortest path problem in a weighted graph with BFS?

Answer 19

Convert any u->v of weight, for example, 5, to a graph where there are 4 dummy nodes in between.

Of course, this will add many nodes and edges to the graph if the weights are big

Question 20

We’re going to discuss finding the shortest path in a weight graph for the following algorithms:

1. DAG-relaxation
2. Bellman-Ford
3. Dijkstra.

At what situation/complexity does each algorithm operate?

Answer 20

1. DAG relaxation over DAGS at linear time (O(V+E)).
2. Bellman-Ford - any graph, any weight function , O(V*E)
3. Dijkstra, all weights are non-negative, O(VlogV+E)

Question 21

Given a function delta(v) =delta(s,v) which outputs the minimum distance from s (the source node) to v, how can I create a data structure that will tell me P(v) (who is the parent of v) for all v?

Answer 21

Start with an empty data structure, where the parent of s is set to null.

For every v, look at its parents (incoming neighbors). if for a parent u, it is the case that delta(v)=delta(u)+w(v,u) then u is also a parent (there can possibly be more than one) of v in a shortest path from s. So i can assign p(v)=u.

In fact one iteration though all the nodes and their incoming edges will be sufficient.

Question 22

Why doesn’t a simple DFS-like can’t calculate distances for any DAG?

Answer 22

Because a DAG, although acyclic, can still have multiple paths to the same node.

For example u->v->w
and u->v1->v2>-v3->w

Question 23

Explain how DAG-relaxation works

Answer 23

Maintain estimates, which are upper bounds, d(s,v)>=delta(s,v).

Gradually lower those high estimates until d=delta (the estimates are the same as the actual distance).

Set d=infinite for all v,set d=0 for s.

If there’s a e,(u,v) such that d(s,v)= d(v)>d(u)+w(u,v) then set d(v)=d(u)+w(u,v) ->relaxation

Process each v in a topological order. For each outgoing neighbor, process its adjacent neighbors (relax any (u,v) that can be relaxed).

Question 24

DAG relaxation: what is it? Why is it safe?

Answer 24

Relaxation is If there’s a e,(u,v) such that d(s,v)= d(v)>d(u)+w(u,v) then set d(v)=d(u)+w(u,v)

it’s safe as d(s,v) is either infinite, or the weight of some path from s to v, and so >= then delta(s,v).

Question 25

What's the complexity of DAG relaxation?

Answer 25

It takes only one iteration through the topological order sorted vertices of G (and all of the outgoing edges) so O(V+E). Correctness if provable on the hypothesis that if d=delta for every node with a lower topological order, i will set d as delta for the next node.

Question 26

Short answers for the following: In any undirected graph G = (V, E), the eccentricity (u) of a vertex u ∈ V is the shortest distance to its farthest vertex v, i.e., (u) = max{δ(u, v) | v ∈ V }. The radius R(G) of an undirected graph G = (V, E) is the smallest eccentricity of any vertex, i.e., R(G) = min{(u) | u ∈ V }. (a) Given connected undirected graph G, describe an O(|V ||E|)-time algorithm to determine the radius of G. (b) GivenconnectedundirectedgraphG,describeanO(|E|)-timealgorithmtodetermineanupper bound R∗ on the radius of G, such that R(G) ≤ R∗ ≤ 2R(G).

Answer 26

A. Run BFS for every single node. since the graph is connected, |E|>=|V| or |V|=O(|E|) and therefore O(V^2+VE) is nothing but O(VE) B. Run BFS on ANY node and return its epsilon.

Question 27

Short answer to the following: MIT has heard complaints regarding the speed of their WiFi network. The network consists of r routers, some of which are marked as entry points which are connected to the rest of the internet. Some pairs of routers are directly connected to each other via bidirectional wires. Each wire wi between two routers has a known length `i measured in a positive integer number of feet. The latency of a router in the network is proportional to the minimum feet of wire a signal from the router must pass through to reach an entry point. Assume the latency of every router is finite and there is at most 100r feet of wire in the entire network. Given a schematic of the network depicting all routers and the lengths of all wires, describe an O(r)-time algorithm to determine the sum total latency, summed over all routers in the network.

Answer 27

Two things: 1. Convert each edge with length l to l edges connected to l-1 dummy vertices. Since total vertices/edges I added is bounded by 100r, it the same "complexity" (O(r)). 2. Run BFS but at L0 put all of the entry points! In the lecture, the lecturer created a dummy "super point" and connected it to all of the entry points.

Question 28

Solve shortly: Wizard Potry Harter and her three wizard friends have been tasked with searching every room of a Labyrinth for magical artifacts. The Labyrinth consists of n rooms, where each room has at most four doors leading to other rooms. Assume all doors begin closed and every room in the Labyrinth is reachable from a specified entry room by traversing doors between rooms. Some doors are protected by evil enchantments that must be disenchanted before they can be opened; but all other doors may be opened freely. Given a map of the Labyrinth marking each door as enchanted or not, describe an O(n)-time algorithm to determine the minimum number of doors that must be disenchanted in order to visit every room of the Labyrinth, beginning from the entry room.

Answer 28

1. Edges are doors that aren't enchanted, vertices are rooms. 2. Compute (full BFS/DFS) all the connected components of the graph (this take O(n) since degree(v)<=4) 3.Run BFS starting from the connected component containing entry room on the graph of connected components (vertices are now CCs, edges are enchanted doors connecting between them). or... Skip step 3 and just return |CC|-1 : to visit all connected components using the output from 3, we will traverse the underlying tree of that algorithm - but since we're not required to return the actual paths but just the number of nodes, then we can simply output |CC|-1 without calculating it :D

Question 29

What's the output of the Bellman-Ford algo?

Answer 29

Input is a general graph with weights that might be negative (and contain cycles) Output is -infinite to nodes which are not reachable -minus infinity to nodes where negative cycles exist -min distance to the source node otherwise

Question 30

Warm-up exercise for Bellman Ford: Given an undirected graph G, give an algorithm which finds out if there's a negative cycle.

Answer 30

If there's a negative edge (v,u) i can just take that edge over and over again :D That's why we will restrict our discussion (BF algo) for directed graphs

Question 31

Exercise 2: Given an algorithm that solves single source shortest path in O(V*(V+E)) show an algo that solves it in O(V*E) (in the lecture on BF he will show only the first)

Answer 31

If the graph is connected, then we are done since E>=V. Run DFS for the source node, and run that algo only for the connected component of s.

Question 32

Prove the following claim: If delta(s,v) is finite (not infinity or minus infinity) then there exists path between s and v that is simple (each vertex appears in it at most once).

Answer 32

If it was not simple, then there's a cycle in the shortest path s- ..v'-...-v'-..v. If the weight of the cycle is negative then delta should be minus infinite. If the weight is positive or 0, we can remove it to get "reduce" delta which is impossible since it's a minimum, or we can create a shorter path that doesn't contain the cycle (and keep removing all such cycles until we get a simple path).

Question 33

How many edges do simple paths have?

Answer 33

At most V-1

Question 34

What's a k-edge distance from s to v?

Answer 34

The weight of a shortest path from s to v by using k edges AT MOST. We will denote that function by δₖ

Question 35

Prove: If δ|v|(s,v) <δ|v|-1(s,v) then there's a negative cycle from s to v (and so the "full" delta is minus infinity).

Answer 35

If there was a shortest path, then δ |v|-1 would be the accurate value. Since it's not, then there's no shortest path. Since δ v is not infinity there's a path between them. We will call such v a witness (that there's a negative cycle in the graph).

Question 36

Prove: if δ(s,v)=minus infinity, then v is reachable from a witness

Answer 36

δ(s,v)=minus infinity means that there's a negative weight cycle from the path from s to v. I'll prove something stronger: every negative weight cycle reachable from s contains a witness. Lecturer's proof: By traingle we have for each v in the cycle C, and every v'->v edge within that cycle delta|V|(s,v) <= delta|v-1|(s,v')+weight(v',v) Summing this inequality for all v in C yields for all v in c: sum of delta|v|(s,v)<= delta|v-1|(s,v')+weight(v',v) but the sum of weight(v',v) over all vertices v in C is thee weight of the cycle, which is negative, so that mean that the <= is just < or sum over all v in c sum(delta|v|(s,v) < sum(delta|v-1|(s,v) which means that there's a v in C such that delta|v|(s,v)

Question 37

Describe Bellman-Ford algorithm

Answer 37

The idea is graph duplication (it will be explore on a different question), make |V|+1 levels, vk in level k represents reaching vertex v using at most k edges. We are going to connect vertices from lower levels only to higher levels, which means that the duplicated graph will not contain any cycles (a->b->c->a means that there's some higher level pointing at a lower level) -> that is exactly a DAG and so we can use the linear time algo that we already know (DAG relaxation) to find SSSP for the modified algorithm.

Question 38

How do I build the modified, duplicates, graph in Bellman-Ford?

Answer 38

Take all the vertices in G, say v1...v|v| and 'duplicate' them all at |V|+1 levels from 0 to |V|. Add a subscript to each node, so for example node v1 in level 0 will read v10, node vn at level 3 will be vn3. Then for each two subsequent levels (say,level 0 and level 1 or level 2 to level 3) add edges: for each (v,u) in the original graph add the edge (v0,u1) for example for the edges between level 0 and level 1, and it will have the same weight as the edge (v,u), and also add an edge between a vertex and itself (v0,v1) with a weight of 0. Notice that the modified graph cannot have cycles, as all the edges are pointing towards a more 'advanced' layer (there are no edges between vertices even inside of a layer).

Question 39

When building the modified graph for Bellman Ford, why do i need the edges between an edge and itself (well,itself on the next level)

Answer 39

to represent "at most" k, this will represent "not moving".

Question 40

After running DAG for the modified Bellman-Ford graph, 1. delta(s0,vk) =? 2. delta(s0,u|v|-1)>delta(s0,u|v|) then?

Answer 40

1. deltak(s,v) 2.delta(s,u) = minus infinity for each such vertex u,set all vertices reachable from u delta's to be minus infinity.

Question 41

What is the assumption of Dijkstra?

Answer 41

All the weights are non-negative

Question 42

What's the idea,conceptually, of Dijkstra?

Answer 42

Expand from the source in a BFS-y way. This works since, without negative weights, any path from s to v that goes through u-its weight will be bigger or equal to the weight of the shortest path from s to u.

Question 43

To implement Dijkstra, I need a Datastructure named 'changeable priority queue'. What is it used for, and what are the operations on it?

Answer 43

It's used to find the next vertix I want to operate on fast. The 3 operations supported are: 1. Build(on iterable) 2. Delete min() ->deletes the minimum key 3. Decrease key(id,key) - Notice that each item has a key, as well as an ID. This can be easily implemented at O(logn) with a priority queue (which support by default operations 1 and 2) and cross reference it with some dictionary (an AVL or a hashtable but since we know that our ids are between 0 and |v|-1 I can literally use an array).

Question 44

Describe Jijkstra's algorithm in full

Answer 44

1. Set d(s,v) = infinity for all v in V set d(s,s) = 0 2. Build changeable priority queue with (id=v,key=d(s,v)) for all v in V 3. While len(CPQ)>0: delete the next item (v,d) with a minimum key from CPQ. update all the items such that v->u to have (id=u,key=min(previous_key, d(s,v)+w(v,u)).

Question 45

Prove Dijkstra's algorithm

Answer 45

It's sufficient to show that d(s,v) = delta(s,v) when v is removed from CPQ. Proof is by induction assume that the K first elements removed from CPQ show for the (k+1)th element. Let's look at a shortest path from s to v: s-.-...-u. Either all vertices were removed from CPQ or not. Let's look THE FIRST vertex (the closest to u,it might be u itself) on that path from s to u which was not removed from CPQ yet, say v. s-....VNIQ-VIQ-....u. I know that VNIQ updated VIQ when it was removed from the queue to have d(s,VIQ)<=d(s,VNIQ)+w(VNIQ,VIQ). From the induction assumption, d(s,VNIQ)=delta(s,VNIQ) at that point. Therefore, d(s,VIQ) was updated to be delta(s,VIQ) at that point (any sub-path of a shortest path is a shortest path). Since we chose to remove u before we chose to remove VIQ, we know that d(s,u)<=d(s,VIQ) = delta(s,VIQ) since delta(s,u)>= delta(s,VIQ) it follows that all of those are the exact same quantity.

Question 46

What's the running time of dijsktra?

Answer 46

We build the CPQ once (B time) We delete the minimum from the Q up to |V| times so O(|V| * M) We may need to relax elements in CPQ up to once for each outgoing edge so O(|E|* D) With a binary heap this would amount to |E|logV, but with a ds (fibonnacci heap) that isn't going to be taught in this class, this will amount to O(VLOGV +E) which is what I can use in theoretical problems

Question 47

What problem Johnson's algorithm solve?

Answer 47

APSP: all pairs shortest paths input: G + w output: delta(u,v) for every u,v in V (or abort if there's a negative weight cycle in the graph). Notice that the output itself is theta(V^2) since for every pair of vertices I need to return a number.

Question 48

What would be a "brute force" solution with our current knowledge, to solve APSP?

Answer 48

Run SSSP for all vertices, so for example solve it in O(V^2*E) time (run Bellman ford for each node) , or if we know that all the weights are non-negative then Dijksta for every vertex will be O(V^2logV+VE) With Johnson's algorithm we will focus on doing something more intelligent than running BF V times.

Question 49

Why do we not care for undirected graphs in the context of Johnson's algorithm?

Answer 49

If we have an undirected graph, we can detect in O(|E|) if we have a negative cycle (iff there's ANY negative edge), if we do, abort, otherwise just run Dijkstra V times.

Question 50

What's the idea behind Johnson's algorithm?

Answer 50

make a new graph G' where edge weights non-negative while preserving shortest paths.

Question 51

GIVEN the distances from the new graph G', how can I compute the distances in the new tree? How much time does it take?

Answer 51

Given a shortest paths distances in G', I can computre the parents in the new graph G' in O(|V|+|E|) time for each vertex (actually |E| is sufficient ) and do it for each node would taOke O(|V|*(|V|+|E|))

Question 52

Prove: If a negative cycle exists then no G' with non negative weights that preserves the shortest paths in G exists

Answer 52

If a negative cycle exists then a shortest path between two vertices in a cycle, c1 and c2 is infinite and non-simple, but a graph with non-negative weights has only shortest paths that are simple.

Question 53

Define this transformation: Take the largest negative weight in a graph, say -wmax define w = w+wmax. This way we will not have negative weights in our graph. Does this work? Why

Answer 53

It doesn't work because it changes the smallest weight paths. In particular, if there was a small path using many edges, it will now have a bigger weight than some bigger path with way less edges.

Question 54

What transformation idea does work for Johnson's algorithm transformation of G to G'? based on what observation?

Answer 54

Simple observation: every path that is going into v uses an edge incoming to v. Every path that goes through v uses an edge going out of v. Tranformation idea: Add/subtract the same number for all incoming edges to V and subtract/add the same number for all outgoing edges from V!

Question 55

transformation idea does work for Johnson's algorithm transformation of G to G': What if I'll add the same number to all incoming edges and subtract/add a different number to all outgoing edges to v?

Answer 55

The paths going through v will benefit or be penalized by the difference between the two numbers. Therefore it needs to be the same number.

Question 56

Transformation idea for Johnson's: Add/subtract the same number for all incoming edges to V and subtract/add the same number for all outgoing edges from V - prove that this doesn't change shortest paths

Answer 56

Proof: Either the path from any vertex s to t touches v or it doesn't. If v is never on the path, then since path weight is unchanged. If v is 'in the middle', any number of times (although, in reality, it can only be in a shortest path once), then we added and subtracted the same weight so the path's weight doesn't changed. If v=s then we add the same constant TO EVERY PATH STARTING FROM V. Therefore, shortest path from s to v doesn't change. same for s=t.

Question 57

Given the transformation, we want every weight to be non-negative. What could be the issue and how do we solve it?

Answer 57

Issue: Let's denote h(v) as the number we added/subtracted from v. In other words we want w'(u,v) >=0 or w(u,v)+h(u)-h(v)>=0 or h(v)<=w(u,v)+h(u) This looks a lot like the triangle inequality, but the h=delta values might not be finite if there are nodes that aren't accessible ( I didn't understand that statement). Solution: Add a super vertex s with 0 weight edges to all other vertices. Run SSSP (BF because there can be negative weights) from s. If delta(s,v) is not 0 for any v then there is at least one negative weight cycle in the graph. Otherwise, I know that the shortest paths (all are not minus infinity) satisfy the equation for h, and therefore h(v)=delta(s,v) is a legitimate function that modifies G to G'. Notice that h(v) can be negative since yes, there's a path from s to v of weight 0, but there can paths of negative value (without negative cycles) if there are negative weights in the original graph. So to find h(V) I just run SSSP (BF) from s to all v, find delta(v) and that's simply h(V) that I want to subtract/add to each incoming/outgoing edge of v.

Question 58

Describe entire Johnson's algorithm in high level

Answer 58

1. Construct Gs from g (make a suprt node s with 0 weight edges to each vertex). 2. Compute delta(s,v) for all v by SSSP (BF). If there exists delta(s,v) = minus infinity then abort (there exists a negative cycle) else: 3.h(v)=delta(s,v), create G' from G and h: the weight of the edge between (u,v) will have w'(u,v)=w(u,v)+h(u)-h(v) = w(u,v)+delta(s,u)-delta(s,v) (from the Gs graph) Solve G' for all vertices by Dijkstra. And lastly: Compute (G)'s short distances from (G')'s short distances.

Question 59

What's the definition of greedy algorithms?

Answer 59

Repeatedly make locally best choice/decision, ignoring effect on the future

Question 60

What's a spanning tree?

Answer 60

a subgraph of G, G', which is a tree that contains all the vertices of G (and a subset of its edges of course).

Question 61

Define the minimum spanning tree problem

Answer 61

Given a weight graph G(V,E),w, find a spanning tree G', such that Sum(w(E')) is minimal.

Question 62

If a problem can be solved correctly with a greedy algorithm, I can prove two properties about it, what?

Answer 62

1. Optimal substructure: (similiar to DP): Optimal solution to problem incorporates optimal solutions to subproblem(s) 2. Greedy choice property: locally optimal choices lead to a globally optimal solution

Question 63

Optimal substructure for MST greedy solution - name it

Answer 63

If I know that some edge e={u,v} is in some MST(there can be many MSTs), I can collapse both uv into one component (if they have a common neighbor then delete the max edge), take all of the edges outgoing and ongoing into my component, and then choose the minimum edge again

Question 64

Prove: if e is part of some MST of G, then G/e (the contracted graph without E and with a vertex uv which represents the former {u,v} nodes)-its MST with e will be a MST of G.

Answer 64

Proof: I know that e is an edge of some MST, say, T*=(V,E0) of G, and I know that T1 is a MST of G', T*1=(V,E*1=E/e). I want to prove that T*1+e is a MST of G. If T1+e is equal to T0 then I'm done. But the weights of T*1+e has to be the same as the weight of T*: If w(T*)>w(T*1)+w(e) then E*1+e creates a minimum spanning tree of full G which is less than w(T*) (T*1+e). If w(T*1)+w(e)>w(T*) then I can find a minimum spanning tree for G' which is less than w(T*1) (T*/e). In other words, w(T*) = w(T*1+e) or T*1+e is a spanning tree of G.

Question 65

Greedy choice property for MST: consider any cut (V/S,S) (S is a subset of V), and define any edge from S to V/S a crossing edge. Then .... what? and How to prove?

Answer 65

Then min weight edge {u,v} over crossing cut is part of some MST! Proof: Cut and paste argument (this is almost always how we prove greedy algorithms to be correct). Let T* be any MST of G which doesn't include e (if no such tree exist then I'm done :D). Since it's a tree, it connects some vertices between V/S and S (otherwise T* isn't connecting all v in V). In particular, there's some e' which crosses the cut. If I remove e' and add e, I will get a MST (all that I need to do is prove that T*-e'+e is a tree and I'm done, since by definition w(e)<=w(e'). T*-e'+e is connected and doesn't have cycles: No cycles: If there are cycles in T*-e'+e there has to be a cycle between u-v, but that means that there's a path with no e or e' from u to v, whereas in a tree a path is unique. connected: Inside S and V/S there's no change so the only concern is given vertx v1 is S and vertex v2 in V/S but we can create a path to u and v from either sides of S and V/S and connect... )

Question 66

What type of argument do we usually use to prove greedy algorithms to be correct?

Answer 66

Cut and paste arguments, for example, if I take some optimal solution that doesn't have some property that i want (for example some edge e to be in the solution), and i cut part of it and then paste the property that I want, and it's still an optimal solution -> then cut and paste works.

Question 67

Describe Prim's algorithm

Answer 67

https://youtu.be/tKwnms5iRBU?t=2580