My PhD student Abhinav Aggarwal wrote a really nice blog post on a problem I assigned on a final exam. This was a kind of interesting dynamic programming problem about playing a simple game against an opponent (who is not always playing optimally). I don’t usually like to give out solutions to problems that I write, but in this case, Abhinav’s writeup is so nice that I’ll point to it here.
Filed under: Uncategorized | Tags: distributed computing, game theory, teaching
You’ve got 3 hours to cover the most interesting and important results in distributed computing. Your audience is eager, young scientists in diverse disciplines: biology, economics, physics, sociology, chemistry, math, computer science. What do you cover? 
Below is my list. It’s definitely biased to theory. I hope I’m not making anyone mad by excluding something important. Well actually, I hope I am making you mad enough to leave a comment below 🙂
- Form impacts Function. Network structure can have significant effect on algorithms running over the network. There are two problems I’m thinking of covering here: 1) routing (i.e. Kleinberg’s small world paper); and 2) graph coloring. I like both of these problems because they are easily motivated and have ties to human experiments (Milgram’s experiment for routing, and this experimental paper in Science for graph coloring). Kleinberg’s result is easy and fun to teach. I need to do more research on distributed graph coloring to determine which results are most elegant and easiest to present.
- Anarchy is Inefficient. This segment will cover algorithmic game theory. “Inefficient” has two meanings: 1) computational inefficiency of computing a Nash equilbrium, and 2) social welfare inefficiency in terms of price of anarchy. I’ll also take about ways to get around this inefficiency: cheap talk, the billboard model, mediators and general mechanism design.
- Solidarity enables Resilience. Distributed systems can be robust to both internal and external perturbations. I plan to start with Von Neumann’s seminal paper and follow up work (by Nick Pippenger, among others), and follow with work on consensus and secure multiparty computation. Finally, I’ll tie back to game theory by discussing connections between game theory and secure multiparty computation (of course I’ll mention the Beet Farmers).
 Full disclosure: this problem is not completely hypothetical. I’m doing some lectures at the Santa Fe Institute summer school this summer.
This is what I have been reduced to:
“Let P (x), Q(x), R(x), S (x, y) be the predicates, “x is a true dungeon master”, “x has sex appeal”, “x is a wood-elf ”, “x is a friend to y”. Translate the following statements into predicate logic.
• A true dungeon master is a friend to all wood-elves
• Only true dungeon masters have sex appeal
• Bob is not a friend to some wood-elf
Prove from the statements that Bob does not have sex appeal.”
I’m not sure when it happened, but for at least several years it has been the case that solutions for the problems in any good textbook can be found somewhere on the Internet. When I first started teaching, my homework sets were usually a combination of easier problems from the text book and harder problems that I made up. These days, even for the easy problems, I can’t really assign anything from a text book.
Definitely the ubiquity of solutions to written hw problems has its downsides. It has made my job a little bit harder, but this hasn’t been a big problem really. The major downside is that there some very good problems that students are missing out on. For example, I recently covered the proof that square root of 2 is irrational in my mathematical foundations of computer science class. A great hw problem to ask students after they see this proof is to prove that square root of 3 is irrational. However, I really don’t feel it is fair to assign this hw problem in a large class where certainly at least one student will look up the solution on the Internet.
I’m curious how other lecturers are dealing with this issue, and how students feel about it. Should we be trying harder to hide the solutions to good hw problems? Should we plant “fake” solutions on the web? What happens when you google “dungeon master” and “sex appeal”? (P.S. Hello to my CS261 students!)
When I first started as a professor, I felt that what students needed to do well in a class, above all else, was precise, error-free lectures, and lot’s of practice doing problems. Based on this ideas, I did most of my lectures from slides that I had very carefully prepared before hand, and gave the class lots and lots of problems to solve. This actually worked pretty well for a while – I got great feedback from students, was nominated for some teaching awards, and enjoyed the experience.
However, eventually I realized that my lectures were not as exciting as they could be. I read some articles on Tomorrows Professor listserv, that bemoaned the use of pre-prepared slides. They claimed that extensive use of slides makes lectures completely predictable and unresponsive. This semester, as an experiment, I stopped using slides, or even lecture notes of any kind. I memorize enough of the lecture so that I can be sure to use terminology that is reasonably close to the textbook and to the notes I’ve posted from previous years of the class.
How have things changed? I find teaching a more exciting and sometimes scary activity. Also, it’s easier for me to respond to feedback from the class as a whole about e.g. whether it’s worthwhile to go over an example of a particular concept. When a student asks an interesting question, I definitely spend more time than I used to on exploring the answer in depth. For me, at least, the lectures are a lot more fun and challenging. From the feedback I’m getting from students so far, they also seem to be more engaged. Do I make more mistakes in lecture? Definitely. However, I feel that I’m slowly getting better at checking things on the fly and am making fewer mistakes now than when I started this.
How has this changed my teaching philosophy? I realize now that a big part of education is inspiration, motivation, and a kind of educational “entertainment”. I also realize that it’s just much more engrossing and memorable to watch someone walk carefully across a rope in the air, than to trudge across a line on the floor that was drawn before the performance even began!