Author: adilakhter

Solidarity with Shahbag

The shahbag movement is a long-overdue protest against the war criminals of Bangladesh who were associated with the killing of around 3 million Bangladeshis and raping/torturing around 200 thousands women and children . To demand capital punishment for the war criminals (e.g., Abdul Quader Molla) and to ban on Bangladesh’s largest Islamic party, tens of thousands talented youth have been protesting at SHAHBAGH for last 8 days. Our only demand is to seek justice against the war criminals for their atrocities committed during the liberation war of the country in 1971. While the wikipedia page details about this historic event, the following video summarizes our message.

“Injustice anywhere is a threat to justice everywhere”-Martin Luther King Jr.

#shahbag Courtesy: Faisal Nahian
Supporting Shahbag Protest at Stuttgart Source: http://en.wikipedia.org/wiki/2013_Shahbag_Protest
Solidarity with #shabag from Hague Netherlands
“Bangladeshi social activists participate in a rally demanding the death sentence for the country’s war criminals in Dhaka.”
“The country has finally united against an enemy that has burdened it with corruption and hatred even before it was born.” ©Rajiv Ashrafi

The shahbag movement is a long-overdue protest against the war criminals of Bangladesh who were associated with the killing of around 3 million Bangladeshis and raping/torturing around 200 thousands women and children .  To demand capital punishment for the war criminals (e.g., Abdul Quader Molla) and to ban on Bangladesh’s largest Islamic party, tens of thousands talented youth have been protesting at SHAHBAGH for last 8 days.  Our only demand is to seek justice against the war criminals for their atrocities committed during the liberation war of the country in 1971. While the wikipedia page details about this historic event, the following video summarizes this dark spot of humanity.


This post is my humble tribute to the tens of thousands of people who are relentlessly protesting at SHAHBAGH. And, we will not stop until we get justice.

We, the youth of Bangladesh… all we seek JUSTICE, nothing more or nothing less…

Last but not the least, I would like to express my gratitude to all who are expressing solidarity with SHAHBAG from all over the world. Nation will never forget your contributions. Being a Bangladeshi, I have never been so proud. I am so overwhelmed that I am literally standing tall.

Solidarity with #shahbag from The Netherlands.

Recent Updates

For recent updates on #shahbag, please visit  shahbag.org. জয় বাংলা !

Project Euler 06. Sum square difference with F#

Problem Definition

Available at Sum square difference

The sum of the squares of the first ten natural numbers is,

12 + 22 + ... + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025-385 = 2640.Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Implementation

open System
let squareOfSum n =
let i = n*(n+1)/2
i*i
let sumOfSquare n =
[1..n]
|> List.fold (fun acc x -> acc + x*x) 0
let solveEuler6 N =
(squareOfSum N)- (sumOfSquare N)
view raw euler06.fs hosted with ❤ by GitHub

Project Euler 04. Largest Palindrome Product with F#

Problem Definition

Available at Largest Palindrome Product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 * 99.

Find the largest palindrome made from the product of two 3-digit numbers.

Implementation

We have to find out a palindrome p such that —

where both  a and b are  three digit number.  To do so, we first define a function that checks whether a  number (e.g., p) is a palindrome.

let ispalindrom (x:int):bool =
let s = x.ToString()
s = (s |> (fun x -> new string(x.ToCharArray() |> Array.rev)))
view raw ispalindrom.fs hosted with ❤ by GitHub

Then, we  iterate over all the tuples (a,b) of three digit numbers  e.g.,  [100..999]  that satisfy the  following equation.

Finally, we check if a*b is a palindrome and get the largest palindrome, as outlined below.

seq{
for x in 100..999 do
for y in x..999 do
if ispalindrom (x*y) then yield (x*y)}
|> Seq.max
view raw euler04.fs hosted with ❤ by GitHub

Would/did you solve it differently? Please let me know your opinion in the comment section below.

Happy problem solving …

problem solving

SPOJ 6219. Edit Distance (EDIST) with F#

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.

Implementation

Using Dynamic Programming, we can compute the edit distance between two string sequences. But for that, we need to derive a recursive definition of Edit Distance. We denote the distance between two strings as D, which can be defined using  a recurrence as follows.

Case 1 : Both and are empty strings, denoted as :

Case 2 : Either or is :

Case 3 : Both and are not :

daum_equation_1359460361956

Here , where is the last character of and contains rest of the characters. Same goes for .  We define edit distance between and using a recurrence and in term of and .

can be defined as the minimum, or the least expensive one of the following three alternatives stated in the above equation.

  • Substitution: If , then the overall distance is simply . Otherwise, we need a substitution operation that replaces with , and thus, the overall distance will be .
  • Insertion: Second possibility is to convert to by inserting in . In this case, the distance will be . Here, +1 is the cost of the insert operation.
  • Deletion: Last alternative is to convert to by deleting from that costs +1. Then the distance become .

As this is a ternary recurrence, it would result in an exponential run-time, which is quite  impractical. However, using the dynamic programming with memoization, this recurrence can be solved using a 2D array. The code to solve this problem is outline below.

let computeEditDistance (source:string,target:string) =
let height,width = (source.Length, target.Length)
let grid: int [,] = Array2D.zeroCreate<int> (height+1) (width+1) // 2D Array for memoization
for h = 0 to height do
for w = 0 to width do
grid.[h,w] <-
match h,w with
| h,0 -> h // case 1 and 2
| 0, w -> w
| h, w ->
let s,t = source.[h-1],target.[w-1]
let substitution = grid.[h-1,w-1]+(if s = t then 0 else 1)
let insertion = grid.[h,w-1] + 1
let deletion = grid.[h-1,w] + 1
min (insertion, deletion, substitution) // case 3
grid.[height,width]
view raw gistfile1.fs hosted with ❤ by GitHub

As shown in line 14, the distance grid.[h,w] can be computed locally by taking the min of the three alternatives stated in the recurrence (computed in line 11,12, 13). By obtaining the locally optimum solutions, we eventually get the edit distance from  grid.[s.length, t.length].

Complexity: Run-time complexity: . Lets denote the lengths of both strings as . Then, the complexity become . Space complexity is also same.

Complete source code is outlined in the next page.

Pages: Page 1, Page 2

Reversing List in groups of given size with F#

Problem Statement:

Given a list, write a function to reverse every K element when k is an input to the function.

Example:

Input: [1;2;3;4;5;6;7;8] and k = 3
Output:[3;2;1;6;5;4;8.7]

In case of an empty list, it just returns [].

Solution with F#:

From the problem definition, the signature of reverseK is quite trivial:

val reverseK : x:int list -> k:int -> int list
view raw gistfile1.fs hosted with ❤ by GitHub

In order to implement this function, we have used int list list, which in essence, acts as an accumulator to store the intermediate results. In addition, for every Kth element, we are creating a new list (Line 5) and resetting counter i to zero for further processing.  In a sense, we are splitting the list in K chunks and reversing it.

let rec reverseK (x:int list) (k:int):int list=
let rec reverseKAux (x:int list) (acc:int list list) (i:int)=
match x with
| [] -> acc
| xhd::xtl when k=i ->
reverseKAux (xhd::xtl) ([]::acc) 0
| xhd::xtl ->
match acc with
| h::t -> reverseKAux xtl ((xhd::h)::t) (i+1)
| [] -> reverseKAux xtl ([xhd]::[]) (i+1)
in
reverseKAux x [[]] 0
|> List.rev
|> List.collect (fun x -> x)
view raw gistfile1.fs hosted with ❤ by GitHub

These results are afterwards reversed and flattened using List.rev and List.collect as shown in Line 13 and in Line 14.

Algorithmic Complexity:

Complexity of the above algorithm: O(n).

Solution with c:

An implementation of this problem in C is available here.

Output:

> reverseK [1;2;3;4;5;6;7;8] 3;;
val it : int list = [3; 2; 1; 6; 5; 4; 8; 7]
> reverseK [] 3;;
val it : int list = []
view raw gistfile1.fs hosted with ❤ by GitHub
Design a site like this with WordPress.com
Get started