Coloring

On November 10th I gave my problem-based lesson about graph coloring. My goal was to get the students to think about a concrete problem (coloring a map) and then abstract it and make conjectures, trying to either prove their conjecture or, more likely, find a counter-example to disprove it.

Example: Coloring a map with five regions.

Example: Coloring a map with five regions.

The goal of the coloring problem is to color the regions of a map with as few different colors as possible such that no two neighboring regions share the same color. I chose this problem because, while it requires abstract and logical thinking, it doesn’t require any arithmetic. Part of my experience with the Knapsack Problem Lesson was that the students often got confused when/what to add/subtract/multiply. I had originally intended to talk about the Traveling Salesperson Problem, but figured they would get lost figuring out distances and not get a chance to think about the optimization problem itself.

The first block went pretty well, despite having less time than the other blocks due to a Veteran’s Day assembly that morning. The students grasped the idea almost immediately, and for once I didn’t have anyone ask: “what are we supposed to do” when I handed out the maps to be colored. I tried to be a bit mysterious about how many colors they would need to color the map, which frustrated some, who wanted to know if they were “doing it right”. Most students managed to color the map with either four or five colors. As for abstracting the map into a graph, the students seemed adept at adapting the coloring to the graph, but struggled generating a graph from a map. In retrospect, I wish I would have included more problems on the second worksheet that involved constructing graphs from a given map, as this was one of the main ideas I was trying to drive home (creating an abstract model of a concrete problem).

The second block really knocked this out of the park. In this past, second block has always seemed the most engaged, and this was certainly true here. I had a grant observer and photographer in the room, in addition to the usual cohort of teachers and paras. The students were amazingly focused considering the five adults roaming about. In fact, they blazed through my prepared lesson with almost 40 minutes to spare, so I had the pleasure of winging it. I’m not being sarcastic there, as it was a lot of fun. We worked on the extra credit problem (proving it was impossible to color the map with only three colors) as a class and came up with an informal proof using the state of Kentucky. The students correctly observed that any region surrounded by an odd number of neighbors in a cycle would require four colors, which certainly impressed me. We also worked on constructing graphs from maps, and talked about some of the history and applications of graph theory.

Third block, as is so often the case, had discipline issues. Keeping the kids on task was the usual challenge, and putting them into groups was a definite mistake. At the prompting of my teacher, we aborted the group work and made them work on the second worksheet individually in silence. There wasn’t a lot of time for discussion after dealing with that, but I’m not convinced it would have been constructive given the mood in the room. I think in the future I’ll have to consider lessons that don’t involve group work for this class, because it has been a fiasco every time.

That said, looking over the worksheets after class, I was pleased with the performance of the students. In my interactions while they worked on the second worksheet, I felt like they were thinking critically about the notion of conjectures and counter-examples. The worksheets turned in by the third block students were almost uniformly high quality, demonstrating there is no shortage of ability in that class.

Several students that normally don’t engage were thinking very hard about how to color the map, and I was happy to see that they employed several approaches to solving it, unprompted by myself or the other teachers. Many planned out their colors with a pencil before committing to the crayons. I heard one student explaining to another her strategy on reusing colors. Some said they started in the east because it was more complicated and they didn’t want to get stuck.

I’ve learned that trying to tackle “real-world” problems in one class is hard, even with block scheduling, due to the amount of background knowledge required to solve them. This is especially true with the computational problems I’m presenting, which at the very least require arithmetic that is at the edge of the students’ comfort zone. I feel like avoiding that distraction with this problem was the right decision, and I’ll look for future lessons that are similar in this respect. As always, I’m immensely grateful to my teacher for letting me present stuff that is not even remotely related to her curriculum (I try to tie it in when I see the opportunity, but that isn’t my primary goal) and for teaching me the fine art of managing teenagers.

Advertisements

About Andrew Farmer

I am a PhD student in Computer Science at the University of Kansas. I'm interested in functional programming languages, compilers, and language transformation tools.
This entry was posted in 2011-2012 GK12, Uncategorized. Bookmark the permalink.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s