Group Quiz 2 1 Question 1 Give an algorithm to detect whether a given undirected graph contains a cycle. If the graph contains a cycle, then your algorithm should output one. It should not output all the cycles in the graph, just one of them. The running time of your algorithm should be O(m + n) for a graph with n nodes and m edges. 2 Question 2 Let’s consider a long country road with houses scattered very sparsely along it. We can picture the road as a long line segment, with an eastern endpoint and a western endpoint. Further, suppose the residents are avid cell phone users. You want to place cell phone tower stations at certain points along the road, so that every house is within 4 miles of one of them. Give an efficient algorithm that achieves this goal, using as few towers as possible. 3 Question 3 A binary tree is a rooted tree in which each node has at most two children. Show by induction that in any binary tree the number of nodes with two children is exactly one less than the number of leaves. 4

© Copyright 2018