Graph Algorithms:

6. Application: Procrastinator's Sort The year is 430BC. Socrastes The Philosopher has a collection of important ethical questions to ponder over. Some of these questions have dependencies, i.e: "Is it eth ical to consume meat?" should be answered before the question "What should I eat for lunch?" is resolved. Socrastes may only consider one question at a time, but nev- ertheless, Socrastes is a masterful philosopher: whenever Socrastes begins thinking about a question, Socrastes is guaranteed to answer it in a few days. Socrastes will always respect the dependencies between questions in choosing which questions to think about. However, whenever Socrastes has a choice between two questions 2 to ponder, Socrastes will always choose the less important question to think about. 3 Suppose that Socrastes ranks the importance of questions on an integer scale from 1 to 10. If an algorithm which returns a possible order that Socrastes might think about the questions in O(n +m) time. (* ) the number of questions is n and the number of dependencies is m, describe 6. Application: Procrastinator's Sort The year is 430BC. Socrastes The Philosopher has a collection of important ethical questions to ponder over. Some of these questions have dependencies, i.e: "Is it eth ical to consume meat?" should be answered before the question "What should I eat for lunch?" is resolved. Socrastes may only consider one question at a time, but nev- ertheless, Socrastes is a masterful philosopher: whenever Socrastes begins thinking about a question, Socrastes is guaranteed to answer it in a few days. Socrastes will always respect the dependencies between questions in choosing which questions to think about. However, whenever Socrastes has a choice between two questions 2 to ponder, Socrastes will always choose the less important question to think about. 3 Suppose that Socrastes ranks the importance of questions on an integer scale from 1 to 10. If an algorithm which returns a possible order that Socrastes might think about the questions in O(n +m) time. (* ) the number of questions is n and the number of dependencies is m, describe