Sunday, September 24, 2006

It's another AssignmentRush(tm) time!

I have just given up on trying to optimize my graph algorithm for CS220. It is now 6:20pm, I finished it (all functions working) at 4pm...it's due 8:30. Pretty much all day yesterday and today, that's what I was doing.

And then tomorrow morning, I need to compose the start of my gestural piece so I can hold Eve off for another week, then the rest of the day it's CS210 time (already done some of the work but only about 10%). Then, if I need it I have all of Tuesday as well (and I probably will need it) - it's due Wednesday noon, but I have Holiday Programme on Wednesday (which means I need an earlier night's sleep as well). Being able to drive to work and back is going to be really helpful. Then, Thursday I'm going to work with Ajita to analyze a Bach fugue, and write a 1000 word essay which is due on Monday.

I don't like these busy periods, but it's always better on the other side. Next week hopefully will be breezier. Maybe. Probably not, cause CS210 has another assignment due two weeks after, and it's way harder. And I have to do more work on my composition major piece. And marking for CS101 is gonna come in any time now, and I also agreed to do Shari's duo piece which means I have to practice it (and check stuff). In light of this I probably won't do my own duo for a workshop. I'm too lazy.

I cannot wait for the holidays. So I can get a job. And spend my entire holidays working. Yay.

The dude said he'd get the lady to call me back. They haven't yet.

I wonder if they will call tomorrow. I need money.

---

So what does my CS220 program do? I actually had to write four, but the one I just finished takes in a graph:

something like this

(0)----(1)
.|..../.|..|.../..|..(2)./..(3)...|./....|...(4)
.|/.....|....|
(5)----(6)--(7)



And detects how many unique cycles of length 4 there are. A cycle is pretty self explanatory; 0 --> 1 --> 5 --> 2 --> 0 is a cycle. 2-->0-->1-->5-->2 is the same cycle, so the program cannot count that.

Seems easy, but ;_; took me freaking forever. I finally managed to get it to work though; it generates a BFS traversal search forest to a depth of 2, detects which pair of nodes have shared parents and children (because if a pair of nodes have the same parent and a shared child, there is a four cycle parent --> left node --> child --> right node --> parent) And then it only counts it if the parent is the smallest node and the left node is smaller than the right node (this ensures only unique cycles are counted).

One of the sample inputs we were supposed to test our program with has 3000 nodes.

It takes the computer approximately one minute to tell me that in that graph, there were 31299961 unique cycles of length 4.

Yes.

Apparently, you only get full marks if it does it in 45 seconds. I spent two hours trying to tweak it without much success; I need a better algorithm. I stopped caring - at least I got it working. Working should be more marks than slow, right?

Hope so.

The program is so computer intensive that every time I run it, my computer fan goes berserk to start cooling itself down.

No comments: