.Net implementation: binary serialization format used by Google

Protobuf-net is the .net implementation of protocol buffers. Protocol buffers is the the binary serialization format used by Google for data communications. The advantages of using protocol buffer include:

• small in size – efficient data storage (far smaller than xml)
• cheap to process – both at the client and server
• platform independent – portable between different programming architectures
• extensible – to add new data to old messages

Protobuf-net can serialize the .net objects to their binary streams and deserialize the binary streams to .net objects with efficient compression.

Protobuf-net can be used with your existing project by including its .dll. The package can be downloaded from . Follow the steps below to use it with existing project in Monodevelop.

1. Create a C# console project.
2. In the References, click on .Net Assembly and add the protobuf-net.dll.
3. Now you can use the Protobuf library in your project.
4. Use Serializer class to serialize and deserialize the data.

Sample code

using System;
using System.IO;
using ProtoBuf;

namespace protobufnet
{
	[ProtoContract]
	public class Person
	{
	    [ProtoMember(1)]
	    public string Name { get; set; }
	    [ProtoMember(2)]
	    public int Age { get; set; }
	    [ProtoMember(3)]
	    public DateTime DateOfBirth { get; set; }        
	    [ProtoMember(4)]        
	    public Address Address { get; set; }
	}
	
	[ProtoContract]
	public class Address
	{
	    [ProtoMember(1)]
	    public string Number { get; set; }
	    [ProtoMember(2)]
	    public string StreetName { get; set; }
	}
	
	class MainClass
	{		
		public void serializeDeserializeData()
		{
			var person = new Person {
		        Name = "Fred",
		        Address = new Address {
		            Number = "Flat 1",
		            StreetName = "The Meadows"
		        }
		    };
		    using (var file = File.Create("person.bin")) {
		        Serializer.Serialize(file, person);
		    }	
			
			Person newPerson;
            using (FileStream file = File.OpenRead("person.bin"))
            {
                newPerson = Serializer.Deserialize<Person>(file);
            }

            Console.WriteLine("expected Name {0}", person.Name);
            Console.WriteLine("actual Name {0}", newPerson.Name);
		}
		
		public static void Main (string[] args)
		{			
			MainClass mainclass = new MainClass();
			mainclass.serializeDeserializeData();
			Console.WriteLine ("Serialization and Deserialization completed!");
		}
	}
}

Maximum Sum in 2-d array

Given an m by n two-dimensional array arr (1 < = n,m < = 100) of arbitrary integers, find the maximum sub-array.Maximum sub-array is defined to be the sub-array whose sum of integer elements are the maximum possible.

Explanation:

• First, calculate the vertical prefix sum for all columns (an O(n²) algorithm).
• Second, assume that the maximum sub-array will be between row a and row b, inclusive. There are only O(n²) a, b pairs such that a < b. Try each of them.
• Since we already have the vertical prefix sum for all columns, the sum of elements in arr[a..b][c] for column c can be computed in O(1) time. This allows us to imagine each column sum as if it is a single element of a one-dimensional array across all columns (one dimensional array with one row and n columns).
• There’s an O(n) algorithm to compute the maximum sub-array for a one-dimensional array, known as Kadane’s Algorithm.
• Applying the Kadane’s algorithm inside each a and b combination gives the total complexity of O(n³).

#include<iostream>
using namespace std;

#define M 100
#define N 100

void kadane(int input[], int n, int &x1, int &x2, int &max)
{
    int cur, i;
    max = 0;
    cur = 0;
    x1 = x2 = 0;
    int lx1, lx2;
    lx1 = 0;
    for(int i = 0; i<n; i++)
    {
        cur = cur+input[i];
        if(cur > max)
        {
            max = cur;
            x2 = i;
            x1 = lx1;
        }
        if (cur < 0)
        {
            cur = 0;
            lx1 = i + 1;
        }
    }
}

main()
{
    int tmp[100], n, x1, x2;
    int cur, max_sum, fx1, fx2, fy1, fy2;
    int i,j,k;
    int input[M][N];
    fx1 = fx2 = fy1 = fy2 = max_sum = cur = -1;

    for (i=0; i< M; i++)
    {
        for(k=0; k<N; k++)
            tmp[k] = 0;

        for (j=i; j<M; j++)
        {
            for(k=0; k<N; k++)
                tmp[k] += input[j][k];
            kadane(tmp, N, x1, x2, cur);

            if (cur > max_sum)
            {
                fy1 = x1;
                fy2 = x2;
                fx1 = i;
                fx2 = j;
                max_sum = cur;
            }
        }
    }
    cout << "max Sum = " << max_sum << " from (" << fx1 << "," << fy1 << ") to ("
        << fx2 << "," << fy2 << ")" << endl;
}