## Better Old Programs

May 14, 2011

Long story short, well more like short story even shorter, I got a new laptop and reinstalled Ubuntu 10.04 on my external hard drive.
Don’t worry I had a separate home partition so most of my important files were saved. However, I still have to get back some programs and libraries that I liked using. So this post is going to document what I did to get them each back. Mainly this is for my own personal use since I know that I will most likely have to solve this problem again at some point in the future.

## Mozilla Firefox

Now there is nothing wrong with the version that Ubuntu supplies, that is until a new version of Firefox is released. So all you really need to do is to your repository with the following commands:
 sudo add-apt-repository ppa:mozillateam/firefox-stable sudo apt-get update && sudo apt-get upgrade 

## Amarok 1.4

This is just a personal thing. I’m sure that the new Amarok is a wonderful program, I am just more familiar with the old version. That being said, getting this to work is a little more complicated that ‘fixing’ Firefox.
 sudo gedit /etc/apt/source.list 
Well you can actually use whatever text editor you want, I just put gedit since it will most likely be what most people (non-linux users) are used to.
Then add the following lines to the file (I added them to the bottom but don’t see why you can’t add them anywhere else)

 deb http://ppa.launchpad.net/bogdanb/ppa/ubuntu jaunty main deb-src http://ppa.launchpad.net/bogdanb/ppa/ubuntu jaunty main 

If you have any other version of Amarok installed you will need to remove it.
 sudo apt-get remove amarok* && sudo apt-get autoclean 
Now you can install what you want
 sudo apt-get install amarok14 

Hopefully there were no errors. If you got something about a mysqlclient15 file then go to this site, download the file, then run the last command again.

## Getting a Boost

March 11, 2011

Most of you that use C++ (and some of you that don’t) are sure to have heard of Boost C++. I won’t go into what it is, since if you want to know that just follow the previous link. I will however talk about the “installation” process. This is mainly for me, in case I ever feel like putting it on another computer, but I suppose some people might find this useful.

## Step 1

Download Boost, I would recommend the latest version but it’s your call. You can find download links by going to the Boost website and doing a little “read-n-search”, aka using your brain. I will assume that you have downloaded the file (let’s call it FILE, and assume it is has extension bz2) to your desktop. Open a terminal and move to where you would like the Boost files/libraries/binaries to be located, call this $BOOST. In short you just run the following in the terminal:  cd$BOOST tar --bzip2 -xf ~/Desktop/FILE 

## Step 2

At this point you are more or less done and are able to use quite a few of the provided libraries. However, there are some libraries that need to be built. So let’s go ahead and build them all, since you never know when you’ll need one, and you aren’t that strapped for space on your system.

## Step 4

Hopefully, you have made it this far without any errors. So it is time to test that everything actually works.

//ASSUME THIS FILE IS CALLED test.cpp
#include <boost/regex.hpp>
#include <iostream>
#include <string>

int main()
{
std::string line;
boost::regex pat( "^Subject: (Re: |Aw: )*(.*)" );

while (std::cin)
{
std::getline(std::cin, line);
boost::smatch matches;
if (boost::regex_match(line, matches, pat))
std::cout << matches[2] << std::endl;
}
}


Use the following to compile
 g++ -o test test.cpp -I $BOOST/boost_1_46_0 -L$OTHER_PATH -lboost_regex ./test 

If there are any mistakes or if you have any suggestions let me know. I know this isn’t the best walk through but I think it’s better (for beginners) than the one presented at the Boost website.

## Learning CaCO3

December 1, 2010

In case you are wondering, and are too lazy to head over to Google, CaCO3 is the chemical formula for a pearl. With that tidbit of information in hand it shouldn’t be too hard to guess that in this post I am going to tell you that I have decided to start learning Perl.

This all started a few days before (American) Thanksgiving when I was a little bored and didn’t feel like doing course work. Originally the plan was to learn Python, but somehow I ended up reading stuff about Perl and was hooked. There are quite a few online tutorials out there to help you get started, some better than other in my opinion. For me the problem was finding one that was targeted at my level and could keep my interest. Sure I didn’t know how to program in Perl but I knew C++ and some Java and after seeing a few examples of Perl realized that the syntax wasn’t all that different. So the tutorials that held your hand while explaining what a variable was got boring rather quickly.

In the ended I chose to follow one that skipped all the “baby stuff” and just said, “Suppose you had problem X to solve. This is one way you could attack it.” Then it would provide some lines of code explain what a few key words meant and leave you to figure out why and how it worked. The only time the tutorial didn’t stick to this format was when they introduced regular expressions. The first paragraph for that section explained what a regular expression was and did a little hand holding. But after that it was back to “figure it out yourself from example code” business as usual.

The one thing that was beat into me was that there is always more than 1 way to do something. Also whenever in doubt of if something is possible I remember this quote “Can I do that? OF COURSE, THIS IS PERL!”

Well off to learn more Perl and write more scripts.

## Smart Phone Data

November 21, 2010

At this point I am sure that you have heard about cell phone companies trying to limit data use (at least in the US).  Sure I’m not a huge fan of this move but I understand why the change is underway. Some providers (like T-Mobile) still offer unlimited plans.  However, to limit use even for these user T-Mobile supposedly reduces transfer rates once you exceed 5GB of data use.  This shouldn’t bother too many people since getting close to that limit is very hard.

When I read that last bit of info about T-Mobile it got me to thinking, why not charge for speed and not amount? The strain on the networks is coming from the large bandwidth demand which is slightly related to the amount of data a person uses.  If instead of partitioning individuals based on amount of data used, instead do so based on how much they are willing to pay for speed.  Cable and DSL providers have been doing this and it seems to be working just fine.  Furthermore, with capped speeds you in some ways have also set a theoretical limit on data usage. Plus I don’t think you’ll lose money if you use a reasonable pricing model. Most of the high data users will want the faster/fastest speeds, as it will be the only way they can continue  doing what they have been doing.  The real bonus is that some more moderate users will be willing to pay for higher speeds resulting in a gain for the company.  This won’t put anymore strain on a network since as things are, everyone is getting “premium” speed.  So why not cut some “dead weight”?

This post was typed on my Nexus One so please excuse any spelling errors. I have tried my best to eliminate as many as possibe.

## Inclusion Exclusion

August 22, 2010

I am sure that most of you have heard of the inclusion exclusion principle.  If not then I suggest that you either head over to Google or Wikipedia.  It is a really useful technique with many applications; even to this day I am still discovering new ways in which it can be used.

In this post I will outline a partial solution to the following problem located on SPOJ, PGCD.

The first thing you should notice is that the answer to (a,b) will be the same as the solution to (b,a).  This is because of the symmetry of the $gcd(\cdot,\cdot)$ operation, thus suppose that $a\le b$.

Suppose that there are $a$ columns in our gcd table.  We will find how many primes there are in each column.  Suppose that there are $m$ rows, and we are looking at column $n=p_1p_2\cdots p_r$, where $p_1,p_2,\cdots,p_r$ are distinct primes.  I’m not going to consider the case where a prime factor is repeated, though I have a feeling that the solution below should still work.

First we find how many multiples there are of each prime between $1\ \mbox{and}\ m$.  This is just

$\displaystyle\sum_{i=1}^r\left\lfloor\frac{n}{p_i}\right\rfloor$

But what about the multiples of say, $p_1p_2$?  Well they were counted twice, and their entry in the table is not going to be a prime (you can easily convince yourself of this fact).  So we just subtract them out twice, leaving our answer as

$\displaystyle\sum_{i=1}^r\left\lfloor\frac{n}{p_i}\right\rfloor-\sum_{1\le i

Now what about the divisors of $n$ with exactly 3 prime factors?  Their multiples have been removed too many times, thus we need to add them back.  If we continue this way we see that we will be using inclusion exclusion.

So to solve this we can use the following code.


#include bitset
#include vector

bitset PIE;
for(int i=2 to n;++i)
{
vector prime_factors=factor(i);
int r=prime_factors.size();
for(int cnt=1 to 2^r - 1;++cnt)
{
PIE=cnt;//express cnt in base 2 and store in PIE
int ones=PIE.count();//the number of 1s in our bit string
int p=1;
for(int j=0 to prime_factors.size() -1;++j)
if(PIE[j])
p*=prime_factors[j];
if(ones&1)//there are an odd number of 1s
else//there are an even number of 1s
}
}

This isn’t totally legal code because I had to paste it into HTML so the less than and greater than signs disappear and I don’t want to waste the time to fix it (even though I know how to).
For those of you that don’t know the bitset is just a string of 1s and 0s. When I did PIE=cnt I basically set it so that the bit string was equal to the base 2 representation of cnt. Using this method we can get all possible combinations of the prime factors.
The code can easily be converted to Java since I think it too has something similar to a bitset. If your language of choice doesn’t have a bit set, no need to worry. You can just get the base 2 representation on your own (it’s not that hard, trust me).
WARNING: This approach will only be feasible if each number doesn’t have too many prime factors. Not the case with the problem on SPOJ since each number can be decomposed into the product of at most 23 primes, and at most 9 distinct primes. So I’m not sure if the time limit will allow you use this method, I haven’t tried, but please let me know if you do.

## Included Files

August 22, 2010

Do you ever wonder where the files you include in your C/C++ programs are located, and how the linker finds them?  Well on a Linux system (unless you have changed things) they are located at /usr/include and /usr/include/c++.  If you go you can see the list of files you can #include in your program.  Additionally, you can view the source code, if you are the kind of person (and I have a feeling that you are) that finds these things interesting.

## Thoughts on my Nexus One

August 4, 2010

Well I’m not the first person to buy a Nexus One in America, but I’m one of the last to do so.  As a responsible consumer it is my duty to share my experiences with you readers.  I’ve had the phone for a little more than a week and thus think I know how I will be using it for the most part. Before I start I would like to mention that the biggest problem I have with the phone is my phone number.  This has nothing to do with Google/HTC, but rather T-mobile, so this little issue won’t be making it into the review.

At first I thought about just having this review be another pros/cons list.  But when I started there were many things that fell into both categories.  So I realized it would be easier, and a little more organized if I just commented on each aspect one at a time.

OPERATING SYSTEM: This is a big plus.  The Nexus One is the only phone currently on the market running a legitimate version of Android 2.2.  Although the phone ships with version 2.1 it starts to download the update soon after activation.  There is a noticeable speed difference between the two versions.  Also the ability to use the phone as a wireless hot-spot is wonderful (in my case it doesn’t cost me any extra for this feature).  The added flash support doesn’t hurt either.  For more information about the update just look on any tech website/blog, or even do a quick search for ‘Android 2.2’.

USER INTERFACE: The screen is usually quick to react to all of touch commands.  When this isn’t the case, it is almost always do to an application freezing, something the phone can’t take all the blame for (I’m looking at you app developer).  The phone comes with 5 screens for you to place icons, for me this is a bit much since I only really use 4.  For those of you that are used to using the HTC Sense UI that comes with 7 screens (or so I have read) this might feel like a downgrade.  Another thing that matters is screen brightness.  You are able to choose between 3 screen brightness levels.  Obviously the brighter the screen the more strain you will be putting on the battery.  I find that the dimmest level is more than good enough when you are inside and the second level (out of 3) is fine when you are in obstructed sunlight.  I don’t know how well the screen manages when you are in direct sunlight but my guess is that even on the brightest setting you will still need to cup your hands over the phone if you want to see more than just large icons (you know…things like text).

KEYBOARD: You should know that I would have preferred the Nexus One to have had a physical keyboard as an option instead of only the on-screen keyboard that is provided.  Since there isn’t much I can do about this (though I think there might be ways to connect to an external keyboard, probably through bluetooth is my guess) I have gotten used to the set up.  If you ever need to type something that is longer than 2 words I suggest that you use the keyboard in landscape mode.  Otherwise your thumbs will accidentally hit wrong keys and increase the number of typos.  The only problem with typing in the landscape mode is that the keyboard takes up most of the screen.  Thus if you need to enter text into more than one area you will have to close the keyboard after each entry.  When using the portrait version you don’t have this problem, but as mentioned before you are more typo prone.

SOFT KEYS and TRACKBALL: I refer to the four keys located right above the track ball as the soft keys.  The trackball is quite useful when the area you need to click is too small for you to accurately do so by touch.  I would prefer that instead of a physical ball it was laser operated, similar to the Droid Incredible.  However, both versions do have their downfalls.  If something goes wrong with the laster/hardware or you damage the physical trackball then you are just SOL in both cases.  As for the soft keys they work well most of the time.  The only time I have a problem is when the phone is parallel to the ground.  When this happens you have to press a button repeatedly for it to perform is designated action.  Sometimes even that isn’t enough if you aren’t pushing the button in the right place (near the top close to the screen edge).  Some other reviews claim that the back button is confusing, but I find it rather intuitive; it will always take you to the previously viewed screen, so this isn’t a problem unless you have horrible short term memory.

BATTERY: Depending on use I can get anywhere between half a day and two days from a full battery.  Removing the batter is rather simple…once you are able to remove the back of the phone, which isn’t quite as simple.

OVERALL: I’ll keep this short, 4/5.  The reason for a 4 and not anything higher is because of the keyboard, screen in the sun, and  the fact that there are more “advanced” phones out there.  Though the Nexus One is “old”, it is by no means irrelevant.  It is still the phone that the Google developers use to do testing (I’m sure it’s not the only phone but it is certainly one they make sure their product works on.  Which is part of the reason this is the only phone running Android 2.2).