20-CS-122-001 | Computer Science II | Spring 2012 |
---|---|---|
Topological Sort |
A positive integer n, and for each 0 ≤ i < n, a subset of the integers in {0,1,2,...,n-1} which are considered to be less than i. |
A function that takes the above as input and outputs a list of all integers from 0 to n-1 where every integer x is later in the list than all integers that are considered to be less than x. |
Note:
It is possible that, for example, 87 < 11. In other words, the meaning of the operator < does not follow the familiar meaning. This situation is common in computer science but is difficult for some to accept perhaps due to a rigid math curriculum in primary and secondary school. Lots of operators are "overloaded" in real-life math, especially in applications to computer security. |
Idea:
Of course, this is just topological sort. |