[Lowerbounds, Upperbounds]

On my way to squashing one of the TexPoint bugs, I stumbled upon Andreas Glatz’s page on his patched version of TexPoint, currently at version 2.6.1 and version 2.7 is said to be released sometime around mid-October. I guess I will try Andreas’ version a bit later.

Looking at the development log of Andreas’ page, it seems that Andreas started the development after George Necula, who started TexPoint, released version 2.0.3 in October 2003. Meanwhile, George has not released any newer version yet.

Curiously, there is also a Mac version! Interesting… (although I really don’t have any money to buy a PowerBook yet.)

Although the first theory lunch of the year won’t be until September 14, I’ve received a suggestion that we could hold a lunch and town meeting of sorts on the 7th. This would be an opportunity to meet the new members of our community, hear about the theory courses being offered this semester, and discuss various topics of general interest. In particular, there has been a bit of talk about various note-taking and audience feedback schemes we might want to try out at theory lunch.

So… town meeting? Yea or nay? If people are interested and would actually attend, I’ll try and set something up. If and when I do set something up, I’ll send out an announcement.

It is surprisingly not easy to correctly set the margin in LaTeX, and it’s worse if you actually have to adhere to a given specification like:

The total allowable width of the text area is 6.5 inches wide by 8.75 inches high. The top margin on each page should be 1.2 inches from the top edge of the page. The left margin should be 0.9 inch from the left edge. The footer with page number should be at the bottom of the text area.

The above specification may look familiar to some people. Indeed, I copied it from the documentation of the geometry package by Hideo Umeki.

I don’t know why, but it seems that many people have managed to avoid running into this fantastic and easy-to-use package. The package is sort of new, in the sense that it didn’t make its way into the first edition of The LaTeX Companion. (But this must-have book is already in its second edition… Yes, go buy a copy if you haven’t.) And somehow it also doesn’t get described in the 133-minute May 2005 version of The Not So Short Introduction to LaTeX2e. (In fact, TNSSI doesn’t have a complete solution to setting margin… Anyway.)

Let’s start with a simple case first. Suppose you want your document to have an one-inch margin on letter paper in portrait. This case is extremely common.

\usepackage[dvips,letterpaper,margin=1in]{geometry}


Now sometimes you may need to squeeze an 0.1 inch from one of the sides. In that case, you can specify lmargin, rmargin, tmargin and bmargin individually.

To switch to landscape, just add the landscape option. The package will even automatically correct for the landscape swapping problem in ghostscript viewers.

And if you happen to be using pdflatex, you can still leave dvips as one of the option. The package will automatically override.

The package manual documents a lot more options. Dig it up if you need something more sophisticated. There is probably an easy way to do it with geometry.

P.S. There is also the vmargin package, but it is a bit more complicated to use than geometry. It was the solution in the first edition of The LaTeX Companion.

P.P.S. To get the above specification, the manual of geometry suggests:

\usepackage[total={6.5in,8.75in}, top=1.2in, left=0.9in, includefoot]{geometry}


In a secret mission, last week I forced myself to write a 20-page document with TeXnicCenter, a Visual-Studio-like text editor for LaTeX. It was a rather painful experience given its current BibTeX support. Here is the feature list for this (quote) “extremely feature rich” editor. (Perhaps I missed the bib support feature somewhere in this feature list?)

One feature I like about TeXnicCenter is its Navigator (screenshot), which is a tree widget showing the section structure of the document. In Visual Studio, this would be showing the class structure. It is very useful for navigating between sections and can help somewhat when inserting labels.

And that reminds me that a couple years ago I have blown my officemate away by showing him how to use RefTeX. This comes standard with Emacs. (It’s in lisp/textmode/reftex.el.)

Once loaded, it adds the following five key bindings, along with another five that are related to indexing:

• C-c =
  reftex-toc shows you a table of content in a separate window and let you navigate among sections. Pressing Enter on a section brings your cursor right there.
• C-c [
  reftex-citation scans your current bib file and help you insert \cite. It prompts you for a regex and then show you all matching entries. Press Enter on the desired entry and the proper \cite will be inserted for you! (This is a killer feature if you have long bibitem key to your bib entries.)
• C-c )
  reftex-reference shows you the table of content of sections, equations etc. It works like reftex-citation and inserts \ref.
• C-c (
  reftex-label helps you insert \labels by offering a somewhat intelligent default.
• C-c &
  When the cursor is on a \ref, reftex-view-crossref brings up the corresponding \label in a separate window. When the cursor is on a \label, then it shows you occurrences of the label one-by-one. The same dual features are available when you are on a \cite and a bib entry.

P.S. Emacs means GNU Emacs. I suppose XEmacs will be similar.

Even though many of us do not use TeX directly, knowing TeX can certainly help you use LaTeX better. For one thing, you can write your own macros.

For many years TeX by Topic by Victor Eijkhout is one of the best—if not the best—reference books on TeX since it is organized by, urr, topic. And here is the good news: Victor has generously put the full text online after the publisher reverted the rights to him. Kudos!

http://www.eijkhout.net/tbt/

P.S. Reading TeX by Topic by itself can be very unproductive since it’s a reference book. For a book on TeX that you should read cover to cover, nothing beats Knuth’s The TeXbook.

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?

According to this article in CNN Money, these three jobs have at least one thing in common. Since I am not yet interested in being an architect and I can’t stand the heat in the kitchen, my perspective would be that

A career with one of the most disproportionate ratios of training to pay is that of academic research scientist.

Perhaps a Jedi knight training would have gotten me more pay. Patience…

And it’s made tougher still by the fact that in many disciplines, there aren’t nearly as many tenure-track positions as there are candidates.

I can easily imagine this being the case for liberal arts subjects, but perhaps this is also true, or getting more true, for Computer Science too. I don’t have figures to know the situation.

At the end of the article is this inspiring, surprising list of six-figure jobs: stunt driver; auctioneer; matchmaker; head groundskeeper; and fashion-trend forecaster.

I predict that next year’s fashion will be different from this year’s. Really, that makes my mom feel proud.

A Workshop to Celebrate the 60th Birthday of Alan Frieze.

Dates: Oct 21 and 22 2005
Location: Carnegie Mellon, Pittsburgh, PA

As you may recall from our earlier announcement, Alan Frieze is turning 60 this coming Fall, and we are celebrating with a workshop focusing on probabilistic combinatorics and randomized algorithms.

There is a new web site for the workshop which includes a tentative schedule as well as registration, banquet and hotel information.

http://www.aladdin.cs.cmu.edu/workshops/ffest/

There will be no registration fee if you register before Friday, September 30, 2005. Please register early to help us with planning. On the evening of Friday, 21 October 2005, there will be a workshop banquet featuring reminiscences about the life and career of Alan Frieze (both respectful and otherwise).

IMPORTANT: Out-of-town visitors should make hotel reservations immediately since availability is severely limited due a number of events in Pittsburgh on the weekend of the workshop.

Graduate student and post-doc funding: Travel funding is available for a limited number of graduate students and/or postdocs who will be attending the workshop. This funding is restricted to US citizens and permanent residents. To apply send a description of your research interests and one brief letter of support (preferably from an academic advisor) to Tom Bohman at tbohman@math.cmu.edu. Applications for this funding must be received by September 15, 2005. Travel awards will be in the form of room (3 nights stay in a shared hotel room) and up to \$300 for airfare.

As you may know, FOCS will be held in Pittsburgh, beginning the day after this workshop.

FriezeFest 2005 is being sponsored by the National Security Agency, the Aladdin center at CMU, the Tepper School of Business and the Department of Mathematical Sciences.

We hope that you will be able to join us,

Tom Bohman, Mike Molloy and R. Ravi

As a manual of geometry and Postscript, the beginning chapters of this book reminds me a lot of my junior school Logo tutorials. But very soon Bill Casselman starts to draw 3D objects in 2D and projection is where the story gets very interesting. (Think how to draw a polyhedron on a piece of paper.)

The book has an online version and a paper edition.

P.S. One tidbit I learned from this book is that doughnut, oh I mean, torus means cushion in Latin. Hehe.

http://www.sethgodin.com/freeprize/reallybad-1.pdf

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.

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.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.

http://games.slashdot.org/article.pl?sid=05/04/24/1259241

Unlike normal Tetris(R), however, Bastet does not choose your next brick at random. Instead, Bastet uses a special algorithm designed to choose the worst brick possible.

Surely this situation will sound too familiar among the algorithm designers.

I also checked my Worst-Case Scenario Survival Handbook. No, it doesn’t tell me how to survive Bastet. My high score so far is 5 lines, after trying about 10 games. At last, there is a game that I will happily accept my low scores.

P.S. Although not directly related, this reminds me of Tetris is Hard, Even to Approximate by Demaine, Hohenberger and Liben-Nowell.

I find this recent book (sort of available online) by Mark Jason Dominus to be very CS-friendly. The reason: Closures!

The Perl Review: Why did you write Higher Order Perl?

Mark Jason Dominus: [...] But I had a few hidden agenda items as well. The book is about how to use closures, and I think there are too many languages around that have no easy way to use closures. Java, in particular, seems to me to be a giant step back towards the languages of the 1970s.

Two interesting tidbits from the book are:

• The term memoization was coined in 1968 by Donald Michie.
• Data marshalling is so named because it was first studied in 1962 by Edward Waite Marshall, then with the General Electric corporation.

In a previous job, I have done a lot of programming that involves data marshalling, now the term finally makes sense!

http://www.qinfo.org/people/nielsen/blog/?p=120

The philosophy underlying the essay is based on a famous quote attributed to Aristotle: “We are what we repeatedly do. Excellence, then, is not an act but a habit.’’ Underlying all our habits are models (often unconscious) of how the world works.

Thanks to Aristotle, and Nielsen.

A couple days ago a pretty savvy Windows user in our Theory group asked me if there is any keyboard shortcut to rename a file in Explorer. I don’t know how I learned about it, but F2 is the answer. It seems to have dated back to my Lotus 123 days. In Lotus 123, F2 means “edit cell” and it also works in Excel for the obvious reason. I also notice that Microsoft actually publishes a list in their knowledge base:

http://support.microsoft.com/default.aspx?scid=kb;en-us;Q301583

Well, but this list is surely not comprehensive. For one thing, I note that Ctrl+Shift+Esc is not listed anywhere. (This brings up the Task Manager.)

Luis officially launched Peekaboom a couple days back, but the even more “real” launch is actually today.

Here is the story on Pittsburgh Post-Gazette and this is the presentation Roy has made on it. Roy is a member of the Peekaboom team that Luis has assembled in REU.

Michael Nelson has a nice introductory series written on expander graphs. I particularly like the fact that Michael has taken the time to “boil down” the proofs. Thank you!

http://www.qinfo.org/people/nielsen/blog/?p=224

Dear Expanders, are you really all algebraic?

In Part 1, I have shown how you can increment a “binary” counter in `O(1)` time if you use a redundant number system. Now I am going to show you how you can apply this simple abstraction to deamortize Binomial Heaps (here is the Wikipedia page for Binomial Heaps if you want a refresher).

Where does the amortization come in for Binomial Heaps? Well, all the time bounds are indeed stated as worst-case bounds. But, as is commonly taught in many places, you can have a more precise time bound for Insert if you do an amortized analysis. The argument is particularly simple if we use a binary counter abstraction.

We will encode the configuration of the binomial trees using a binary counter `d_{log n}…d_1d_0`. We set `d_i` to be 1 iff a binomial tree of rank `i` is present. Inserting into a binomial heap is now precisely incrementing this counter. Linking two binomial tree of rank `i` to form a binomial tree of rank `i+1` is exactly converting a 2 in `d_i` to a 1 in `d_{i+1}`. Guess there must be a reason why it’s called a binomial heap.

The amortized analysis can be done using the credit invariant method. We argue that over a series of `n` insertions, the digits only changed at most `2n` times. For each rank (digit), we open a bank account. Each insertion pays two dollars: one spent immediately for the actual insertion and one deposited at the account of the first 0 that turned into a 1—observe that precisely one 0 will turn into a 1 in every increment as the propagation will stop immediately afterwards. The dollar deposited in the account of this 1 will be used to turn it back into a 0 during a future insertion.

Check that we will have enough money to pay for all digit changes during any insertion. As we never go bankrupt, we conclude that 2 dollars per insertion is enough. In other words, insertion actually takes “only” amortized `O(1)` time.

Equipped with our technology from Part 1, now we can implement insertion in worst-case `O(1)` time simply by using a redundant counter. Indeed we will allow two binomial trees of rank `i` to co-exist for a while, until the counter needs to link the two when fixing its regularity. Simple enough.

For those of you who want to know how redundant counters were invented in the first place, see

• Michael J. Clancy and Donald E. Knuth. A Programming and Problem-Solving Seminar. Technical Report STAN-CS-77-606, Computer Science Department, Stanford University, April 1977.

Note that over the years many extensions to redundant counters have been developed, and in fact the terminologies used in this series are “modern”. We will talk more about those in the future.

Your laptop just makes the familiar “oh-oh” sound. You know you have an instant message in ICQ.

The problem is, it’s 5:30 in the morning right now… Indeed you forgot to turn off your speaker the night before.

It doesn’t have to be like this.

The one last time this happened to me, I decided to fix this problem once and for all. So I wrote a command line utility that lets me mute and un-mute my computer speaker. Couple this with the Task Scheduler in Windows, my laptop knows when to keep quiet.

Usage: cmdmute [0|1]
0 - Mute OFF
1 - Mute ON
Toggle if no argument is given.


Update on 2007-01-30: Source posted. Compile it with cl cmdmute.cpp winmm.lib

Update on 2008-11-11: I use this only on Windows XP and I don’t have Vista for testing.

Update on 2008-12-23: I heard that nircmd works on Windows Vista.