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]
 Wednesday, August 2, 2006

I'm working a bit with SQL Server Reporting Services 2005 these days, and discovered a pretty funny bug. Somebody has probably found it already, but I think it is kind of funny. This is how it's reproduced:

  1. Create a new report in the report designer.
  2. Click some element, the report itself, for instance, and select Background Color: Expression in the properties window.
  3. Select "Custom", pick a color, red for instance, and double click it do put it into the expression window.
  4. Click OK and watch the report turn.... BLUE!

It looks like the hex-formatted color string is reversed when it is inserted into the expression editor window.

So where do I find the guys who wrote it, hmm. Was it out my office door, to the right and 50 meters straight ahead?

posted on Wednesday, August 2, 2006 4:27:38 AM (W. Europe Standard Time, UTC+01:00)  #    Comments [0]
 Thursday, July 13, 2006

Any of you tried that? Well, if you have, you probably encountered some interesting behavior. At least I did.

I'm developing a web application here on the SQL Server Team @ Microsoft that needs to run in an application pool that runs with the identity of a domain user account. The application also uses Windows Integrated Authentication.
For some reason I was not able to access the website from any other place than the local machine, even though I am an admin on the machine. I just kept getting login-boxes, which is equivalent to access denied. After three login attempts it resulted in "HTTP Error 401.1 - Unauthorized: Access is denied due to invalid credentials."

When using Integrated Authentication, IIS is by default configured with two authentication methods: Negotiate (Kerberos) and NTLM, with Negotiate as the primary that is tried first. After burning off a few hours trying to figure this out, I found that in my setup, Kerberos authentication fails, and IIS will not let you access the web site. The same is also true if run the App Pool as a local user, and the server running IIS are not using a WINS or DNS name. It looks like the easiest solution is to disable Kerberos and force IIS to use NTLM. See the MS TechNet article below for how to do that. The blog link below describes another solution to this problem which may be preferable.

So now it works, thanks to these links:


posted on Thursday, July 13, 2006 3:05:15 AM (W. Europe Standard Time, UTC+01:00)  #    Comments [2]
 Friday, June 30, 2006

As I wrote in my last post, I have a summer internship at Microsoft in Redmond, USA this summer. The same also applies to Vegard Andreas Larsen, also from Norway, studying at the same university as I do.

Lately a couple of Norwegian journalists have got to know this, and Vegard and I suddenly got a lot of publicity. The local newspaper Fredriksstad Blad published an article about me three weeks ago, and today Norways second and third largest newspapers published two articles:

Fredriksstad Blad:

The articles are in Norwegian only :(

posted on Friday, June 30, 2006 1:39:55 AM (W. Europe Standard Time, UTC+01:00)  #    Comments [0]