An algorithm for finding cut vertices

Related Readings: Biconnected Component
Note: kind of similar to finding strongly connected components

Special thanks to JJ & Brent for this!

Maximum subarray problem

This is one of those nice little problems that I used to know how to solve, but I have forgotten over time...

Problem Description: Given a array of n integers, (there can be negative integers), find the subarray which gives you the maximum sum in O(n) time.

Solution (Intuition): Observe that the smallest max sum is 0 (the solution subarray can be empty). Hence, we do not want to go below this number. A positive number contributes to increasing sum (so we take it in), but negative numbers decrease the sum. Hence, the solution subarray must start with a positive number. We have two variables, max_so_far and max_ending_here.

Solution (Code):

Another Ubuntu Upgrade

Just upgraded to Ubuntu 10.10, but not without a few glitches.

1. I did the usual alternate cd upgrade
2. Upgrade froze with about 20% left. Restarted computer but could not boot into X.
3. Decided to use recovery option in grub boot menu
4. Manually mount the alternate cd iso, and ran sudo ./cdromupgrade from terminal. This miraculously solved all problems. It appears to "resume" the upgrade process.

Conclusion: running ./cdromupgrade from cmd line seems like a good idea for future upgrades. Its definitely faster too. It might also be a good idea to defer the Internet update until the upgrade is finished.