Homework #3 Solution

$30.00

Description

  1. Give an algorithm based on BFS that given a graph G = (V; E) (in adjacency list represen-tation) checks whether or not G has a cycle. For full-credit, your algorithm should run in

time O(jV j + jEj). Prove that your algorithm works (you can use properties of BFS that we stated in class without further proving them). [.75 points]

  1. Problem 4.1 from here (Chapter 4 of [DPV]). For part (a), you don’t have to show how the d-values are computed, just show the values after each iteration in a table with columns indicating the vertices and rows denoting the iterations. For part (b), it su ces to draw the nal shortest path tree. [.75 points]

  1. Consider the interval scheduling problem we studied in class: Given a sequence of requests

with start and nish times (s(i); t(i)), i = 1; : : : ; n, nd a set of non-con icting jobs of maximum possible size. Show that the following algorithm solves the problem correctly (i.e., returns a set of non-con icting jobs of maximum size).

Latest Start Time (LST):

(a) Set R f1; : : : ; ng, and A ;.

  1. While R 6= ;:

    1. Pick request i 2 R with the latest start time.

    1. Add i to A.

1

    1. Remove all requests that con ict with i (including i) from R.

  1. Return A.

The goal of the problem is to give you some practice in analyzing a greedy algorithm and to better understand the analysis of EFF that we did in class. So for full-credit, you cannot assume the analysis of ‘Earliest Finish First’ (you can use the ideas though) and your answer must be comparable in detail to our analysis of EFF in class. [.75 points]

(Hint: You can follow the same approach we used for analyzing Earliest Finish First in class.)

4* Given an undirected graph G = (V; E), a subset of vertices I V is an independent set in G if no two vertices in I are adjacent to each other. Let (G) = maxfjIj : I an independent set in Gg. The goal of the following questions is to give an e cient algorithm for computing an inde-pendent set of maximum size in a tree. Recall that a leaf in a graph is a vertex of degree at most 1 and that every acyclic graph (graph without any cycles) has at least one leaf.

Let T = (V; E) be an acyclic graph on n vertices.

  1. Prove that if u is a leaf in T , then there is a maximum-size independent set in T which

contains u. That is, for every leaf u, there is an independent set I such that u 2 I and jIj = (T ). [.3 points]

  1. Give the graph T as input (in adjacency-list representation), give an algorithm to com-pute an independent-set of maximum size, (T ), in T . To get full credit your algorithm

should run in time O(jV j jEj) (or better) and you must prove correctness of your al-gorithm. You don’t need to analyze the time-complexity of your algorithm and it is su cient to solve this part assuming part (1) (if you want) even if you don’t solve it. [.45 points]

(Hint: You can try a greedy approach where you add vertices one after the other based on property (1).)

Additional Problems. DO NOT turn in answers for the following problems – they are meant for your curiosity and understanding.

  1. Given an undirected graph G = (V; E) as input, use DFS to check if G has a cycle and if

does output the cycle. This can be solved in time O(jV j + jEj). (Note that unlike detecting a cycle, nding a cycle when one exists is much harder using BFS.)

  1. Problems 4.8, 4.9, 4.18 from [DPV].

  1. Problem 4.4, 4.7, 4.13, 4.17 from textbook [KT].

2