The year is 430BC. Socrastes The Philosopher has a collection of important ethic
ID: 3735867 • Letter: T
Question
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 the number of questions is n and the number of dependencies is m, describe
an algorithm which returns a possible order that Socrastes might think about the
questions in O(n + m) time.
Use topological Sort as a framework. Make sure the solution is completed in O(m + n) time.
Explanation / Answer
Solution:
Let's consider this problem as a digraph of vertices and edges in which the vertices will represent the questions and the directed edges will represent the flow of questions and dependency between them.
The algorithm is given below:
The above algorithm is considering n number of questions and mm dependencies between them and according to that the algorithm will compute in
T(n)= O(n + m) time.
I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.