Monday, December 18, 2006

I've decided to restructure a bit. I spent quite a bit of time in the library today looking for a suitable textbook on Databases (in preparation for the seminar I'm taking next semester) and not really finding one. As it turns out, though, the third volume in Knuth's Masterwork is on sorting and searching, which is relevant. So I'm going to set as a new goal to have volume three finished by the end of the break (January 8). And I'll take the other two more slowly after that. The preface says that it's mostly stand-alone, so there shouldn't be a problem reading the volumes out of order.



I won't set a specific reading schedule - just say "by January 8." In the meantime, I'll read 20pp. a day of Dr. Purdom's book to keep in shape for is advanced class instead. The only course page I could find for his advanced class was from 1999. Assuming he hasn't changed much since then (and that's a very safe assumption I'm sure...), the textbook will be the same book we used in the intro course. I guess we'll just finish chapters 6, 7 and 8. We covered the first five chapters in the intro course.





 

Saturday, December 16, 2006

OK, well, obviously I didn't meet my stated goals on this blog! So I'm going to have to start over. I do want to read Knuth's Masterwork, but I think the pace I set for myself last time is simply too much. So here's how I'll do it this time. I'll try to have the first book finished by mid-January - which means reading at just over 10 pages a day. The second book I'd like to finish by the end of February, and I want to be done with all three by the end of the semester. I'm taking Advanced Algorithms, so this will work out nicely for that course. And at 10-15 pages a day, there's no reason I shouldn't be able to stick to it this time. It's a realistic goal, but it still requires some discipline to do the reading every day.

I'm taking a much-deserved end-of-semester break through tomorrow (actually, I have to drive to Indy and gather some information on a programming project, so I will be doing SOME work tomorrow!). When that ends on Monday, I'll take up posting to this blog daily. Stay tuned!

Thursday, October 26, 2006

Alright, well, this blog is admittedly in trouble. It isn't for nothing that I say I have discipline problems! I had plenty of time to do reading yesterday, but ended up doing homework in Friedman's class instead. This turned out to have been a very good idea, though, as Friedman's homework for this week throws you a nasty little curveball just as you think you're finishing it. I won't go into details (if I do I'll be typing here for some time and won't get any reading in Knuth's book done!), will just say that it involves implementing call/cc - an operator that Friedman describes as "the most complicated operator known to man, except possibly Ruby's 'yield'" - in an interpreter, then cps-ing and registerizing the interpreter, which means that call/cc REALLY has to be implemented. I can't just use calls to call/cc itself, I have to actually get it working on its own. Anyone in the know will feel my pain.

Like everything else in computer science, it turns out to be simple at the base. But that doesn't mean it's simple to figure out! Fortunately, I figured it out about an hour ago, so the homework will be clean sailing from here (so it seems...). But 3 hours of potential reading time yesterday are still gone forever. Na ja. Good thing I did that, though, because otherwise I wouldn't have gotten to participate in the after-class discussion on the topic that three of us having trouble with it had; that really cleared a lot of things up.

OK, but this is off-topic rambling. On to on-topic rambling. Amazon says that volumes 2 and 3 have finally shipped. There were some delays, so I checked out volume 2 from the library as a precaution. I will be returning it tomorrow. I also got another foundational book by Knuth - only on this one he's only a co-author. This book is Conrete Mathematics: a foundation for computer science. Judging by the table of contents, it is probably actually more relevant to the task at hand in my algorithms class. Pity that I have already sworn to read The Art of Computer Programming v.1-3 as my discipline project!

Not that a whole lot of discipline is getting accomplished... Story of my life. AHEM. Off to read. Noah can take his deathwatch and shove it (grumble, grumble). More specifically, off to get some coffee made. Am getting tired, but if this project doesn't get started soon...

TODAY'S GOAL: p. 500
CURRENT STANDING: p. 23

*sigh*

Thursday, October 19, 2006

Well, no discussion section today in my class, but no progress made either. Officially 130 pages behind now. Got home today and took a nap, which I very much needed.

Homework for Friedman's class is mostly done, though, which frees up a lot of time for the weekend.

Wednesday, October 18, 2006

Unfortunately, nothing to report again today. I have simply had no time to read and am now 80 pages behind schedule. This will have to be recouped this weekend.



Discussion section is cancelled in the class I teach, however, so I have additional time tomorrow and on Friday to make up the loss. Definitely not the start I was hoping for, but it's the deadline that matters.



 

Tuesday, October 17, 2006

Well, it's the first day, and I'm already a bit behind in my reading, so this entry will have to be short. Not an auspicious start, I know, but lots of things came up.



At present, I've read 12 of the 50 pages that I set out for myself today, but I'll be up for another two hours or so, so I should make it to 50 before I turn in.



I'm pleased to say that the book is quite readable. When you're given a giant 700-page hardcover with nothing but math in it, it can be a bit intimidating. Fortunately, Knuth has a really nice writing style. I wasn't wrong about him being thorough! He takes the time to explain every point in great detail, so this has the virtue of being one of the few books in the world that can honestly make the claim that it is suitable both for beginners and experts. I find it much less dense than Purdom's book, even though it actually manages to explain more.



I've done most of the exercises for the first section - but there are a few at the end that have me a little stumped. Knuth has a rating system for exercises - where each gets a two-digit number. The first digit - from 1 to 5 - gives the basic level. So a 00 would be something you should instantly know the answer for, a 10 is just a test to see that you were paying attention, a 20 might take 15-20 minutes to work, but should pose no serious difficulties. Anything in the 30 range is a serious problem requiring more than an hour of thinking (more than two if the TV is on, he says), things in the 40s are appropriate for term projects in a class, and anything starting with a 5 is a known but as yet unsolved problem in the field. He also notes when exercises are "recommended," when they involve "math," and when they involve "higher math."



There is one very interesting problem (rated M25 - for "mathematically oriented, medium to moderate difficulty - will require more than 15min.") that involves a set of very simple equations that are computationally complete (like a Turing machine, they can perform any calculations we might consider "computation," though maybe not efficiently), and the reader is asked to implement the Euclidean Algorithm (for finding the greatest common divisor) with them. I haven't given it much though, and I probably won't tonight (finishing the reading takes precedence), so I won't say much about it today, but it's likely to appear in this column tomorrow.



Anyway - enough of this. Reading comes first. I admit I'm off to a shaky start, but am still optimistic I'll have the first three volumes out of the way by the end of November.



 

Monday, October 16, 2006


To Don Knuth: teacher, algorithm analyzer, and inventor of TEX


So reads the dedication to the textbook we use in my Algorithms class.

Dr. Purdom frequently drops Knuth's name in class. Apparently they were in gradschool at more or less the same time (this checks out - Purdom was a 1966 PhD from Cal Tech, Knuth a 1963 PhD. The Wiki page on Knuth shows that he was also a professor there from 1963-1968.), and Purdom took his first course in Algorithms analysis from Knuth.

You really can't do better than that, and I don't blame Purdom a whit for dropping Knuth's name. Knuth is considered by many to be the father of Computer Science and is often credited with having more or less invented the field of Algorithms analysis. He's also celebrated as a founder of geek culture, and his quirks are legendary. (For example, Knuth has a standing promise with the world to pay $2.56 - a hexidecimal dollar - for every error someone finds in his books. Most of these checks go uncashed, however, as they are considered collector's items. He has written over $20,000 worth of such checks.) I don't know all that much about him myself. From what I do know, I know that he and I are very different people. This makes it possible for me to admire him.

People have their own reasons for admiring others, of course, but the way I understand it, admiration means that the person possesses characteristics you don't have but might like to have. So many people, when you ask them to list their heroes, list people they want to be associated with. It's a sly way of asking you to think of them as you think of that person. For example, if a person tells you they admire Dr. Martin Luther King Jr., it tends to mean that, rather than admiring his rhetorical style or his bravery (or plaigarism skills or womanizing, who knows?), they just want you to know that they suffer from white guilt and are taking affirmative action to resolve the problem. This isn't actually admiration as I understand it. Admiration, rather, means that someone is something you like but will never be. This is the case with me and Knuth.

From what I know about Knuth, he is methodical and self-disciplined to a zen monk extreme. I am exactly the opposite. I have no self discipline, and it's a constant problem in my life. I am only able to do or focus on things I'm interested in. This presents a huge hurdle to my ability to get schoolwork done on time, for example. (And in fact one of the main reasons I'm pursuing a career as an academic is because I don't think I can be assigned things to do for the rest of my life. It is crucial that I do things I want to do and find interesting - or else things don't get done. Not an attitude one can really have on a corporate payroll...) A cool Russian professor I had as an undergraduate said once that "life is a fight against laziness," and I took that to heart. I wouldn't call myself lazy, exactly. I do a lot more actual work than most people. But I would say that I'm undisciplined. And I do indeed take affirmative action to deal with this problem.

Today in Algorithms we had a midterm. It was much easier for me than I expected. I have been neglecting this class and was shooting for a 50 on the exam; I spent all yesterday cramming with that goal in mind. (Of course, this is a Computer Science course, so please understand that grades in that range, while bad, are not "terrible.") I think I will probably get a 75. But if I'm to get an A in the course, which I fully intend to do, I will have to buckle down.

One of the stories Dr. Purdom told about Knuth that seemed characteristic was that when he showed up at Case Western the dean gave the standard speech about how one in three wouldn't make it to graduation. Knuth took that seriously and so resolved to do all the problems in his Calculus book, whether or not they were actually assigned. Asked whether this didn't take up too much of his time, he responded that no, in fact it took up only slightly more time than doing only the assigned problems, the reason being that if you do all the problems you get really good at the subject and so can finish the assigned problems faster than you otherwise would. Or, in other words, "slow and steady wins the race." I have seen so many examples of this in my life - of people who have this kind of discipline getting where they want to go.

In that spirit, I have resolved to save my Algorithms grade by reading the first three volumes of Knuth's masterwork. Once a year I embark on a 6-week discipline project of some kind - usually vegetarianism. I've already filled that requirement this year (had no meat from the second week of January to the end of February), but it never hurts to do it twice. Finishing Knuth's book in 6 weeks will mean reading 50 pages a day - and I'll still come up 200 pages short, I think. But these are foundational textbooks in Computer Science; I should read them anyway, and this is a great excuse to do so.

This blog will document this project. The main point, really, is to keep me focused on it. If I have daily reports to write, I'm unlikely to give up and go back to reading Purdom's book.

Of course, I will also maintain my regular blog.

I wouldn't be Knuth for the world. I like my flaky personality. Stodgy people are good for the economy, which is great because the fact that they're around means I don't have to be one. But it's interesting to try to be one for a day (or six weeks, as the case may be). I can't really imagine what life would be like if I actually did everything I set out to do (and knew how to only set out to do things I would do - which is the real secret to being one of these people), but projects like this are a good way to get a taste. Wish me luck.