As teachers, we are continually faced with the chicken-egg dilemma. Beginning computer scientists need to start with small, manageable problems in order develop foundational skills. However, these toy applications are not always engaging to students and may not appear relevant to the problems
they face in their everyday lives.
I was at a meeting at Facebook this summer and was struck by the enormity of scale that they deal with. Talking to students about how they use Facebook, and then expanding into a general discussion about how to organize and search MASSIVE amounts of data is an interesting and highly relevant exercise. Interesting facts I gleaned from the meeting:
* Facebook is the most popular Web site, with more than 700 billion minutes spent on Facebook every month by more than 500 million users. That’s more time spent than the next six most popular Web sites combined.
* There are more than 8 billion action events occurring each day on Facebook, including roughly 100 million photo uploads.
* If you graphed the social network defined by Facebook, there would be more than 500 million nodes (people and groups) and more than 80 billion edges (friend relationships and group memberships).
I found one tidbit especially interesting and have already incorporated it into an assignment. When you enter text in a Facebook search box, you may notice that it starts showing possible matches immediately, starting with ranked items that match the first character you type, then refining them as you enter more characters. Given that the number of possible search matches is HUGE, it is important to do this search and refinement efficiently in order to appear instantaneous to the user. It turns out, they simply utilize two binary searches – one binary search through the sorted list of potential matches to find the first matching one, then a second binary search to find the last match. Simple, fast, and understandable to a CS1 student.
Dave Reed
CSTA Board of Directors