CSC 477/677 Assignment 5

Due date: Wednesday, October 9, 2013, 2:30 PM.

1. Design an algorithm that finds a topological ordering of a directed acyclic graph, or determines that the directed graph has a cycle. (But the algorithm need not list the nodes of the cycle.)
   
   Specification: Let G be a directed graph with n nodes and m directed edges, given to you in edge list form. For simplicity, assume that the names of the nodes are the integers from 1 to n, and that you know, in advance, the value of n.
   
   The output must be a list of the nodes of G in a topological order, or a message stating that G has a cycle. or a message explicitly stating that there is a cycle. For full credit, the time complexity of your algorithm must be Θ(n+m).
   
   You can explain the algorithm in whatever manner you deem appropriate, subject to the condition that the graduate assistant can understand it without too much stress. It should be clear what data structures you are using. Statements (in plain English) explaining what each array (or whatever) is for are especially welcome.
   
   You should also explain the time complexity of your algorithm. If the description of your algorithm is not easy enough to understand, it could be graded as wrong, even if it is right.
   
   Sample input file:
   2 3
   6 5
   3 5
   1 6
   1 2
   3 4
   6 3
   
   Possible output file for that input:
   1 6 2 3 5 4
   
   
2. Design an algorithm which computes the number of non-empty monotone increasing subsequences of a finite sequence of distinct numbers.
   For example, if the input sequence is 2, 5, 1, 7 then the output is 9, because there are exactly nine non-empty monotone increasing subsequences, namely:
   1. 2
   2. 2,5
   3. 2,5,7
   4. 2,7
   5. 5
   6. 5,7
   7. 1
   8. 1,7
   9. 7
   Your algorithm should use dynamic programming. Be sure to identify the subproblems in your explanation.
   
   I used my algorithm to work out some larger instances. I did these by hand. I double-checked my calculations, but I could have made an error.
   
   1. Input: 6,3,7,1,4,9,2,5,8: Output: 48
   2. Input: 5,1,8,6,4,9,3,5,2: Output: 31
   3. Input: 9,8,7,6,5,4,3,2,1: Output: 9
   4. Input: 1,2,3,4,5,6,7,8,9: Output: 511