CHAPTER 3: Algorithms Flashcards

Question

PRIMS ALGORTHIM: EXAMPLE ``` [A] [4][B] [5][7][C] [9][8][8][D] [5][5][5][8][E] ``` STARTING AT D

Answer 1

``` start at D: •cheapest Edge out costs 8 (pick any one of the cheapest) pick DB at random •cheapest from D or B to New vertex: BA costing 4 • cheapest from (A,B,D) to new: (AC, AE or BE) pick AC costing 5 • cheapest from (A,B,C,D) to E: (AE, BE, CE) all cost 5 ``` so 8+5+5+4=22 same minimal value but DIFFERENT MST than kruskals

Answer 2

*Kruskal's algorithm always finds a cheapest spanning tree: Suppose we have a tree T from kruskal's. let T_m be a minimum spanning tree. Need to show w(T)=w(T_m) over edges of w(e_i) ≤w(e_i)≤...≤... (i.e. transform T to T_m edge by Edge, by exchange principal ,and show each step is a minimal spanning tree) Let T be a spanning tree of G and e=xy an edge not in T. Then: unique path P from x to y using only edges of T. if f is any edge in P then T'=T\f∪e is a spanning tree ie can exchange edges in P for e. *always add cheapest edge in T but not in T_m in T∪T_m will be loops: BDE .....

Answer 3

notes on proof: ?? drawn diagrams deleting edges, adding to get loops either adding edges or making loops Exchange principle: Let T be a spanning tree of G, and e = xy an edge not in T. Then: Unique path P from x to y using only edges of T I If f any edge in P, then T0 = T \f ∪e a spanning tree i.e., can exchange edges in P for e. Basic idea of proofs: * Let T be spanning tree produced by algorithm I Let Tm be a minimal spanning tree * Transform Tm to T edge by edge using exchange principle * Show each step is a minimal spanning tree Key: always add cheapest edge in T but not Tm.

Answer 4

2 greedy algorithms: Kruskal: add cheapest edge that doesn't make a loop Prims: start at v, add cheapest edge to the new vertex *not immediately clear they find MST but proof wont be on the exam

Answer 5

* TSP- visiting every vertex and returning * shortest paths * longest paths

Answer 6

A directed graph is one where each edge has a chosen starting and ending point, usually indicated with arrows. *walks on directed graphs can only follow that direction

Answer 7

All edges have distinct weights: * * Never have to make an arbitrary choice * * Unique minimal weight spanning tree All edges have the same weight: * * Any spanning tree is minimal * *Probably too many to write down A few edges have repeated weights: * * Only a few places we have to make a choice * * Can ﬁnd them with case by case analysis breaking ties

Answer 8

Dijkstra’s algorithm for shortest path cant have negative edge weights Input: A weighted (possibly directed) graph G and starting vertex v ∈ G output: For every vertex w ∈ G a list of all shortest paths from v to w Initialize: From starting vertex v list every edge out of v as a potential shortest path to corresponding vertex w Iterate: * *Choose w with cheapest potential shortest path and make these paths permanent * * Update list of potential paths by adding edges out of w to the shortest paths to w and checking if they’re cheaper than known paths

Answer 9

marking route on graph S to T writing: possible paths setting cheapest possible path as permanent ``` Step 1: possible paths from S SB 7**** chosen SA 11 Step 2: possible out of B,chosen SA 11 but SBA 10**** SBD 17 ``` Step 3:possible out of A SBAD 16** SBAC 20 SBADC 20 SBADF 25 Step 4: out of C SBADF * SBACF * SBADCF all cost 25*** S..CE= 20+10 = 30 Step 5: New record for S-E S_{3 ways} FE 28** S_{3 ways} FT 36 Step 6: S..ET cost 28+7=35 less than 36 ``` cheapest path: SB 7 SBA 10 SBAD 16 SBAC or SBADC 20 ``` ``` SF = 25 in 3 ways S_(3 ways) FE 28 S_ .. ET 35 …. SBACFET SBADFET SBADCFET ```

Answer 10

General answer: Edges In all shortest paths: these are: always SB, BA,FE,ET ``` sometimes: AC AD CE CF DF ```

Answer 11

Any edge in any shortest path ``` eg both SB BA AC AD CE DF CF FE ET ```

Answer 12

Suppose we’re at the step were Dijkstra’s decides the cheapest path to w. Then: A cheaper path to w would have to go through a vertex u we haven’t found the cheapest path to yet. But! Even getting to u costs more than our cheapest path to w. An observation: Dijkstra’s algorithm depends on the edge weights being non-negative! * optimal- if all we know is a weighted graph cant improve col * not good In practical as every edge considered * driving distances * A* algorithm avoids searching London: Supposes we have an easy to calculate “heuristic distance” h(v,w), that is a lower bound for the actual distance d(v,w).

Answer 13

Scheduling a large problem with many parts For example, building a house. * Some can be done at same time: (ﬁnishing interior rooms) * Some need to be done in order: (foundation before walls) * How early could whole project be ﬁnished? Solution: longest path * Encode tasks as edges in directed weighted graph * Edge e follows edge f if task f requires task e * Length of longest path is the shortest time to complete project Building the directed graph from a list of tasks and dependencies can require a few tricks and won’t be tested

Answer 14

A necessary assumption: If the graph has a directed cycle, we could get an inﬁnitely long path by repeating graph over and over again. Graphs in scheduling applications are acyclic: Otherwise we’d have a cycle of tasks that all depend on each other and we could never start the project!

Answer 15

A directed graph G is acyclic if it has no directed cycles.

Answer 16

Initializing: * Topologically sort the vertices of G * List every edge of starting vertex as potential longest path Iterate: * Make the potential longest path to the ﬁrst vertex w on the list permanent * Update the list of potential longest paths adding edges out of w to longest paths to w and seeing if they create new longest paths

Answer 17

If G is acyclic it’s easy to order the vertices of G so that if there’s an edge from v to w, then w comes after v Note: the topological sort doesn't have to be unique ``` eg UVWX UWVX directed edges UV UW VX WX ``` *if a graph has a directed cycle we cant order it every tree has a topological ordering, as it has no cycles ie start from top and leaves at end HOW TO: We choose an unvisited vertex. Explore out until we cant or have already written down in ordering . Then we add that last vertex to the end of our ordering. Go back to prev vertex and explore out if made a choice, adding. Then we can select another unvisited node. Topological orderings aren't unique.

Answer 18

Topological sort this graph: SBADCFET List every edge of starting vertex as potential longest path: potential longest paths out of S: SB 7* SA 11 Iterate: * Make the potential longest path to the ﬁrst vertex w on the list (most expensive to next vertex) permanent * Update the list of potential longest paths adding edges out of w to longest paths to w and seeing if they create new longest paths potential longest path out of B: SBA costs 10 but SA costs 11* SBD 17 potential longest path out of A: SAC 21 SAD 17* and SBD 17* potential longest path from D: SADC 21* SBDC 21* (and SAC 21*) SADF 26 SBDF 26 ``` potential longest path from C: SADCE 31 SBDCE 31 SBDCF 26* SADCF 26* or SADF* SBDF* ``` ``` potential longest path from F: S...FT 37 S...FE 29 But SBDCE 31* SADCE 31* potential longest path from E: S...ET 38* (as S..FT 37 less than 38) ``` So our longest paths are: SBDCET SADCET SACET DIAGRAM: of all possible longest edges in paths and including in order ``` arrows ___ ____ ___ / ↘/ ↘/ ↘ S→B→A→D→C→F→E→T \ ↗ \ ↗\ ↗ ------- ------ ----- ``` ``` longest path B-7 A-11 D-17 [from B=10+7, A=11+6] C-21 [from A=11+10, D=17+4] F-26 [from C =21+3, D=17+4] E-31 [from C=21+10, F= 26+3] T-38 [from E=31+7, F=26+11] ``` marking on diagram edges SB SA DF CE ET bold AD--- AC--- BD--- all longest path end CET but 3 ways get to C

Answer 19

Any edge in the largest paths increase makes longest path longer ``` SA SB AC AD DC BD CE ET ```

Answer 20

THE EDGES IN ALL LONGEST PATHS ET CE ie we are considering the longest path still so decrease all our options

Answer 21

A Travelling Salesperson wants to start from home, visit every city on their list, then return home for as cheaply as possible. The Travelling Salesperson Problem, or TSP, is the following. Given a weighted graph G (usually G is the complete graph), what is the Hamiltonian cycle (i.e. closed walk visit every vertex) of cheapest weight *we don't tend to solve: only find bounds

Answer 22

Let G be a graph n and vertex set V and edge set E. Suppose we want to determine whether G has a Hamiltonian cycle. Weight a complete graph on the vertex set V as follows: make every edge in G have weight 1, and every edge not in G have slightly higher weight: w(uv) = {1 uv ∈ E {1 + ε uv / ∈ E Then, G has a Hamiltonian cycle if and only if there is a solution to the TSP with weight n. *as we only used the edges in the original graph

Answer 23

ﬁnd the weight of any Hamiltonian cycle *One greedy algorithm: nearest neighbour Keeping going to the closest city you haven’t been to

Answer 24

only nearest haven't been to. ie only the nearest to the one we just visited, no going back to consider other choices.

Answer 25

can’t use a cycle Any Hamiltonian cycle has length greater than solution to TSP (ie connect every vertex vs return to original vertex) To ﬁnd lower bound to TSP * Pick a vertex v ∈ G * Find a minimum weight spanning tree T on G \v ie remove this vertex. * Find the two cheapest edges e1 and e2 out of v, the vertex we removed * w(T) + w(e1) + w(e2) is a lower bound: ie its cheaper than any Hamiltonian cycle

Answer 26

Suppose that C was the Hamiltonian cycle of minimum weight. We split the C into two pieces: the two edges f1 and f2 adjacent to v, and the rest, which we’ll call R. Edges adjacent to v: e1 and e2 were the two cheapest edges next to v, so: w(f1) + w(f2) ≥ w(e1) + w(e2) The rest: C a cycle, so R = C \v is a path Paths are special cases of trees R visits every vertex of G \v Hence R a spanning tree and w(R) ≥ w(T) (If C is a Hamiltonian cycle delete A and the 2 edges in C that visit A. ill have a path through every vertex except A. C\{A_{g,h}} is a spanning tree of G\A and so w(g,h) is bigger than w(t) For the lower bound to be attainable ie be a Hamiltonian cycle, we need 1) T has to be in path 2) the 2 cheapest edges out of A have to go to the two ends of the path )

Answer 27

nearest neighbour for upper bound: start at A ``` AC 10 CB 21 BD 39 DE 45 EF 24 FG 11 GA 75 ```

CHAPTER 3: Algorithms Flashcards

(51 cards)