Algorithms Forum RSS Feed

algorithm problem in sofware project

Thu, 11 Mar 2010 09:13:10 -0700

hey dudes
we're in a middle of a software project, and we got stuck somewhere. in this part we should do something like this:
1. get a rule that looks like !0-4?2-4@@ that defines a password structure, and a dictionary filename
2. break the rule into parts, !0-4 ?2-4 @ @
each part represents an other rule- let's say !0-4 means the first part of the password should contain between 0 and 4 english chars, ?2-4 means that the second part should contain between 2 and 4 general chars (including %,^ etc), and @ means that we receive a word from a dictionary, so let's say the dictionary has the words "abc" and "asd", a good password (that fits in the rule) is alpha%&abcasd, because we can divide it into alph a%& abc asd and it fits the rule.
3. we get an int n (and here's the hard part), we want to generate the n'th password, so that for different n's we'll get different results. in other words, there is a 1 to 1 correspondence between the n's and the passwords generated by the rule.
the problem is that we can get rules like !0-2!0-2, and then the password aa can be generated in 3 different ways- (aa)(), ()(aa), (a)(a). this ofc gets even more complex for longer and more complex rules.

i'd be glad if someone could help us out here...we're really stuck :\

Problems with a time algorithm.

Mon, 15 Feb 2010 06:27:15 -0700

Hey there. I have a little problem that is probably not hard to figure out, but I have been programming for a week straight and my brain is a little cheezed out:P

I have number of datapoints that each need a timestamp. The time between each datapoint is 0.25 seconds, and I need an algorithm to convert the index of the datapoint to a timestamp. If I only needed to know each second the problem would have been nonexistant, by just using Seconds = Datapoints Mod 60 and so forth, but now I need to put in hundreds of a second too.

So, the datapoints is added 4 per second, so the timeformat should be something like HH:MM:SS:%%.

i would really appreciate any help given.

Cheers

need help with an algorithm

Fri, 05 Feb 2010 05:51:04 -0700

Hello everyone
Am searching for a simple example algorithm that is suitable to be amended according to the constant execution time paradigm.

and also a proposal to rewrite the algorithm so that the variation in execution time will be reduced.

Is it possible?
Thanks to you

Expression equivalence checking

Mon, 01 Feb 2010 11:40:23 -0700

Hi All.

I'm trying to solve following problem:

Given two ariphmetic expressions, operations are +, -, *, /, () and operands are just identifiers.
Operations are not associative, but + and * are commutative.
The question is: whether it is possible to rename identifiers and to rearrange operands at commutative operations (+, *) so that to reduce one expression to another.

For example:

1.
Input:
A+B
C+B
Output:
Yes

2.
Input:
(A+A)+B
C+(D+D)
Выход:
Yes

3.
Input:
(A+A)+B
(A+B)+A
Output:
No

4.
Input:
A+A+B
A+B+A
Output:
NO

5.
Input:
A+B*C
A1+A2*A2
Output:
No

6.
Input:
(A+B-C)*(C+C)
(D+D)*(B+A-D)
Output:
Yes

I created following algorithm:

1. Build expressions' trees. (They are binaries trees).
2. Check for trees ismorphism with fixed roots.
3. Check identifiers sets.

But is this algorithm correct?
And how to do stage 3 except full recursive?

Thanks.

Read From File And Return the max sum

Sat, 30 Jan 2010 09:02:30 -0700

Hey everybody,So I've given a triangular pyramid of numbers with N (1<Ν≤1000) levels. I need to write a program that finds the highest sum of numbers starting from the top level and ending at the bottom level of the pyramid. At each step I can go diagonally down to the left or diagonally down to the right as indicated by the lines joining the numbers in the diagrams below.
The first line of the input file INPUT.TXT contains N. The following N lines contain the integers for each level, separated by a single space. These integers are positive and have a maximum value of 100.
The output file OUTPUT.TXT should contain a single number, which is the maximum sum that the program has found.

Input.Txt
3
8
12 1
2 7 8

OUTPUT.TXT
27

Please help :P

Read From File And Return the max sum

Sat, 30 Jan 2010 09:00:11 -0700

methods of visiting all the elements on a given level of a binary tree

Sat, 23 Jan 2010 10:38:17 -0700

Hello
I know of only one method of visiting the elements on one level of a tree. This method is not very efficient. This is the way I do it(PHP implementation):

private function NextNode(&$node,$curlevel,$desiredlevel,&$nodesnr=
null)
        {
            if($node == null)
                return;
            $curlevel++;

            if($curlevel == $desiredlevel)
            {
                $this->Visit($node);
                if($nodesnr!==null)
                    $nodesnr++;
            }

            $this->NextNode($node->left,$curlevel,$desiredlevel,$nodesnr);
            $this->NextNode($node->right,$curlevel,$desiredlevel,$nodesnr);
        }

I travese all the nodes of the tree in depth(inorder) and I check if teh level is equal to my desired level and if so I visit that node. I also keep track on the number of nodes but that is not relevant to the question.
This is inefficient because it goes throgh the entire tree.

Does anyone know of a better(more efficient) sollution?
Thank you in advance

methods of all the elements on a given level of a binary tree

Sat, 23 Jan 2010 10:34:36 -0700

Hello
I know of only one method of visiting the elements on one level of a tree. This method is not very efficient. This is the way I do it(PHP implementation):

private function NextNode(&$node,$curlevel,$desiredlevel,&$nodesnr=
null)
        {
            if($node == null)
                return;
            $curlevel++;

            if($curlevel == $desiredlevel)
            {
                $this->Visit($node);
                if($nodesnr!==null)
                    $nodesnr++;
            }

            $this->NextNode($node->left,$curlevel,$desiredlevel,$nodesnr);
            $this->NextNode($node->right,$curlevel,$desiredlevel,$nodesnr);
        }

Neural Network general question

Thu, 14 Jan 2010 06:40:11 -0700

Hello,

I'm experimenting with backprop NN's and have a couple questions regarding implementation / training:

1. Since the usual method of training a BPNN means normalizing inputs to accommodate the sigmoidal function limitations, how does one accurately model a continuous function with solutions that fall outside these ranges? I've got a few answers in my mind, but it's not really clear to me just yet. That is, suppose I want to model the relationship between, say, product demand and price. Do I have to normalize the NN input / target values for training and then "scale" the outputs after I run the NN so the outputs are meaningful in their original context (i.e., they look like real prices, not normalized values)?

2. Is it legitimate to mix real and discrete inputs? Citing the product demand example, suppose the price of a product in a particular area is dependent upon two things: the month of the year and the local demand in terms of quantity. It would seem most sensible to normalize the quantities as a series of real (continuous) values, and the months as discrete integers (vectors in a binary or one-of-N format). Thus, the inputs would consist of a real-value input for demand, and a series of inputs for a vector of 1's and 0's to represent the month.

Any comments / links would be appreciated.

Thanks.

Outlook VBA Network file access problem

Wed, 06 Jan 2010 15:36:58 -0700

Hi Guys,

I have a problem running the following code when the file path is pointed at a mapped network drive location. It runs perfectly when pointed at my core drive but I have to run it over a network!! The code runs to this line and then exits without error!

oWB.Worksheets(strSheetName).Cells(theRow + 1, 2).Value = Mid(Item.Body, lLen + lRmsNo, 5)

I am using XP SP3 Outlook 2003 VBA 6.5 (nope, can't change this selection!)

Any ideas would be appreciated:

Sub SetRAMS(ByVal Item As Object)

Dim strPath As String
Dim strSheetName As String
Dim aRng As Range
Dim oExcel As Excel.Application
Dim oWB As Workbook
Dim xlSht As Excel.Worksheet
Dim myOlMItem As Outlook.MailItem
Dim strName As String
Dim lLen As Long
Dim lLenNxt As Long
Dim strRmNo As String
Dim strRmLoc As String
Dim strRmDet As String
Dim strTemp As String
Dim rngCell As Range
Dim rngTmp As Range

Dim lRmsNo As Long 'RAMS no offset
Dim lRmDes As Long 'RAMS description offset
Dim lRmLoc As Long 'RAMS physical location offset
Dim lLenTot As Long 'Body string total length

Dim theRow As Variant

lRmsNo = Len("New RAMS Request: R0")
lRmDes = Len("Details: ")
lRmLoc = Len("In Relation to: ")

strRmNo = "New RAMS Request: R0"
strRmDet = "Details: "
strRmLoc = "In Relation to: "

lLenTot = Len(Item.Body)

strSheetName = "Sheet1"

strPath = "G:\Works\RAMS TEMP.xls"

Set oExcel = New Excel.Application

' On Error GoTo error_now:

Set oWB = oExcel.Workbooks.Open(strPath, 2, False)

oWB.Worksheets(strSheetName).Activate

theRow = oWB.Worksheets(strSheetName).Cells(1, 2).End(xlDown).Row

lLen = InStr(1, Item.Body, strRmNo, vbTextCompare)

oWB.Worksheets(strSheetName).Cells(theRow + 1, 2).Value = Mid(Item.Body, lLen + lRmsNo, 5)

lLen = InStr(1, Item.Body, strRmDet, vbTextCompare)
lLenNxt = (lLen - InStr(1, Item.Body, strRmLoc, vbTextCompare)) - lRmLoc
lLen = InStr(1, Item.Body, strRmLoc, vbTextCompare)

oWB.Worksheets(strSheetName).Cells(theRow + 1, 4).Value = Mid(Item.Body, lLen + lRmLoc, lLenNxt)

lLen = InStr(1, Item.Body, strRmDet, vbTextCompare)

oWB.Worksheets(strSheetName).Cells(theRow + 1, 3).Value = Mid(Item.Body, lLen + lRmDes, lLenTot - lLen)
oWB.Worksheets(strSheetName).Cells(theRow + 1, 1).RowHeight = 12

oWB.Save
oWB.Close

Set oExcel = Nothing
Set oWB = Nothing

Exit Sub

Thanks in advance
Aidan

Find if a sum of any two elements is set S is equal to given x in nlgn

Wed, 06 Jan 2010 15:17:42 -0700

Hi!
I got a little problem with this excercise from Introduction to Algorithms (Cormen et al.).

Given a set S of n integers, and an integer x, describe an algorithm of time complexity n*lg(n) which finds if sum of any two elements from S are equal to x.

Examining every pair gives n*n algorithm, which is not what I want.
I think a merge-sort like algorithm could be used, but have no idea how to check if there are two such elements in two subsets (the merge step) in linear time. But maybe the whole idea is wrong. If someone can give any hints on this, I'd appreciate it =)

Oh. My second idea is a 2*n*lg(n) algorithm given below.

merge-sort(S) // takes n*lg(n)
for each y in S: // n times
r = x - y
binary-search(S, r) // takes at most lg(n)
if found then return

If anyone knows a better (faster) solution please let me know.

regards
LaChupacabra

Find specific row in N * N matrix

Tue, 05 Jan 2010 06:12:26 -0700

Hi,

I need an algorithm to tell me what rows (row number) in N * N matrix are all 0.

for example:

0 1 0 1 0 ... 1
0 0 0 0 1 ... 0
0 0 0 0 0 ... 0
. . . . . . . .
. . . . . . . .
. . . . . . . .
1 1 1 1 1 ... 1
0 1 1 0 0 ... 0
0 0 0 0 0 ... 0

above n * n matrix has 2 rows that all entries are 0.

Reqd algo for getting different results based on 'n' conditions

Sun, 20 Dec 2009 03:11:33 -0700

Hi,

Which algorithm should be used to solve problems like these:

condition1 condition2 condition3 result
a1 b1 c1 res1
a2 b2 c2 res2
a3 b3 c3 res3
a2 b4 c2 res4
a4 b2 c2 res4
a4 b4 c2 res4

Automated design of a wireless network

Sat, 28 Nov 2009 08:37:37 -0700

Hello!
Help me please with the following problem:
There is a set A of censors in 2-dim. space with known coordinates (x,y). Also there is the set B of points of potential location of wireless routers (WiFi/ZigBee/etc). Each censor must be connected with a wire with length not more than L to the closest router. The max. radius of the wireless connection (i.e. max distance between 2 neighbouring routers) = R. Surely, R is much larger than L. Also there is the limit of number of censors connected to one router. Each router must be able to communicate with at least one another router, so that all of them create a connected graph without isolated 'islands'. I need to find the subset of B where to place the routers so that the total number of routers is minimal.

After search in Google I realized that this problem is called "facility location problem", but it has no restrictions about distance between facilities. It deals only with distances between a facility and clients. I think that at first I'll solve the facility location and then check the constraint about "connected graph" and if it's not satisfied, add more routers as graph bridges etc - is that right?
The actual questions are:
1. Have you ever met software for automated design of networks, that computes the optimal locations for communication nodes on the same principles as I've described?
2. What literature, websites and keywords could you suggest?
3. In whole, what ideas arise, what algoritms and methods can help in such task?
Thanks in advance.

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?

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!