Advanced Algorithms #1 - Union/Find on Disjoint-set Data Structures.

Code
https://github.com/angellaa/AdvancedAlgorithms

Webcast (in Italian)

Slides

Advanced Algorithms #1 - Union/Find on Disjoint-set Data Structures

Questa serie di WebCast ha l'obiettivo ambizioso di aiutarti a costruire competenze algoritmiche avanzate e farti diventare un Top Coder! In ogni lezione, risolveremo insieme un problema complesso per maturare nel tempo un arsenale di tecniche che potrai riutilizzare nell'affrontare qualunque tipo di problema. Scriveremo algoritmi che spesso non sono neanche affrontati in corsi universitari come Depth First Search, Breath First Search, Convex Hull, Kd-Trees, Max Flow, Radix Sort, Suffix Array ecc. Buon divertimento :)

Registrati alla prima sessione: Union/Find on Disjoint-set Data Structures

Configuring the TopCoder Arena for C# developers

If you read my previous post (Learning Algorithms with TopCoder - Getting Started Guide) you are probably motivated in solving TopCoder problems and putting yourself under test. You probably created an account and tried the arena and you quickly realized that the experience is not that great.

Why?

• You have to read the text of the problem inside the arena
• You have to manually create the class and copy the method signature
• Testing the code with the examples is a manual process in the arena
• Debugging against the examples force you to code all the examples manually
• You have to copy the code from Visual Studio into the Coding Area

This is tremendously annoying!

Fortunately, there is a solution to these problems using some arena plugins. It is a little bit annoying to setup but once done your coding experience is vastly improved and you can finally focus on writing algorithms.

You can find some only-text documentation at the following link:
http://www.topcoder.com/contest/classes/ExampleBuilder/ExampleBuilder.html

First of all, download the TopCoder.zip file and extract it into C:\TopCoder

The folder contains an empty Visual Studio .NET 4.5 C# console application and a folder jars with the plugin code.

In this post, I want to explain step by step how to configure the TopCoder arena to be able to start solving SRM problems in TopCoder using C# and Visual Studio.

Launch the arena and open the Editor options.

Add a new editor with the following information:

• Name: ExampleBuilder
• EntryPoint: codeprocessor.EntryPoint
• ClassPath: C:\TopCoder\jars\CodeProcessor.jar;C:\TopCoder\jars\FileEdit.jar; C:\TopCoder\jars\ExampleBuilder.jar

Select the new editor and click Configure.

Insert the entry point fileedit.EntryPoint and the processor class tc_plugin.ExampleBuilder

Then, click Verify.

Press OK and then Click Configure.

Specify the enter directory to C:\TopCoder, check "Write the problem description using HTML" and check "Write the Problem Description to separate file" with extension html.

Click the Code Template tab, select the C# language.

Copy the template code from here but feel free to customize it as you like.

Save everything.

Now you have everything set up and you are ready to code.

Open one of the past SRM: Practise Rooms > SRMs.

Select one of the problem.

The default editor will launch by default. Make sure that you select C# as your language.

Change your editor to ExampleBuilder.

This will trigger the creation of two files:

• A C# source file with the problem and the tests
• An html file with the description of the problem

You can open the html file and read the problem statement in your favourite browser (maybe in a separate screen if you have a multi-monitor setup).

At this point, you can open the TopCoder Visual Studio solution and include the file in the project.

You can see that all the examples has been automatically added as tests and the only thing that you need to do is to provide the implementation of the algorithm in the method.

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class BinaryCode 
{
    public string[] decode(string message) 
    {
        // IMPLEMENTATION GOES HERE  
        string[] res = new string[0];
        return res;
    }
    
    // BEGIN CUT HERE

    public static void Main(String[] args) 
    {
        try  
        {
            eq(0,(new BinaryCode()).decode("123210122"),new string[] { "011100011",  "NONE" });
            eq(1,(new BinaryCode()).decode("11"),new string[] { "01",  "10" });
            eq(2,(new BinaryCode()).decode("22111"),new string[] { "NONE",  "11001" });
            eq(3,(new BinaryCode()).decode("123210120"),new string[] { "NONE",  "NONE" });
            eq(4,(new BinaryCode()).decode("3"),new string[] { "NONE",  "NONE" });
            eq(5,(new BinaryCode()).decode("12221112222221112221111111112221111"),
                  new string[] { "01101001101101001101001001001101001",                  
                                 "10110010110110010110010010010110010" });
        } 
        catch(Exception exx)  
        {
            Console.WriteLine(exx);
            Console.WriteLine(exx.StackTrace);
        }
        Console.ReadKey();
    }
    ...

    // END CUT HERE
}

You can see the results of the tests simply running the project with F5.

How do you actually submit your code?

Click Compile and the source code will be automatically copied into the arena.

Finally click Submit.

To summarize, once you setup your development machine like I explained in this post you will be able to open any TopCoder problem, start coding your algorithm immediately and have a lot of fun. During a competition, this technique can also save you a lot of time and increase the chance of getting an higher score.

Enjoy coding!

Andrea

I am officially a Microsoft C# Specialist

Yesterday, I passed the "Programming in C#" exam.

This makes me officially a Microsoft C# Specialist.

If you are a C# developer you should definitely try the exam!

The following are the resources that I used in order to prepare for it:

• C# 5 in a Nutshell: The Definitive Reference
• Programming in C# Jump Start on Microsoft Virtual Academy

If you don't mind waiting, Microsoft is releasing an official book in July:

• Exam Ref 70-483: Programming In C#

Good luck

The Iterator Pattern in .NET

The Iterator Pattern provides a way to access the elements of an aggregate object (collection) sequentially without exposing its underling representation.

The ultimate goal of the pattern is to decouple the client from the implementation of the collection that always remains well encapsulated.

This is definitely my favourite pattern in particular for how it is supported by C#.

It's easy, amazing and extremely powerful.

The Client

In the .NET framework the pattern is fully supported by all the collections in the Base Class Library and the C# language provides the foreach keyword to iterate a collection in an extremely simple way. Every .NET developer knows it.

What is the beauty of the pattern?

The beauty is that the client does not need to know nothing about the internals of the collection in order to iterate through its elements. Replacing the List with an HashSet does not require to change the foreach loop in any way.

How does it works?

The foreach loop works only on collections that implement the interface IEnumerable or the generic version IEnumerable<T>.

All the .NET framework collections implement that interfaces included List and HashSet.

The IEnumerable interface contains a factory method that should return an implementation of the interface IEnumerator or the generic IEnumerator<T>.

An enumerator class is responsible to enumerate the collection. It is a read-only, forward-only cursor over a collection.

The property Current returns the current element in the collection; the method MoveNext() advances the enumerator to the next element of the collection; the method Reset() sets the enumerator to its initial position, which is before the first element in the collection.

Everything becomes clear when you see how the C# compiler translates the foreach loop using directly the enumerator. This is the magic!

Using a .NET disassembler like ILSpy or dotPeek however we can't see the translated version in C#. In order to have a confirmation that what I said is actually true we have to look directly at the generated IL.

It is easy to see that the compiler actually does something more. It wraps the enumeration in a try/finally construct in order to properly Dispose the enumerator. This is important because IEnumerator implements IDisposable.

Finally, this is the correct C# version of foreach.

The foreach statement simply provides a very elegant way to generically enumerate a collection.

How to Implement Enumerable Collections

OK, brilliant,we now know how to enumerate any collection using the foreach keyword and in particular how this is actually done under the cover.

It's time to create a custom collection. For example, a collection that is able to store any integer between 0 and N using internally a frequency array. This is actually pretty simple to do.

However, the following code does not compile. The compiler is not able to initialize and enumerate the collection.

We obviously need to implement the IEnumerable interface

A typical choice is to use a nested type to implement the enumerator. This allows to access the internal of the collection to accomplish the job. Note that the enumerator is intrinsically coupled to the collection. It turns out that implementing an enumerator it is not so easy as it may seems initially.

The complexity of implementing the enumerator arises because it is required to maintain the current state of the iteration between subsequent calls to MoveNext. In the example the variables pos and count are required in order to maintain the state of the iteration.

Can you understand the code inside MoveNext?

Yes, I know. You may understand it but it is definitely not intuitive.

Fortunately, the C# compiler comes in help here with the keyword yield that implements the concept of coroutines in .NET.

You can implement all in the following beautiful way without the need to manually implement the enumerator yourself.

This looks like really magical!

But we are curious, let's deep dive and see the code generated by the compiler.

OK, the compiler create an instance of a compiler generated enumerator class passing through a property a reference to the collection. The compiler generated enumerator is also a nested collection.

The compiler generates a state machine under the cover. It is really impressive what it does but all this complexity is hidden to the developer thank to the yield keyword.

The Iterator Pattern and LINQ to Objects

Everything we discussed so far has always been available since C# 2.0.

C# 3.0 added LINQ to the language expanding in a significant way the potential of the language. This is without any doubts the main reason why I love C#.

The power of LINQ to Objects in particular is related to the fact that iterators are highly composable.

Consider the code that print the double of the even numbers from the collection using LINQ to Objects.

How the enumeration process works in this case?

The first call to Where generate a enumerable object that wraps the source collection using the decorator pattern. The object itself however is also the enumerator of itself. The main logic is inside the MoveNext method that iterates the source collection and then apply the filter.

The same is for the Select method where the source collection in this case will be the result returned by the Where method.

The execution at run-time will be a chain of enumerations that is simply described by the following sequence diagram.

Conclusion

The iterator pattern these days is a fundamental pattern and it is fully integrated in the modern programming languages and libraries. In particular in C# you can leverage the pattern using the foreach statement in the client code, and implementing IEnumerable and IEnumerator when you create new collections. Don't forget the incredible support that the yield keyword can provide you when you implement your custom collections.

It's important to notice that the iterator pattern is a good example of the Single Responsibility Principle: "A class should have only on reason to change". The Enumerator class is a class with the single responsibility to traverse a collection.

The main benefit of the pattern is decoupling the clients from the internals of the collections. This allows to change the collection without affecting clients.

Conditional Attribute in C#

Conditional directives in C# are extremely useful to include or exclude regions of code from compilation. This allows you to target different platforms.

Consider a class Logger with a Log method. If you want to log a message only in debug mode you could do something like this.

This code is ugly isn't it?

This is an another way to do it but it is not exactly what we would like. The code works but there are lots of useless function calls that reduce the performance at run time.

This is the situation when the Conditional attribute is useful. The following code is equivalent to the first example but much more readable.

This attribute is in fact extensively used in the classes Debug and Trace.

The next time you use conditional directives, keep in mind the Conditional attribute.

Unsafe and Fixed keywords in C#

C# allows you to manage memory directly when needed mainly for performance reasons.

In order to do so you need to compile your code using the /unsafe switch. This is required because unsafe code cannot be verified by the CLR.

In Visual Studio you can enable this in the Properties panel.

In this post I would like to run a simple experiment to measure the difference in performance when you run a very simple matrix filter: computes the square of each number in the matrix.

The safe method:

The unsafe method:

The unsafe keyword denote that the method contains unsafe code. The keyword fixed is required to pin a managed object (matrix in this case) in order to avoid that the garbage collector move the object while we perform the operation.

Inside an unsafe block it is possible to use pointers in C#. Surprised?

This is the code that compares the performance of the two versions:

The output is the following:

Safe time: 0.4410526
Unsafe time: 0.1252171
Unsafe is 3.52230326369162 times faster


There is a lot to say about unsafe in C# but I don't want to go deep in the subject because the use of pointers is almost never required and it should be avoided if possible.

The important lessons from this post are:

• C# allows to use pointers and manage the memory directly if you need it
• Unsafe code in C# can improve performance
• Always measure performances to justify the use of unsafe code

The Template Method Pattern in .NET

The Template Method Pattern defines the skeleton of an algorithm in a method, deferring some steps to subclasses. Template Method lets subclasses redefine certain steps of an algorithm without changing the algorithm's structure.

This pattern is typically used to implement frameworks as an important technique for code reuse. It allows to encapsulate pieces of algorithms so that subclasses can hook themselves right into a computation.

You can use this pattern when you recognize that two or more algorithms are similar except that some of the steps require different implementations.

General procedure to follow:

• Create a class (abstract if you want mandatory steps)
• Create a generalized version of the algorithm in a method or more (possibly sealed)
• Use protected abstract methods when a step of the algorithm is required
• Use protected virtual methods when a step is optional
• If needed, add a default implementation for optional steps
• Create a subclass for each specific algorithm implementing all the various steps

It is quite easy to create a simple example of the pattern but I think that is much more useful to identify implementation of the pattern in your favourite frameworks. This pattern is used in almost every framework.

Example: The XNA Framework

The XNA Framework extensively use the Template Method Pattern to provide a base class Game that encapsulates the common algorithms of a game. Each subclass of the Game class implement a specific game reusing lots of the code defined in the baseclass.

If you look at the documentation of the Game class on MSDN you can see that there a lot of protected virtual methods. Each of this method can be seen as a step of the "generic game" algorithm.

Let's consider the two more important hooks:

• Update()
• Draw() 

Using a .NET Disassembler you can easily look inside the Game class and identify the template methods.

You can see that the Game class provides a default implementation of Update() and Draw() methods.

As a consumer of the framework the only thing you need to do is to override Update() and Draw() and the base class will take care of all the aspects of the game.

It is important to notice that clients can call or not the base class method with the default implementation. This can cause subtle bugs that can be hard to find and can be seen as a drawbacks of the pattern. As a framework implementer you should avoid this situation if you can, otherwise is important to document well what a client should do.

Example: Event Handling in .NET libraries

The entire .NET framework uses the Template Method Pattern extensively to provide internal clients with a simplified way to handle events.

Microsoft recommends using a protected virtual method for raising each event. This provides a way for subclasses to handle the event using an override.

You can see an example of this pattern in the ASP.NET Control class.

An internal client can override the method and add custom logic to it. Note that the Page class inherit indirectly from the Control class.

Having a default implementation makes the client asking the following questions:

• Should I call the base method?
• Should I write my custom code before calling the base method?
• Should I write my custom code after calling the base method?

There is not a generic answer to this questions because it always depends by the framework and how the base method is implemented. This should clearly be documented because it can be the source of many problems.

A way to avoid all of this problems is to use abstract methods. However, adding too many abstract methods can make the framework difficult to use because the client is forced to override all the methods even if it is not necessary.

Finding the right trade-off is surely not something easy to do.

Microsoft says on this:

The derived class can choose not to call the base class during the processing of OnEventName. Be prepared for this by not including any processing in the OnEventName method that is required for the base class to work correctly.

This problem is strictly related to the Liskov substitution principle. Not calling the base class can violate the principle.

Design Principles and Limitations

It is possible to continue forever with examples from the .NET Framework but I think that you got the idea behind the pattern.

The object oriented design principles used by the pattern are:

• "The Hollywood Principle": Don't call us, we'll call you.
• The Open/Close principle

The main benefits of the pattern is:

• Code reuse (subclasses implement only the behaviour that can vary)

There are however some limitations in using this pattern.

The first limitation is that the pattern rely on inheritance. A way to avoid inheritance and achieve a similar goal is to use the Strategy Pattern.

The second limitation is that inheritance makes difficult to merge two child algorithms into one. In that situation, the Decorator Pattern can be a solution.