DARPA was an early huge supporter of quantum computing, but the QuIST program ran it’s course and, so far, there hasn’t been any “equivalent” replacement program, as far as I’m aware (but what do I know!) Thus it was interesting to run across this article, which has an awesome title: “Schrodinger’s Contracts: US Explores Quantum Computing.” Somehow this makes me picture my brain in a superposition of solving and not solving research problems. Now if only I could do ampitude amplification on my brain.
Classroom Presenter
Well the term is over and a new term has begun. No teaching this term for me, so its time to hit the research hard! Last term I taught CSE 326: Data Structures, which covers a lot of fun and core material. Hopefully the students will have forgiven my tendancy to assign more difficult theorish problems 🙂
The class I taught was for majors here in CSE at UW and we had two lecture sections of thirty plus students. Ruth Anderson, a recently minted Ph.D. here at UW, taught one of the sections and I taught the other, although we stuck to basically the same schedule. Ruth is a member of the Education and Technology Group in our department which led to us using a very interesting tool in teaching: Tablet PCs! And not just me using a tablet for presentation, but the students using tablets as well! The software which we used for this is being developed here at UW and is called Classroom Presenter (most recent version is 3.0).
Here’s how it works. Say you have a bunch of powerpoint slides which you will be using for your lecture. Well you can use Classroom Presenter to display these slides and write on them just like in Powerpoint. But the cool thing is the added flexibility for interaction. Before the class we (errr I mean the people who are running the Classroom Presenter project!) set up a wireless access point along with tablets for every student (or for student groups working in teams.) The student then get access to your slides as you are displaying them Not only that, but the students can write on your slides and beam up the answers to you. You then get a beautiful list of the student submissions and can choose to display these at the front of the class. (You can lock the students so that they only have access to the slide you are working on, or you can unlock the slides so they can browse ahead or behind.) So, for example, you can choose to do an inclass problem with the students, have the students beam their answers up to you, and display common errors that were made or correct answers, etc. Getting feedback when you’re teaching is always a real hard thing to achieve. In large classes it’s not uncommon to see these little clicker things for voting on multiple choice questions which allows a teacher to see if the students are comprehending the material. The tablets take this to the next level (and are perhaps best not for large classes but for medium or small classes) since you get to see worked out problems, in real time. It’s also quite fun because the students get to see what they wrote displayed up front along with all the funny things they like to draw with their submissions.
(As an interesting side note, I often wish that during research talks I could have access to the speakers slides. Too often the speaker runs through a slide too fast and you don’t have time to either read or digest or write down what they display. If I had the slides on my laptop I could parse through the slides myself. I could even parse ahead if I understand what is being said and in the worse case determine that I really don’t need to listen to the talk and so daydream about my research. 🙂 Come on Powerpoint team, wouldn’t this be an awesome feature?)
Teaching with tablets is, I think, an interesting way to mix in a less harsh version of Socratic teaching (less harsh in that you are not at the mercy of your peers and teacher when you have to do a problem in front of the class.) I’d also love to see an even more Socratic version of the software which would not anonymize the submissions. For small classes or even when working in groups this would be an interesting way to teach and perform collaborative research.
Oh, and another cool feature of Classroom Presenter is that there is a way to take a slide, and squash it down to the upper-right corner of the screen revealing an area where you can write free of blocking the slides. This is great when you overpopulate your powerpoint slides and need scratch room to write (Powerpoint allows you to pull up a blank sheet to write on, but this isn’t as effective as having a small version of what you are talking about available.) Oh and it also allows you to keep teacher notes: notes that are displayed on your screen but not on the projected screen (you add these directly onto the slide and the can be anything, not just text.)
All in all, I think I rather enjoyed using the Tablets with Classroom Presenter. Like all new things it took a little getting used to (especially judging the time.) On the other hand I certainly think that there were a few exercises that really helped me understand the where the students were having trouble and where they were doing fine. Classroom of the future? Who knows! But maybe a glimpse of a more interactive teaching tomorrow.
Lightning Rods Against God's Fury
I recently picked up Discarded Science: Ideas that seemed good at the time…
…In November 1755 the most destructive earthquake ever to strike the northeastern US hit at Cape Ann, some 50km south of Boston. The Reverend Thomas Prince, of South Church, Boston, knew at once who was to blame: Benjamin Franklin (1706-1790), for having invented the lightning conductor. Before Franklin’s scheme of putting pointed metal rods on tall buildings had been universally adopted, God had been able to express His wrath by blasting something with lightning. Now that the presumptuous Franklin had taken that option away from Him, He was having to use earthquakes instead.
Which leads, of course, to the question of just how many tools of God has Science destroyed?
Debug First?
After Scott confessed to still programming in BASIC, I had a good time recalling how I first learned to program. My first interaction with a computer and “programming” was through LOGO, that cute little program for programming a little turtle to draw graphics. Drawing cool and crazy pictures was fun! But I don’t really remember learning that as “programming” so much as it was learning geometry (I was in the second grade at the time) and I certainly recall sharing the computer (probably not very sharefully.) But the real way I learned to program was not through LOGO but through debuging!
In the (g)olden days of my halycon youth you could buy computer magazines which had in the back of the magazine lines of BASIC to enter into your computer in order to play a game. Now I was all about playing games, and when we obtained at TRS-80 Color Computer, my parents only bought one game cartridge, so in order to play more games we had to type them into the computer. A group of neighborhood kids would get together and do this. One person would read and the other would type and others which check to make sure what was being typed was correct. Even with these precautions, however, we would, invariably make a mistake. So when you made a mistake you had to go looking through the program to find out where we made an error. Eventually, at first, we’d just go through the whole program line by line. But as we got more sophisticated we began to understand how, when the game died while doing X it meant that the program was probably at Y when this happened and so we began to understand what all that funny stuff we were typing in was. Eventually we got very good at debugging the code we typed into the computer. Indeed, in a very real sense, I learned to debug before I learned to code! (Years later I can still recall the astonishment of a high school teacher who watched me debug a program in a fairly rapid time 🙂 )
So here is a question. Sure we could teach students to program using your favorite language FAVLANG, but what if it was possible for us to teach debuging before we taught programming. What if the structure of the introduction to programming was centered around finding and fixing bugs. I mean, after reading Dreaming in Code, where the book ends with thousands of bugs left unfixed, I can only imagine that good debugging skills are important. Maybe even as important as coding skills? Just a thought. But even if this is not the way to go, how could you teach debugging before you taught programming? Now that’s fun to think about.
"Dreaming in Code" by Scott Rosenberg
Many of you have probably read the classic The Soul of a New Machine
PRINT *, 'RIP, John Backus'
John Backus, who led the team that invented FORTRAN, has passed away. In a testimony to the staying power of FORTRAN, when I was doing an undergraduate research project in astrophysics in 1995, most of the code I delt with was written in FORTRAN.
The Great Wedding Diet of 2007
(Note, the below plot is indicative of a method for losing weight which not exactly healthy and is not recommended!) Results of the great wedding diet of 2007:
The method? Little food and running four to five miles every morning. Funny how that works.
Okay, for old times sake, here is, for comparison, my last diet:
Quantum versus Classical: Exponent SMACKDOWN!
The world is quantum mechanical, damnit, and so (the party line goes) it shouldn’t be surprising if we find that a theory of computation based on quantum theory is more elegant than one based on machines whose concept of reality is so restrictive as to not allow cats both alive and dead. Okay, so we can say this half in jest, half seriously, but does it really hold any water? In order to solve this question of asthetics (joke about mathematics deleted), I propose that we hold a Quantum versus Classical beauty contest. Now since quantum computers are at least as powerful as classical computers, we can’t just say that an algorithm is better because it has a better runtime or better use of space, etc. Instead we need to use our artistic taste, i.e. pretend we have a clue about what it means for a result to be elegant (and yes, that was a dig at a certain popular science book 😉 )
Round 1
So I propose we perform this artistic measuring with a quantum versus classical exponent SMACKDOWN! (the exclamation mark is a part of the word.) Consider, for example, the recent quantum algorithm for evaluating a NAND tree (here and here with an explanation by the traveling complexity theory salesman here. Also the awesome NAND formula paper here) This quantum algorithm has a running time of [tex]$O(N^{1/2 + epsilon})$[/tex]. Now compare this with the best and optimal classical algorithm for this problem. The result? [tex]$O(N^{0.753 dots})$[/tex] where [tex]$0.753 dots approx log_2(1+sqrt{33})-2$[/tex]. Bleh. Round One of the Quantum Versus Classical Exponent SMACKDOWN! most certainly goes to the quantum world. One half is certainly better than something which is has both a logarithm and a square root of thirty three!
Round 2
But ha, say the classical complexity theorists. What about Grover’s problem? Sure in this unstructured query search the quantum world achieves a speedup from [tex]$O(N)$[/tex] classically to [tex]$O(N^{1/2})$[/tex] quantum mechanically, but look at your exponent. One half? Who the hell ordered one half. I mean if you had gotten log of N or even constant, then you would have something to brag about. But a square root speedup. Who ordered that? Round two of the Quantum verus Classical Exponent SMACKDOWN! most certainly goes to the classical world were weird square root speedups are not ubiquitous for straightforward unstructured query searches.
Round 3
To be continued!
The Physics of "All-In"?
Combining two excellent topics, physics and poker, physics/0703122:
Universal statistical properties of poker tournaments
Authors: Clément Sire
We present a simple model of Texas hold’em poker tournaments which contains the two main aspects of the game: i. the minimal bet is the blind, which grows exponentially with time; ii. players have a finite probability to go “all-in”, hence betting all their chips. The distribution of the number of chips of players not yet eliminated (measured in units of its average) is found to be independent of time during most of the tournament, and reproduces accurately Internet poker tournaments data. This model makes the connection between poker tournaments and the persistence problem widely studied in physics, as well as some recent physical models of biological evolution or competing agents, and extreme value statistics which arises in many physical contexts.
The Computer Recommends….
Scirate.com now has a simple recommending engine. Right now it’s very basic, but I hope to improve it and make it a little more interesting in the future.