jQuery

Fourth day of coding in java script & I have already written one fairly advanced app. Also today I started learning jQuery too. For javascript n00bs let me clarify- jQuery is the awsmest js library of this world written by another God John Resig.
jQuery  program I wrote today was - dynamic tab adder & remover in  arbitrary js container. I currently dont have functionality to support downloads through blogger but I hope to add it soon enough so I ll put for download all my work.

I have never found anything so exciting to codeup as whole javascript paradigm. I found my first ever dynamic scoped lanuage in js. What that means is :

If I have some variables in a program & user at run time enters a string say "totalSalary" , I can show him the contents of the variable "totalSalary". If you think this is trivial to do in your favorite static language- think again !

//TODO: 1) Creation of own home page in full javascript.
//TODO: 2) An auto suggest box

Dominoes

Source: Spoj.pl

Problem: We have n sticks standing at some points on number line. Location & height of each are given . A single knock( to left or right) of some stick with knock all sticks which it touches. That is if a stick of height h at location h is knocked right , it will knock all sticks at x+1 , x+2....x+h.

Given all sticks' information , Find the minimum number of knocks required to knock all the sticks. We can only spend O(nlogn) time at max.


Link to exact problem page here.

Adding Fractions

Source: CodeChef April Challange. See here

Problem: You have an array A of length n with each entry stroing a fraction a/b.
Define B[i] as length of sequence starting at i such that sum of fractions of this sequnce is largest amongst all sequnces beginning at i. Sum of a/b & c/d is defined to be (a+b)/(c+d).
Compute Array B given A.

LCM Sum

Source : CodeChef

Problem: Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.

Update:  Solution given by a friend Tarundeep posted  in comments.

Finding smallest cycle

The inspiration of this problem comes from an exam problem which I extended beyond limits of exams .

We are given a graph with edge weights which can be negative . There might be negative cycles as well in the graph. Given a vertex v, find the smallest simple cycle containing v.

Bin Packing ( Simplied Version )

Source : Problem from tutorial sheet of ADA ( course at IITD in algorithm design )

Problem : We are given n1 objects of type 1 with size s1 each , n2 of type 2 with size s2 each & n3 of type 3 with size s3 each. We have a large supply of bins each of size S. Find the minimum number of bind needed to pack all the objects. ( Obvly , Objects are not to be cut in fractions )

The begnning

This blog would be the place where I would be venting out my love for maths , algorithms , puzzles & programming. You are welcome to contribute. :)