Adil Akhter

Solving SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#

Mon, 15 Apr 2013 15:30:00 GMT

The Bytelandian Gold Coins problem, officially published in SPOJ, is centered around computing the maximum dollars that can be exchanged for a Bytelandian gold coin. In this post, we outline a solution to this problem with memoization and F#.

Interpretation

The problem definition enforces following rules to perform the exchange. Consider, a Bytelandian gold coin --

It can be exchanged to three other coins, i.e., coins. Thus, coin yields value in bytelandian gold coins.

Alternatively, coin can be exchanged for dollars.

Our objective is to derive an algorithm that maximizes the dollars exchanged from the gold coin . (read more)

UVa 10664. Luggage with Dynamic Programming

Sat, 13 Apr 2013 12:51:00 GMT

The UVa 10664: Luggage is a typical example of the problems that can be solved using dynamic programming (DP) technique. In fact, after further analysis, this problem can be realized as a special case of Subset-Sum problem, which we have discussed in a recent post.

The following Java code snippet outlines an algorithm using dynamic programming to solve this problem. (read more)

Solving SPOJ 97. Party Schedule with Dynamic Programing and F#

Thu, 11 Apr 2013 06:15:00 GMT

The Party Schedule problem, published in SPOJ website, is about deriving an optimal set of parties that maximizes fun value, given a party budget: and parties: where each party have an entrance cost , and is associated with a fun value . In this post, we discuss how to solve this problem by first outlining an algorithm, and afterwards, by implementing that using F#. This problem is a special case of Knapsack problem. Main objective of this problem is to select a subset of parties that maximizes fun value, subject to the restriction that the budget must not exceed . More formally, we are given a budget as the bound. All parties have costs and values . We have to select a subset such that is as large as possible, and subject to the following restriction-- (read more)

Solving Subset Sum with Dynamic Programming and F#

Wed, 10 Apr 2013 21:31:00 GMT

The Subset Sum (Main72) problem, officially published in SPOJ, is about computing the sum of all integers that can be obtained from the summations over any subset of the given set (of integers). A naïve solution would be to derive all the subsets of the given set, which unfortunately would result in time complexity, given that is the number of elements in the set. This post outlines a more efficient (pseudo-polynomial) solution to this problem using Dynamic Programming and F#. Additionally, we post C# code of the solution...(read more)

Levenshtein Distance with F#

Wed, 10 Apr 2013 19:20:00 GMT

This problem can be solved using dynamic programming with memoization technique. In essence, it is about computing the Edit Distance, also known as, Levenshtein Distance between two given strings.

Definition. Edit Distance—a.k.a “Lavenshtein Distance”--is the minimum number of edit operations required to transform one word into another. The allowable edit operations are letter insertion, letter deletion and letter substitution ...(read more)

UVa 10706. Number Sequence with F#

Wed, 10 Apr 2013 18:57:00 GMT

This post describes an algorithm to solve UVa 10706: Number Sequence problem from UVa OJ. Before outlining the algorithm, we first give an overview of this problem in the next section... continue reading.

UVa 136. Ugly Numbers with F#

Tue, 26 Mar 2013 21:23:00 GMT

This blog-post is about UVa 136: Ugly Number, a trivial, but interesting UVa problem. The crux involves computing 1500^th Ugly number, where a Ugly number is defined as a number whose prime factors are only 2, 3 or 5. Following illustrates a sequence of Ugly numbers:

1,2,3,4,5,6,8,9,10,12,15...

Collatz Problem a.k.a. 3n+1 Problem

Tue, 26 Mar 2013 21:21:00 GMT

This post focuses on Collatz problem, which is also known as, among others, the 3n+1 problem, and the Syracuse problem. Outline. We begin by introducing Collatz conjecture; afterwards, we presents an algorithm to solve the problem (UVa 100 or SPOJ 4073) published in both UVa and SPOJ. The primary advantage of having it in SPOJ is that we can use F# to derive a simple and elegant solution; at the same time, we can verify it via SPOJ's online judge... continue reading.

Coordination Strategies: Beyond Scrum | Part 3

Tue, 07 Jun 2011 18:40:00 GMT

In the previous post, we discuss different strategies that are imperative in successful implementation of Scrum process model in the GSD context. In this post, we take this discussion further by introducing few strategies that are originated from other disciplines than software development; however, can have positive impact on the LFDS. (read more)

Coordination Strategies: On Successful Implementation of Global Software Development using Large-scale Fully Distributed Scrum| Part 2

Tue, 07 Jun 2011 18:30:00 GMT

In the previous post, we discussed the motivation behind employing various coordination strategies while using LFDS in GSD context. In this post, we discuss several intra- and inter-team coordination strategies to successfully implement LFDS to alleviate the impediments incurred by the GSD. Two primary aspects – “scaling” and “distribution” of Scrum are the focus of these strategies. (read more)

Coordination Strategies: On Successful Implementation of Global Software Development using Large-scale Fully Distributed Scrum | Part 1

Tue, 07 Jun 2011 18:25:00 GMT

Software engineering is evolving every day to address the ever increasing growth of system’s complexity and size along with the application domains and level of interactions with the other systems. In current era of globalization, with the intention of the increase in productivity and resource utilization, large-scale global software development (GSD) is a reality. However, it is known that the successful implementation of large-scale GSD using traditional distributed development process is quite difficult. The consistently increasing popularity of agile software development approaches is the result of their ideology for reducing complexity and focusing strongly on coordination, collaboration and communication. It makes the adaptation of agile methodology, such as- Scrum an obvious choice in the GSD context.

However, inherently, Scrum is only meant for local small teams and employing it to the large-scale GSD is a paradigm shift for this agile process. Therefore, this fact necessitate a pragmatic derivation of coordination strategies or best practices to successfully implement Scrum framework in the large-scale GSD context. In this post, we start we defining several concepts relevant for this topic. Afterwards, we provide the rational behind these strategies in successful implementation of GSD powered by LFDS. (read more)

Essence: Software Language Composition

Tue, 08 Feb 2011 20:15:00 GMT

Language composition is one of the desirable aspects of Software Language Engineering to enable reusability of the existing languages.

"From now on, a main goal in designing a language should be to plan for growth.” - Guy Steele: Growing a Language, OOPSLA'98 invited talk[1].

A language should be designed in such a way that evolving it with respect to different language constructs requires the minimum effort. It is well-recognized that designing a high quality language requires considerable effort. Therefore, reusability is a highly desirable property in the context of software language engineering(SLE) that can support language evolution and integration in modest maintenance effort; thus, reusability of languages has become one of the primary research concern in the field of SLE.

The complexity of this problem increases with the ubiquitous proliferation of Domain-specific Languages (DSLs) as composition of various DSLs in the context of solving different problems has become a real-world use-case scenario. Wider-acceptability of DSLs further warrant modular composition of language features since the realization of the DSLs can only be discerned if efforts put in their implementation can somehow be optimized. Therefore, just as any other disciplines, reusability is the key here.

These days I am working on designing a meta-language that supports modular definition of the language constructs. Primary objective of this endeavor is to promote "Language-as-a-Library" ideology in software language design. Thus, we envisage that the outcome of this research would be a framework that would facilitate rapid software language development by reusing the exiting language features as much as possible and thus, it will enable cost-effective language development.

The goal of designing language in a modular and reusable manner, I started with a survey to find out the existing state-of-the-art framework that supports these kinds of features. Hence, this blog contributes to this research endeavor by providing an outlook of the existing strategies or patterns of software language composition, the technologies promoting the notion of modular and composable languages; and by reviewing the state-of-the-art approaches of software language composition in solving the relevant issues.

References

1. Jr., G.L.S.: Growing a language. Higher-Order and Symbolic Computation 12(3), 221–236 (1999).

Domain-specific Languages(DSLs)

Tue, 08 Feb 2011 18:06:00 GMT

Domain-specific languages (DSLs) are basically programming languages. But they are specifically targeted/tailored towards particular problem domains. Hence, it implies to the fact that DSLs are narrow in applicably unlike General-purpose programming languages(GPLs)[1]; hence, DSL precisely abstracts the domain and its semantics. At the same time, being specific to a particular problem domains make it hard to reuse and adapt to a new problem domains or to the same evolving domain with new set of requirements.

Figure 1: DSLs are bridging the semantic gaps.

“Only way to manage complexity is to bring order to chaos”

Complex software systems consist of several concerns such as, performance, reliability , fault-tolerance, persistency. Hence, domain specialization is required to capture these concerns precisely and to perform various analyses specific to the domain. DSLs , thus reduce the complexity of complex systems by providing high level linguistic abstraction through succinct syntax and by isolating concerns from one another which additionally results in highly cohesive sub-systems. Following figure illustrate the fact that DSLs covers various concerns of complex software systems vertically rather than horizontally.

Figure 2 : Vertical domain specialization of DSLs in a complex system.

Although in recent years DSL-centric paradigm gets wider-applicability in various application domains due to the increase of domain specialization, the fundamental ideas[2] of DSLs existed long before.As we were discussing in this blog, the inherent implementation strategies of DSLs warrant re-thinking the software process involved in DSLs development. To a large extent, success of a DSL depends on the cost-effectiveness of the end product. We believe that it can only be achieved through modularizing definition of DSLs and by promoting reusability of the existing language constructs. Different aspects even when beginning a DSL development thus require careful considerations.

Key Properties of a DSL

Coverage
Expressivity
Completeness
Portability
Support for evolution
Quality of the generated artifacts.

Types of DSLs

Primarily, DSLs can be categorized into following categories–

Implicit DSLs or Explicit DSLs

Textual DSLs or Visual DSLs

Basic Components of a DSL

Alike GPLs, a DSL is constructed with the following primary components.

Syntax definition formalism for defining syntax.
A parser to parse the syntax of DSL and construct Abstract Syntax Tree(AST) or underlying model. ( however, visual DSLs does not require parsers as AST can be constructed from the end-users’ specification).
Model Transformer. It performs several model-to-model transformation such as, dusugaring , normalizing , decorating. As such, it annotate more context to AST.
Afterwards, Semantic Analyzer performs static consistency checking.
Code Generators. Final artifacts are generated through model transformation and string interpolation. In several DSLs, during code generations or in earlier phases, a meta-model is created. Afterwards, artifacts are generated by utilizing this meta-model. This way of creating a meta-model and generating artifacts from it promotes robust and maintainable code generator along with quality outcomes. Complex systems may require additional tuning, which can be facilitated via Code Customization ( we will discuss about it in later blog posts) .

Figure 3 : Various phases of step-by-step transformations and finally, code generation using a DSL [3].

Aside above mentioned components, support of rich development environment is increasingly becoming important to get expected productivity from a DSLs. Several language workbenches[3] thus are providing rich support from various editor services such as code folding , syntax highlighting , reference resolving, syntax completion.

[in-progress]

References

[1] Spinellis, D. (2001). "Notable design patterns for domain-specific languages." J. Syst. Softw. 56(1): 91-99.
[2] Landin, P. J. (1966). "The next 700 programming languages." Commun. ACM 9(3): 157-166.
[3]L. Kats, E. Visser.The Spoofax Language Workbench . Rules for Declarative Speci?cation of Languages and IDEs.

F#: Computing Length of a List (Tail Recursive)

Wed, 08 Dec 2010 00:42:00 GMT

The code snippets listed below defines a function to compute the length of a give list using F#. Note that these functions are also known polymorphic function, as they work with any type of list (as shown in the output).

// naive implementation
let rec length list =
    match list with
        | [] -> 0
        | _::tail -> 1 + computeLength tail

A tail recursive implementation is outlined next.

// Tail recursive computation of List's length
let length list =
    // Auxiliary function to compute length
    // It store intermediate result in acc.
    let rec lengthAux acc list =
        match list with
        | [] -> acc
        | _::tail -> lengthAux (acc+1) tail
    lengthAux 0 list // invoking lengthAux with acc = 0

Output:

> length [];;
val it : int = 0
> length [1;2;3;4];;
val it : int = 4
> length ['a';'b'];;
val it : int = 2

Cr-Documentor - A Cool DXCore Plug-in for Visual Studio

Mon, 24 Nov 2008 12:48:00 GMT

May be I am last person on the Earth, who discovered and started using this way too cool plug-in recently ….however, if you have not checked it out yet – probably you should do it now :).

Cr_Documentor gives you just-in time rendering of your XML Documentation to preview it. So, you can update your documentation and at the same time you can preview it how it would look like after you generate documentation for your project using rendering engine like NDoc or SandCastle –

It gives you real time error message if there is any error with the documentation you created. For example , in the following example, since in line 16 , I missed “name” attribute in paramref , it is showing the error with red bold letter :) -

After fixing the problem, it looks -

In addition , Cr_Documentor provides a context menu that presents great support for documentation like-

Last but not the least, Cr_Documentor also offers options to configure the compatibility level , unrecognized tag handling , Formatting , Display and preview -

Using the options , you can really configure different aspects of your Documentation. For example, if you change the preview style to SandCastle – the preview will look like -

If you want to check it out , you will have to download and Install the DxCore ( A Powerful extensibility framework for Visual Studio) first. Then, you can download and get more details about Cr_Documentor from Google Code.

In conclusion , by leveraging Cr_Documentor, writing and maintaining Xml Documentation for your projects would be far more easy and less error-prone. I can’t help thanking Lutz Roeder and Travis Illig for taking it this far. It’s just wonderful !!!

.Net Provider Pattern - Designing decoupled and extensible Component for .Net Application

Sun, 02 Nov 2008 21:22:00 GMT

Provider design pattern of .Net Framework 2.0 facilitates an approach to design components in a decoupled and extensible manner. Ron Howard mentioned-

“A provider is simply a contract between an API and the Business Logic/Data Abstraction Layer. The provider is the implementation of the API separate from the API itself.”

Provider pattern is a way to get rid of the coupling among the components while making the components extensible. Main reason for our today's discussion on Provider Pattern is its wonderful ability to publish the API and at the same time make the API pluggable; that is-- it gives us the flexibility to choose the API that is best suited for the application rather than the one developed by API developer. And from an API developer perspective, it allows them to create an extension point for the API where clients of the framework can extend the functionality in their own way.

In this post, we investigate this design pattern, and show how we can utilize it to make components decoupled while providing extension points for configuration. To do so, we present the outline of today's discussion as follows-–(read more)

More on Unit Testing : TestContext

Sun, 04 May 2008 10:24:00 GMT

From empirical evidence, we know that improving code coverage by verifying all the boundary conditions, and ensuring quality of code-base significantly enhances maintainability and comprehensibility of complex software systems. Therefore, writing effective unit and integration tests has become one of the integral part in software development life cycle. In fact, development methodology such as TDD has been embraced rapidly due to these realized benefits. In today's post, we talk more about TestContext of mstest. In particular, we focus on its usage in devising effective unit tests. Before moving forward, we would like to outline the previous posts of the series regarding Unit Testing.

What is TestContext?

TestContext is an abstract class of Microsoft.VisualStudio.TestTools.UnitTesting namespace. It exposed several properties related to the current context (i.e., current test run). In addition, it provides following supports: (read more)

Passing Parameter to a Predicate in .Net2.0

Fri, 18 Apr 2008 14:34:00 GMT

In this post, we will see how to pass parameter to a method representing Predicate.

Let's say, we have a collection of SprintBacklogItem and we want to filter all the SprintBacklogItem with Title start's with, let say "QA" or "Dev Task" depending on a input parameter. Now from the previous post we know that , predicate only have 1 parameter of type T.

Then, how to pass a input parameter _HeaderToSearch in Predicate?

1. To do that, we need to a new object called ListMatcher -

public class ListMatcher 
   { 
       private string _HeaderToSearch; 
       public ListMatcher(string headerToSearch) 
       { 
           _HeaderToSearch = headerToSearch; 
       }  

       public bool Predicate(SprintBacklogItem item) 
       { 
           return item.Title.StartsWith(_HeaderToSearch, StringComparison.InvariantCultureIgnoreCase); 
       }  

   }

2. Next , I initialized the ListMatcher object and use the HeaderToSearch to filter the items-

ListMatcher matcher = new ListMatcher("QA"); 
this.FindAll(matcher.Predicate);

Done.:)

TDD - In a Nutshell

Fri, 18 Apr 2008 12:58:00 GMT

"One Picture's Worth Thousands Words"

Benefits( from my personal experience):
1. Development can be done much quicker. You already jot down all the test cases before writing codes. By that way, you are giving much time in thinking how to solve problem. Codes become much more standard and organized because of the brainstorming.
2. Quality of code is far better and deterministic.
3. Tests are the first class document for how your code will eventually work. Any developer/tester can go through the test cases you covered and get the idea how the system should work in different cases. J Isn’t it too cool ?
4. Easier and risk free to change the code - you just need to run the tests, you will get to know where there might be some problem.

And so on...

Why is Unit Testing so important?

Fri, 18 Apr 2008 11:47:00 GMT

Moved to http://adilakhter.wordpress.com/2008/04/18/why-is-unit-testing-so-important/