Algorithms Forum RSS Feed

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.)

QR code

Fri, 19 Jun 2009 13:38:17 -0700

Hi,

I write QR decoder.
If I get distortion QR image,
decoder cannot recognize it.
For example, if I make QR photo angularly.
How can I adjust QR image?

Permutation and Combination Algorithm Please help!!!

Fri, 12 Jun 2009 09:55:42 -0700

Hello Folks,
With regards to math and algorithms in general, you are the only minds I could think of that could help me solve this problem I've been battling with for the past two days. Your help will be very much appreciated. So here it goes.

The Question is I can have a series of numbers consisting of N number of sixes and a single other number between one and five. I have X number of individuals over which i can distribute the series of numbers.

So for instance X1 can take B number of sixes and 1 other integer and X2 can take C number of sixes such that B+C+ (1 other integer) will exhaust the series. In other words any number of X over which the distribution is done over must completely exhaust the series.

The purpose of the algorithm I want is to find out all the possible ways of distributing N sixes and 1 other integer over X number of individuals such that any number of X over which the distribution is done completely exhaust the series.

I hope I've explained the problem clearly enough?

I would also appreciate it if this addition could be made to the algorithm: the distributions may be done over any X individual in either negative bias or positive bias. so for instance X1 may take B number of -(sixes) and 1 -(other number) and X2 can take C number of sixes such that it completely exhausts the series thus if I have a series of 3 sixes and two to distribute over four individuals i can have the following distributions:

Distribution:1
X1:{6,6,6,1}
X2:
X3:
X4:

or
Distribution:2
X1:-{6,6,6,1}
X2:
X3:
X4:

or
Distribution:3
X1:{6,6}
X2:-{6,1}
X3:
X4:

or
Distribution:4
X1:{6,1}
X2:-{6}
X3:{1}
X4:
and so on!

Note:
X1:6,6,6,1=X1:6,1,6,6 = X1:1,6,6,6 and so on...

Well that's it. one way I thought of doing this was to do the math and find out the number of possible ways to do the distribution and then randomly generate some possible ways such that each newly generated pattern does not match a previously generated pattern of distribution, until the number of generated patterns equals the number of possible ways but of course this would take forever to complete and will be come very inefficient as the number of pattern grows!

The algorithms can be written in pseudo code or presented in a flow chart but languages such as java, c#, or basic are also welcome. c# is most preferred as this is the language I'm working in

So as to the question why I'm doing this, If you haven't already guessed
I want to find out all the possible moves a player can make with any of his/her active pieces in a ludo game.
So If there's is a more efficient way of doing it other than the algorithm I stated above, Please share

Algorithm for generating continents/islands

Wed, 03 Jun 2009 13:33:20 -0700

Hello,

currently i'm programming a mapeditor. i want to include some nice scripts, which generate some islands/continents or other interesting shapes. the algorithm only need to tell me, if to set land on the field (x,y) or not. But in that direction i have no experience.

so if you can tell me some good internetsites or names of algorithm which can be used for this, i have a point at which i can start with the search. some example are also welcome, the programming-speech doesn't plays any role to me. so pseudocode will also be good.

i'm thankfull for every help.

yours
ralfonso

Divide Set Algorithm to recive the vector (1,1,...,1)

Sun, 17 May 2009 23:27:03 -0700

So I'm stuck at this question, the goal is to find a lower bound.
I have a set of natural numbers, each action is
choose a number>1 (refer as k) and divide the whole set (the vector (a1,a2,...,an) by this k then insted of the number's value enter this formula: i/k+i%k (Div+Mod)

for example:
(13,5,8,40) for k=4 we get: (13/4+13%4,5/4+5%4,8/4+8%4,40/4+40%4)
(4,2,2,10) then repeat the action.

-We know the higest number has value N
I need a lower bound of minimum action (If it helps i know the upper bound is 2*sqrt(N))

It's really urgent!!!
Thanks in advance,
Rom.

Single Destination shortest path

Sun, 10 May 2009 02:16:09 -0700

hi...i am used to and i ve implemented single source shortest path dijstra's algorithm...
shortest path from start to all the vertices...

but for same destination from many sources it will be single destination shortest path...
but how do i modify single source to single destination....

any help plzzzzz.

Best combination of sets algorithm

Wed, 06 May 2009 01:38:53 -0700

Hi,

I need help with creating an algorithm to solve the problem below in the most efficient manner (efficiency in this case means low processing, not memory)

(Disclaimer: I studied discrete maths as part of my university course, but this was many years ago and I have forgotten most of the correct syntax. Sorry!)

Imagine we have

Set A (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,2 0)
Set B (3,3,4,5,5,5,5,5,6,6,7,8,12)
Set C
(
Set C.A (1,2) = 10
Set C.B (1,4,3) = 15
Set C.C (3,4,5) = 20
Set C.D (3,3,4,5) = 25
Set C.E (5,6) = 10
Set C.F (5,5,6) = 10
Set C.G (3,3,4,5,5,5,5,5,6,6,7,8,12) = 5
)

B is a subset of A
C is a subset of A

I need to find
1) Which C are in B
2) What is the best combination of C. (Best means the biggest value i.e. C.A is worth 10, C.B is worth 15 etc)

When a C is found in B; B is to be reduced by C (e.g. if C.G is applied to B, there will nothing left in B)
A single instance of C can be applied to B a number of times (e.g. C.E above is in B twice)

Assume I have done 1 and the method is called GetApplicableSets(SetB) and the example above would return C.C, C.D, C.E, C.F, C.G

How do I do 2?

pattern matching algoritham

Wed, 22 Apr 2009 21:51:21 -0700

I have a text like following pattern

xxzzdggjkllkxxzzzzxxzzxz

And also two pattens like xx and zz

I need to find longest possible string which include above two patterns.

So any one can post a algorithm for this it is very help full for me.

please help me .......

errors in pseudocode help

Wed, 15 Apr 2009 14:27:57 -0700

I tried using Actors but it isn't working. It says the words "write" and/or "read" aren't declared. Im writing this for CH is there any other way I can do it, or other words? (We've been using cout and cin things)?

Now that you have been working on Ch programs for the past few weeks, you should have become more familiar with the process of translating a problem/solution description into code. In this lab, you are given a problem statement that makes use of the programming elements learned over the past few weeks. You are expected to devise an algorithm to solve this problem and translate it into code. You are expected to work on your own. Some hints are given at the end of this handout to help you with this process. Remember that your code will not look like everyone else’s.

Write a program that inputs an even integer from the user (we will refer to this as x in the rest of the handout) and outputs all even numbers between zero and the input number (inclusive).

Hints:

1. Remember to declare needed variable(s). How many variables do you need and of what type?

2. The problem statement is essentially asking you to print the number sequence 0 2 4 6 … x. What is the relationship between each number in the sequence and the next number?

3. You will need a while loop to generate the sequence of number and output them. What should be the loop condition if you want to stop after you have printed x?

Save your program file as lab12.ch in your H drive. Test your program and be sure that it prints the correct sequence of numbers. Transfer a copy of the finalized version of your program to your Submissions folder.

HELP WITH THIS PSEUDOCODE PLEASE!

Tue, 14 Apr 2009 09:47:03 -0700

Can anyone help me write a pseudocode for this problem please?

Write a program that inputs an even integer from the user (we will refer to this as x in the rest of the handout) and outputs all even numbers between zero and the input number (inclusive).

Hints:

1. Remember to declare needed variable(s). How many variables do you need and of what type?

2. The problem statement is essentially asking you to print the number sequence 0 2 4 6 … x. What is the relationship between each number in the sequence and the next number?

3. You will need a while loop to generate the sequence of number and output them. What should be the loop condition if you want to stop after you have printed x?

calculating MFCC

Sun, 05 Apr 2009 02:58:28 -0700

Hi. I'm not sure if this should go here or the algorithm forum, so apologies if it's in the wrong forum. I'm trying to find the MFCC of my mp3 files. I'm using Fmod (although I'd rather use Bass but I'm not sure how to get the frequency of the whole song, in non-realtime). I get the frequency and now I'm following wikipedia's article on MFCC.
Here's my psuedocode for it:
1) Take the Fourier transform of (a windowed excerpt of) a signal.
Code:
I use getSpectrum with the FMOD_DSP_FFT_WINDOW_TRIANGLE parameter

2)Map the powers of the spectrum obtained above onto the mel scale, using triangular overlapping windows.

I go through the spectrum array and use this equation on each value:
Code:
mel = 1127.01048log e (1+f/700)

Take the logs of the powers at each of the mel frequencies.
I then go through the new mel-array and take the log of each :
Code:
mLog[i] = (Math.log(melArray[i]))

Take the discrete cosine transform of the list of mel log powers, as if it were a signal. (Then find amplitude of DCT result)
I'm not sure what I do here. How do I calculate the DCT?

Am I on the right track?
Thanks

dynamic programming problem

Fri, 03 Apr 2009 14:25:10 -0700

Hi I have a to solve this problem with dynamic programming
We have system that generates sequence of chars, system can be only in one stat at a time. If system is in the state qi in the next step he goes to state qj with probability pij while generating char aij.
As input we have:
number n
matrix p(matrix of probabilities), its size is nxn
matrix a(matrix of chars), also nxn
sequence of chars
I need to find most probable way how was the sequence of chars in the input created. I just need some hints, how to solve it with dynamic programming, if I could use tree, it would be easy, bet I cant.
Thanks for all advices

Language recognition using Neural Networks

Sat, 28 Mar 2009 22:39:14 -0700

Hi,

We have to select a project for our 3rd year engineering, and we have decided to implement a system which recognizes the language (from a sentence, paragraph, or a complete long text). We aim to do that using neural networks.

I am absolutely new to 'world' of neural networks. Is the project I have described above feasible? I have absolutely no idea of neural networks currently. We intend to 'train' the network using passages of languages first (English, Spanish, French etc), and then make it ready for recognition - is this how things work? Can someone please guide us further how to proceed?

We can use any software to implement this - MATLAB, C/C++, Java.. What would be the best tool for a newbie?

Thanks.

PS: Pardon me if this post is in the wrong forum, but I could not find any forum on PH dedicated to neural networks.

Priority Queue Algorithms

Sat, 21 Mar 2009 07:56:17 -0700

Hey guys, my first post here :) greetings!! I'm searching for Recent Algorithms to maintain elements in a priority queue... i have a project to make... can you help me??

thank you all

crossword solving algorithm

Sun, 08 Mar 2009 08:38:22 -0700

HI all

is there any good crossword solving algorithm?

I have matrix of (rows x cols) and a dictionary of words to be filled in the matrix. This words have to fit in horizontal and vertical direction.

thx

a cd is bootable or not?

Wed, 04 Mar 2009 13:35:56 -0700

Hi everyone .

Can anyone help me about how to determine a cd is bootable or not with using java? or any other programming language.

thanx.

Edit distance recomputation

Tue, 03 Mar 2009 09:17:36 -0700

Dear participants,

I have a question concerning effective re-computations of an edit distance. What I mean is the following:

suppose we have two strings A, B and a value d = edit_dist(A,B) computed with an algorithm like the Levenshtein algorithm. Now we change A into A' using one edit operation i.e. we insert, delete or change one character in A. Is there a way to avoid a complete recomputation d' = edit_dist(A',B)?

I'd be appreciate a lot if someone can point to an article or book where this problem is treated.

Thx

finding two consecutive zeros in a bit string

Tue, 03 Mar 2009 05:54:35 -0700

Hi,
Please help to design an algorithm that determines if a bit string of length n contains two consecutive zeros. It has to solve the problem by examining fewer than n bits. Or I need to give an adversary strategy to force algorithm to examine every bit. n = 2,3,5.
Thanks for help

voronoi diagram on a sphere

Sun, 01 Mar 2009 19:27:49 -0700

hi,

does anyone out there happen to know how one would go by building a voronoi diagram on a sphere? The "sites" of the diagram are on the unit sphere. Some effort has been put into the problem, and I have actually three ideas on how to proceed :

1/ With Fortune's algorithm
I tried to transpose Fortune's line-sweep algorithm to the surface of a sphere, but I got stuck on a mathematical problem, some formula that is supposed to define the surface that separates space in two, all points of space closer to a given point on the sphere on one side, and all points closer to circle on the sphere (not a great circle, just any circle - an intersection between the sphere and a plane). It looks like this :
Ax + By + Cz + Dsqrt(1-y^2) = 0
To implement the algorithm, I need to determine an intersection between two such things and I really don't know how to manipulate them (the sqrt(1-y^2) term being the problem).

2/ Using a Delaunay triangulation instead
It seems that it would be easier to implement on a sphere since the math is more intuitive, at least in the incremental algorithms I've seen. But even though the algorithm would be of the same average complexity as Fortune's algorithm - O(n log(n)) - it seems it would be a lot slower given all the intersection tests required.

3/ Using Fortune's algorithm, but this time on a 2D stereographic projection of the sphere
I think the idea is cool but I need some proof that it would give the same output. The stereographic projection doesn't preserve distances which is kind of a central theme in Voronoi diagrams. On the other hand, I get the feeling that it should work on a Delauney triangulation, and if it works for one, it works for the other... I just lack the math "intuition" to prove one way or the other.

Well, I hope someone can help me out, and I hope this is posted in the right place.
cheers

Need your intelligence and knowledge!!

Sun, 01 Mar 2009 11:00:42 -0700

Hi to all!
I search an algorithm to that problem:
You have N rectangles N is may be between 0 and 1000. You must arrange them with the least area. You are given the dimensions of all rectangles (may be square you know from math all squares are rectangle ).
and they want the minimum area includes all rectangles and coordinates of left corner of each rectangle assuming (0,0) the upper left corner.
Thans for your help

Help me figure out this pseudocode!!

Wed, 25 Feb 2009 18:29:09 -0700

You are the owner of a vegetarian pizzeria and you want to write a program to allow the customer to order only ONE pizza online. You will prompt the customer for his/her name, pizza size being order (small, medium, or large), and pizza type being ordered (veggie or cheese), and then input this data. You are to output the customer name, pizza size, pizza type, and cost of pizza back to the customer. For a veggie pizza, small costs $10, medium costs $12.25, and large costs $14.50. For a cheese pizza, small costs $7, medium costs $8, and large costs $9. Be sure to validate the size and type of pizza, and if the data is invalid, output an appropriate message to the customer.

I don't understand how to write this as a pseudocode. This is not my homework. This is an extra problem I'm trying to do on my own to understand how to do other kind of pesudocode's problems.