hw3-7

pdf

School

University of British Columbia *

*We aren’t endorsed by this school

Course

221

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by AdmiralStrawCrocodile17

Question 7: Task ordering Part 1 It's almost the holdays and you haven't sorted out your holiday tasks! This requires a bit of planning. There are lots of things to do, like doing your laundry which requires getting more laundry soap which requires going to the store which requires calling your friend to get a ride... You decide to draw a directed graph. Each node in the graph is a task (something you need to do). Each edge from node A to node B means that you must do task A before task B. The goal is to find a sequence (an ordering) of the tasks so that every edge in the graph is directed from an earlier task to a later task in the sequence. Such a sequence is called a valid ordering of the graph. For example, the only valid ordering in is BAC. Select each ordering that is valid for the above graph. @ H,C D,EIFBAG[] (b)E, A C1,G B, DH,F (© H,ED,CB,IFAG(] (d)H,D,ECIBAGF(] Select all possible options that apply. @ Which of the following graphs have no valid orderings? (a) °"'° )

(©) o [:] (d) ) Select all possible options that apply. @ Part 2 We want to find a valid ordering for a graph or determine that no such ordering exists. We'll use depth-first search to do it. Notice that the pseudocode we've given you has only odd line numbers. We'll adapt DFS to our purpose by adding two even numbered lines. Note: This is DFS in a directed graph. The edge (v, w) is directed from v to w. r 75 DFSValid(G) { 77 unmark all vertices 79 unmark all edges 81 for each vertex v { 83 if v is unmarked { 85 DFS(G,V) 87 } 89 } 91 return seq 93 } 95 DFS(G, v) { 97 mark v 99 for each edge (v,w) { 101 if w is unmarked { 103 mark (v,w) TREE 105 DFS(G,w) 107 } else if (v,w) is unmarked { 109 mark (v,w) NONTREE 111 } 113} 115 } - — 1 Note that seq is a global variable that is initially an empty list. At what even line number should we add add v to front of seq

SO seq, returned by a call to DFsvalid(G), is a valid ordering of G (if one exists)? Line= 114 © At what even line number should we add if w not in seq then fail so DFS fails if the graph has no valid ordering? Note: multiple line numbers are possible locations. Enter the first possible line number. Line= 108 @ Part 3 You decide to call all your friends to help with your tasks. You have enough friends to assign a different friend to each task, but it still may take a long time to finish all the tasks because: A task cannot be started until all of the tasks that have an edge to it have been finished. You want an algorithm to determine how quickly all the tasks can be finished with your friends help. e Let time[v] be the amount of time to finish task v after someone starts working on it. (time[v] is a positive integer.) e Let ECT[v] be the minimum amount of time to finish task v if you and your friends start working on tasks now. (ECT[v] stands for the earliest completion time of task v.) e If atask v has no edges to it then ECT[v] = time[v], otherwise ECT[v] is greater than time[v]. In the above graph, each node v is labeled with its name and time[v]. What is ECT[G] in the above graph? ECT[G] = @ 30 ® Consider the following code:

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

1 calculate ECT(G,time) { 2 seq = DFSvalid(G) // from part 2. 3 maxECT = © 4 for i=1ton{ 5 v = seq[i] 6 ECT[v] = time[v] 7 for each edge (u,v) { 8 ECT[v] = ? 9 } 10 maxECT = max(maxECT, ECT[v]) 11} 12 return maxECT 13 } L — What is the correct code to fill in at line 8 to calculate EcT[v] for all tasks v in the graph G = (V, E) with |V| = n given the time vector time? () max(ECT[v], time[v]) (b) max(ECT[v], ECT[u] + time[v]) ([ ) (c) max(ECT[v], ECT[u]) (d) time[u] (e) time[v] (f) max(ECT[v], ECT[u]) + time[v] What is the asymptotic running time of calculate ECT(G,time) where G has n vertices and m edges? You may assume G has an adjacency list for incoming edges and one for outgoing edges. You may assume the check if w not in seq then fail in DFS(G, v) takes O(1) time. (a) ©(mlogn) (b) B(n?) (©) ©(mn) (d) ©(n+m) (] (e) O(m?) This question is complete and cannot be answered again. Correct answer Part 1 It's almost the holdays and you haven't sorted out your holiday tasks! This requires a bit of planning. There are lots of things to do, like doing your laundry which requires getting more laundry soap which requires going to the store which requires calling your friend to get a ride... You decide to draw a directed graph. Each node in the graph is a task (something you need to do). Each edge from node A to node B means that you must do task A before task B. The goal is to find a sequence (an ordering) of the tasks so that every edge in the graph is directed from an earlier task to a later task in the sequence. Such a sequence is called a valid ordering of the graph. For example, the only valid ordering in

o °¢° is BAC. Select each ordering that is valid for the above graph. @H CDEIFBAG (C) Hl EI DI CI BI II FI AI G Which of the following graphs have no valid orderings? (a) (©) (d) O 0C °‘er’.e Part 2 We want to find a valid ordering for a graph or determine that no such ordering exists. We'll use depth-first search to do it. Notice that the pseudocode we've given you has only odd line numbers. We'll adapt DFS to our purpose by adding two even numbered lines. Note: This is DFS in a directed graph. The edge (v, w) is directed from v to w.

75 DFSvalid(G) { 77 unmark all vertices 79 unmark all edges 81 for each vertex v { 83 if v is unmarked { 85 DFS(G,V) 87 } 89 } 91 return seq 93 } 95 DFS(G, v) { 97 mark v 99 for each edge (v,w) { 101 if w is unmarked { 103 mark (v,w) TREE 105 DFS(G,w) 107 } else if (v,w) is unmarked { 109 mark (v,w) NONTREE 111 } 113} 115 } L= Note that seq is a global variable that is initially an empty list. At what even line number should we add add v to front of seq SO seq, returned by a call to DFSvalid(G), is a valid ordering of G (if one exists)? Line =114 At what even line number should we add if w not in seq then fail so DFS fails if the graph has no valid ordering? Note: multiple line numbers are possible locations. Enter the first possible line number. Line = 108 Part 3 You decide to call all your friends to help with your tasks. You have enough friends to assign a different friend to each task, but it still may take a long time to finish all the tasks because: A task cannot be started until all of the tasks that have an edge to it have been finished. You want an algorithm to determine how quickly all the tasks can be finished with your friends help. o Let time[v] be the amount of time to finish task v after someone starts working on it. (time[v] is a positive integer.) e Let ECT[v] be the minimum amount of time to finish task v if you and your friends start working on tasks now. (ECT[v] stands for the earliest completion time of task v.) e If atask v has no edges to it then ECT[v] = time[v], otherwise ECT[v] is greater than time[v]. In the above graph, each node v is labeled with its name and time[v]. What is ECT[G] in the above graph? ECT[G] = 23 Consider the following code:

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

1 calculate ECT(G,time) { 2 seq = DFSvalid(G) // from part 2. 3 maxECT = © 4 for i=1ton{ 5 v = seq[i] 6 ECT[v] = time[v] 7 for each edge (u,v) { 8 ECT[v] = ? 9 } 10 maxECT = max(maxECT, ECT[v]) 11} 12 return maxECT 13 } L — What is the correct code to fill in at line 8 to calculate EcT[v] for all tasks v in the graph G = (V, E) with |V| = n given the time vector time? (b) max(ECT[v], ECT[u] + time[v]) What is the asymptotic running time of calculate ECT(G,time) where G has n vertices and m edges? You may assume G has an adjacency list for incoming edges and one for outgoing edges. You may assume the check if w not in seq then fail in DFS(G, v) takes O(1) time. (d) ©(n +m) Submitted answer 2 % hide ~ Submitted at 2023-12-05 11:32:43 (PST) [ o ] [ \ae ] Part 1 It's almost the holdays and you haven't sorted out your holiday tasks! This requires a bit of planning. There are lots of things to do, like doing your laundry which requires getting more laundry soap which requires going to the store which requires calling your friend to get a ride... You decide to draw a directed graph. Each node in the graph is a task (something you need to do). Each edge from node A to node B means that you must do task A before task B. The goal is to find a sequence (an ordering) of the tasks so that every edge in the graph is directed from an earlier task to a later task in the sequence. Such a sequence is called a valid ordering of the graph. For example, the only valid ordering in is BAC. Select each ordering that is valid for the above graph. (a)H,C D,E I F B A G[] (¢ H,ED,CB,IFAG] (d)H,D,EC 1B A G F_] Which of the following graphs have no valid orderings?

) ~— Q R QL = —~+ N We want to find a valid ordering for a graph or determine that no such ordering exists. We'll use depth-first search to do it. Notice that the pseudocode we've given you has only odd line numbers. We'll adapt DFS to our purpose by adding two even numbered lines. Note: This is DFS in a directed graph. The edge (v, w) is directed from v to w. 75 DFSValid(G) { 77 unmark all vertices 79 unmark all edges 81 for each vertex v { 83 if v is unmarked { 85 DFS(G, V) 87 } 89 } 91 return seq 93 } 95 DFS(G, v) { 97 mark v 99 for each edge (v,w) { 101 if w is unmarked { 103 mark (v,w) TREE 105 DFS(G,w) 107 } else if (v,w) is unmarked { 109 mark (v,w) NONTREE 111 } 113} 115 } (= Note that seq is a global variable that is initially an empty list. At what even line number should we add add v to front of seq sO seq, returned by a call to DFsvalid(G), is a valid ordering of G (if one exists)? Line = 114 At what even line number should we add

if w not in seq then fail so DFS fails if the graph has no valid ordering? Note: multiple line numbers are possible locations. Enter the first possible line number. Line = 108 Part 3 You decide to call all your friends to help with your tasks. You have enough friends to assign a different friend to each task, but it still may take a long time to finish all the tasks because: A task cannot be started until all of the tasks that have an edge to it have been finished. You want an algorithm to determine how quickly all the tasks can be finished with your friends help. e Let time[v] be the amount of time to finish task v after someone starts working on it. (time[v] is a positive integer.) e Let ECT[v] be the minimum amount of time to finish task v if you and your friends start working on tasks now. (ECT[v] stands for the earliest completion time of task v.) e If atask v has no edges to it then ECT[v] = time[v], otherwise ECT[v] is greater than time[v]. In the above graph, each node v is labeled with its name and time[v]. What is ECT[G] in the above graph? ECT[G] =30 0%] Consider the following code: 1 calculate ECT(G,time) { 2 seq = DFSvalid(G) // from part 2. 3 maxeCT = @ 4 for i=1ton{ 5 v = seq[i] 6 ECT[v] = time[v] 7 for each edge (u,v) { 8 ECT[v] = ? 9 } 10 maxECT = max(maxECT, ECT[v]) 11} 12 return maxECT 13 } | - | What is the correct code to fill in at line 8 to calculate EcT[v] for all tasks v in the graph G = (V, E) with |V| = n given the time vector time? (b) max(ECT[v], ECT[u] + time[v]) What is the asymptotic running time of calculate ECT(G,time) where G has n vertices and m edges? You may assume G has an adjacency list for incoming edges and one for outgoing edges. You may assume the check if w not in seq then fail in DFS(G, v) takes O(1) time. (d) ©(n +m) Submitted answer 1 Submitted at 2023-12-05 01:14:27 (PST) saved, not graded | [ ;i ) ] [ show Vv ] Homework 3 Assessment overview

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Question Submission status: Available points: — Total points: 6.22 /8 [Report an error in this question ] Previous question Personal Notes No attached notes Notes can't be added or deleted because the assessment is closed. Auto-graded question

hw3-7

Related Documents