• Sit with your project group!

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• General project approaches.
• Time to work on projects and ask questions.

Preliminaries

Admin

• If you find that you have to leave early for Thanksgiving break, please let me know. I hope that you will have much to give thanks for!

Upcoming Work

• Homework: Phase 2 of project due tonight. (Yes, a few of you need extra time. If that's the case, let me know.)
• Reading for Wednesday: Nothing; we're continuing with hash tables

Extra Credit

Academic

• Learning from Alums, Today at 2:15: Alex Cohn '11 (in person)
• TEC Extras TODAY at 4:15 in Burling: Emma Lange on UI/UX on the Libraries' Web Sites
• Epic talk, Tuesday, 7:00 pm, CLS
• CS Extras Thursday the 4th: Summer Opportunities in CS
  • Rescheduled from today

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music. (No KDIC for Sam)
• Ezra's Radio show Thursdays at midnight. Radio melodrama. (Not this week)
• Charlie's Friday Night "War in Animated Film" ExCo. (Not this week)
• Dance show 4-5.
• One acts 6-7.
• Lots of basketball games.

Questions

General project approaches

Here's a sample ten-team round-robin schedule. Based on algorithm taken from Wikipedia page on round-robin tournaments, although generated using a slightly different pattern.

Day 1: T0 vs. T9, T1 vs. T8, T2 vs. T7, T3 vs. T6, T4 vs. T5
Day 2: T0 vs. T8, T9 vs. T7, T1 vs. T6, T2 vs. T5, T3 vs. T4
Day 3: T0 vs. T7, T8 vs. T6, T9 vs. T5, T1 vs. T4, T2 vs. T3
Day 4: T0 vs. T6, T7 vs. T5, T8 vs. T4, T9 vs. T3, T1 vs. T2
Day 5: T0 vs. T5, T6 vs. T4, T7 vs. T3, T8 vs. T2, T9 vs. T1
Day 6: T0 vs. T4, T5 vs. T3, T6 vs. T2, T7 vs. T1, T8 vs. T9
Day 7: T0 vs. T3, T4 vs. T2, T5 vs. T1, T6 vs. T4, T7 vs. T8
Day 8: T0 vs. T2, T3 vs. T1, T4 vs. T9, T5 vs. T3, T6 vs. T7
Day 9: T0 vs. T1, T2 vs. T9, T3 vs. T8, T4 vs. T2, T5 vs. T6

Two sets of this is a full schedule. (In the first set, we treat the left member of each pairing as the home team; in the second we treat the right member of each pairing as the home team.)

What can we do to make this meet the other criteria?

• We have 10! different assignments of real teams to numbered teams. (Okay, many effectively lead to the same pairings, but it's still a lot.)
• We have 18! (or 16!) different assignments of real dates to numbered dates.
• So we have lots of options.
• We can start by randomly assigning or naively assigning.
• Once we've assigned,
  • We can randomly permute assignments of days or teams.
  • We can sensibly permute assignments of days or teams (e.g., move the pairings with the longest distances to the correct weeks).
• We can mix these techniques, keeping track of the "best" schedules we've seen so far.

Reaching this stage

• How did I reach this stage of the algorithm design process?
• I picked a simpler problem to start with.
  
  • Dealing with days with some teams who can play and some who can't play seemed hard. I chose to assume that everyone can play every week.
• I started by asking myself how to build a few simple schedules by hand, and quickly realized that you need care to even make a simple schedule with no restrictions.
• I spent awhile looking at ways to draw/model schedules to help me generate them automatically.
• I could not generate a round-robin algorithm in the limited time I had available for the problem, so I looked one up online.

Where to go next?

If I were implementing the project, I'd probably begin with a really simple approach: I would just randomly assign everything, have a program "assess" the schedule and print out in what ways the schedule failed, and then think about how I'd adjust the schedule by hand. I'd expect to learn some things doing so.

But I tend to think ahead, so I expect that my algorithm would look something like the following.

• Step one: Randomly assign teams.
• Step two: Compute a "fitness" for each row (the number of teams that have to travel less than N miles).
• Step three: Compute a "fitness" for an unordered schedule (the number of rows in which all the teams travel less than N miles).
• Step four: Randomly permute the team assignment until I have an unordered schedule fitness that is at least the number of low-travel days in the schedule. (Is this necessary? That's why I need code.)
• Step five: Randomly assign all the high-fitness days to the low-travel days.
• Step six: Randomly assign all of the remaining days to the other days.
• Step seven: Check other criteria; randomly permute until we meet those criteria.

But I'd learn things along the way, so the process might change significantly. I might also find that steps four and seven take too long, and would then start to think about potential improvements.

Time to work on projects and ask additional questions

If you can't get it to work for all ten teams, see if it works for four and then six and then ....