# Back from finals!

I haven’t posted anything for the last few weeks as I was busy with finals. Now that I’m (almost) done, I will have a lot more time on hand to do (and read!) interesting things which I can then write about.

This semester was my last at McGill and it feels a bit strange to think that I’m done with my undergrad. As I hadn’t done any elective courses over the previous three years, I had completed all my degree requirements but still had a few credits left over to do with as I pleased. I picked a few upper-year courses in Philosophy and Computer Science, and although I probably should’ve picked courses which would have been better for my GPA, I couldn’t turn these courses down.

Algorithm Design

The COMP course on algorithm design I have done this semester has been the most interesting computer science course I have done so far. It dealt with graph theory, network flows, and dynamic programming. To illustrate, here is a sample problem on network flows:

As a response to natural disasters, we want an algorithm to assign ‘n’ injured people to k hospitals. There is an unlimited supply of ambulances, but everybody should be transported to a hospital within a 30 minute drive of their current location. Finally, in order to balance the load, every hospital should  receive at most ‘n/k’ people. Describe a polynomial time algorithm to accept as input an ‘nxk’ array of driving times which will decide if a balanced assignment of people to hospitals is possible, and provide an assignment of each patient to each hospital.

Network flow solutions and algorithms find particular application in matching problems (as the one above), so I’m thinking one application could be in Auction Theory or perhaps in market micro-structure design. I will have to read more into both these categories to see if and how network flow algorithms are applied. I also read a paper a while back which used network flow analysis to determine the spread of a liquidity crunch across financial institutions. Interesting stuff.

Dynamic Programming

Dynamic programming was, for me, the most difficult to get my head around. Both network flow and dynamic programming problems remind me of the types of problems you would see in a math puzzle book, just made more formalized and mathematical. As an example, here is a dynamic programming problem:

“Consider a 2-D map with a horizontal river passing through its center. There are ‘n’ cities on the southern bank with x-coordinates a(1) … a(n) and ‘n’ cities on the northern bank with x-coordinates b(1) … b(n). You want to connect as many north-south pairs of cities as possible with bridges such that no two bridges cross. When connecting cities, you can only connect city ‘i’ on the northern bank to city ‘i’ on the southern bank. Write an algorithm which gives the best possible pairs of cities to connect such that no bridges overlap.

The problems associated with both network flows and dynamic programming look deceptively simple. Once you start working on them you realize their complexity and after you have been working on them for a while, they become simple again. You begin to reduce new problems you encounter to old ones you’ve already seen and structure their solutions accordingly. For example, the one above can be reduced to something called the ‘Longest Integer Sequence’ problem and the solution can be obtained fairly easily after that.

Applications