Problem Solving & TopCoder

There's no argument in the fact that problem solving is a vital part of our intellectual functions and something that helps keep the mind sharp. Even something as simple as a logic puzzle, such as Sudoku, can help influence our mental well being.

One of my favorite activities to keep my problem solving sharp is participating in competitions at TopCoder, a company dedicated towards providing online competitions in algorithms, component design, and so on. I personally participate in the algorithms competitions. I highly recommend for everyone who can program in Java/C/C++/C# to participate from time to time, even if you feel like you have no chance. If anything, it will keep your mind and your programming skills sharp. The scoring system is based on time, so you learn to gear your mind towards immediately being able to categorize problems and then developing a solution.

Currently, the TopCoder Collegiate Challenge is underway, and I have surpassed my expectations this year. Last year I only made it past the qualification rounds, but this year I have matched that and even made it past two more online rounds. If I am able to make it pass two more online rounds then I would have the opportunity to go to Orland and compete against 47 of the world's finest. I don't expect to make it this far from a realistic point-of-view, not a pessimistic one. Nevertheless, I will definitely try my best to make it even further.

Don't think it's just your physical self that needs to be kept "in shape"!

WADS 2007: Days 2 & 3

D A Y 2

Session 5 (Invited Talk)
The day started off with an invited talk from Michael Langston from the University of Tennesse. The talk was on challenges in data analysis, and how sometimes you can have beautiful data to work with (good correlation, easy to work with, e.t.c.) and sometimes you can have tough data to work with. Although not particularly intriguing to myself (I'm still leaning towards a more theoretical area of research), the things he described are exactly the things I have experienced this summer with my cross-disciplinary work. All and all this was a good talk.

Session 6B
I missed the very first presentation in this session, but the second one was about Steiner trees again (everyone loves a Steiner tree). Not quite computing, because that is NP-Complete The session ended off with computing minimum-depth planar graph embeddings in quartic time. I enjoy graphs so I also enjoyed both of these talks!

Session 7A/7b
This session really wasn't doing it for me so I skipped it. I probably should have looked into the computational geometry presentations taking place in 7A though because it is starting to interest me somewhat.

Session 8B
I checked out some parameterized algorithms and kernelization algorithms. Nothing much to report besides the fact that it wasn't overly exciting! For those who are unfamiliar with kernelization, it's simply taking a problem instance and breaking it down into a smaller problem instance. From here we solve this smaller problem instance and from it we can extract the solution to the original problem. This is a common technique in creating algorithms that have good bounds for running times when analyzed parametrically.

Conference Dinner
Lobster! Nothing to say about the dinner besides for the fact that it was delicious. I joined a few of the PHD/Masters students - Aaron Lee from Carleton University, Cora Borradaile from Brown University and another guy from Calgary whose name escapes me at the moment - at the pub next to the Alexander Keith's brewery after for a couple of drinks. Good times!


D A Y 3

Session 9B
I sort of slept in through these...

Session 10B
Approximation of graph distances and shortest paths. Nothing particularly interesting to point out. I just enjoyed going to all of these graph theory talks because I'm not completely out of the blue when they mention crazy terms and the like.

Session 11B
To end off the conference were two sessions with four presentations. The first two involved suffix arrays. One of the grad students which I was fairly familiar with over the course of the past couple of days, Orgad Keller from Israel, done an excellent job at presenting his work (clarity, leaving out the overly complicated details, e.t.c.). The third talk was interesting; it dealt with streaming algorithms, those which receive input in a stream and use much less space (a fuzzy term, I know) than the actual amount of data. They proposed optimal (or maybe ti was near optimal) ways of solving the straggler identification problem. The last presentation I left for, because it was on TCP acknowledgment.

It was all over and Jason was saddened because he enjoyed his time at Dalhousie. But alas, all good things must come to and end. Back to the ol' grind now and in a couple of weeks school starts again. That's kind of exciting too. . . for now.

WADS 2007: Day #1

I figure I should write a blog entry now before I actually forget what happened yesterday!

Session 1 (Invited Talk)
The day started with a presentation whose major title was "Finding small holes" given by Jeff Erickson. It was a small talk on computational topology. It was surprisingly interesting and I was very intrigued overall by the area. The presentation placed an emphasis on a practical application of itself, which was surface reconstruction from potentially noisy data. The processes described showed how surface reconstruction could be done much better by taking advantage of computational topology. No actual algorithms were presented, but the ideas to establish the algorithms were.

For all of you with low G.P.A.s and thinking you wouldn't really be able to go beyond an undergraduate degree because of it, think again. Jeff Erickson cracked a joke about him being potentially one of the lower G.P.A.s amongst most professors with a 2.4/4.0. Doing well in undergraduate studies doesn't necessarily mean you're prepared to do research and be a professor, and similarly for not doing so well you could be perfect through graduate studies. If it's something you would really like to do, get out there and do it!

Session 2B
Nothing particularly interesting here besides for the last talk of the session. At first I thought it was going to be ridiculous because they themed their talk around Donald Duck and Uncle Scrooge, but it was actually quite interesting. The paper was called "The Stackelberg minimum spanning tree game." Their problem was to take a graph with some known and unknown edge weights, and fill in the edges with unknown weights such that the MST maximizes the sum of the values of the weights given to the unknown edges (sorry if I lost you there). One of the characters which presented this talk was Erik Demaine, a guy who came to Dalhousie at age 14 (I think that's right). He's 26 now and is a professor at MIT. The man is brilliant and quite comical also!

Session 3A
I probably should have went to session B here because this session was completely about graph drawing, which isn't a real particular interest of mine. It was cute, but that's about it.

Session 4A
A couple of interesting computational geometry presentations in this session: steiner trees, art gallery problems, and Delaunay triangulations. The last one was particularly interesting because of the reference to one of its practical applications, which is triangulating GIS data for 3D representation. I enjoyed these talks and I think it gives computational geometry a +1 on my list of things I would potentially do for my thesis/grad studies.

All in all, a great day!

GSoC + WADS 2007

The GSoC is nearing an end and there's not much to do really. I think once I get back home on Saturday I'm going to completely look over my Geometry module and see what little things I can do to fix it up (documentation, refactoring, etc).

The WADS 2007 conference reception was last night, and I met some interesting people from all over the world. The talks seem like they'll be fairly interesting overall, with some neat algorithms coming forth. For now I'm lacking something to blog about, but after the day is over and I have taken in some of these presentations, hopefully I'll have something interesting to write about! Note that I'm really liking this Dalhousie CS building over the CS department at MUN (i.e., our corner in the engineering building)

End of July Update

Yet again, not much to update on. We're just beating away at the newly merged trunk and trying to fix up some issues before the 0.5 release. After that it'll just be more issue fixing. Considering this summer I've been taking a course on ordinary differential equations I may consider working on the facilities in SymPy that solve ODEs. Only one more month left to the summer but a lot has gotten done. I'm looking forward to it though, to see what state SymPy is in.

I'm also looking forward to school starting again. Ignoring work, this summer has been far from what I hoped it would be, but I'm probably partly to blame for that one. As for school, I'll be taking these courses:
  • Integration and Metric Spaces
  • Abstract Algebra
  • Combinatorial Analysis
  • Computer Graphics
  • Computational Complexity
I'm not looking forward to the first one, but the rest of them should be alright. Although it might be a bit of work, I expect Computer Graphics to be somewhat enjoyable, or as enjoyable as a school-related item can be! This year will be my last year of regular courses. I'm hoping to have another research award next Summer and then the Fall following it will be my honors thesis, and I have no idea what to do for that at the moment. So at the end of '08 I'll officially have my undergraduate degree from MUN: a joint major in Computer Science and Pure Mathematics.

GSoC Update

It's been quite some time since I've had an update, so I felt like it is only due time to write a little something. There's been a lot of "off to the side" work. Preparations are currently under way to merge the research branch of SymPy with the actual trunk. This is a fair amount of work, and hence we're trying to coordinate everything so that things run smoothly. I have rewritten unit tests to be supported by py.test, but there is also the moving/updating of tests from the trunk and ensuring modules still work along with their tests. This whole merge will be my major task for the next little while.

I will be heading to WADS 2007, the Workshop on Algorithms and Data Structures, during mid August. It is a conference that [sort of] deals with my current research area so I was advised to go. I'm doing so for not only that reason, but also because I would like to see if the academia lifestyle is the one for me. The conference looks to have some interesting papers, and I bet there will be some interesting people to meet.

Approximations

My latest work involves upgrading the approximations implemented in a lot of the evalf() methods, along with adding some new approximations. Problems with precision caused the older evalf() methods to evaluate incorrectly. Although the error was little, to someone actually asking for high precision results would probably consider it quite significant. There was a lot of work to be done, but I have most of it working now, albeit some of the new series approximations I have implemented converge slowly in large domains, they are at least there as a foundation. When working on this I came across a lot of small bugs that were floating around and fixed them also.

After finishing this I was able to use arc cosine approximations to ensure that Polygon.angles was returning correct results (or at least for the test cases I wrote it works!). After I get a few more test cases written I'll be committing my latest Geometry module work and then consider working on some more core stuff.

Some updates

I have a midterm on Wednesday, so I've been studying on and off for that this weekend and haven't gotten a whole lot done. I've added some more functionality to polygons (ex: checking convexity). The last thing I want to work on is the ability to fetch a dictionary of {point: angle} entries for a polygon. There'll be a lot of acos floating around, but there's really no other way about it. After I can get a couple of these things done then all I have left is committing the changes to the repository.

I've still been debating moving all of the is_*** (previously are_***) methods to util.py, external of the classes. My only argument against this now is that if someone feels like importing particular things they would have to import the individual functions if they existed in util.py instead of the classes. Because of this, I think I'm just going to keep it as is for now. This single, simple little thing has taken the most thought!

Updates: Interface Changes+Documentation

There hasn't been much out of me for a week, so I decided it was about time for an update. I was feeling a little under the weather all of last week (note that loss of appetite is now my least favorite symptom) and hence did not get a lot of work done, or at least not nearly as much as I was hoping to get done.

What did get done last week was some [very basic] documentation of the interface which, at least for now, exists on my website. I started work on changes to the interface also as suggested by comments on my Decisions, Decisions post (these changes which are yet to be reflected in the documentation). I have decided to go with the "is_" prefix and remove the static method decorators. Tomorrow I'm going to try once more to move all of these methods to an external location (util.py) so that I get the best of many worlds (are_*** prefix, can potentially be used in a more general context, less bloated classes). If that fails I will keep things as they are and move on. At least removing the static methods has taken take care of one thing, and that is hiding the LinearEntity class.

Quick Update

I've looked into changing around the interface a bit, but I always ran into trouble so I've decided to leave things as they are and have begun writing some basic documentation. That's about all that has been happening for the past couple of weeks. Before this week is done I should have the documentation written and then will look into what to do after.

Decisions, Decisions

SymPy
One of the major usability issues I'm finding with the current interface for the geometry module is the static methods that exist. In one way they really make sense since things are grouped together appropriately, but it's extra typing required and the ideas of concurrency and collinearity, for example, will [most likely] be obvious to those using the module. This brings me to a few options to take, and I'd love to hear any one's opinion:
  1. Leave everything as is so one would call, for example, Point.are_collinear() or LinearEntity.are_concurrent()
  2. Refactor all of these static methods outside of the class into a more "global" setting such as util.py so that class prefixes would not be required, hence separating control and structure (Very Model-View-Controller oriented design). Currently the control is in the classes and accesses the private data of each. This option would not access the private data since it will be external to the class itself. This is doable since all pertinent data is readily available through methods or property methods.
  3. Since all the functionality already exists in the classes, simply leave it there and wrap all of them in a more global setting so that less code has to be moved and very little written.

I personally like #2. The classes will become simpler, and I can hide more things. In terms of the latter statement, the reason I like #2 is because I'd like to hide the LinearEntity class as much as possible. It's more or less there to reduce a lot of code that would be rewritten, yet I don't really want it to be exposed. Right now this is the only thing I'm really looking at in terms of the interface, because I think it's a reasonable one. So, any thoughts or suggestions on those options, or maybe a better option that I haven't thought about?

Research
As for my research, things are coming along there too. I really wish I put a bit more extra effort in there since it is what I plan on doing in my future. Progress has been quite limited lately due to the fact that I'm entering the more difficult area of my problem for analysis. The problem is simply Largest Common Subgraph, and currently I'm only doing an analysis under the classical complexity theory (i.e., NP-Completeness). I'm gonna take a close look into a few of the "unknown" areas left and then hopefully start looking into a parameterized analysis of the problem. Parameterized analysis is a big thing for my supervisor, especially since his PhD supervisor was half of the team which developed the theory. I really like it; it's a very practical complexity theory.

What I'm hoping to do is more in-depth literature search, start BibTeX-ing my references and really focus on writing a paper out of this. With both a classical and parameterized approach, along with algorithms for some of the sub-problems that are poly-time, I'm hoping I can get a paper out of this. Maybe I'll also introduce the practicality of the problem with examples from chemistry (such as molecules, and similarity between them). If all goes well, maybe it can even become my honours thesis, or at least a strong foundation for my honours thesis.

Rubber Bands

My latest development is the convex hull algorithm. For anyone who may be unfamiliar with a convex hull, think about it this way: imagine a set of points in the 2D plane. Now imagine stretching a rubber band so that every point is inside the rubber band. Finally, let this rubber band close in on the points. Every point that the rubber band touches is part of the convex hull, and forms a polygon such that every point is contained on or within the polygon. I used the Graham scan algorithm to perform this calculation.

This pretty much completes the functionality that I specified I would do so now it's time to go back and look over everything for usability purposes. I want to make the interface as intuitive and as simple as possible for use. After that, it's documentation stages. Finally, after all of this is done I'll look into other possibilities for the geometry module such as 3D geometry, or possibly consider working on some other stuff in the SymPy core.

Updates!

Since it has been over a week since my last update, I figured I'd just leave a note so that everyone knows what's on the go with my SoC work. One thing I've been doing is profiling the code and making small modifications here and there to speed things up a tiny bit. Some things may be impossible to speed up since I use the simplest possible formulas and whatnot. I've also been looking at the interface, and have been considering how to improve its usability. I haven't came to too many decisions as of yet. I'm hoping that within the next week I can have those decisions made. I am fairly happy overall with the current interface, and think it's fairly simple to use. Once I get that finalized I'll start working on some documentation about the interface, and also a tutorial. I'm also going to go through the code and rewrite the docstrings so that they are a little more than the obvious.

I have been working though, fixing up some simple issues, mostly involving pretty printing. Got to have things print pretty though! I think eventually I may start looking into the match routines and see if I can make them more robust. That's about it for now!

Current Work

So basically I've been kind of caught up this week in a bunch of things. As for my SoC work, I'm working on some core stuff for the trig module, which will include simplification of some trig identities along with trig expansion. Right now what I have gets unbearably slow quite fast, so I'm looking into ways of speeding things up. As for taking an expression and combining it into a single expression, well I'm not worrying about that for now because it seems like it may be much more complex (but I don't know for sure). Things are moving though, and things are going pretty good especially considering the fact that the actual date for beginning coding is a little more than two weeks from now.

Getting There

So the first iteration is nearing completion. You can get a copy of it by clicking here. Most of the functionality is there, but I do not guarantee that it will all work perfectly yet. There isn't a lot missing besides for a couple of things in polygon/triangle, along with some missing ellipse intersections (besides for ellipse/line intersection). You can give it a try, but there is no document describing how to use it right now. The layout of code is very similar, but not the same, as the UML Diagram I created before starting.

If anyone decides to give it a try, give me some feedback on the interface and how easy it is to use, some suggestions you would make, some errors you encountered, and your own test cases that fail. All feedback will be greatly appreciated. One of the things I didn't plan on doing but may work on later is reporting to the user what conditions will make something True. For example, if the user asks if the points (1, 1), (2, 2) and (x1, x2) are collinear, there is no way to tell. Right now the system will return False, but why not be a bit more informative and return some structure, or raise some exception saying that it would be True if x1=x2. Maple works this way.

There's still a fair bit of work to do, but at least a "proof of concept" implementation is in place. The set of test cases I've been using are also available if someone wants to look at them for ideas on how to use the code.

Things Are Coming Along

The current update is basically focused at what's been done, and what's left to do. I've mostly finished off line, ray, segment, points, ellipses and circles. Most of what's left to do is in ellipse (intersection primarily). Now all that is left to do is Polygon (general, regular, and triangles as a specific case). Note that I have a pretty extensive set of test cases in place for what I have done. I have been doing these test cases incrementally because it's easiest this way. Once everything is done though, I will start working on a much more complex set of test cases to truly test the module.

After these things are done I'll take a step back, look at what is done and see how to improve the overall interface. Once that is done I will look into optimizations of existing code. Finally, to finish off I will look into some more advanced geometry applications. One thing I'm waiting on is simplification to be done in SymPy (which I believe is ratsimp's eventual purpose). This is because a lot of comparisons are happening which compare some expression to zero, and even though some things should be zero they are not coming out that way because proper simplification of expressions is not happening. Right now I'm just expanding things and hoping they come out to zero (which in most cases they do).

Now, for some decisions that have been made:
  • Line/Ray/Segment inherit from LinearEntity. This allowed me to write less code while still having everything meaningful. At first I was going to have Ray/Segment inherit from Line but this doesn't make sense.
  • In terms of everything, many functions depend on others so that optimizing will generally take place in less places. For example, for Line I have random_point and arbitrary_point functions. Instead of rewriting code I make random_point get an arbitrary point and then make substitutions
I'm hoping to update design.png soon to reflect what I have done. Work starts tomorrow but I'm hoping to have most of the basic functionality finished by the end of this weekend.

Brownie Points

It seems I always do my best work late at night; I just finished off the Point class, all except for one method which depends on the Line class. I also have a test method created for the Point's methods. Tomorrow I'm hoping to [at least] get the Line class finished, along with its children (Ray and Segment). Monday I hope to finish the Ellipse and Circle classes. I'm hoping that things will move quickly and smoothly so that I can begin working on the different polygon classes also. Once I get all the simple functionality done I can start working on more complex things.

Tuesday marks the start of my research work, which for the first couple of weeks will simply be my supervisor teaching me some different complexity theories and how to work with them. Should be interesting, but I'm anxious to start getting into an actual research topic. I'm hoping that everything will run smoothly (i.e., that I understand things instead of struggling with them) so that my supervisor and I can get into a problem as soon as possible! I've been reading Computers and Intractability by Garey and Johnson to get up to speed on everything!

Design Is Started

Just a quick update. I've got a pretty good start on the UML diagram for the foundation of the geometry module. You can get to it by following the My SymPy Workings link to the right or go to it directly by clicking here. This is just an initial, very basic diagram for the moment, and some things aren't really descried in the diagram. For example, Some things I have as methods but they might really be attributes fetched by an overloaded __getattr__ operator (eg, area for Polygons and Ellipses).

Any feedback on the current diagram, or suggestions for additions, would be great. Now, it's time for bed!

The Return

So home is as boring as always; No surprise there. One good thing about going home though, was that I managed to find a book that I had hanging around from grade 11, simply titled Advanced Problems in Geometry. This book will be excellent for my Summer of Code work since it will give me a large set of tougher problems to use as grounds for testing. I'm hoping to really get at the design tomorrow, and have a few diagrams and documents up at the end of the week describing the design that I am going to start with.

Home Sweet Home

Well, looks like I'll be heading home for the weekend. I probably should since I haven't been home since holidays ended (the end of December). Bringing home my old computer to set up for mom. Installed the new Ubuntu, or Xubuntu to be specific. Besides for a few minor troubles with regards to display everything looks pretty good!

So my research on the possible representations for geometrical entities is nearing the end. The final updates are just about here for the representation research document. The latest update includes a quick analysis of the sources for the Maple geometry module. It was not very easy to go through, but I managed to pull some good stuff from it (mostly formulas for calculating different things). If anyone has some suggestions or ideas regarding the material in the document, please feel free to leave a comment. All feedback is greatly appreciated!

Lots of Research

So the research is in, and there isn't much that is outside of the normal when it comes to representation of different geometrical entities. If everything is a go-ahead then I'll most likely be starting the design planning next week. Getting an early start because this summer is gonna be busy and plus, this stuff is pretty fun to play with. The last thing to do before design planning is reading through a few geometry books to see what I can pull from them. As a side note, if anyone has some links to geometry software that has source or implementation details readily available, links would be greatly appreciated! I actually just found out how to print the source of Maple functions (one's that are not built into the core) within Maple. I guess I'll be going through those tomorrow and seeing how Maple does things for some insight.

First cool thing of the summer is getting to bring math and Python together with the SoC. Second cool thing of the summer is that I get to do some CS research on the side, supervised by one of my favorite professors. This professor also mentioned that he's hoping that I can help him with a paper he's co-writing. If I can give a big enough contribution this could mean the first time I'll have a name attached to a publication. Good material for grad school!

Summer is great, but for now, getting some sleep is gonna be even greater!

Summer Is Here

Today's exam went pretty good. It seems that my alpha-beta pruning technique needs a little bit of work, or rather I need to reduce the stupidity that tends to come forth from time to time. Maybe I'm just not a morning person. Well, at least they're all done now. I can't wait to see the results since I'm doing a little "experiment" this semester. I studied, on average, about 30-40% less than previous semesters and I want to see how significant of a difference this makes.

I checked out a few geometry books from the library to start reading, from introductory to expert. to start reading. Hopefully the intro book will refresh my memory, and the advanced books will offer some insight into more advanced algorithms for different things. Hopefully by Friday I'll have a better idea of how I'm going to represent these geometrical entities. Better yet, I'll probably have the answer to "Why am I going to represent the geometrical entities this way?"

I also done some more Google searching for existing geometry software. I came across a geometry package that sort of does some stuff that I'm looking to do, but it is more GIS focused. I'm going to look through some of the source and see if I can pull anything good out of it. I also checked out SourceForge and found GMath. Most of my other searching just led to geometry software that is outside of what I plan on doing for this summer (eg, dynamic geometry). I'm going to look at these other pieces of software, and if none of my findings go against my current "decisions" then I will probably move on to the planning phase.

I'm expecting this to be a busy summer, but that's just the way I like it. If I'm not being constructive then I'm usually just wasting time. I should probably go to bed since it's 2:30 in the morning!

Beginnings: Summer of Code '07

This blog is dedicated to any developmental stuff that I am working on. Currently that is mostly limited to the Summer of Code '07 Geometry Module for SymPy.

There's not much to say right at the moment besides for my initial start at research, which can be found here. Overall, it has been difficult finding some generalized geometry software similar to what I'll be creating for SymPy, and even more difficult to find available implementation details. Considering this, I will probably begin work on a plan for the interfaces within the next couple of weeks. The number of options for representation of each geometrical entity is small, so it should be fine to just make what seems to be the obvious choice and play with it to see how everything runs.

My Database/A.I. exam is tomorrow, but after that I can get down and dirty with this stuff!