Algorithms Forum RSS Feed (Replies Included)

8 queens problem

Tue, 17 Nov 2009 01:01:45 -0700

hello,

can someone help me wiht writing the algorithm for the 8 queens problem.

Thanx,
akshay

Unique Number Generation

Tue, 10 Nov 2009 23:35:44 -0700

Hi,

Suppose I have a list of numbers, say (a,b....n) i want to generate a unique number say u so that no other list, say (a1,b1... n1) will not give a number u1 and u!=u1 if (a,b...n)!=(a1,b1...n1)

More over (a,b,...n) is same list as (b,a...n), so they should both generate u, ie order does not matter.

Any one has any idea?

What i came up with is (a+b+...n)+(a*b*...*n), can this fail in any time?

Regards,
Jishnu

Re: Find ANY ONE of the k smallest elements

Sun, 25 Oct 2009 20:58:03 -0700

oh wow nevermind the answer is so simple =/

I don't even need to think about k-select algorithms here!

Find ANY ONE of the k smallest elements

Sun, 25 Oct 2009 03:22:40 -0700

Hey guys, I was hoping someone could help me out with this problem, I might be over thinking it too much and the answer might be very simple but its not getting to me.

The problem has to deal with the k-smallest element problem, you are given n elements and an integer k such that 1 < k < n. The problem is to find ANY ONE of the k smallest elements.

So for example, if k = 4, the output may be either the first, second, third, or fourth-smallest element.

I am looking for a FAST algorithm to solve this problem and to figure out how many comparisons it performs. I also need to give a lower bound as a function of n and k on the number of comparisons needed to solve this problem.

Any help is appreciated, thanks!

Joey

Re: a tiny problem

Thu, 22 Oct 2009 12:48:55 -0700

No, that's the mod operator. So,
-20 % 24 is equivalent to -20 mod 24 (in psuedo code).
If you are questioning the math behind it, here is the complicated answer: http://en.wikipedia.org/wiki/Modular_arithmetic

Consider:
52 % 24 = 4
28 % 24 = 4
4 % 24 = 4
-20 % 24 = 4

52 = 2 * 24 +4
28 = 1 * 24 + 4
4 = 0 * 24 + 4
-20 = -1 * 24 + 4

Re: a tiny problem

Sat, 17 Oct 2009 20:41:48 -0700

-20%24=4???How do calculate that?!Is it not -20?!

Re: a tiny problem

Fri, 16 Oct 2009 10:42:43 -0700

(2 - 22) = -20
-20 % 24 = 4
Bear in mind that % returns the remainder of the division of its arguments.

Re: a tiny problem

Thu, 15 Oct 2009 19:46:01 -0700

The slightly longer answer is
SIZE = 24

def dis(a, b):
d1 = (a - b) % size
d2 = (b - a) % size
return min(d1, d2)
-----------------------
It dosen't work:
a=22,b=2
d1=(22-2)%24 = 20
d2=(2-22)%24 = -20
min(d1,d2)=20 is not the right answer 4?!!!!!??!!?!

Re: a tiny problem

Thu, 15 Oct 2009 15:24:57 -0700

The short answer in Python is

lambda a, b, size: min((a - b) % size, (b - a) % size)

where a and b are inputs and size is the number of elements (24 for this case).

The slightly longer answer is
SIZE = 24

def dis(a, b):
d1 = (a - b) % size
d2 = (b - a) % size
return min(d1, d2)

And, if you don't like modular arithmetic,
SIZE = 24

def dis2(a, b):
high = max(a, b)
low = min(a, b)
dis1 = high - low
dis2 = SIZE - dis1
return min(dis1, dis2)

That one only works for values of a and b in range(0, 24), but it saves you the trouble of having to understand modular arithmetic. ;)

a tiny problem

Fri, 09 Oct 2009 01:22:49 -0700

As the following picture:
It's a circle that is consist of the numbers,how can i simply calculate the distance between some tow numbers,for example,5 and 8 is 3;22 and 2 is 4 ???????????
0 1 2 3 4 5
23 6
22 7
21 8
20 9
19 10
18 11
17 16 15 14 13 12

Algorithm for finding out the cheapst combination

Fri, 09 Oct 2009 00:36:44 -0700

Hello, I have a few sets which are like

SET A(1,2,3,11,10) - $30
SET B(2,5,8) - $20
SET C(6) -$25
SET D(6,8) -$30
SET E(7,5) -$20
SET F(5,6,7,8,9,10) -$60
.
.
.

and so on... All are random, Now consider sets D,E and F I want to buy the cheapest combination for a set, SET Q(7,8,6,5) the answer should be SET D + SET E, not the SET F

Please link... thanks

Re: About random question

Sun, 04 Oct 2009 13:08:00 -0700

I don't know what hardware you have or what the purpose is, but there are a few generic options.

The last used seed number could be stored into permanent memory (if available) and used the next time when needed. This way the random values are good as long as the seed isn't lost.

Maybe you don't even need very good random values? That would be the case if the values are needed for doing something not so important, like making a visual effect, for example. Then you could just use any preset seed value.

If you have some input to your MCU, then you can sample values from it. For example, consider an electronic dice. One way to get a random value is to measure the time between pressing the key and releasing it. (You may not have time, but maybe you have a timer). Be creative!

There are special additional chips for generating random bits, but you can also use things like accelerometers, thermistors, photoresistors, etc. to gather variable data from the environment.

Optimization problem with sets.

Sun, 04 Oct 2009 07:17:00 -0700

Hello!

I have a set that contains maximum 10^6 items. All item are 4^n number, where 0 <= n <= 11, all items have a price that can be 1 <= price <= 10^8. And I also have another number k, where k is 4^n number and 0 <= n <= 11. The items are ordered monotonically first according to size of numbers, then to prices.
I want to take the sum of the items that equal to number k, and the price is minimal.

The example:
A := {16(1),16(2),16(3),16(4),64(11)}and k=64. (format: Number (price) -> 16(1))
So, the solution is 16(1),16(2),16(3),16(4), because 1+2+3+4=10 smaller then 11.

Any idea?
Thanks!

Re: About random question

Mon, 28 Sep 2009 07:35:42 -0700

If I use a 8-bit MCU,there is no explicit system time,so how can i
get the seed source?!Thank you!

Re: About random question

Mon, 28 Sep 2009 00:56:41 -0700

It depends.

For security-related applications, where you would want to create random keys so that a third party couldn't guess them, using only the time is not enough. The operating system typically provides means of creating better random values (Linux and Mac have /dev/random, Windows has a cryptography API). The OS uses seeds such as disk writes per second, processor cache misses, port I/O, time, etc.

For artificial intelligence, fuzzy logic or things like that, using 1-2 seeds is fine. But because time is very predictable and changes at a fixed rate, then in some cases it might not seem random enough. Then you would use a formula like you described to constantly recalculate the seed number based on the current time and the previous seed number.

Time is a good seed, because it is one of the few metrics that are readily available for all programs at any permission levels. You would need admin access to get values from other system hardware. Another value that is often used in games is the time between keypresses, however many other applications don't get any keyboard input at all.

The formula Rand_Number = (Rand_Seed * X + Y) mod Z is good, because there is a good chance the number will overflow because of the multiplication. This means the higher digits are discarded, because they won't fit into the 32 or 64 bits the computer uses to store the number. Without the formula, the seed number would only change linearly, because time is linear.

About random question

Sun, 27 Sep 2009 22:01:07 -0700

Hi, guys!
I have read a lot algorithms about random-generation,most of them use the system time as the seed,and then calculate it with
formula Rand_Number = (Rand_Seed * X + Y) mod Z, why use the system time as the seed,is it random enough? then if the seed is random,why calculate it again through this formula?

( WWW.Sneakers2World.COM ) Nike Air Max Tailwind 2010

Sat, 19 Sep 2009 02:38:49 -0700

( WWW.Sneakers2World.COM ) Nike Womens Air Max Skyline

( WWW.Sneakers2World.COM ) Nike Air Zenyth Womens Sneakers

( WWW.Sneakers2World.COM ) Nike Air Zenyth Mens Sneakers

( WWW.Sneakers2World.COM ) Nike Air Max Tailwind 2010

(WWW.Sneakers2World.COM) Wholesale Nike Air Force 1

Sat, 19 Sep 2009 02:37:24 -0700

(WWW.Sneakers2World.COM) Wholesale Nike Air Force 1, Nike Air Force 1 Low, Nike Air Force 1 One

(WWW.Sneakers2World.COM) Wholesale Air Force One 25 Anniversary sneakers, Nike Air Force One 25 th Sneakers

(www.sneakers2world.com ) Nike Air Force 1 for Sell, Nike Air Force 1 Low, Nike Air Force 1 Mid, Nike Air Force 1 exclusive,
Nike Air Force 1 special edition

(WWW.Sneakers2World.COM) Nike Air Max 1 OG

Sat, 19 Sep 2009 02:36:38 -0700

(WWW.Sneakers2World.COM) Nike Sportswear Nike Air Max 1,aka Nike Air Max

(WWW.Sneakers2World.COM) Nike Air Max 1 OG

(WWW.Sneakers2World.COM) Nike Air Max 1 Original Quickstrike

(WWW.Sneakers2World.COM) Patta x Nike Air Max 1 Trainers wholesale

(WWW.Sneakers2World.COM) Patta x Nike Air Max 1 Premium Tier Zero Holiday 2009

Accept Paypal ( WWW.Sneakers2World.COM ) cheap discount wholesale Nike

Sat, 19 Sep 2009 02:35:49 -0700

Accept Paypal ( WWW.Sneakers2World.COM ) cheap discount wholesale Nike Air Force One Low
Accept Paypal ( WWW.Sneakers2World.COM ) cheap discount wholesale Nike Air Force One High
Accept Paypal ( WWW.Sneakers2World.COM ) cheap discount wholesale Light Up Nike Air Force One
Accept Paypal ( WWW.Sneakers2World.COM ) cheap discount wholesale Obama Custom Air Force One
Accept Paypal ( WWW.Sneakers2World.COM ) cheap discount wholesale Nike SB Dunk Low

Re: Creating .ISO files...

Wed, 16 Sep 2009 23:51:18 -0700

If you use a Mac, this is a tutorial on how to use DVD Copy (to ISO) Tool to create ISO image from DVD on Mac.

Now you have finished creating an ISO File to your Mac, then you can enjoy watching your movie on your Mac or sharing with others.

Tips: You can review the ISO image by using the Finder to mount the .iso image (double click) and DVD Player to play the DVD by specifying the location of the VIDEO_TS folder in the mounted image, you also can know more details about playing ISO file on your Mac.

And if anytime, you want to burn the ISO file to another DVD disc, Know more How to Burn ISO file to DVD on Mac.

Software Development training

Sun, 06 Sep 2009 08:00:06 -0700

Hi Guys

I would like to develop web based database/applications.

I would like to develop websites, web based database type applications and web based forum applications

I am a total beginner into this field and would like some help with training.

There are several things out there like PHP,.net,mysql,SERVOY...........

Can somebody suggest the best platform/language for this type of job?

I am planning to take some training and then hopefully get started.

John

Genetic algorithm

Sun, 30 Aug 2009 06:04:47 -0700

Hello, i am a new user of Matlab
and i want to create a genetic algorithm optimizing the wights of a fuzzy map. my problem is that i am not familiar with the genetic algorithm functions of matlab and, thus, i cant insert propely my objective function. any tips ?

Levenshtein algorithm

Sat, 22 Aug 2009 06:33:16 -0700

hi,i just came across the string distance algorithm.
I took a paper and a pen to work out the exact algorithm.The answer seems to be correct.
But i could not understand why it is like that.
to fill d[i][j]
we look left,top,left diagonal.
(i guess this is where we check whether to insert,replace or delete)
But i am not sure how it is and why it is.
Can someone explain me why d's are checked for all three conditions .
I went throught this algo in wiki andhttp://www.merriampark.com/ld.htm

Optimization

Sat, 01 Aug 2009 18:32:21 -0700

Hello! I am a beginner programmer. I have a problem with the runtime of one of my applications.

I have a website application that tries to compute for recommended objects to users. The recommended results is based on the user as well as the currently viewed object.

My problem is, I have 500 artworks and almost 30 users. What I do is, for each user, I compute the value for recommendation for EACH artwork. So that means, for 1 object, I compare ALL of the other objects to it. Then after the computation, I store it in the Database. So for each user, I have around 250000 records inside the Database.

Can I have any tips regarding on how to optimize it? Either some changes to the Database model or some changes to the code. I have 3 FOR loops (1 for user, 1 for viewed object, 1 for target objects). I have already tried using UNION ALL, but the INSERT statements doesn't seem to be the case.

Help please!