Thursday, May 17, 2007

I am studying for my exam in Performance Engineering these days, and came across a nice way of estimating Pi in the chapter about Monte Carlo simulations (random number simulations) yesterday. The idea is that you use random numbers to estimate something, in this case the number Pi.

Let's take a look at the figure below. Here we have the unit circle (a circle with radius 1 and center in origo) drawn in a coordinate system. Up to the right, in the first quadrant, I have shaded a square area with sides of length 1.


As you probably should remember from school, the area of a circle is A = Pi * r^2, and this circle therefore has an area of A = Pi * 1^2 = Pi. One fourth of the circle is in the shaded area, and this part of the circle therefore has the area Pi / 4. The shaded area itself has an area of 1 * 1 = 1. Then we define R to be the ratio between the area of the shaded part of the circle and the whole shaded area. This ratio is R = (Pi / 4) / 1 = Pi / 4.

Now, let's imagine throwing darts at the shaded area at random (we do not aim for any specific area). Of all the darts hitting the shaded area, a ratio of them, corresponding to R (since there is equal probability for hitting any part of the square), should hit inside the circle. For instance, if the ratio is 0.7, and 10 darts hit the shaded area, 7 should hit inside the shaded part of the circle.

If we throw a fair amount of darts, we should be able to calculate R using the formula R = DartsInsideGreyCircle / TotalDartsInsideGreyArea. As we have from the paragraph above, R = Pi / 4, which means that Pi = R * 4. We have estimated Pi!

The JavaScript simulation below illustrates this. Click start and watch what happens! If you let it run for a while, the result will actually get quite close to the actual value of Pi.

Coordinates: (x, y) = (0, 0)
Hits inside: 0, hits outside: 0
Ratio: R = HitsInside / (HitsInside + HitsOutside) = 0.
Estimated Pi value: π ≈ 4 * R = 0.
Speed: 1 /s.
Note: If you are reading this through an RSS feed, you may need to open the blog post in a browser to be able to run it.
posted on Wednesday, May 16, 2007 11:26:07 PM (W. Europe Standard Time, UTC+01:00)  #    Comments [0]
 Monday, March 19, 2007

As many others, I also have a voicemail message box for my cell phone number that the caller gets redirected to if I don't answer the phone in something like 15 seconds. What I've found is that 15 seconds is a pretty short time when the phone is ringing and you need to find out where it is. It is OK if you're sitting right next to it, but if it is in some jacket lying somewhere around you're very likely to miss the call.

Therefore I called my phone company (Telenor) today to find out if it is possible to increase this timeout. I got a rather interesting answer:
Dial **61*<Your Voicemail Number>**<Timeout in seconds># on your phone, and you're done.

I don't know if it works only for Telenor customers, but it's worth a try :-) I also found that on my Windows Mobile phone I can actually change this setting under Settings --> Phone --> Services --> Call Forwarding, so that's maybe a more general solution.

So now I've got 25 seconds to find my phone when it rings :-)


posted on Monday, March 19, 2007 1:19:15 AM (W. Europe Standard Time, UTC+01:00)  #    Comments [2]
 Wednesday, February 7, 2007

During Christmas I took two upgrade exams (70-431: MS SQL 2005 Imp&Maint, 70-553: MCSD to MCPD Part 1) to upgrade my Visual Studio 2003 and SQL Server 2000 certifications to .NET Framework 2.0 and SQL Server 2005. Those combined with two I took in Redmond last summer (70-447: MCDBA to MCITP:DBA, 70-554: MCSD to MCPD Part 2) gave me a bunch of new certifications all at once, more precisely 4 x MCTS, MCITP: DBA and MCPD: Ent.App.Dev.

Then the interesting part: All of those come with welcome kits with diplomas, some also with pins and wallet cards in separate envelopes. Therefore, I was wondering if they were going to put everything in one envelope when I ordered something like 9 welcome kits at once. But they didn't, and here the other day I found my mailbox full of welcome kits :-) Take a look at the picture below where I have spread them out on the bed.


posted on Wednesday, February 7, 2007 1:59:59 AM (W. Europe Standard Time, UTC+01:00)  #    Comments [8]
 Wednesday, December 20, 2006

School is out for Christmas (I had my last exam last Friday), so now I have time do fun things, like coding (surprise).

I think algorithmic programming and databases and SQL queries are cool things, so why not combine them? Yesterday I got an idea of implementing some well-known algorithm in SQL, and I figured out that Dijkstra's Shortest Path algorithm should be fun to implement.

Dijkstra's shortest path algorithm finds, well, the shortest path from one vertex to the other vertexes in a weighted graph. The edges have lengths (or costs or whatever), and the shortest path from one vertex to another is the path where the sum of these lengths are as small as possible. Take a look at the illustration below, showing a graph with some Norwegian cities. The shortest path from Trondheim to Fredrikstad has been highlighted (for those of you that know Norway, not very realistic, but let's pretend it is just for the fun of it).

The algorithm works like a breadth first search that takes the edge weights into account, starting at one vertex and traversing through the graph.

So, how do we implement this in Transact-SQL (MS SQL Server's SQL dialect)? Well, first we need some way to represent the graph. I've created two tables:


The City table is pretty straightforward. The Road table contains one row for every road from one city to another, and the length of that road. Notice that we have two rows for every two cities we have a road between them, one each way. But, now to the real stuff: The implementation of the algorithm:

CREATE PROCEDURE [dbo].[Dijkstra]
    @StartCity Int
    -- Automatically rollback the transaction if something goes wrong.    
    -- SET NOCOUNT ON added to prevent extra result sets from
    -- interfering with SELECT statements.

    -- Create a temporary table for storing the estimates as the algorithm runs
    CREATE TABLE #CityList
        CityId Int NOT NULL,    -- The City Id
        Estimate Int NOT NULL,    -- What is the distance to this city, so far?
        Predecessor Int NULL,    -- The city we came from to get to this city with this distance.
        Done bit NOT NULL        -- Are we done with this city yet (is the estimate the final distance)?

    -- Fill the temporary table with initial data
    INSERT INTO #CityList (CityId, Estimate, Predecessor, Done)
    SELECT CityId, 2147483647, NULL, 0 FROM City
    -- Set the estimate for the city we start in to be 0.
    UPDATE #CityList SET Estimate = 0 WHERE CityID = @StartCity
    IF @@rowcount <> 1
        RAISERROR ('Couldn''t set start city', 11, 1)
        ROLLBACK TRAN        

    DECLARE @FromCity Int, @CurrentEstimate Int

    -- Run the algorithm until we decide that we are finished
    WHILE 1=1
        -- Reset the variable, so we can detect getting no records in the next step.
        SELECT @FromCity = NULL

        -- Select the CityID and current estimate for a city not done, with the lowest estimate.
        SELECT TOP 1 @FromCity = CityId, @CurrentEstimate = Estimate
        FROM #CityList WHERE Done = 0 AND Estimate < 2147483647
        ORDER BY Estimate
        -- Stop if we have no more unvisited, reachable cities.
        IF @FromCity IS NULL BREAK

        -- We are now done with this city.
        UPDATE #CityList SET Done = 1 WHERE CityId = @FromCity

        -- Update the estimates to all neighbour cities of this one (all the cities
        -- there are roads to from this city). Only update the estimate if the new
        -- proposal (to go via the current city) is better (lower).
        UPDATE #CityList SET #CityList.Estimate = @CurrentEstimate + Road.Distance,
            #CityList.Predecessor = @FromCity
        FROM #CityList INNER JOIN Road ON #CityList.CityID = Road.ToCity
        WHERE Road.FromCity = @FromCity AND (@CurrentEstimate + Road.Distance) < #CityList.Estimate
    -- Select the results.
    SELECT City1.Name AS ToCity, Estimate AS Distance, city2.Name AS Predecessor FROM #CityList
    INNER JOIN City city1 ON #CityList.CityId = City1.CityID
    LEFT OUTER JOIN City city2 ON #CityList.Predecessor = city2.CityID
    -- Drop the temp table.
    DROP TABLE #CityList

If we run it with Trondheim as start city (@StartCity = 1), we get this result table:


This says that from Trondheim, we have a distance 0 to Trondheim, 2 to Bergen and so on, and 6 to Fredrikstad. The Predecessor column says what city we came from when we went to each city. We can see that to get to Fredrikstad, we came from Oslo, and to get to Oslo, we came from Bergen. To get to Bergen, we came from Trondheim. Therefore, to get to Fredrikstad, we took the path Trondheim, Bergen, Oslo, Fredrikstad.

I have included the SQL script to create the database:

Dijkstra.txt (8,03 KB)
TestScript.txt (1,26 KB)

posted on Wednesday, December 20, 2006 5:45:10 PM (W. Europe Standard Time, UTC+01:00)  #    Comments [12]
 Sunday, November 5, 2006

A couple of months ago my team from Imagine Cup (Team NTNU) got an invitation to TechEd 2006 in Barcelona from the organizers of Imagine Cup and Microsoft EMEA.

We are going to present our solution and talk a little about our experience in India to the students attending TechEd. We're maybe also going to have a booth with some posters and stuff where we can show our solution. TechEd starts on Monday, so now it's time to get to Barcelona.

It's also going to be exciting to see all the new stuff they are going to show at TechEd. I've never attended a developer conference at this scale, so this is going to be interesting!

posted on Sunday, November 5, 2006 1:28:35 AM (W. Europe Standard Time, UTC+01:00)  #    Comments [0]
 Friday, November 3, 2006

On Wednesday Gøran and I held the third lecture in the .NET course I mentioned in the last blog post. This time it was about Windows Workflow Foundation, which is a very cool product. I'm looking forward to testing it more. The lecture was recorded on video this time too, see links below (only in Norwegian this time too, unfortunately).

Part 1:

Part 2:

posted on Friday, November 3, 2006 11:57:47 PM (W. Europe Standard Time, UTC+01:00)  #    Comments [0]
 Friday, October 13, 2006

It has long irritated me that NTNU - The Norwegian University of Science and Technology - doesn't offer ANY courses on Microsoft Technology whatsoever, at least as far as I know. We're only learning Java and other stuff, and .NET and C# are lucky to be mentioned at the end of a sentence. The foremost university in the country should take a look at the figures for which technologies are really used by software companies today.

But, things are starting to change, but not exactly in the way I expected them to:

  1. It is not my department, the Department of Computer and Information Science (IDI) that is responsible for the change, but the Department of Engineering Design and Materials! The first .NET course at NTNU is not hosted by the computer science people, but by the engineering design and materials people! Come on, IDI, take the hint! Look outside your own little Java sandbox.
  2. Guess who is holding the lectures! It's Rune Zakariassen from Microsoft, me and a friend of mine, Gøran, from Microsoft Student Community NTNU. That's pretty cool!

The course is a preparation study for 5th year students starting on their diploma assignment, and consists of four seminars with lectures and hands-on labs. The first one was an introduction to .NET and C#. The second one, held this Wednesday was about Windows Communication Foundation (WCF), and the two next ones will be about Windows Workflow Foundation (WF) and real time communication. The idea behind the course is to give the students a superficial knowledge about these technologies so they can use them in their assignments.

The lectures were recorded on video. Here are the videos from the WCF lecture (in Norwegian, unfortunately):

Part 1:
Part 2:

posted on Friday, October 13, 2006 2:30:32 AM (W. Europe Standard Time, UTC+01:00)  #    Comments [7]

I'm still alive, but I've been so busy the last couple of months that I haven't had the time to update the blog. So here comes a blog post a bit longer than usual.

A lot of things have happened since the last post from August 3rd:
- Team Norway got third place in the Software Design final in Imagine Cup
- My internship at Microsoft is over
- I'm back in Norway at school

So, let's take the first things first.

From the 4th to the 12th of August I had one week off from my internship at Microsoft to participate in the International finals of Imagine Cup 2006 in Agra and New Delhi, India, together with my team mates from Norway. I flew from Seattle to New York, had 20 minutes to get on the plane to New Delhi and then spent the next 14 hours on that plane. We actually flew right above Trondheim, the city where I study here in Norway. I took around 30 hours in total, and then add the 11,5 hours of time difference and staying up the first night in India to get our demo up and running, and you're there.

We didn't really expect to get as far as we got in India, since we knew there were going to be very many good teams and solutions. But we wanted to do our best, and at least we would get to see what India and the Imagine Cup finals are like :-)

Our team consists of four students from NTNU; Jan-Kristian (who is a FTE at MS now), Jonas, Gøran and me. We participated in the Software Design category, in which you are to come up with an idea on this year's Imagine Cup theme and design a software solution around this.
The Software Design category consisted of three rounds. The first round was a 20 minute presentation where we presented our solution to the judges, and then 10 minutes with Q&A after wards. We held our presentation, and we thought it went pretty well, but we were still a bit surprised when we were selected to be among the 12 best teams that went to the second round. Now we were starting to think "maybe we're onto something here", and went for the second round presentation to do our best.

As always, things didn't come together before the last moment. We stayed up all night before the first round to get our demo up and running, and when we got to the second round, we had to improve it a bit. So we were coding to the last moment. After the second round, things got even better when it was announced that we were among the six best teams, along with Denmark, Italy, Japan, China and Brazil. We were to present our solution to all the other contestants at the biggest conference center in New Delhi! The presentation went well, and we managed to answer the questions the judges came up with pretty well. Finally we ended up third, winning $10 000 and a trip to England in January!

The trip was great; we got to see India and met a lot of other smart people with the same interests. The only showstopper was that I got sick a couple of days, probably because I ate some ice cream which I shouldn't have eaten. I missed a couple of things, the trip to Taj Mahal, among others.

Thanks to all the people who made Imagine Cup 2006 possible and to all the participants for a great time in India!

Us on stage in Delhi, presenting the MSN bot in our solution.

After the prize ceremony. We won $10 000! (Me on the far left)

Gøran has published a few photos from India on his Flickr site:

When we got third place, we got a lot of publicity on many internet sites and in many newspapers. The number of results when you google my name has skyrocketed from about fifty to several hundred.

Here is a collection of links to news paper articles about Imagine Cup (mostly in Norwegian, unfortunately): Demokraten: Fredrikstad-student i verdenstoppen Dagbladet: Nerde-bronse Fredrikstad Blad: Bronse til Hvaler-gutt i Imagine Cup Fredrikstad Blad: Til topps i Imagine Cup? Fredrikstad Blad: Til "data-VM" i India Microsoft Announces Imagine Cup 2006 Winners - Norwegian Students Take 3rd Adressavisen: NTNU-bronse i India NTNU-studenter i verdensklasse Adressavisen: NTNU-studenter i verdenstoppen Computerworld: Tredjeplass for NTNU-studenter Dagens IT: Forsvarer Norges ære Dagens IT: NTNU-studenter på verdenstoppen NTNU-studenter på global medaljeplass Nordmenn i global teknologikonkurranse  Grunder: Stor seier for NTNU-studentene Nettavisen: NTNU helt i tet Nordlys: Lakselv-studenter kan nå helt til tops Gjør suksess i India Nordlys: Lakselvgutter i verdenstoppen

I'll talk more about my internship at Microsoft in a later blog post.

posted on Friday, October 13, 2006 2:21:43 AM (W. Europe Standard Time, UTC+01:00)  #    Comments [0]