## Assignments

• Problem Set 1 - Due Tues, Jan 17 [PDF]
• Problem Set 2 - Due Tues, Jan 24 [PDF]
• Problem Set 3 - Due Tues, Jan 31 [PDF]
• Problem Set 4 - Due Tues, Feb 7 [PDF]
• Problem Set 5 - Due Tues, Feb 14 [PDF]
• Problem Set 6 - Due Tues, Feb 21 [PDF]
• Problem Set 7 - Due Tues, Feb 28 [PDF]
• Problem Set 8 - Due Tues, March 20 [PDF]
• Problem Set 9 - Due Tues, March 27 [PDF]
• Problem Set 10 - Due Tues, April 3 [PDF]
Note: No new challenge problems this week -- it's make-up work week: turn in any that you hadn't done from problem sets 4-10 for half credit!
• Problem Set 11 - Due Tues, April 10 [PDF]
• Challenge Problem - Due Tues, April 24 [PDF]
Some sample graphs for testing (these aren't sample inputs for the program, since it's missing the first line with the solution criteria):
• Sample input from problem handout: challenge-sample.in
• Medium input based on real map: challenge-med.in (note: this covers approximately this area of Greensboro) [Updated 4/20: Now a single connected component.]
• Large input based on real map: challenge-large.in (note: this covers approximately this area of Greensboro) [Updated 4/20: Now a single connected component.]
Actual inputs (with constraints):
• challenge-med1.in - medium sized input (approximately 500 nodes) with "perfect" (100%) constraint. A good solution has 5 stations with worst distance 78.
• challenge-med2.in - medium sized input (approximately 500 nodes) with "good" (80%) constraint. A good solution has 4 stations with worst distance 103.
• challenge-large1.in - large input (approximately 5000 nodes) with "perfect" (100%) constraint. A good solution has 19 stations with worst distance 178. [Update: Running for a longer time, I found a solution with 17 stations and max distance 177.]
• challenge-large2.in - large input (approximately 5000 nodes) with "good" (80%) constraint. A good solution has 20 stations with worst distance 273. [Update: Running for a longer time, I found a solution with 16 stations and max distance 270.]
Also available: Timing Code examples
Testing data for ninja point competition - based on maps of Winston-Salem: