University of Nevada Las Vegas
Howard R. Hughes College of Engineering
School of Computer Science
My Home Page

CSC 477/677 Assignment 5

Due date: Thursday, March 13, 2008, 4:00 PM.

All assignments must be handwritten (not typed or printed from a computer file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper. Write your name on each sheet, and do not fold the pages or crimp the corners. (You may use a paper clip or a staple.)
Turn the pages in to me on or before the due date.
  1. Write an algorithm which topologically sorts a directed graph, or else discovers that it has a cycle.
    The input of your algorithm is a file. The first line is of the file is n, the number of nodes. Each node is an integer from 1 to n. Every other line is an edge. In this graph, for example, there are 8 nodes, and there are 8 edges, including an edge from 1 to 7 and an edge from an edge from 4 to 3, for example.
    Your program must be hand written using code or pseudo code, and should run in O(n+m) time, where m is the number of edges.
  2. Work Exercise 24.1-4 on page 591 of your textbook.
  3. Work Exercise 24.2-1 on page 594 of your textbook.
  4. Work Exercise 24.3-1 on page 600 of your textbook.
  5. Work Exercise 25.1-1 on page 627 of your textbook.

Back to Course Page