20-CS-122-001 Computer Science II Spring 2012
Topological Sort

Virtual functions, classes, inheritance, lists, queues, stacks, applications

    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.

    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.

    Of course, this is just topological sort.