Class Notes (806,817)
Canada (492,453)
CSCA67H3 (56)
Lecture 6

Week 6 - Topological Sort.pdf

6 Pages
Unlock Document

University of Toronto Scarborough
Computer Science
Anna Bretscher

Topological Orderings Problem. Your company needs a new website. There will be many pages with links between them. The public is itching to view your website so you want to publish each page as soon as it is ready. Caveat: You don’t want any broken links. Q. What order do you create the pages in? Example. Let W = fw ;w1;w 2w ;3 ;4 ;w5g b6 th7 set of webpages. Suppose that: ▯ page w 1inks to pages fw ;2 ;w3;w 6, 7 ▯ pages w 3nd w li4k to page w , 8 ▯ pages w 2nd w li7k to page w an5 ▯ page w 6inks to pages w a2d w . 4 Q. In order that there are no broken links, in which order should the pages be written? A. 1 Q. How can we think of this problem as a graph? A. Draw the graph. Q. In this case there is an acceptable ordering. If there were no acceptable ordering, what property would the graph have? A. 2 Q. What do you notice about w and 5 w 8 5 6 A. 7 These types of vertices are called sinks. 4 1 8 Q. What do you notice about w ? 1 3 2 A. These types of vertices are called sources. Q. Which type of vertices (webpages) should be written first? A. Q. If webpages w and w are written first, imagine deleting them 8 5 from the graph. What do you notice about w ;w ;w 4nd w2? 3 7 A.
More Less

Related notes for CSCA67H3

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.