tag:blogger.com,1999:blog-3722233.post113388315814190578..comments2024-11-14T17:42:16.782-06:00Comments on Computational Complexity: How I Became a TheoristLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-1133984068294996442005-12-07T13:34:00.000-06:002005-12-07T13:34:00.000-06:00For a change, here's my story.I ended up in comput...For a change, here's my story.<BR/><BR/>I ended up in computer science because I had done well in <I>some</I> IIT-JEE. The only thing I knew about CS at that time was that it involved programming which was interesting. I was happy for not having to study electrical engineering which I would have done if my rank had been a little lower. After that, some fascinating classes on algorithms and theory of computation convinced me.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133942734197304392005-12-07T02:05:00.000-06:002005-12-07T02:05:00.000-06:00So either it's true that Lance has a flair for fic...So either it's true that Lance has a flair for fiction or that he switched to theory for an interesting reason (or perhaps both).<BR/><BR/>But we will never know which is the case. Just like a theorem in complexity... EIP, anyone?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133937189165531282005-12-07T00:33:00.000-06:002005-12-07T00:33:00.000-06:00May be, there was no such question! Lance just wro...May be, there was no such question! Lance just wrote it to make things look more melodramatic!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133929494025038072005-12-06T22:24:00.000-06:002005-12-06T22:24:00.000-06:00I don't remember the equation but I do remember th...I don't remember the equation but I do remember that when I did find out why it was true, it wasn't for any particularly interesting reason.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133919127355640202005-12-06T19:32:00.000-06:002005-12-06T19:32:00.000-06:00I would like to agree with Bryce, that Lance's res...I would like to agree with Bryce, that Lance's response was awesome.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133916138872975192005-12-06T18:42:00.000-06:002005-12-06T18:42:00.000-06:00As a math undergraduate, I liked numbers and was c...As a math undergraduate, I liked numbers and was convinced I would go into number theory. But then, as part of the requirements, I reluctantly had to take an intro to programming course, which was taught with an emphasis on algorithms and had challenging monthly programming assignments. <BR/><BR/>First programming assignment: the stable marriage problem. I was frustrated by my inability to prove correctness of the algorithm. (students were supposed to come up with that proof as part of the assignment).<BR/><BR/>Second programming assignment: red-black trees. A total nightmare, with messy pointers all over the place; I was unable to finish the assignment, even with an extended deadline.<BR/><BR/>One question asked for an estimate of the average height of a tree containing n values and was the occasion of a serious headache -- we had zero probability background and it took a while to realize that the uniform distribution was not the same as the distribution obtained after inserting n values in random order.<BR/><BR/>Third programming assignment: quadtrees and 2-d trees. A comparately pleasurable way to explore recursive programs. I thought that that was magical and fascinating!!<BR/><BR/>Then there were some memorable lectures on sorting algorithms. For some inexplicable reason, I thought that the n log n average running time of quicksort was the coolest thing I had ever seen.<BR/><BR/>So, that's how I became a computer scientist, via the powerful attraction of programming, and a theorist, via trying to design and analyze algorithms for my programming assignments.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133915186702327322005-12-06T18:26:00.000-06:002005-12-06T18:26:00.000-06:00For me, one turn off to CS PhD programs was that t...For me, one turn off to CS PhD programs was that there seems to be a pressure to find and advisor and start publishing immediately. This attitude seems less prevalent in math, where it is expected students will spend a fair ammount of time learning a subject area. Although its annoying that one is there mostly because universities need billions of calculus TAs, it also means there's more of an opportunity to really size up the different things you could be studying without being pressured into commiting immediately.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133900779804046932005-12-06T14:26:00.000-06:002005-12-06T14:26:00.000-06:00I think it is true that *some* bright students in ...I think it is true that *some* bright students in math go into other fields, especially CS. But I don't think there's anything to complain about. Enough number of the best and the brightest stay in math that it thrives (at its own pace). In fact, if every mathematically talented person stays in math, the market for mathematicians cannot absorb them (of course, they can become school teachers and do some good). It is actually good for everyone that some of them go into Physics, CS, Finance, etc..Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133893978240549212005-12-06T12:32:00.000-06:002005-12-06T12:32:00.000-06:00I heard occasional complaints from mathematicians ...I heard occasional complaints from mathematicians that they were losing bright students first to physics, then to CS. This blog's readers are not a good sample to prove this, of course. <BR/><BR/>Is their complaint substantiated?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133892591853753932005-12-06T12:09:00.000-06:002005-12-06T12:09:00.000-06:00I started as an undergrad in pure math. I asked my...I started as an undergrad in pure math. I asked my Calculus II teacher who had a C64 at home to teach me how to program, just for general culture (back then we had no generally available computers at the math department). <BR/><BR/>He was a really busy higher up honcho but he agreed to teach me, provided I showed at his house on Saturday from 7:00 to 12:00am. I learned to write programs in basic, but didn't get really excited about it. <BR/><BR/>Then one day, a classmate I liked was having problems with her programming assignment which was due next day. So I decided to read the entire book overnight and identify the bug. It was some arcane 'only-in-apple-pascal' reserved word problem. It was only then that I realized that there was great beauty (pun intended) in the world of computer science, and that the deep ideas behind CS were highly mathematical in nature. <BR/><BR/>I completed my undergrad in pure math, but focused all my electives in CS theory: graph theory I and II, game theory, complexity I and II, advanced data structures, operations research, programming languages and grammars, numerical analysis, probability I and II, measure theory, etc.<BR/><BR/><BR/>Alex Lopez-OrtizAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1133886888501538862005-12-06T10:34:00.000-06:002005-12-06T10:34:00.000-06:00Similar story, except I was majoring in math. In ...Similar story, except I was majoring in math. In some advanced algebra class, I was watching the prof do a proof. I realized I could follow every line, but I had no intuition as to where the proof was going, and why I cared. On the other hand, Harry Lewis's automata theory course and Michael Rabin's randomized algorithms course seemed, well, so beautiful, real, and intuitive. <BR/><BR/>I'm glad I found TCS. It just goes to show you really should experiment and try new (intellectual) things in college. Despite this, I still always, always feel I should have taken more math classes...Michael Mitzenmacherhttps://www.blogger.com/profile/06738274256402616703noreply@blogger.com