RandQSLet’s talk about algorithms! I’m taking a randomized algorithms course next semester and having never taken regular algorithms, I figured I should do some self-study first. So, basically I’m working my way through chapters 1-5 of the Randomized Algorithms textbook.  The book is actually pretty reasonable, even for someone who hasn’t taken algorithms before.  Ok, now let’s talk about something cool: RandQS.

RandQS is short for Randomized Quick-Sort. It’s an efficient algorithm used to sort lists of numbers.  This is important because, for computers, sorting isn’t necessarily an easy task. If you gave a computer a long list of numbers, it would have to compare every number versus every other number and do this recursively – i.e. look at all possible combinations. This is not very computationally easy!

So, we use randomized algorithms. RandQS works like this:

1. Pick a random number from our list.
2. Take all of the numbers bigger than our random number and make a list. Do the same with the numbers smaller. So you’ll have two new lists.
3. Go back to step 1 with our two new lists. Do this as many times as we need to.

Why is this important? First, this algorithm runs faster than its non-randomized deterministic cousin! Secondly, it’s really easy to implement. This is huge for people who have to design algorithms for sorting enormous quantities of data – like the people who build the sorting engine for MySQL, for example.

Since I am Mathematica geek, below is the relevant bit of Mathematica code, for those of you coming from Google looking for it. Note that this algorithm only works with unique sets but could probably be easily modified to work with sets that have duplicates. You can download the whole notebook file down at the bottom.

SetSize = 100;
S = RandomInteger[{0, 100}, SetSize]
RandQS[sss_] := Module[{sOne, sTwo, y}, (

    (* pick our random element  *)
    y = RandomChoice[sss];

    (* build set larger and set smaller by doing comparisons*)

    sOne = sTwo = List[];

    If[# < y, AppendTo[sOne, #]] & /@ sss;
    If[# > y, AppendTo[sTwo, #]] & /@ sss;

    If[Length[sOne] > 1, sOne = RandQS[sOne]];
    If[Length[sTwo] > 1, sTwo = RandQS[sTwo]];

    Return[Flatten[Join[sOne, {y}, sTwo]]];
    )];
RandQS[S]

Download RandQS.nb

Now that the semester is over and I’ve barely scratched my way through, I’m going to point out some helpful books that other may find useful. I suggest reading these *before* you start an economics PhD program and doing the exercises in the books.

Mathematics for Economists by C. Simon. This was by far, the most useful book available. It provided excellent summaries and explanations for tough topics, such as convexity/concavity, quasi convexity, homogeneity, and linear algebra. It provides some in depth coverage of calculus techniques but I found those to be rather unhelpful. The calculus in the Yamane book below was much better. It’s kind of an expensive book, so I recommend getting this in advance from the library.

A First Course in Optimization Theory by R. Sundaram. This is a tremendously well-written book. In fact, for a tough topic, like optimization theory Sundaram does a really great job. He covers Lagrange, Kuhn-Tucker, Supermodularity, and basic convex optimization. This is stuff that comes up repeatedly in intro PhD micro, so it’s mandatory reading.

Mathematics for Economists by T. Yamane. I got this book from the library because it looked helpful and it is a very helpful book, especially the coverage of calculus. The chapters on differentiation and integration are the highlight of the book. The only problem is that because this book is old, it’s a little bit *too easy*. However, you should go through this book, as a refresher before going onto the Simon or Sundaram texts.

Principals of Mathematical Analysis by W. Rudin. Everyone in economics talks about this book like it is the most helpful book ever written. I found this book to be “ok”. It does provide sufficient coverage of real analysis but goes way to fast and the exercises are not great.  Of course, I’m in the minority on this. Either way, the book is pretty cheap, so you should at least add it to your bookshelf.

Today is the Sunday before my finals week. I actually only have two finals; a large micro-economics final and a take home probabilistic method final. I’ve already spent about 5 hours working on the take-home final and I’m terrified about the micro final on Wednesday night. Friday was the last day of classes, so I’ve had a few days to compile my thoughts about my first quarter.  I have to admit that I didn’t do a very good job following my own advice but I will be following it next quarter.

The below list can also be titled, “How I am going to do better next quarter”

• Study Early, Study Often. This sounds really cliche but it is the most important thing you can do. Do *all* readings, buy all the books required for the course, and after every session, go through and type up your notes. The coursework on the PhD level is so much more intense than a Masters or Bachelors program. I’ve had some course sessions where they covered an entire undergrad quarter in a single session.
• Type up your Notes. See the above comments. I plan on doing this for all of my courses next time. For every hour of notes, you’ll have to spend at least 30-45 minutes reviewing and typing them up.
• Study on Saturday Nights. This sounds terrifying, I know. The nice thing about Saturday nights is that you’ll be the only one studying, so you can get a lot done. I consider this the price of getting a PhD.  I prefer to go out on Friday nights and spend Saturday and Sunday nights studying.
• Try Not to TA Your First Quarter. This may be unavoidable for some but I’d suggest not TAing your first quarter. It can be very time consuming, especially if you’re not totally familiar with the material yourself (or you’re rusty from not having taken the class in a long time).  I had to drop my third class in lieu of my TA position, since I couldn’t handle all of the workload.  However, being a TA is generally a positive experience, so I do suggest doing it at some point.
• Spend Time Outside of the Office. Not all PhD students get an office but those of you that do; don’t spend too much time in your office talking to people. It can be easy to spend an entire workday (9-5) in your office talking to colleagues, professors, etc. If you can get out of your office and go to a cafe or the library, you’ll have more time to focus on the material.
• Walk Everywhere. Being a PhD student means that the only free-time you have will be at times when nobody else in the world is awake (3am, usually). It’s really hard to get a decent workout at 3am – most gyms are closed and you’re probably burned out.  The best way I found to stay in moderately healthy shape was to walk everywhere – from my apartment a mile from campus, to campus, to town, etc.  Also, the food that you’ll eat on campus is probably terrible for you; so you’ll have to work off the extra calories.
• Go to Office Hours. After you type up the material, you’ll probably have a dozen questions that you didn’t ask during class. Go to office hours; it’s a good chance to network with colleagues (other PhD students) and helps with the material.
• Read the Book First. If possible, try to read the course text before the class starts. This sounds unreasonable, but will help immensely and spreading out the work later on.

I drink a lot of coffee. When I lived in Ann Arbor, I would routinely go to 3 or more cafes a day. It was always one early in the day for breakfast, one around lunchtime and then maybe one later in the day. When I was working in Livonia, Michigan, I used to always hit up the great Biggby coffeehouse down the street.

So, when I moved to Evanston, I had to find some good coffee!  It took about 3 or 4 months to figure out the local “coffee scene”. I think I’ve finally figured out a way to stay caffeinated from 6am to 2am. Here is my recommended coffee plan for fellow Evanston dwellers.

6am-noon: Peet’s Coffee (on Chicago by the Whole Foods). Peets definitely has the best coffee in Evanston. It’s usually not burnt and they really brew some good stuff. The downside is that it’s always really busy and sometimes the lines are long. There is rarely a place to sit, so usually I get a coffee and run.

noon-10pm: Unicorn Cafe (on Sherman, closer to campus). The Unicorn is probably the coolest cafe in Evanston. Their coffee isn’t as good as Peets but it is miles better than any chain coffee. There are a million places to plug in your laptop and the music there is really great (lots of good indie stuff)

10pm-2am: Kafeine. It’s a coffeehouse with a waitstaff. I don’t really like this place very much, it’s busy, the service is HORRIBLE, you can’t go on Monday (open-mic), the music is so-so, and it is full of high-schoolers. However, it is open until 1am on weeknights and 2am on weekends. They warm up your chocolate chip cookies too – that is awesome. Fortunately, I can get an insane amount of work done here because I am not interested/distracted by crappy music, high schoolers, or so-so coffee.