CMPSC 465 Spring 2022
Consider the directed graph G given below.
1. Run DFS-with-timing on this graph G: give the pre and post number of each vertex. Whenever there
is a choice of vertices to explore, always pick the one that is alphabetically first.
Copyright By PowCoder代写 加微信 powcoder
2. Draw the meta-graph of G.
3. WhatistheminimumnumberofedgesyoumustaddtoGtomakeitstronglyconnected(i.e.,itconsists of a single connected component after adding these edges)? Give such a set of edges.
1. (8 + 6 + 6 = 20 pts.)
Data Structures & Algorithms
Chunhao Wang and Midterm Part 2
2. (20 pts.) You are given a directed graph G = (V, E). Design an algorithm to determine if there exist two distinct vertices u, v ∈ V such that for every vertex w ∈ V \ {u, v} either w can reach u, or w can reach v, or both. Describe your algorithm, analyze its running time, and explain why it is correct. Your algorithm should run in O(|V | + |E|) time. (Hint: You may find Problem 3 in Assignment 06 relevant.)
3. (7+7=14pts.)
1. Design an instance of convex hull problem with 7 points, such that if Graham-Scan algorithm runs on your instance, the sequence of stack operations is (push, push, push, push, push, pop, pop, pop, push, push). Include a visual illustration of these 7 points and the convex hull. You will need to guarantee no three points in your instance locate on the same line.
2. Give 7 lines such that the convex hull of their dual points has 3 vertices. Include a visual illustration of your 7 lines and their dual points, and label which line corresponds to which dual point. You will need to guarantee no two lines are parallel and no three lines intersect at the same point.
CMPSC 465, Spring 2022, Midterm Part 2 1
4. (8 + 15.5 = 23.5 pts.) You are given a directed graph G = (V,E), a vertex s ∈ V , edge length c(e) for each e ∈ E, and an integer d > 0; c(e) could be negative but the graph does not contain negative cycles. We aim to find the length of the shortest path from s to each vertex such that the number of edges on it is at most d. In other words, we do not consider paths with more than d edges; among the paths from s to each vertex with at most d edges, we aim to find the shortest one.
1. A simple intuition is to use Bellman-Ford algorithm but run d instead of |V | − 1 rounds. Give an example where this algorithm does not work.
2. Design an algorithm that does work, analyze its running time, and explain why it is correct. Your algorithm should run in O(|V | · |E|) time. (Hint: modify Bellman-Ford algorithm by adding a data structure companied with dist array to keep track of the number of edges.)
CMPSC 465, Spring 2022, Midterm Part 2 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com