Solutions will be presented in class on May 6, May 8, and at our scheduled final-exam period on May 17. Sign up for a time and a problem ASAP!
Prove (e.g. by induction) that
Your company has a big project, which has been broken up into N tasks. Some tasks are prerequisites for others (task i must be completed before task j can start). It's also possible that two tasks must overlap: either one can start first, either one can end first, but there has to be a time that both tasks are underway simultaneously.
Your program should take in a bunch of such constraints (either "task i must finish before task j starts" or "tasks i and j must overlap"), determine whether it's possible to meet all the constraints, and if so, produce an ordered list of the form "start task 5, start task 3, finish task 5,start task 2, start task 4, finish task 4, finish task 3, finish task 2" that meets them all.
Recall the definition of a connected graph. In this problem we'll study how securely connected a graph is. (For example, if we think of the graph as representing a computer network, could an enemy disconnect the network by sabotaging a single computer or communication link?)
A bridge edge is defined as an edge which, if removed, would leave a disconnected graph.
An articulation point is defined as a vertex which, if removed (with all its incident edges) would leave a disconnected graph.
Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its bridge edges.
Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its articulation points.
For both of these, you'll get partial credit for a correct but inefficient algorithm.
Hint: It may help to start by drawing a graph with a single bridge edge or an articulation point, run a breadth-first or depth-first search on it, and see what's special about the bridge edge or articulation point. Then try one with two bridge edges or two articulation points....