Last day!

So today was pretty much a lot of work on the paper. I wrote the introduction and conclusion and polished up a bunch of sections.

Wow. I've learned a lot! This is certainly not the end of this project: it has a lot of potential to be something that stays around with the CS department even long after I'm gone.

Harvest Time!

This morning, I realized that I'm really starting to get in the flow of my work, and I'm getting a really good pattern. A few moments later, I realized that I have exactly four days before my report needs to be done.

So, I'm harnessing that flow to eek out as many algorithms as I can today and tomorrow, and I'll spend the weekend going back over and touching everything up. I got two more in today: both very useful graph algorithms (I know I said I was done with the graph section, but I couldn't resist these two, and a few sites mentioned they're useful to know).

I have a good handle on dynamic programming, so tomorrow I'll focus on that section.

Dynamic Programming

I finally figured out what's going on with dynamic programming--and it's really not that hard once I wrapped my mind around it. I think I expected it to be really confusing: one of the first sentences in the chapter was "many people have a difficult time understanding it."

It turned out that I've actually used the technique before, I just didn't know what it was called. Anyway, the basic idea is to break up the problem into a bunch of subproblems, each of which needs to be solved more than once. Then, you can store the solutions to the subproblems so you only have to solve each one once.

Wrestling

Today wasn't as productive as I hoped. I wrestled with dynamic programming for a while. It seems to be unlike anything I've ever done, and honestly I thought hard about defenestrating my book several times today. While writing this, I realized that it's probably time to switch sources. I have a couple ideas for other resources to target tomorrow: particularly the TopCoder tutorials.

I'm also trying to find a succinct way to express an algorithm for finding the area of a polygon. So far, I've discovered (1) a formula for the area of regular polygons and (2) the fact that you can find the area of any polygon by breaking it up into triangles. I'm looking for some algorithm to reliably get those triangles--and I know it's out there.

Much Progress

Wow--I've made a great deal of progress today, and my report is starting to look less like a skeleton and more like a finished product.

I wrapped up my number theory algorithms section and took another chunk out of the graph algorithms section. Most of these are really specific algorithms, unlike the ones I focused on in the first week. This means that they are pretty much unchanged when applied to a problem.

My plan for the rest of the week is clear: I've decided on a few more algorithms to cover, and I'll also be revisiting some I've already written about, to clarify with more examples. A big priority is returning to the four main techniques: Complete Search, Greedy, Divide-and-Conquer, and Dynamic Programming. I left them to the end because they're more broad than the number theory, geometric, and graph algorithms--but they're also some of the most helpful.

Euclid's Algorithm

Today I coded up Euclid's Algorithm for finding the gcd. Euclid's algorithm also returns a linear combination of the two given numbers such that the sum is 1.

I haven't yet found an example for why that linear combination can come in useful, though there are many that require finding the gcd.

Beginning Numerical and Geometry Problems!

I'm taking a breather from some of the more general algorithms to tackle some of the more narrowly-defined algorithms. Today I looked at a couple algorithms relating to prime numbers.

I coded up a program to get the prime factors of a number--this took some time, but was perhaps the easiest part of my project thus far. It's pretty clear when this algorithm needs to be used, and there aren't any alterations that need to be made based on the problem (at least that I can think of).

Perhaps most interestingly, I discovered that this algorithm, combined with backtracking, can be used to solve the more common problem of finding all the factors of a number. In fact, one of the particular solutions I worked with in backtracking, generating subsets, is exactly the idea applied here. Basically, the prime factoring algorithm produces the primes, and then the subset algorithm generates all possible subsets of those prime factors. The product of the elements in each subset is a factor.