CSC 495: Problem Solving and Programming
Navigation
Class Home
Syllabus
Handouts
Assignments
Ninja Points
Class Code
Solutions
More Information

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: