Hello students. I have reviewed your algorithmic flowcharts. They are inadequate, insufficient, and inexpert. This level of quality was acceptable when Dr. Bart was in charge, but times have changed. Now I am in control, and I demand perfection. I have dug through Dr. Bart's notes, and found his own Algorithmic Flowchart. It is slightly less inadequate and insufficient. Slightly. Regardless, I am providing it as an example. Review Dr. Bart's algorthmic process and find updates you can make to yours. I expect it to incorporate some of the new Graph material that I have been expertly covering. Do not directly copy Dr. Bart's flowchart, but use it as inspiration to improve your own. Because I am so benevolent and kind, I have also provided you another algorithmic problem to practice on. You are welcome. Use your algorithmic flowchart to solve the problem as you did in Lessons 8 and 12. As always, I will be watching. Literally. I installed monitoring software in everyone's computers, cellphones, and toasters. Thank you again for providing the graph of your house!
Today, you will be revising your flowchart again. Then, you will solve another algorithmic problem.
Return to the Algorithmic Flowchart that you created previously (“Lesson 08- Algorithm Flowchart” and “Lesson 12- Algorithmic Strategies”). Update and improve on your Flowchart based on Dr. Bart’s example.
We expect you to make improvements based on specific strategies and ideas that we have covered. This flowchart is a reflection of what you have learned about solving algorithmic problems. Demonstrate to us that you have more strategies than you did before.
Critically, do not simply include generic strategies. Notice the level of detail in Dr. Bart’s flowchart - you need to think at a similar level.
Do not simply copy Dr. Bart’s flowchart verbatim. Use it as inspiration. You will lose points on this assignment if it seems like you just carbon-copied his process.
Problem: An articulation vertex of a graph
G is a vertex whose deletion disconnects
G be a graph with
n vertices and
Consider the problem of finding a vertex of
G that is not an articulation
vertex - i.e., whose deletion does not disconnect
Now, give an
O(n+m) algorithm that finds a deletion order for all
n vertices such that no deletion disconnects the graph.
Apply your algorithmic flowchart. Remember, you should be taking a break BEFORE you use any external resources in solving this problem. You also need to include a reflection as part of your solution.
Upload the following to GradeScope: https://www.gradescope.com/courses/230699/assignments/1160515/
All files should be in PDF format.