$30.00
Description

Give an algorithm based on BFS that given a graph G = (V; E) (in adjacency list representation) checks whether or not G has a cycle. For fullcredit, 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]

Problem 4.1 from here (Chapter 4 of [DPV]). For part (a), you don’t have to show how the dvalues 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]

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 noncon icting jobs of maximum possible size. Show that the following algorithm solves the problem correctly (i.e., returns a set of noncon icting jobs of maximum size).
Latest Start Time (LST):
(a) Set R f1; : : : ; ng, and A ;.

While R 6= ;:


Pick request i 2 R with the latest start time.



Add i to A.

1


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


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 fullcredit, 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 independent 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.

Prove that if u is a leaf in T , then there is a maximumsize 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]

Give the graph T as input (in adjacencylist representation), give an algorithm to compute an independentset 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 algorithm. You don’t need to analyze the timecomplexity 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.

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.)

Problems 4.8, 4.9, 4.18 from [DPV].

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