Algorithms

Discuss everything related to IOI here. For more general or advanced topics use CS forum.

Moderators:Labib, bristy1588

User avatar
Zzzz
Posts:172
Joined:Tue Dec 07, 2010 6:28 am
Location:22° 48' 0" N / 89° 33' 0" E
Algorithms

Unread post by Zzzz » Wed Feb 09, 2011 1:42 pm

Can anyone suggest some useful algorithms? For example, I have just learned Dijkstra's algorithm.

If possible please give some links also.

Important: Please don't think that, Zzzz probably knows this 'easy and wellknown' algorithm, so I need not to suggest it.
Every logical solution to a problem has its own beauty.
(Important: Please make sure that you have read about the Rules, Posting Permissions and Forum Language)

User avatar
Mohaimin
Posts:38
Joined:Thu Dec 09, 2010 7:38 pm
Location:Dhaka
Contact:

Re: Algorithms

Unread post by Mohaimin » Thu Feb 10, 2011 8:03 am

For fast prime number generation, learn Sieve of Eratosthenes.

HandaramTheGreat
Posts:135
Joined:Thu Dec 09, 2010 12:10 pm

Re: Algorithms

Unread post by HandaramTheGreat » Thu Feb 10, 2011 9:24 am

আমি সর্বসাকল্যে তিনটা অ্যালগো জানি... :mrgreen:
bubble sort (i dunno quick sort, but there's a ready-made one --- qsort under stdlib.h)
prime power factorization (trial division)
binary search (& linear search too :P )
euclid's algorithm
আরে! চারটা হয়ে গেল!

HandaramTheGreat
Posts:135
Joined:Thu Dec 09, 2010 12:10 pm

Re: Algorithms

Unread post by HandaramTheGreat » Thu Feb 10, 2011 10:26 am

can anyone give some reference to understand time complexity? i just know what it is, haven't enough knowledge 'bout it...

abir91
Posts:52
Joined:Sun Dec 19, 2010 11:48 am

Re: Algorithms

Unread post by abir91 » Thu Feb 10, 2011 4:11 pm

@Hadaram: Here.

I guess you probably already know this. Let me repeat again -- "Algorithm is a creative process. You will go nowhere near to achieving competency in algorithm design by trying to "understand algorithms" better." So I suggest a better way can be try to solve a problem. If you are stuck, post the problem here. I will give you appropriate references without spoiling everything. This approach is better than learning lots of algorithms is because if you know a lot of algorithms, after a while, you will start losing your ability to think "out of the box". :)

Some elaboration. When you see an algorithm. Ask these questions:
"What if I remove this step and replace it with something else?"
"What are the limitations of this algorithm?"
"What are the similarities between algorithm A and algorithm B?" etc.

So, here goes a problem from me:

Given an array of n natural numbers. Find the k-th element of the array. Try to make your algorithm as efficient as possible.
Abir

Have you read the Forum Rules and Guidelines?

HandaramTheGreat
Posts:135
Joined:Thu Dec 09, 2010 12:10 pm

Re: Algorithms

Unread post by HandaramTheGreat » Thu Feb 10, 2011 7:30 pm

thanks for your valuable suggestions... :)
array[k-1] would be required element...

abir91
Posts:52
Joined:Sun Dec 19, 2010 11:48 am

Re: Algorithms

Unread post by abir91 » Thu Feb 10, 2011 10:57 pm

Sorry for the confusion. The question asks to find the k-th smallest number from the array (all the numbers are unique)
Abir

Have you read the Forum Rules and Guidelines?

HandaramTheGreat
Posts:135
Joined:Thu Dec 09, 2010 12:10 pm

Re: Algorithms

Unread post by HandaramTheGreat » Wed Feb 16, 2011 3:54 pm

sorting the array, array[k-1]...

abir91
Posts:52
Joined:Sun Dec 19, 2010 11:48 am

Re: Algorithms

Unread post by abir91 » Wed Feb 16, 2011 7:11 pm

Good try! So it is O(N log N) now. Can we do better?
Abir

Have you read the Forum Rules and Guidelines?

HandaramTheGreat
Posts:135
Joined:Thu Dec 09, 2010 12:10 pm

Re: Algorithms

Unread post by HandaramTheGreat » Wed Feb 16, 2011 9:03 pm

i can't find another way... let alone 'better'...

Post Reply