Graph Algorithms (part 2 of CSC 282),
http://www.cs.rochester.edu/~stefanko/Teaching/20CS282
IMPORTANT: Homework must be typeset. (Why? The homework has to be collected electronically. Grading handwritten homework was difficult. Grading photographs of handwritten homework is prohibitively difficult.)
Homework 2 due: Oct. 8 (Thursday); submit on Gradescope.
Problem sessions before Homework 2 is due:
Oct. 5 (Monday) 6:15pm – 7:15pm in Hoyt Hall Room 104
Oct. 6 (Tuesday) 6:15pm – 7:15pm in Hoyt Hall Room 104
Oct. 7 (Wednesday) 6:15pm – 7:15pm in Hoyt Hall Room 104 (might have to move ONLINE)
Oct. 7 (Wednesday) 7:40pm – 8:40pm in ONLINE
1 Homework – solve and turn in
2.1 (due Thursday, Oct. 8) Let G = (V, E) be a directed graph (digraph) given in the following adjacency-list representation: for each vertex v ∈ V we have a linked list of out-neighbors of v. Assume that V = {1, . . . , n} and let m := |E|.
1. Write pseudocode for a procedure which outputs an adjacency-list representation of the reverse digraph (i. e., G with each edge reversed). The procedure should run in time O(m + n).
2. Write pseudocode for a procedure which outputs the adjacency-list representation of G in which the out- neighbors of each vertex are listed in the increasing order. The procedure should run in time O(m + n).
3. Write pseudocode for a procedure which checks if G is undirected (i. e., the reverse of every e ∈ E is also in E). The procedure should run in time O(m + n).
2.2 (due Thursday, Oct. 8) We will call a directed graph G = (V, E) good if for every pair of vertices u, v ∈ V there exists a path from u to v or there exists a path from v to u. For example, the following two graphs are good: ({1, 2}, {(1, 2)}) and ({1, 2}, {(1, 2), (2, 1)}). For example, the following graph is not good: ({1, 2}, {}). Give an O(m + n) algorithm that decides whether a given directed graph is good.
2.3 (due Thursday, Oct. 8)
1. WearegivenaDAG(directedacyclicgraph)G=(V,E)andtwoverticesu,v∈V. AssumethatV ={1,…,n} and let m := |E|. We want to figure out the length of the longest u-v-path in G (the length of a path v1, . . . , vk is k − 1). Give an O(m + n) algorithm for the problem. Write pseudocode for the algorithm.
2. We are given a DAG G = (V,E), two vertices u,v ∈ V and a subset S ⊆ V. We want to figure out whether there exists a u-v-path in G that contains a vertex in S (that is, does there exist k and a path v1, . . . , vk such that v1 = u, vk = v and {v1,…,vk}∩S ̸= ∅). Give an O(m+n) algorithm for the problem. Write pseudocode for the algorithm.
3. We are given a directed graph G = (V,E), two vertices u,v ∈ V and a positive integer l. We want to figure out whether there exists a u-v-walk of length at least l (remember, in a walk we allow repeated vertices and edges; the length of a walk v1, . . . , vk is k − 1). Give an O(m + n) algorithm for the problem. Clearly describe your algorithm (pseudocode is not required). You can use any algorithm covered in class/textbook (you don’t need to write pseudocode for the algorithm used).
1
2 Additional problems
Try to solve the following problems from Cormen-Leiserson-Rivest-Stein. We will go over the ones that you choose in the problem sessions.
• 22.1-1, 22.1-6, 22.1-7, 22.2-6, 22.2-8, 22.3-9, 22.3-11, 22.5-1, 22.5-3, 22.5-4, 22.5-7, • 24.1-5, 24.1-6, 24.3-7, 24.3-8, 24.3-9, 24.4-5,
• 25.2-6, 25.2-8,
• 26.2-10, 26.2-11.
Try to solve the following problems from Dasgupta-Papadimitriou-Vazirani. We will go over the ones that you choose in the problem sessions.
• 3.1, 3.2, 3.3, 3.4, 3.6, 3.7, 3.8, 3.9, 3.11, 3.12, 3.13, 3.15, 3.18, 3.19, 3.21, 3.22, 3.23, 3.24, 3.25, 3.26, 3.27, • 4.1, 4.2, 4.3, 4.4, 4.5, 4.7, 4.8, 4.10, 4.11, 4.13, 4.15, 4.17, 4.18, 4.19, 4.20, 4.21,
• 5.1, 5.2, 5.3, 5.7.
Try to solve the following problems from http://jeffe.cs.illinois.edu/teaching/algorithms/all-graphs.pdf We will go over the ones that you choose in the problem sessions.
• Section 18: problems 9, 10, 11, 12,
• Section 19: problems 1, 5, 6, 7, 9,
• Section 20: problems 1, 2, 3, 4, 5, 6, 7, 8, • Section 21: problems 4, 5, 6, 7, 9, 11, 12, • Section 2: problems 3, 4, 5, 6.
2