CSE 417 Homework 2, Winter 2011

Do this assignment independently. Submit your answers to items 1, 2, 4, 5, and 6 on paper at the beginning of class on January 19. Submit your code (for item 3) via the Catalyst CollectIt dropbox by 2:20 PM on January 19.
  1. (10 points). In Kleinberg and Tardos, Chapter 3, Exercise 1, except that you should give a list of the set of topological orderings, rather than just the number of them.
  2. (20 points). In Kleinberg and Tardos, Chapter 3, Exercise 2.
  3. (30 points). Develop an implementation of your algorithm of the previous problem, using either Java (version 6). or Python 3.1. Starter code for both languages is available, along with several test cases. (The starter code reads in a sample graph and builds a representation of it in memory.) The adjacency list representation is used in BOTH the input and the RAM representation. Java starter code. Python starter code.
  4. (20 points). In Kleinberg and Tardos, Chapter 3, Exercise 4.
  5. (10 points). In Kleinberg and Tardos, Chapter 3, Exercise 5.
  6. (10 points). In Kleinberg and Tardos, Chapter 3, Exercise 6.