Navigation

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 makeup work week: turn in any that you hadn't done from problem sets 410 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: challengesample.in
 Medium input based on real map: challengemed.in (note: this covers approximately this area of Greensboro) [Updated 4/20: Now a single connected component.]
 Large input based on real map: challengelarge.in (note: this covers approximately this area of Greensboro) [Updated 4/20: Now a single connected component.]
Actual inputs (with constraints):
 challengemed1.in  medium sized input (approximately 500 nodes) with "perfect" (100%) constraint. A good solution has 5 stations with worst distance 78.
 challengemed2.in  medium sized input (approximately 500 nodes) with "good" (80%) constraint. A good solution has 4 stations with worst distance 103.
 challengelarge1.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.]
 challengelarge2.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 WinstonSalem:
