ICPC @ TUM and a Quick State of the Union

Guess what's coming to TUM:

Alright, you didn't actually have to guess.
The ICPC is a yearly programming contest at universities around the world, so naturally I was very excited today to find out that TUM is also participating. Teams can have between two and three members, and I've already recruited Robert for my team, which is definitely something to be excited about aswell, given that he's been coding since he was about 12 years old.
I've been doing a lot of problems on Project Euler lately, in fact I've recently hit 50 solved problems, but competing in a live event will be a very different feeling I expect.
The competition is Saturday in a week (04/02/2012), and will go on for 5 hours as far as I know, during which everyone needs to try and solve as many out of 10 problems as they can. On first glance I was hesitant to spend all Saturday at uni, but then I found out there's gonna be pizza so that was that.

If you're studying at TUM and are looking for a team to join for ICPC, drop me a comment here or send me an email! You can find more info on ICPC here: http://cm.baylor.edu/welcome.icpc and here: http://icpc.in.tum.de/index.php/Main_Page

By the way, Robert is also the guy who's working on the WikiGraph (still unsure of that name) project with me. He's been talking about starting a Blog, so I'll be sure to post a link on here once that happens. Seriously, the guy has skills.
Speaking of Wikigraph, there are some news on what's going on with that as well:

• We're getting good graphs for networks of up to fifteen thousand or so nodes, but beyond that our computational capacities don't allow for completing graphs in a reasonable amount of time.
• I've talked to two of my professors, and it looks like we may be able to get time on a 30-40 core cluster to run our program, which might allow us to graph the entire German Wikipedia (1.2 million articles). This would be pretty amazing, but we're definitely going to have to work on properly scaling the algorithm so we don't get buggy as the network gets huge. 
• I'm also working on a way to read the input from a database (specifically the Wikipedia dumps of all pages and pagelinks, which is available at  http://dumps.wikimedia.org/), but I'll post some technical stuff on that later. The gist of it is that I have to combine the pages dump (320MB) and pagelinks dump (2.6GB) to get a full description of all the connections. I'm still unsure of what the best way to do it is, and I don't want to waste time trying to do it inefficiently when dealing with these huge amounts of data. Finding disconnected subgraphs may also present itself to be a problem.
• Different datasets are also being worked on, one thing I'm particularly interested in is mapping Darknet/Meshnet, so I'm looking for a way to actually extract the entire set of nodes and their connections. I'm not sure if it's actually possible either, I'll have to look more closely into it.
• Finally, I used some of the source code from this project to create a simulation of planets/particles interacting through gravity - a planetary system, basically. It's almost more fun to play around with, in fact. Also more on that soon.

9868 nodes in WikiGraph

Ha! I located one of the bugs, apparently the setting of the repulsion strength parameter in the balancing algorithm caused the flying off into infinity of nodes. I fixed it, and right away managed to graph almost 10,000 articles centered on Mathematics! I could probably go larger, but each of these Graphs is taking up to half an hour to fully balance on my computer. Let's see, maybe TUM has a nice multicore machine we can use for a bit...

Completed Python Logic Circuit Simulator

Project website

Logic gates are interesting, with a few of them you can create circuits with fairly complex functions. Most of the time, the function of the circuit is anything but obvious from just looking at it. For example, consider this one:
That's an adder. You set the inputs A and B to True or False ( 1 or 0), and the circuit will perform a binary addition where S will give you the sum of the two, and C_out the carry bit. The carry bit can then be fed into another full adder at C_in, and you'll also have two more inputs. This can be expanded to any size one wishes.
All currently functioning computers rely on such gates. Most likely, millions and millions of them are in your cellphone.

If you're at least a little familiar with formal logic, more specifically logical connections such as "and", "or", "nor", "xor" (="exclusive or") and so on, the way these circuits work will probably make sense to you very quickly.

I've written a few posts recently about a logic gate simulator I am writing in Python, pyGates. I won't say I finished it, because there are still a few bugs that come up every now and then, but it's far enough along for others to use. Here's a screenshot of what it currently looks like:


You can create new gates by simply dragging them from the left side of the screen, and destroy them by simply dragging them back there. This is actually the only part where I still get bugs every now and then, sometimes cables don't get destroyed properly, but I'll work on fixing this. For now, you can usually work around that by manually deleting the cable - detaching it from the other gate it is connected to, and clicking into empty space.

The website for the project, a zip file with everything you need and the raw source code is located at my website here: http://home.in.tum.de/~dowling/pyGates/.