Category Archives: Teaching & Talks

The Amazing Miss A

Via this post in Michael Trick’s Operations Research Blog, I discovered a truly mesmerizing article about teaching: The Amazing Miss A And Why We Should Care About Her. I hope you would enjoy it as much as I do.

And after you have read Michael’s post and the article, I invite you to think about CS education.

My Vote Goes to Red-Black

On Geomblog, Piotr mentioned a problem that I think many of us can share: if we really have to pick just one to teach (as in his case), do we go with 2-4 trees or red-black trees?

For the most part, the pros and cons of the two approaches are quite, urr, balanced. :P But there has been one critical issue that tilt my preference towards RB. On the surface, the issue is “augmentation”, ala CLRS chapter 14 style. But it really is about the number of rotations used during insertions and deletions…

There is a fascinating history behind this, which is summarized by Ottmann and Wood up to 1990. It all started with a design from Olivie and a swift response from Tarjan. The rest of the juicy bits, well, I offer no spoiler. This post merely needs the following fact to make sense: in the worst case, some implementations of RB need only $O(1)$ rotations during restructuring and the remaining work are color changes; some implementations need logarithmic number of rotations.

But if we can afford a logarithmic number of color changes in the worst case, isn’t it just “a matter of constants” even if we have to do a logarithmic number of rotations as well?

In many cases, the answer is indeed yes, but there is no lack of interesting cases due to augmentations that make rotations “expensive”. For a starter: see section 13.4 of Bob’s textbook, pp 570-571 in the C++ 3rd edition, where this very issue is raised and the model answer is presented. Here is a favorite example of mine: Seidel and Aargon used this to highlight why treaps are preferable to splay trees in applications like segment trees. Let’s end with one more related to this post: McCreight’s priority search trees, used as the motivating example in Ottmann and Wood, also critically rely on search trees that use only $O(1)$ number of rotations to restructure. More precisely, doing $p$ rotations yields a bound of $O(p \log n)$. See, it’s not just in the constants!

I will finish this by saying that this doesn’t imply a landslide victory for RB. Conceptually, 2-4 trees are really hard to beat! In fact, even though I would be speaking RB in my mouth, I would be thinking about 2-4 at the back of my mind! (Kind of like some foreign language speakers, no? Ten years ago I was exactly like this, haha.) And really, if we ever get to more advanced stuff like supporting finger searches, I will pick 2-4 on most but not all days. Complications… complications… :P

Exercise: To understand how a 2-4 speaker would speak in RB, what is “black-height” in the 2-4 language?

Reference: Thomas Ottmann, Derick Wood: How to Update a Balanced Binary Tree with a Constant Number of Rotations. SWAT 1990: 122-131

Course Announcement: Special Topics in Combinatorial Optimization

47-853 Special Topics in Combinatorial Optimization: Iterative Relaxation and Rounding

Time: Mondays and Wednesdays 3.30-5.30 pm from August 27 – Oct 15 2007.

Place: Room 318, GSIA (old) building

Instructors: R. Ravi and Mohit Singh

Polyhedral methods have been a powerful tool in combinatorial optimization. In this course we will study exact linear programming formulations for a variety of problems which are polynomial time solvable. In particular, we will explore the effectiveness of a new technique based on iterative augmentation in proving some traditional results. We will also examine min-max relations and efficient algorithms for these problems. Towards the end of the class, we will illustrate the original iterative rounding method that inspired these results as well as some applications to approximation algorithms.

Tentative Outline:

1. Linear Programming
2. Bipartite and general matchings
3. Trees and connectivity augmentation
4. Matroid bases, intersection of two matroids
5. Union of matroids and packing trees
6. Submodular flow minimization
7. Graph orientations, Dilworth’s and Lucchesi-Younger theorems
8. Network design and degree constraints

Grades will be based on revising and correcting already prepared preliminary scribe notes, and on one or two problem sets over the course of the class. Solving any open problem posed in class will automatically absolve you from other work!
We require all attendees to register, if only for audit.

An Idea on Theory Exam Questions

In a discussion with a fellow student about grading, we came up with the following method which can make some Theory exam question with longer proofs easier to grade. I believe that, when used with caution, it can be a good tool to have.

Let me stress the word “caution”, since it is not a good idea to use this method on all problems on all exams.

The basic idea is to give the proof away, but in a scrambled fashion. Suppose the proof can be broken into $k$ “units of thoughts” (each unit is probably one or two statements). We will first append some $n-k$ junk units to the end of the proof, yielding a total of $n$ units. Then, we take a random permutation of the $n$ units and give the list to the students. The answer to such an exam question would then be an ordered sequence of numbers indicating the relevant units in the list.

There are many variations on this idea.

First we need to pick $n$. That clearly should depend on $k$. (Somewhere around $1.5k$ to $2k$ may be a good idea.)

Then we may decide to reveal the value of $k$ or not. (Revealing makes it a lot easier.)

Also, some of the junk units may actually be mathematically wrong but “reasonably sounding” in the context of the proof. We call these bombs. If the answer has a bomb, it automatically gets a zero.

And should we choose to add bombs, then maybe it is also an interesting twist to allow the students to pick out exactly all the bombs. For some classes, being able to pick out exactly all the bombs in a question should really qualify for a full credit for it. (Oh, Number Theory…)

Now that leaves the question of partial credits, which can be a highly subjective matter in the traditional “write-a-proof” format. But in this “pick-out-the-proof” format, it may become easier if the junk units are prepared carefully.

Finally, notice that the permutation needs not be the same for different students. This can be good for rooms with little elbow room. Grading is now a bit harder but should not be too bad.

Quicksort Alike

Recently I had to “analyse” randomized Quicksort over a dinner table. Well, I wasn’t prepared to do it using only a pair of chopsticks and a bowl. So I “cheated”. :P

Instead of picking a random element and accept it as the pivot, we let the partitioning algorithm test if the random element is a balanced pivot, i.e., it sits between the 25-percentile and the 75-percentile. This test takes exactly linear time. And if not, the algorithm will pick another random element and re-test.

Clearly the probability of picking a balanced pivot is 1/2 and so the partitioning algorithm will finish in an expected constant number of trials. The rest of the proof is easy and using five more minutes I “proved” the expected $O(n \log n)$ bound with surprisingly little hand-waving. I also ate a lot of garlic bok choy in the process.

Now here are some simple questions that arise from this incident:

  • What about finding the median as the pivot? (And we have a choice of randomized and deterministic median algorithms.)
  • What about the concentration? Is this $O(n \log n)$ “with high probability”? (For instance, what is the probability that it takes 42 trials before a balanced pivot is found?)
  • Can we use a similar view to analyze the running time of the unmodified version of Quicksort? (Try to come up with a clustering of the nodes in the recursion tree and analyze the running time spent in each cluster of nodes.)

More homework questions…

Collecting Feedback for Talks

Every since I started giving talks, I wanted to know how my talks really were. But then, it seems difficult to collect the real opinions because of various reasons. (Diplomacy, friends, countrymen, comrades, etc.) For a start, I want to be able to conduct a thumbs-up/down vote as publicly as possible, but also preserves the secrecy of the votes.

Being at CMU actually makes this problem very easy to “solve”. All I did was to walk into a real crypto person in the corridor the very next morning. And before I finish telling my story, I am already presented with a proposal that is actually executable by real human beings. The trick is to have a way to distribute secret random bits.

Here is how one system may work to ask each person “Is this a good talk?”. At the door, each person is dealt with a card from a shuffled deck. Half of the cards in the deck have “This is a good talk” written underneath it, and the other half have “This is a bad talk”. That’s the secret bit for each person.

Two bins are placed at the door: “I agree” and “I disagree”. At the end of the talk, you just put the card (faced down, of course) into the appropriate bin. As long as your secret bit is not revealed, no one could be sure what your vote really was from observing which bin you used.

I can think of a number of ways to extend the number of questions asked in various ways, all involving secret initialization bits and XOR’ing with the answer bits.

So what questions do I want to ask? After asking around, it seems that the following questions are more interesting:

  • Do you understand the problem statement?
  • Do you think the problem is interesting?
  • Do you understand the proposed solution in the high level?

This works better than pure thumbs-up/down because we may want to distinguish YNN from YYN.

I guess I will use it in my next talk and see how it goes.

Colloquium on CS Pedagogy 2005-11-01

Tuesday, November 1
3:00 p.m.
3305 Newell-Simon Hall

“Thoughts on Introductory Computer Science Education”
Peter Lee, Professor, School of Computer Science, Carnegie Mellon University

Computer scientists and computer science educators are constantly reassessing the introductory curriculum. The intensity of this reassessment has increased, in large part because it is seen as relevant to the recent concerns about declining enrollments and interest in the field.

For the most part, introductory computer science has emphasized hands-on experiences and the development of programming skills. While hands-on skills development has been a mainstay of almost all introductory laboratory-science courses in, for example, biology and chemistry, introductory CS has been unusual, both in its heavy use of “industrial-strength” tools, such as the C++ programming language and commercial web-development systems, as well as the extent to which skills are emphasized over other aspects of the field, such as its history and scientific (or mathematical) underpinnings. In a sense, intro CS has attempted to serve not only as an introduction to the field but also as a valuable form of vocational training.

In this talk, I will give my thoughts on the introductory curriculum. I will argue that the use of industrial-strength tools is often inappropriate, just as it would be in, say, a high-school chemistry course. Instead, I believe that a more well-rounded curriculum that provides a balance of skills development, mathematical foundations, and historical context would be both more appropriate and more effective in inspiring young people to enter the field and understand its scope.

Insert Blank Slides During Talks

Some days ago Anupam asked me how to insert a blank slide right after the current one during a slide show. It may seem curious to many people, but if you teach with a Tablet PC, then it makes perfect sense. This is analogous to having blank transparencies (and the Tablet stylus as the marker) when using an overhead projector. It’s especially useful when a question pops up from the audience and you would like to address it with the help of writing things down. And if you are using PowerPoint 2003, you can retain all the handwritings you made during the slide show and distribute them together with the exisiting slides.

The straightforward way of doing it is to break out from the slide show, insert a blank slide and then resume the show. But do we have a slicker way?

Turns out this is not hard to do in PowerPoint. First, press Alt-F11 (Tools->Macro->Visual Basic Editor). Select Insert->Module in the main menu. Now enter the following code:

Sub InsertBlankSlide()
Dim newIndex As Long
With ActivePresentation
newIndex = .SlideShowWindow.View.Slide.SlideIndex + 1
.Slides.Add newIndex, ppLayoutBlank
.SlideShowWindow.View.GotoSlide newIndex
End With
End Sub

Select File->Close and Return to PowerPoint. Now go to the Master slide and create a new shape there. Right click on that shape and select Action Settings. In the Mouse Click tab, select Run Macro and pick InsertBlankSlide from the combo box underneath it. Click OK and there you go. (Try running the presentation and click on that new shape.)

For a more elaborate example that also includes changing pen type, I refer you to Anupam’s slides in 15-251 (CMU’s 200-level CS theory core). For example, look at this one. It’s true that you can change the pen type by pressing hot keys during a slide show, but if you are using a slate Tablet PC, then you don’t have a keyboard.

P.S. It would be nice if we can change the pen weight programmatically since the default pen weight is a bit too thick. However, I haven’t spent enough time to get it working. All I know is that this is not possible in the object model that PowerPoint exposes. That, however, only means this cannot be done easily (as I have an example here). On the other hand, Anupam has pointed out that you only need to change the pen weight once during a slide show and the weight will not change during the rest of the show. I guess it’s easier to wait for Office 12 to come out than to nail it. :P

Talks in Portrait Mode

Have you ever seen people giving talks in portrait mode? I think all presentation softwares default to landscape mode since the projectors are usually in landscape. So the choice is deliberate.

Here is a calculation. A 4:3 display at 1024*768 has 786432 pixels. If we maintain the 4:3 aspect ratio in landscape, that would be 768*(768/4*3)=768*576 = 442368 pixels, a 43% decrease. Now the speaker may have actually used an aspect ratio of 11:8.5 because of letter sized paper, but I wouldn’t be able to tell since that gives 768*(768/11*8.5)=768*593=455424, still 42%.

So I am curious, why would anyone not want to use those 40% of the available pixels? Do you know what the reason may be?

Really Bad PowerPoint (and How to Avoid It)

The first thing that most people use PowerPoint for is a TelePrompter!

Indeed, and even though the presenter mode can show you notes, it doesn’t really help unless you tend to stand at the podium. But if you stay there too often, then you surely will become a voice, or worse, noise in the background because the audience will look at your slides and not you.

At the end of the day, technology didn’t take away the basic requirement of delivering good talks: you need to be very, very familiar with your own talk. Then you can walk around and still know what should be said and what’s coming up next.

Wireless Presentation Controls

Over the years I have tried around 10 wireless presentation controls. Three of them are quite notable.

All devices I tried are all Radio Frequency based, so there is no line-of-sight requirement as in Infra-Red devices. (Contrast Wavelan with your TV remote.)

My criteria for a good control is very simple: if the control is within 50 feet of the receiver with no obstruction in-between, then all clicks must be received properly. Not a single missed click is allowed. (50 feet is about the width of the largest projection screen here at CMU.)

To achieve this level of guarantee, there must be (i) tactile click feedback, or else you can’t tell if you really clicked or not, and (ii) a weak battery indicator, or else you can’t tell if it’s a battery problem or a radio problem.

The ones that I like include:

  • Gyration Ultra

    This is by far the champion in terms of operation distance. It comes with two rechargeable battery packs and a battery pack adaptor that allows you to use 3 AAA batteries.

    It’s a gyroscopic mouse, meaning that if you hold onto a special button, then moving your hand in the air will move the mouse cursor. With this feature, I can point to an object with my mouse cursor. I prefer it to a laser pointer (which Ultra doesn’t have) since the mouse cursor can stay at a fixed location (no shaking red dot) and I cannot make the mistake of shooting laser into the audience. It also has a mouse wheel that acts as the third button and lets you flip through slides if you need to.

    I do have two small complaints about the current design: (i) There is a sensor at the bottom of the mouse to sense whether the mouse is in the air or not. The light generated by this sensor can be distracting to the audience. So I try to point the mouse down while giving talks. (ii) There is no way to turn off the mouse. You have to remove the battery pack.

  • Logitech Bluetooth Cordless Presenter

    It’s a bit bigger than Gyration Ultra and it also has great radio performance. It uses 2 AA battery.

    The most important advantage of this device is its click handling. Once you made a click, the device will try its best to get the signal across. In my testing, some clicks will be received several seconds after clicking and that makes me think there is retransmission going on. There is even a indicator light that tells you whether the transmission is successful or not. I really like this approach.

    My complaint about this one is that it is too easy to hit the laser pointer button by mistake. The button is large and soft and is positioned right at the bottom for you to easily make that mistake. Also, while it’s Bluetooth, I have not been able to pair it with my ThinkPad X30′s Bluetooth receiver. The mini-receiver that Logitech provides work well though. Overall a worthy competitor to the Ultra.

  • Honeywell Power Presenter

    I would guess that this uses exactly the same radio circuitry they use for their garage door remote. The size of the control is similar to the size of the garage door remote, so it’s quite a bit smaller and lighter than the previous two. It also features a laser pointer. It uses CR2032, so always carry an extra with you.

    It works well if you know this trick: move your hand while you are holding down a button. Somehow this movement is necessary to ensure the click goes through. Once the click has been received, you can release the button. This can take up to about half a second.

    The complaint I have is the awkward click handling (which admittedly I have already gotten used to). I prefer the retransmission approach and it matters since this one does not have as good a range as the previous two.

The one thing I did not test is security proofness. I can imagine that at a conference, there can be multiple identical products being used in close distance. Well, if the speaker in the next room can also advance your slides… :P

P.S. I also note that these days some Bluetooth-enabled cellphones can be used as a presentation control. Check out floAt’s Mobile Agent if you have a Sony Ericsson phone. I also remember there is a commercial software that does similar things using the volume keys on Bluetooth cellphones.

P.P.S. If you are at CMU, Luis has the Logitech and I have the Gyration and the Honeywell. Adam also has the Gyration.

Jump To Page in PowerPoint

Here are some paraphrased comments I have gathered over the years by asking some speakers why they didn’t show me the slide numbers:

  • “It’s a clutter and it distracts my audience.”
  • “It takes up precious screen estate. Look, 1024×768 is not a lot.”
  • “My talk has multiple page animations that make the slide numbers large and that makes my audience feel that I am cramping a lot of material into one hour.”
  • “I just don’t see why having the slide number can be helpful.”
  • “You mean I can have slide numbers? How?”

The best way for me to debunk all these (except the last) is by asking the following question:

Do you know that you can jump to a particular slide in a PowerPoint show by pressing the slide number followed by Enter? Say you want to go to slide 42 during your talk, you press 4 2 Enter (3 keys) and say voila!

This is an important feature that justifies showing the slide number. Why? This means if you show me the slide numbers, then I can ask questions by first telling you which slide I am referring to and, most importantly, you can go to that slide in 2 seconds for the rest of the audience to follow. This is a big time-saver for all of us.

P.S. There are other fully-documented but not well-used keys in the slide show mode of PowerPoint. Press ? (the question mark) in a slide show and you will see.

P.P.S. Maybe I have just sat through another PowerPoint talk with no slide numbers… I don’t remember what happened. Maybe I should consult with the Department of Truth. :P

Giving Citations in a Talk

The setting is a typical research talk. Your room is filled will reasonably intelligent people but not everyone is exactly in your specialty. (Think conferences.)

For such a talk, I am a strong opponent to giving citations using the standard alpha style (as in BibTeX). It’s at most three alphabets followed by two digits, like this: [AMR03].

Maybe it’s just me, but I’ve met some speakers that would say “A M R Oh Three proved a seven-third plus four epsilon over three approximation…” Now that’s really helpful to the rest of us, isn’t it?

And if the speaker is any good, she would actually say the three lastnames in full. I don’t want to offend anyone, but my experience is that a significant fraction of people in the room would have never picked up the words Amir, Krauthgamer and Rao from *my* speech. It’s not just because of my strong accent (and I confess), but also the fact that sometimes we don’t really know how to pronounce a name properly.

My believe is that we should just spell out the complete last names on at least one of the slides. And if none of your slides has enough space for spelling out [Amir-Krauthgamer-Rao 03], then maybe your slides are a bit too dense?

P.S. In case you are interested, [AMR03] is Constant Factor Approximation of Vertex-Cuts in Planar Graphs in STOC. The classic result in vertex-cuts for planar graphs is the 1979 Lipton-Tarjan `O(sqrt n)` separator theorem. But there is no guarantee that their algorithm will return a cut that has a size close to the optimal. This paper achieves that guarantee, with some technicalities.

Stop your presentation before it kills again!

Kathy Sierra has written a very strong post against the use of PowerPoint and even transparencies for her presentations. To quote her:

Sometimes the best presentation is… no presentation. Ditch the slides completely. Put the projector in the closet, roll the screen back up, and turn the damn lights back on!

Even though you may not want to stop using PowerPoint because it’s not obvious how to use it right, you definitely want to read her post and learn how not to commit the mistakes she mentioned. Some of them are definitely avoidable with practice, such as talking to the slides and dimming the lights, both of which are likely to turn your talk into a unidirectional broadcast.

Among the comments, I discovered this interesting wiki about WhyWeDoNotUsePowerPoint. Heh.

Five Rules for Better PowerPoint Presentations

Michael Hyatt has the following five rules:

  1. Don’t give PowerPoint center stage.
  2. Create a logical flow to your presentation.
  3. Make your presentation readable.
  4. Remember, less is more.
  5. Distribute a handout.

You can read about it in full glory at and be sure to read the comments there too!

(Thanks to Mukesh for sending this link to me.)

In Defense of PowerPoint

Usability expert Don Norman has published his response to Edward Tufte’s The Cognitive Style of PowerPoint. As I have said in a previous post, not everyone, myself included, agrees with the opinion Tufte entirely. Well, according to Norman,

I respectfully submit that all of this is nonsense. Pure nonsense, accompanied by poor understanding of speech making and of the difference between the requirements for a speech-giver, the speech-listener (the audience), and for the reader of a printed document. These are three different things. Tufte-and other critics-seem to think they are one and the same thing. Nonsense, I say, once again.

For those of us that use PowerPoint for teaching, I highly recommend reading both articles, but bear in mind that we have a arguably different purpose of using PowerPoint—teaching is not just giving a (good) talk in a lecture hall.

BTW, even if you don’t have a chance to read Tufte’s work (\$7), I still recommend you to read Norman’s article. It has sufficient context for you to understand the issue.

PowerPoint Remix

Edward R. Tufte is an expert in information design. Some of you may have read his pamphlet The Cognitive Style of PowerPoint (mostly bashing PowerPoint). Here we have his essential ideas in that pamphlet… in the PowerPoint bulleted-list format. :P

P.S. I don’t entirely agree with all of Edward’s ideas in the pamphlet, but the pamphlet is a starting point for those of us who really think about our presentations. Maybe I will write about it later.