One last Molly post for the end of the school year. Tomorrow is her birthday and I enter that moment I have been dreading for the past thirteen years: Two teenage daughters.
Molly's 7th Grade Science teacher wanted to break her class into groups of three to work on a particular project. Each person in the class was asked to list three people they wanted to work with and one person they didn't. The teacher would partition the class so everyone wanted to work with someone else in their group and the person they didn't want to work with was not in their group.
The next day the teacher she thought the partitioning should be easy but took her many hours. One student said she should just ask a computer to find the partitioning. Molly said she needed the right algorithm. When Molly told me about it that night and asked if I could help her figure out the algorithm. I said the problem was likely "NP-complete" (since it is a variation of Exact Cover) and would have to search all the 190 million different partitions of her class of 18 into groups of 3. OK, I probably said this to get out of thinking about an algorithm but maybe Molly got just a little more understanding of P versus NP.
Bill and I are at FCRC next week. Hope to see you there.