In the computer science Ph.D. program here, there are qualifying exams in Operating Systems and either Foundations or Algorithmics. I have to pass both of these exams sometime in the next two years. But if I want to -- and we're "very strongly advised" to do so -- I can take a "free try" at the exams a week from today.
I don't have the background for the systems exam yet, but for the other one, I may have a chance. I've looked at the sample exams for Foundations and Algorithmics, or, as I like to call them, "Just Some Good Old-Fashioned Math Problems, Not Too Different From The Ones You Did In Undergrad" and "Wrenching Pain", respectively. Foundations, please. It's not as though I'm not rusty, though, so when I was in Atlanta last month, I borrowed Alex oniugnip's copy of Sipser and got a head start on re-reading chapters 0 and 1.
Alex's copy of the book differed from mine in one important respect: it hadn't been completely scrawled all over by me in 2004. When I looked at the clean white pages, I saw ghosts of things that I'd written in my copy -- or had I? It was hard to remember. But I felt like there'd been some particular page, back then, that I'd had to absolutely cover with writing, because it was a page that had happened to have a particularly hard-to-understand proof on it, and because writing all over things is how I figure them out. Not only that, but I remembered having to go to Dr. Stone's office, sit down, open the book up to that page, and ask what was going on, because my lack of understanding had brought my progress to a grinding halt and I needed help figuring it out before I could get any further. That had really happened, hadn't it? Geez, what page had that been?
I could see it in my head, that page covered with writing. In fact, I was pretty sure it had a two-digit page number where both digits were the same. Well, that narrowed it down. Surely I could find it again. When I got to the end of chapter 1, I flipped back through Alex's book, stopping at all the multiples of 11, trying to remember. 44, 55, 66, 77...nah, none of this stuff was hard enough to have warranted that much confusion. Maybe I was wrong about the both-digits-the-same thing, or maybe the material hadn't really been that hard after all. I decided my memory was playing tricks on me and gave up.
Eventually, though, I gave Alex his book back and went home and got my own copy off the shelf and looked. And there it was: page 55, covered in scrawl. Equivalence of NFAs and DFAs! Yeah! It had taken forever to wrap my head around that, back in 2004 -- but this time, I'd rolled through it without a hiccup. Amazing. I'd been vaguely aware that I'd learned something since then, but to have physical proof of it was startling and affirming.
Now I'm up to chapter 3. It's nice to be on to the powerful stuff. I've got a lot more reading to do in the next week, but at this point, I'm feeling okay about the sample exam. Here's hoping the real thing isn't drastically different. And if it is, well, I have a couple of years to catch up.