Monthly Archives: December 2010

a Christmas brain teaser

When finding some math worksheets to occupy my six year old daughter on her day off of school, I discovered a Christmas brain teaser for elementary students (in pdf format):

Find a route [between twelve cities] for Santa to follow that is as short as possible. After you have found a route, compare it to others to see if they found a shorter route.

Of course, you will immediately recognize this as the TSP.  The “solution” is amusing:

Try to view this question as open-ended, or your student(s) might be working on it for days. …And if someone figures out the best answer to this question, please let me know and I’ll add it here.

Finding the optimal solution to a twelve city TSP is indeed pretty hard.  So hard, in fact, that the folks at math-drills.com couldn’t find the solution.  I have confidence that my readers can find the optimal solution in less than a day.  But please spend Christmas with your families enjoying holiday cheer.

Happy holidays!


Christmas cookies (and a recipe)

Just for kicks, I decided to take a few pictures of my Christmas cookies this year.  I usually try to make cookies efficiently.  Often, that means bar cookies, since they are uber-efficient (but not pretty).  But this year, I made real cookies that required molding, rolling, cutting, and pressing.  I didn’t use a constraint programming approach, but I did enlist the help of my two daughters to make and decorate the cookies.  My cookies this year include:

My cookie tasters (i.e., my daughters) loved the new almond crescent cookie recipe that we came up with.  I posted it here.  There are some obvious substitutions that will probably work, but I’ll let you use your imagination in that department.  I wrote this recipe from memory, so if I there is an mistake, let me know and I’ll fix it.

Almond crescents

Ingredients:

  1. 3/4 cup ground almonds
  2. 1 3/4 cups flour
  3. 1/4 teaspoon salt
  4. 1/3 cup brown sugar
  5. 1 stick (1/2 cup) Earth Balance spread
  6. 1/3 cup canola oil
  7. 1 teaspoon almond extract
  8. 1/2 teaspoon vanilla extract
  9. Soymilk as needed
  10. 1 cup powdered sugar
  11. cinnamon to taste

Instructions:

  1. Preheat the oven to 375 degrees Fahrenheit.
  2. Mix the dry ingredients (#1-4).  Cut the dry ingredients with the Earth Balance until it resembles crumbs.
  3. Add the oil, extracts, and soymilk and stir until the mixture more or less sticks together.
  4. Take tablespoon-sized amounts of dough and form into crescents.  They don’t rise much, so you can put them close together on the cookie pan.
  5. Bake for 14-16 minutes.  Don’t let these cookies brown. While they are baking, mix the powdered sugar and the cinnamon (I used about 3 big shakes, but more would be better) in a bowl.
  6. Let the cookies cool on the pan until they are warm.  Remove the cookies and cover them with the powdered sugar mixture.

Happy holidays!

Almond crescents

Almond crescents. My kids ate most of them before I was able to take a picture.

Peanut butter blossoms

Peanut butter blossoms

Chocolate spritz cookies

Chocolate spritz cookies

Kolacky, Kolache, Kolachy, Kolach

Kolacky cookies


not a Latin square

I decided to sew a quick Advent calendar earlier in December to ration candy consumption in the house.  Advent calendars have 24 pockets/doors/hooks/etc. for accessing Christmas treats (I prefer chocolate).  I sewed my Advent with five colors of felt.  When I was done, I looked at it and immediately thought that I should have added a 25th pocket, arranged the squares in a five-by-five grid, and assigned the colors according to a Latin square.  Oh well. That is a project for another year.

Advent calendar

The advent calendar that should have been the first Latin square Advent calendar


RIP delicious

DeliciousI am overdue for another post on teaching with technology.  This post is about the social bookmarking tool delicious (or Del.icio.us as you may know it).  Yahoo! announced that they are shutting down delicious.  I decided to write my review anyway, since this review is mainly about social bookmarking tools, which can certainly exist whether or not delicious does.

I gave delicious a test drive this past year.  I still am not sure what social bookmarking really is and how it can be effectively used, but I loved being able to save all of my bookmarks online and access them on whatever computer I am using.  Bookmarks are tagged rather than put in folders (it’s like gmail’s labels vs. every other email client’s folders).  Tag bundles can be used to arbitrarily group tags together under one umbrella.  All of this is quite handy. Eventually, I found myself using delicious on my browser rather than my bookmarks folder.  It was just easy to organize and access bookmarks than using my browser.  Ultimately, I would say that delicious offers a mixture of three benefits that people can take advantage of to varying degrees:

  1. Bookmarks are available online and are always available.
  2. Bookmarks can be shared with others (and are shared with others whether you like it or not).
  3. Bookmarks are tagged instead of put in folders, which improves accessibility.

The only problem with delicious is that #1 and #2 are at odds with one another.  The tags and bookmarks on delicious are public, which means that everyone can see who else tagged the same bookmarks within delicious, and outsiders can view the list of bookmarks that I’ve tagged.  I’ll admit, that part of the social networking aspect is a bit creepy.  However, it was easy enough to make bookmarks private, which essentially solves that problem.  However, the tags for the bookmarks are still public (the solution here is to use inconspicuous tag names).  I was annoyed that Yahoo! announces my bookmarks to everyone and their mother on Yahoo! sites.  This meant that my relatives occasionally are perplexed by my choice of tags.  I never figured out how to manage the privacy settings on delicious, and this comes from someone who was able to master Facebook’s complicated and ever-changing privacy settings.  Delicious just didn’t have an easy and transparent way to manage privacy settings.

I can’t see too many uses for delicious in the classroom, unless I was teaching a course in which we needed to find many links to content specific material.  If I were doing so, Delicious makes it easy to add others to my network (but in reality, I’ve added two people).  We can create a common tag like the rubric for the course in order to find one other’s bookmarks.  I had been hoping to use Delicious in a course I developed on algorithm analysis, but alas, the class was canceled and I wasn’t able to try this.

In retrospect, I found that benefits #1 and #3 are a big deal to me.  I am surprised by that.  But then again, browser bookmarks haven’t really changed since I started using browsers. They could really use some revamping to be useful, and a tool that offers serious benefits in that department could make a really big splash.  Despite the demise of delicious, I am hopeful that there will be better bookmarking options in the future.

In the end, I am not surprised that Delicious is being shut down.  It’s a handy little tool that I will miss, but it doesn’t offer enough to revolutionize how I do things online, and it’s certainly not a game changer with respect to social networking.  The conflict between accessibility and privacy was always a concern for me, and maybe that was an issue for others.  But I do hope that a new tool with better features replaces it.

Do you use delicious?  How do you save and organize your bookmarks?

Related posts:


operations research for six year olds?

I have been meaning to sign my six year-old daughter up for an optional science project at her elementary school, but they need a science project topic up front. Having been a judge for the Illinois Junior Academy of Science state science fair competition, I am familiar with what is needed at the junior high and high school levels.  Picking a topic that would interest a six year old is a new challenge for me.  And personally, I want to do something more exciting than testing dice probabilities or creating histograms of the number of colors in bags of M&Ms.  I am looking to my wonderful readers for inspiration.  Please leave a comment or email me with your ideas. Thank you!


data entry error leads to BCS rank reversals

A score was incorrectly added to a database that is used to rank football teams in the BCS system, which led to two rank reversals in the rankings (between the #10 and #11 teams and between the #17 and #18 teams).  Many sports journalists are talking about all of the implications of the error (What if the error affected the top two ranked teams?!?).  Only one of the six data sources is available publicly, so it is not clear the extent of the data inaccuracies or any errors in the actual BCS formula.

What is interesting is that this is being reported as a math error, but from what I have read, it is a data entry error.  I was actually a little disappointed when I read about what happened, because I initially thought that the BCS algorithm was incorrectly used (it wasn’t, as far as anyone seems to know, but there is room for improvement there).

I have three thoughts:

  • Sports journalists apparently do not understand the different between mathematical formulas and the data used to populate those formulas. Throwing out the BCS formula for ranking teams would not eliminate this type of error, since data from experts (votes, points awarded, etc.) could be incorrectly tabulated and entered into a database.  Such errors would be more difficult to spot than a missing score, since they would not be obvious.
  • Having incorrect, missing, or inaccurate data is a part of life for many of us who analyze data. In every other type of industry or sector, people make big decisions with inaccurate and incomplete information, and life apparently goes on.  When is the BCS data “good enough?” In NCAA football, accurate and complete data should be available for the BCS formula, and as a football fan, I do hope that every effort is made to collect good data.  One missing data point isn’t evidence that there is a systematic problem.  On the contrary, it sounds like the data set is pretty accurate and complete.
  • How can we come to reasonable conclusions about the BCS system when the journalists who are supposed to inform us get the important stuff wrong?  This story has become a non-story for me, as I have been reading articles written by people who are not really responding to the issue at hand (one inaccurate data point).  There are surely other issues with the BCS system (such as not enough oversight), but replacing the BCS formula with another system would not necessarily imply that there would be more oversight.

The secrecy of the BCS formula seems to be one of the reasons for its unpopularity, yet it produces rankings that are virtually identical to other ranking systems.  Is the bias against BCS a function of how most people don’t understand math well?  If the BCS formula was more transparent, would that even be a good thing? Do you consider a single data error a big deal?

But I could be wrong, of course.

Related posts:


holiday reading

It’s that time of year when I actually have some free time to read books.  I read all sorts of books, although I’ve written before about how my reading choices are mostly limited by the audiobook availability at my local library.  I’ve read a few good books in the past twelve months, most of which have nothing to do with OR, but I will share them with you in case you are looking for some books to read this coming year.  Not all of the books are new, but they are new to me.  They are in no particular order.

The Flaw of Averages by Sam Savage.  This is a nifty book about probability distributions and uncertainty that uses intuitive explanations rather than jargon.  The book’s premise is to explain why the entire distribution of uncertain outcomes is needed for decision making rather than just the expected value.  Savage moves beyond merely critisizing expected values in later chapters, where he steps through some key issues in the financial crisis.  This is a fun book to read that I highly recommend to students.

Love is a Mix Tape: Life and Loss, One Song at a Time by Rob Sheffield.  This is one of the two best memoirs I have ever read (the other is The Glass Castle).  This book is written by a music writer about the relationship with his wife.  Music is used to tell the story throughout the book, and while using mix tapes certainly is a gimmick, the writing is truly top notch.  It’s hard to describe the appeal for this book; you simply must read it.  I started to tell my husband about this book, and then I forced him to listen the first audiobook, when he immediately became hooked.  I laughed, I cried, and then I made my first “mix tape” in more than a decade.  This book would be interesting to 30- and 40-somethings who enjoy alternative music, Yankees who have moved to Appalachia, or anyone who has ever wanted to be in a synth-pop duo. I truly enjoyed the narration in the audiobook (it is read by the author) and would recommend the audiobook format.

The Hunger Games Trilogy by Suzanne Collins.  These are the best science fiction books that I have read in a long, long time.  I had given up on the genre when these books drew me back in.  The trilogy takes place in the not too distant future when the US no longer exists.  Panem, a nation that consists of a capital and twelve districts, selects two teenagers from each of the districts to compete to the death on national television.  Katniss Everdeen is the main figure in the books, and she is a great role model that I easily identified with.  The story arc is told in an engaging way across three well-written books.  This trilogy has been described as the next big thing since the Twilight series, but it is in fact much better.  With a great mix of excellent story telling, suspense, violence, and romance, they would appeal to men, women, girls, and boys.  I have never read a book on the day it was released, but I found myself eagerly awaiting the final book’s release.

Friday Night Lights by HG Bissinger.  I am a huge fan of the television series, but had never read the book until my husband gave it to me for Christmas last year.  It is in my unofficial list of top ten nonfiction books that I have read.  This book was written about 20 years ago about a high school football team in West Texas.  I knew it was good when I found myself reading long passages to my husband.

Pride and Prejudice and Zombies by Seth Grahame-Smith and Jane Austen.  I know that everyone and their mother has already read this book, but I recently gave it a shot.  This may be blasphemous to some, but I found this version of the Austen classic to be an improvement upon the original.  And that’s saying a lot, since I am just not that into zombies.

Packing for Mars by Mary Roach.  This is an entertaining book about weird science inspired by the space programs–with an emphasis on weird–written by a science journalist.  Some of the tangents were a little bizarre even by my standards, but I really enjoyed reading about how life in space affects bone density, how frequently astronauts should bathe, and the gender politics in space.  This was a fun read about everything I wanted to know about the science of sending people into outer space that I wouldn’t find from conventional media.

The Road by Cormac McCarthy.  The Road takes place about a decade into a nuclear winter, when all food sources have been exhausted and the few people that are left are either thieves or cannibals or both.  The story follows a father and son trying to survive.  The father tries to teach his son about “carrying the fire” and maintaining a high level of morality, care-taking the next generation when there is apparently no future worth living.  This book is not for the faint of heart.  The sense of fragility and desperation is on every page.  It is painfully depressing, yet it is the science fiction book that I have always wanted to be written.  The NY Times review describes this book as “The road through hell, paved with desperation,” and I think that’s accurate. Yet the beauty of a father transmitting humanity to his son (the next generation) while the son transmits it back cannot be understated.  I couldn’t put this book down and read it in a few hours.

The Politician by Andrew Young.  John Edwards’s fall from grace really has been the political scandal of my adult life.  I was disgusted by how John Edwards publicly lied about the child he fathered for political gain.  The part of the scandal that most intrigued me was why someone with a wife and children would be complicit in Edwards’s lie and falsely claim to be the child’s father.  This is the book about how that happened.  I started reading this book to piece together the scandal, but then it turned into something else: an exploration of morality in the workplace.  Obviously, Young covered up the affair and while he wasn’t the one having an affair, he was complicit in it.  He falls down a slippery slope while doing his job where he eventually wrongs his family by taking part in the scandal himself.  Young of course tries to justify his actions and certainly paints himself in the best possible light.  However, at various points in the book, I tried to put myself in Young’s shoes and tried to determine when and where he went too far.  My husband is quite familiar with the scandal, and we had quite a few engaging conversations about the shades of gray in the actions taken by those surrounding John Edwards.  I enjoyed this book because it started out as a standard political memoir and then turned into much more.

The Time Traveler’s Wife by Audrey Niffenegger.  This is another book that everyone has already read except apparently me.  I resisted reading this book because I find the idea of time travel romance to be corny.  I eventually succumbed to reading the Time Traveler’s Wife when I was struggling to find good audiobooks at the library and heard that this book takes place in Chicago (my home town).  I am glad that I gave it a shot.  The Time Traveler’s Wife is part science fiction and part chick lit, and both aspects of this book are rewarding.  This book is told from two perspectives and not in chronological order, but it’s not hard to follow the story.  The author gets the tone right: this book is intriguing in a time travel paradox sense, is touching, and is funny.  I particularly appreciate that the male time-traveler actually acts and sounds like a real man rather than a chick lit characterization of a man, but I don’t know any men who have read the book to confirm this.  The appeal of this book is hard to explain, but all of the aspects of this book really work together to create a satisfying whole package.


land O links

Here are a few links for your weekend reading:


graph coloring problems over the holiday

I enjoy the holiday season.  I unashamedly celebrate Christmas, and I enjoy decorating the house for the holidays.  This year, I used graph coloring problems to help me decorate.  If you are not familiar with graph coloring, consider a graph with a set of vertices and edges.  The goal is to assign a color to each vertex such that no two connected vertices have the same color and such that the fewest number of colors are used (the chromatic number).  One application is to create maps, such as this one of the United States.

How does graph coloring relate to Christmas decorating? I’ll give you an example. I have had an intense desire for the past 17 years or so to decorate my Christmas tree using only a few, beautifully coordinated colors (like red/silver/gold or purple/silver) rather than throw on a bunch of ornaments of every color like I always do. But I’d decorate the tree OR style, by hanging exactly one ornament on each branch and requiring that adjacent branches have different colors. This in essence imposes a graph coloring problem on my tree decorating.  The chromatic number of a planar graph is 4.  I suppose that the chromatic number of a conic graph (i.e., a Christmas tree) is also four, since a conic graph can be cut along one side to become a plane.  I am not sure if the edges removed to turn the cone into a plane would be problematic, but I doubt it (graph theorists, please leave a comment!).

The reason I have never colored my Christmas tree is that I am sentimental and feel the need to hang all of my favorite ornaments on the tree, regardless of their color. With young kids who create a few new ornaments every year of various colors that don’t fit any of my Christmas tree decorating fantasies, I always thought that I would never color my Christmas tree in the near-future. Or so I thought.

This year, I bought a Christmas tree-shaped centerpiece that requires a gumdrop to be placed on the end of each branch (it is pictured below, along with my Christmas tree).  I examined the centerpiece, and noticed that all of the branches lie in a vertical line, which should allow me to use as few as two colors.  I opted for three (red, green, white), but my daughters insisted on using purple, too.  The best part was when I explained the concept to my six year old, and she was really jazzed by the extra challenge (a future graph theorist?)  When the tree was four-colored, my ~3-year old added a few yellow and orange gumdrops to some of the extra branches, so now the tree has six colors.  But I think there’s a good chance that she will eat the yellow and orange gumdrops at some point, bringing the tree back to four colors as we had originally intended.

On a related note, I once had a conversation about vertex coloring over a bag of Valentine M&Ms.  Valentine M&Ms have four colors whereas holiday M&Ms have three colors, and if you’re eating M&Ms with another nerd, it eventually leads to a discussion of the types of graphs whose chromatic numbers are equal to the number of M&M colors.  I suppose this is the type of problem one nerd has if they eat candy with another nerd, but it’s a good problem to have.

This blog post contributes to the INFORMS monthly blogging theme.  Look for the INFORMS blog to summarize the blogs at the end of the month.

What are your favorite graph coloring results?


Related posts:


OR bloggers to begin a monthly blog-off

During the first “Tweet-up” at the INFORMS Annual Meeting, we tossed around a few blogging ideas.  We decided to try something new: all OR bloggers are invited to write one post about a monthly theme.  The theme will be provided by INFORMS (email your ideas!).  The first theme for the month of December is OR and the holidays.  Look for my post in the coming days as well as posts by all of your favorite OR bloggers.  In the mean time, check out the official INFORMS announcement and Mike Trick’s take for more details.


Follow

Get every new post delivered to your Inbox.

Join 2,039 other followers