The Knapsack Problem and Other Problems

This week I put together a small trial-run version of a problem-based lesson. I’ll be doing a larger problem-based lesson in a couple weeks, and did this for a bit of practice. Boy, did I learn a lot. The general plan was to introduce the problem, talk about the assumptions we could make, have the students work in pairs to find a solution, then compare/discuss solutions and what they learned. I chose this particular optimization problem because it’s both easy to understand and can be solved in a variety of ways. There are also numerous versions of the problem, based on the assumptions you make.

The problem statement:

The Knapsack Problem

The first block was pretty rough, which was my fault. I’m used to thinking about the content of a lesson, and I was pretty excited to talk about the various versions (unbounded, where each item can be used multiple times; 0-1, where each item can be used at most once; and fractional, where fractional items can be used) and various solutions (greedy, random, dynamic programming, search). What I’m not used to thinking about are class logistics. Things like: how to pair the kids, that when you tell them to get whiteboards you also need to tell them to get markers and erasers, that I need to give all the instructions twice before I have anyone move, etc. I made rookie mistakes, like asking them to turn in their whiteboards to me so I could review what they had done, then asking them questions about their solutions (which they no longer had in front of them). Next time I’ll be sure to review my lesson with Mrs. Trauthwein beforehand, to avoid these kind of mistakes.

Second block went much more smoothly. They are usually the most engaged class to begin with, and by correcting my mistakes from the first block, we had time to cover a lot more ground. One group even tackled the fractional version of the problem without me mentioning it. Someone asked how many possible combinations of items there were, so we used a decision tree to discover that there are at most 2^n solutions for the 0-1 problem with n items. This tied in nicely with their distributed practice work, which involved using a tree to represent independent probabilistic outcomes.

Third block started well, but quickly became a total disaster. Some students sitting close to the front would not stop talking, despite my best efforts to be stern. Other students were visibly upset with the interruptions, and started mentally checking out too. The pairwork went fairly well considering, but the discussion afterward never got going, as the class was in chaos. Finally, in frustration, I told the class to get out their homework and work on it for the rest of the class.

Several detentions resulted, but one student was particularly out of control. Talking over other students who were trying to answer my prompts, and proclaiming several times “this is stupid, I don’t get this, this is boring”. I’m ashamed to admit, after trying to quiet this student every way I knew how, I snapped at them: “shut up!”, which I immediately regretted. It had the desired effect, but is wholly inappropriate, and I definitely can’t let that happen again.

By the end, I was both exhausted and annoyed from having to constantly yell over the students to get them to be quiet, only to lose them again after a minute. Now (a few days later) I’m mostly embarrassed that things got that out of hand, and trying to figure out how to handle such a situation in the future. I realize I’m not responsible for how the kids act, but I am responsible for how I respond to these situations, and hopefully next time I’ll handle things better!


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.

2 Responses to The Knapsack Problem and Other Problems

  1. Megan Peck says:

    Wow, sorry you had such a rough time with this. I think that was a very ambitious lesson, especially for a “practice” lesson! Last year I made the mistake of picking a problem that was too easy–they all figured it out in like 4 minutes and were then bored. I’m really impressed with the material you’re getting into with them–for instance, the decision tree discussion you had is awesome.

    I think you just have to learn the class logistics from experience. I’m sure every teacher will tell you that they found out what works through some failed attempts. I’m also guessing that the students aren’t going to hold it against you. I bet they’ll be excited for your next lesson, and you’ll be that much more prepared.

    I wasn’t giving a lesson this week, but the students were absolutely buzzing and a bit out of control. Maybe we can discuss some techniques for reigning in the students when they’re like this. How do you redirect a class that’s ramped up and losing focus?

  2. I told him the same thing Megan. We have all been there and last week was a particularly stressful week where the students were more high strung than normal.

    I love the types of questions Drew is doing. He is pushing the envelope and getting students to think on levels they normally wouldn’t attempt before.

    Deep breaths, regroup and get back on the horse! Its all good!

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s