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.

Rethinking the "canned" code

Dr. Sykes and I had a fruitful conversation today, and the thing that impacted me most was a new way of writing the "canned" code. Ideally, I can phrase the "core" of the algorithm to contain as much as possible of what will be needed to solve each problem. One idea Dr. Sykes mentioned was to write the core algorithm to manipulate an object (abstracting several methods), then allow each solution to define an object and each of those methods.

I've been writing solutions to several problems using the algorithm, but I'd been planning to include them in a separate document from the main report (to prevent the main report from getting too bulky to be a good reference). After talking with Dr. Sykes, I realized that examples are a critical part of a good reference, so I'll include at least one example for every section of the report.

Graph Traversal Algorithms

Today I wrapped up my paper's section on backtracking, and am still pleased with the organization of Skiena's book. My learning process is shaped by the structure of Skiena's book, but it's assisted by the more in-depth coverage of my "Algorithms" tome.

I moved into the realm of graph traversals. My paper is really starting to take shape both on paper and in my mind. I'm seeking to provide basically a toolbox for problem solvers. That includes coded algorithms, example solutions and analysis, and strategies for knowing when to use which algorithm. So far, the easiest part is coding up the algorithms, and it's not that difficult to apply them to certain problems when I know which algorithm to use. It's more challenging to determine when to use each algorithm (and, honestly, that's the line of thinking which will probably be worth the most out of my month's studies).

Also, while dealing with graphs, I realized the importance of vocabulary. Many graph algorithms are specific for a specific kind of graph, and there are many varieties (e.g. connected, simple, weighted, unconnected). It's important to be able to identify which kind of graph will model the situation described in a particular problem. If you can identify the type of graph which models the situation, implementing it with the right tools is a piece of cake.

Waves of relief...

For some days I'd been struggling because it seemed some algorithms weren't as well-defined as I'd hoped. For example, brute force and divide-and-conquer seemed to me to be less algorithms than notions for categorizing thousands of possible algorithms.

Well, I'm delighted to say that these techniques actually can be systematized. I checked out Steven Skiena's "Programming Challenges" from the library. Opening it up to "backtracking," I could instantly could tell that it would be a blessing for me this month. (Thanks for the suggestion, Dr. Sykes!)

One of my goals is to have a "canned" generic algorithm in code, which can be extended to solve specific problems. Skiena actually uses this method of presentation in his chapters (though not in Python), which should be a real boon for speeding up my process. Once I have enough algorithms generically coded up, along with some example applications of them, I can address the more interesting issue of determining which algorithm to use.

Tomorrow I'll tie up the loose ends with Backtracking and move on to graph traversal algorithms.

A Brief Report

Still writing programs. Look for more news tomorrow night!

The 8-Queen Problem

The 8-Queen problem is also solved using complete search, but illustrates the useful principle of pruning impossible solutions.

Briefly, the problem is to use a program to determine all the possible combinations of 8 queens on a chess board so that no queen can be taken by another. I'm working through each possibility for each queen, while skipping those cases in which a queen is horizontally, vertically, or diagonally aligned with another.

Solved a Recycling Problem Using Complete Search

Today I implemented a solution to the first problem I'll analyze using complete search. I've applied it to a problem that considers multiple cities which each have five colors of recycle bins, and five types of recyclable materials. Each city decides on a certain color for each type of material. A governmental organization would like to choose one city's assignment of colors, and the problem is to choose the city which will require the least amount of total change by all the cities. This problem is best solved by "brute force"--or considering all the possible selections, and counting how many changes will be made. Then, it's straightforward to report the city which resulted in the lowest count.

One of the challenges I'm having with the complete search algorithm is that it doesn't fit my mold for how I would handle each algorithm. For most algorithms, I will be able to write up the "recipe" and modify it slightly for each problem. For complete search, however, each problem requires a vastly different approach. In other words, the algorithm is very general.

Complete Search

This is the most straightforward algorithm. Its basic idea is to examine all possible solutions until the solution is found.

Since it's so straightforward, this algorithm is a bit of an anomaly. It's very general, which makes it difficult (impossible, as far as I can tell) to write up a general recipe. So today I've begun coding up two examples.

Stay tuned for more about the problems and their solutions!

Deciding which Algorithms to Study

Today I put together a list of the algorithms I'll be studying in the coming weeks. I prioritized the list based on the most important and most frequently-used algorithms as discussed in my two reference books and a couple web sites.

Backtracking/Complete Search is the first (and likely most straightforward) problem solving technique I'm studying.