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. (3 points)
Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its articulation points. (3 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....
Consider the problem of making change using pennies, nickels, dimes, and quarters (i.e. coin values 1, 5, 10, 25). Give a greedy algorithm which, for any specified number of cents, makes that amount of change with as few coins as possible.
The aforementioned greedy algorithm works fine in the U.S, but it doesn't necessarily work with other coin values. Give an example of a set of coin values for which the aforementioned greedy algorithm does not choose the fewest possible coins.
Implement, test, and debug your coin-changing algorithm (from above) in a real programming language.