Algorithms Forum RSS Feed

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

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

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

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!

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

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!

firmware anaysis: which algorithm/encryption uses?

Thu, 16 Jul 2009 11:59:24 -0700

can you help me find out if/which algorithm it's used by this router firmware (V2.04)
which are the most important indications that must be focused on,
looking at the source codes here:
ftp://ftp.dlink.co.uk/GPL/DI-524UP_GPL.tar.gz
ftp://ftp.dlink.co.uk/GPL/DI-524_E1_GPL.tgz

about how config.bin file get saved/loaded ?
thanks in advance

Request for a E-book

Fri, 10 Jul 2009 18:33:49 -0700

Can u plz help me for a e-book..
Fundamentals of Algorithm - Horowitz & Sahni..

Urgent !!!Plzzz Help me my assignment!!! Pseudocode for an algorithm

Thu, 09 Jul 2009 02:55:07 -0700

pls help me Gentle men and ladies

Question 1

Write the pseudocode for an algorithm that receives an integer and then prints the number of digits in the integer and the sum of the digits. For example, given 13254 it would print that there are 5 digits with a sum of 15.

Question 2

Design an algorithm that tests whether or not two input lists of size n have at least one element in common. Give formulas for best case b(n) and worst case w(n) for your algorithm.

Thanks so much help me pls :(

ASSIGNMENT DATA STRUCTURE

Mon, 06 Jul 2009 22:57:34 -0700

1. Write an iterative and a recursive version of the Fibonacci series algorithm. You need to ensure the correctness of the both algorithms. Both algorithms should produce similar output if given a similar input.

a. Measure the performance of the two algorithms by measuring the time for both algorithms to listing out 10, 20, 30, 40, 50, 60, 70 and 80 of Fibonacci numbers. The listing procedure could be done with a loop. For each test, repeat 3 times and get the average value.

Clustering pairs of similar documents

Sun, 05 Jul 2009 02:46:49 -0700

Hallo,

now I'm writing on my diploma on near duplicate detection. I'm trying to optimize Broder's Algorithm (if you're interested, the paper is called „Syntactic Clustering of the Web“), for near duplicate search and I'm focusing on the detection of similar document pairs. The last step of the algorithm is clustering. Having my pairs of similar documents I now have to build clusters.
Now my data looks like this:
d1,d2
d1,d3
d2,d3
d4,d5
d4,d6
d4,d7
Broder writes that he uses a union-ﬁnd algorithm to build clusters, but doesn't mention which. If I understand it correctly union-find algorithms are: single-link clustering and group-average link clustering. Is that correct? Could you suggest any library which would implement any of them? Maybe you can suggest any reliable links on the issue.

As I didn't find any information on that issue. I thought that some hierarchial clustering algorithm would be the best choice, while the number of clusters is not known in advance. So I tried the WEKA Cobweb implementation. I first created a similarity matrix which looks like this:

d1 d2 d3 d4 d5 d6 d7
d1 1 1 1 0 0 0 0
d2 1 1 1 0 0 0 0
d3 1 1 1 0 0 0 0
d4 0 0 0 1 1 1 1
d5 0 0 0 1 1 0 0
d6 0 0 0 1 0 1 0
d7 0 0 0 1 0 0 1

Cobweb correctly builds a cluster of documents {d1,d2,d3} but the rest of the documents appear in different clusters, not even something like {d4,d5}, {d4,d6}, {d4,d7}. Maybe I must select different acuity or cutoff values. I use the default ones till now. If yes could you please give a hint. I found out, that acuity „is the minimum value for the standard deviation“, and cutoof „sets the category utility threshold by which to prune nodes“. I think, I can even understand what they mean (I browsed through the „Data Mining“ book) but I'm not sure if they can help me, because the number of documents will vary (can be hundreds or thousands). Or maybe I'm mistaken and Cobweb is not a good choice at all?

I'm not too lazy to research more about clustering it's just that it would draw me away from the focus of my diploma for quite a long time.

I would be very thankful for any kind of help, also some keywords perhaps.

Color Sequencing

Thu, 02 Jul 2009 08:02:19 -0700

This might interest some of you. I have this table of 44 colors of a product. While the base product materials are the same, the dyes have different chemical compositions -- and some can be run right after the other in a mixer, some can't. The table looks something like this:

                (Next Batch)
(In Mixer)  White   Blue   Green   Orange   Black
White         X       X      X        X       X
Blue                  X                       X
Green                 X      X        X
Orange                                X       X
Black                                         X
...etc.

Where there's an 'X', the mixer can go from the color in the mixture to the next batch. Where there's a blank, the mixer has to be completely cleaned out (the process of about an hour).

So I'm writing an application that takes a subset of these colors (whatever the customers have ordered and needs to be made that day) and tries to find the run with the fewest cleanouts possible.

What I've come up with so far (and works for small numbers of colors) is a brute-force algorithm that tries every product in every order and returns the shortest list. E.g. For White, Blue, and Green, the program returns "White, Blue, <Cleanout>, Green". The only problem with this is that the algorithm is N!. The execution time for 8 colors is less than a second. 9 colors takes about 6 seconds. 10 takes almost a full minute (10! = 3,628,800 combinations to check). 11 colors is almost 12 minutes....you can see where this is going.

There's gotta be a mathematical model for this somewhere and a better algorithm, but I'm not sure what it's called. Has anybody seen a problem like this before?

partition set of integers

Wed, 01 Jul 2009 14:35:53 -0700

Hello,

I need to partition a set S of integers into k subsets, so that the variance of the sum of the integers in each partition is minimized.

Example, for k=3

the original set:
S = {1, 1, 2, 4, 6, 17, 19, 25, 28, 39, 49}

is split into:
s1={28,19,17}
s2={39,25}
s3={49,6,4,2,1,1}

because it minimizes var(63, 64, 64)

Note that S can have a large number of elements... so I need something relatively efficient.

Any help would be appreciated.

Thanks!!

HeapSort Problem

Sat, 27 Jun 2009 20:21:15 -0700

Got a question for heapsort need to handle in short time

input array A[1.....n]

Sorting algorithms should compute a sorting permutation pi[1...n]

which satisfies the following (1) it is permutation ie pi[i] belong
{1...n} and for all i != j hava pi[i]！ = pi[j] (2) pi sorts (i.e) if we filled an array B[1...n] by placing A[i] into B[pi[i]] then B would be in sorted order.

for example if A= [ 8,5,11,6] the sorting permutation would be [3,1,4,2] since in the sorted array "8" should be in position 3, "5 " should be in position 1 etc.

Show how to modify Heapsort such that it leaves the input
array A unchanged and computess the sorting permutation pi

instead You may assume that all input integers are distinct. You should have O (nlog n) worst-case run time.

thanks for helppp!!!!!

HeapSort Problem

Sat, 27 Jun 2009 20:20:14 -0700

There is a science competition for elementary school kids.

Fri, 26 Jun 2009 16:17:57 -0700

The competition is open to kids who are in schools in our county.

For the purposes of the exercise, let’s say there are two teams from each school that compete. One team is the Math team, and one team is the Physics team.

Each team consists of 3 students.

The rules say that only 4 students from each grade are allowed to attend, because the building where the competition takes place is very small.

This means that even though there are two teams of 3 students each, some students will have to be on both teams.

The children of the coaches are automatically given a position on the team they are coaching.

Now, let’s say 6 kids sign up to go to the competition. The school has to figure out how to select 4 of these 6 kids to compete.

We have two coaches, so we know their kids each have a spot. That leaves 4 team positions open. But since each school is limited to only sending 4 kids total, we can only choose 2 other kids to fill in the remaining spots.

What method do you use to choose the additional 2 kids?

In general, we want to solve the problem of having n teams with 3 members each, with a limit of x kids per school. In the example above, n = 2 and x = 4.

I hope that makes sense.

In the actual competition I’m trying to help with, there are 36 available team positions, but only 20 kids per school are allowed to attend the competition. So if we have 36 kids sign up for 2nd grade, we have to cut 16 of them. (The kids whose parent are coaches won’t be cut.)