My Website

Guys,
Recently I ve hosted my Website.

Check it out.
http://s4sagar.co.cc

My Toolbar For Firefox, Especially for SASTRA Students

Download the file and Drag and Drop into Firefox.
Check it out !
Comments Welcome.
After Installing, Dont forget to :
“Heart-Icon -> Share It”
Enjoy.

http://kontactr.com/sagar/s4sagar.xpi

Mozilla Labs Jetpack – Google It! :: jetpack

Mozilla Labs Jetpack – Google It! :: jetpack.

Add-ons for Mozilla Firefox

Hi guys ,
Recently i have written two addons for Mozilla Firefox using the Jetpack utility.
You can install them from:
http://kontactr.com/sagar/GoogleIt.html
http://kontactr.com/sagar/exploreRelated.html

Comments Welcome.

About Recursion

Recursion is the technique to solve problems by dividing the problem into :

1. A Base Case / Termination Condition.

2. A Sub-Problem / Recursive Call.

3. Combining the results of Sub-Problems to obtain the final result.

Wanna Experience Recursion ? Click the following link …

http://s4sagar.wordpress.com/2009/07/30/about-recursion/

Another funny example for recursion ,

Try googling “recursion”

http://www.google.co.in/search?hl=en&rlz=1C1CHMI_en-USIN307IN308&ei=6ARySvSgB5zW7AOB7oyrCw&sa=X&oi=spell&resnum=0&ct=result&cd=1&q=recursion&spell=1

You will see a “Did  you mean : recursion”

Try clicking “recursion” in “Did you mean: recursion” and you will understand what recursion is

Examples:

1. Factorial Problem

Problem Statement :  To evaluate n !

Recursive Solution :

unsigned int fact ( int n )  {

if( n <= 1 ) return 1;

return n * fact ( n -1 ) ;

}

Terminating Condition /Base Case : n <= 1

Sub-Problem : To evaluate fact( n – 1 )

Final Solution : n * fact ( n  -  1 )

You can see that it combines all the subproblems together .

Advantages :

1. Small source code.

2. Easy to code and understand.

Disadvantages:

1.Take a lot of memory if the recursion depth is high.

For Example, if fact( 500 ) is called,it has to push 499 intermediate results into the System’s Stack before it can evaluate the result.

Simple Optimisation:

unsigned int  fact( int n ) {

int result = 1 ;

for( int i = 2 ;  i <= n ; ++ i )

result *= i;

return result;

}

You can see that there is no time wasted in the flow of controll between functions and its sub-functions , and storing the intermediate values into the stack. You can thus save the Storing and Fetching time into the stack.

Hmm .. Its 3 : 17 A.M already , Guess i ll link you guys to more resources …

2. Fibonacci Series :

http://www.cs.northwestern.edu/academics/courses/110/html/fib_rec.html

3.Towers of Hanoi:

http://www.cs.cmu.edu/~cburch/survey/recurse/hanoi.html

You also get the solve the Tower Of Hanoi by urself in the above link

(Browser should JavaScript 1.2 Enabled)

4.Eight Queens Problem:

http://www.animatedrecursion.com/advanced/the_eight_queens_problem.html

More general n-Queens problem :

http://theory.cs.uvic.ca/amof/e_queeI.htm

5. An example TopCoder Problem :

Problem Statement
	There is nothing more beautiful than just an integer number. You are given an integer n. Write down n in decimal notation with no leading zeroes, and let M be the number of written digits. Perform the following operation exactly ktimes: Choose two different 1-based positions, i and j, such that 1 <= i < j <= M. Swap the digits at positions i and j. This swap must not cause the resulting number to have a leading zero, i.e., if the digit at position j is zero, then i must be strictly greater than 1. Return the maximal possible number you can get at the end of this procedure. If it’s not possible to perform k operations, return -1 instead.
Constraints
-	n will be between 1 and 1,000,000, inclusive.
-	k will be between 1 and 10, inclusive.
Examples
0)
	16375 1 Returns: 76315 The optimal way is to swap 1 and 7.
1)
	432 1 Returns: 423 In this case the result is less than the given number.

More Links:

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Recn/

http://www.topcoder.com/tc?module=ProblemArchive&sr=&er=&sc=&sd=&class=&cat=Recursion&div1l=&div2l=&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=

- Vidya Sagar S

TopCoder Profile : http://www.topcoder.com/tc?module=MemberProfile&cr=22652618

s4sagar@gmail.com

Useful Links for Programming

Some Very Useful Educational Tutorials :

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index

The above link has a lot of tutorials to master yourself in Algorithmic C/C++ Programming . The tutorials are very well explained with lots of examples and practise problems . Its a very good way to learn algorithms .

The tutorials are written by World’s Best Programmers accross the Globe , so you can expect great clarity and efficiency. I assure you that it will be a very enjoyable experience !

Learning the Standard Template Library (STL) :

Today no programming contest uses the Borland’s C/C++ Compiler. Every popular contests require the programmers to code in accordance to GCC/ G++ Compiler ( GNU C Compiler ). It has a lot of improvements and new datastructures , and thus makes programming a very comfortable and pleasurable experience. So , learning the STL is almost a must in today’s scenario.

The best place to Learn STL : http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary

An awesome Problem Arcive :  http://www.topcoder.com/tc?module=ProblemArchive

For beginners : http://www.topcoder.com/tc?module=ProblemArchive&sr=&er=&sc=&sd=&class=&cat=&div1l=&div2l=1&mind1s=&mind2s=&maxd1s=&maxd2s=&wr=

The above link gives you a lot of very easy problems and helps you a lot to improve your programming skill and to develop a sequential logicalcal flow to solve problems .

Once you are comfortable solving the Division 2 Level 1 Problems , you can proceed to Division 2 , Level 2 Problems .

Some world-class Problems : http://www.spoj.pl/problems/classical/

I would suggest one not to try the above link before gaining a good grip in Algorithm Programming from TopCoder . Trust me , it could be very de-motivating to be unable to solve even a single problem .

Programming Contest Calender : http://www.algorithmist.com/index.php/Programming_Contest_Calendar .

Hey visitor, pass the word about this blog if you find it useful.

Feel Free to Leave Your Comments .

Also check out my other article about participating in Algorithm Competitions.

Competing in algorithm competitions

The following article was published in the Cypher Magazine of School Of Computer Sciene Engineering at SASTRA University, Thanjavur, India
Introduction:

Today almost every college has its own online programming contest (SASTRA’s – DOPE : www.daksh.sastra.edu/dope/).
This article is about the requisites for competing in such competitions and how to go about participating in them.
Requisites:

1. Good hold on any programming language – either C, C++, Java, or C#,
C++, C being the most popular languages used for contests.

2. Some knowledge about complexities of code, time of execution and
some debugging skills.

And all the above comes together only with sheer interest and hard work.
The beginning:
1. Make yourself comfortable with the usual C , C++ lab exercises to master
the usage of loops , conditioning and some elementary functions like swap,
search, etc and also some basic data structures including arrays and classes .

2. If you are planning to code in C++ , make sure you first learn the syntaxes of the
Linux based C++ compiler ( g++ ) used in contests.

An amazing link :
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=standardTemplateLibrary

You have to become a member to access the resources.

C users can use the usual syntax, with just a few variations.

For JAVA, you might want to go through its set of “collections” : http://java.sun.com/docs/books/tutorial/collections/index.html

C# has its base class libraries to be seen : http://msdn.microsoft.com/en-us/netframework/aa569603.aspx

3. Become a member in sites like topcoder.com, or spoj.pl , or acm and watch out for contests.

Algorithmist integrates almost all the leading sites’ contest calendar

4. Practice the easy problems from the problem set in TopCoder, or other above mentioned sites. I would suggest u to start with the 250 pointers of TopCoder because they are fairly simple and help u get rid of your errors in the initial stages.

The process of learning:


1. Keep practicing problems from a problem archive.

TopCoder’s archive:  http://www.topcoder.com/tc?module=ProblemArchive
SPOJ’s archive:  http://www.spoj.pl/problems/classical/

2. Keep learning new data structures , StandardTemplateLibrary functions
( Not for C coders)Java, C# and algorithms .
An introduction to Algorithms – by Thomas H Cormen, is a great book to learn algorithms. It also explains about code complexities and time of execution. But I would suggest u to start with the book only after you are comfortable with easy problems like TopCoder’s 250 problems.

3. Looking at others’ code also helps a lot in the process of learning. Although this feature is not available in SPOJ, or ACM , TopCoder gives you this wonderful feature to look at others’ codes.

4. Challenging others’ code (again available only in TopCoder ) helps you to identify the boundary cases and this helps u a lot in typing programs which do not access data out of the boundary , or run in an infinite loop.

Some common un-optimized codes written :

1. Dont use:
for(int i=0;i<strlen(str);i++)
{ … }

Instead use
int l=strlen(str);
for(int i=0;i<l;i++)
{ … }

Each time you call strlen() , it manually goes through the array counting each character. Suppose the string length is 1000. The first loop will take 1000*1000 operations as strlen is called for every iteration. The second loop takes only 1000 operations ( excluding what goes on inside the loop of course )

2. Size() returns unsigned int :
And if you use something like
for(int i=0;i<A.size() – 2 ;i++)
{ … }
Where A is a vector, when the size of the vector is less than 2 , the loop still executes abs( A.size() – 2 ) times since size() returns an unsigned int and when we subtract a number from an unsigned int we get an unsigned int

3. Don’t use long long everywhere in your program. Its very slow compared to int.

4. scanf() is faster then cin .

5. Arrays are faster than vectors.

Some usual errors from the online judge :

• Time Limit Exceeded – A very familiar judge result on Spoj. It means your program took too long to execute. Try optimizing your program and check for accidental infinite loops.

• Wrong Answer – Your program ran on time, but it did not produce the required output.

• Compile Error -Your program had some syntax error. For these errors, click on the text “Compile Error” in the judge result. It`ll take you a page which will list the compile errors and their line numbers in your program.

• Runtime Error – This is usually accompanied by a code like SIGSEV. It can happen due to a lot of reasons, but the two most common are using too much memory ( you can use around 6000*6000*4 bytes of memory ). Other reasons can be there like Divide by Zero.

Conclusion :
“Practice makes a man perfect”
Practice, practice and more practice is all that it takes to reach the top.

Hey visitor, pass the word about this blog if you find it useful.

Feel Free to Leave Your Comments .

- Vidya Sagar , I year , CSE , SASTRA University , India
TopCoder handle : s4sagar
TopCoder profile: http://www.topcoder.com/tc?module=MemberProfile&cr=22652618