pattern/string matching algorithm - Algorithms Discussion Boards

Thanks for showing me the right place. Moved it there.

Hi,

I am working on this project that requires a base protocol to be developed through (sound)whistle patterns. This project is meant to have an alternative for large area communication not using wifi or Bluetooth or any such technology that requires some additional circuitry overheads, we just need sound base transmission and receiver for sound so we decided to use whistle patterns as protocol that will use different wavelengths/patterns.

My concern is patterns may come randomly and I want to search it within database for right match of pattern with efficiency, since it is a sound pattern how do I store it and what is the right approach for searching through it. Also if any garbage then how to identify it well in advance before search even.

Patterns are nothing but commands, information and even at times signals(Normal functioning, some Event occurred, Abnormal condition)

Algorithm that I write should generate whistle with some starting point that marks it as valid may be for receiver to know that next is actual data. Whistle sent may have information about device from which it is coming and other information every time it sends with end of message to it.

I am sorry if this is not very clear but this is what I have.

Thanks!

Rahul Joshi

The MP3 algorithm will reduce the amount of sound data you need to process, by eliminating sounds the human ear can't hear. So although it's a lossy compression method, it accurately reproduces the original signal.

Thank you for your help, I will research more on this.
We actually want to study send/receive of both audible and non-audible (just to see also possible effect of it on birds/animals) if we want to use it should not cause any harm to environment.

Anyways thanks for your comment.

I need to find the shortest path between two points in a maze using recursion. the maze is represented by a two-dimensional array of integers. You can walk through cells in the array if their values are different than -1. In addition, if there are some paths with the same length, the algorithm should find the path with the highest values in the array.

I thought about an algorithm that checks all the possible paths, but I need something more efficient.

thank you!

Homework?
Did you done anything by yourself so far?
Let us see your code...

I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is. (V)

Agree with Kornfeld. What have you tried?[^]

thatraja

Code converters | Education Needed
No thanks, I am all stocked up. - Luc Pattyn
When you're wrestling a gorilla, you don't stop when you're tired, you stop when the gorilla is - Henry Minute

I think this should be common problem in Computer science.

I have a data like this

Java

List<Map<Integer,List<String>>> Qdata = new ArrayList<Map<Integer,List<String>>>();//QUERY
    List<Map<Integer,List<String>>> Tdata = new ArrayList<Map<Integer,List<String>>>();//TARGET

    List<String> Qg1 = Arrays.asList("C", "A", "PC", "R");
    List<String> Qg2 = Arrays.asList("DQ", "EQ", "KC", "AC");
    List<String> Qg3 = Arrays.asList("KQ", "AT");
    List<String> Qg4 = Arrays.asList("KQ", "AT", "DQ", "KC","AC","KQ", "AT", "KC","AC","KQ", "AT", "DQ", "KC","AC");
    List<String> Qg5 = Arrays.asList("KQ", "AT", "DQ", "KC","AC");
    List<String> Qg6 = Arrays.asList("KQ", "AT", "DQ", "KC","AC");
    List<String> Qg7 = Arrays.asList("AC","KQ", "AT","AT", "DQ", "KC","AC");

    Map<Integer,List<String>> Qmap = new HashMap<Integer, List<String>>();
    Qmap.put(1, Qg1);
    Qmap.put(2, Qg2);
    Qmap.put(3, Qg3);
    Qmap.put(4, Qg4);
    Qmap.put(5, Qg5);
    Qmap.put(6, Qg6);
    Qmap.put(7, Qg7);


    List<String> Tg1 = Arrays.asList("C", "A", "PC", "?");
    List<String> Tg2 = Arrays.asList("KQ", "AT","DQ", "EQ", "KC", "AC");
    List<String> Tg3 = Arrays.asList("AT", "DQ", "KC","AC");
    List<String> Tg4 = Arrays.asList("KQ", "AT", "DQ", "KC","AC","KQ", "AT", "KC","AC");
    List<String> Tg5 = Arrays.asList("KQ", "AT", "DQ", "KC","AC");
    List<String> Tg6 = Arrays.asList("KQ", "AT", "DQ", "KC","AC");
    List<String> Tg7 = Arrays.asList("AT","AT", "DQ", "KC","AC");
    List<String> Tg8 = Arrays.asList("AC");
    List<String> Tg9 = Arrays.asList("ACL","AC","C","A","PC");

    Map<Integer,List<String>> Tmap = new HashMap<Integer, List<String>>();
    Tmap.put(1, Tg1);
    Tmap.put(2, Tg2);
    Tmap.put(3, Tg3);
    Tmap.put(4, Tg4);
    Tmap.put(5, Tg5);
    Tmap.put(6, Tg6);
    Tmap.put(7, Tg7);
    Tmap.put(8, Tg8);
    Tmap.put(9, Tg9);

    Qdata.add(Qmap);
    Tdata.add(Tmap)

want to match Qdata with Tdata, the tricky part here is, if you observe the data

Qg3+Qg2 forms Tg2
Tg4+Tg3 forms Qg4 with "kQ" missing between Tg4 and Tg3
Tg8+Tg9 forms Qg7
and with the rest, it is pretty straight forward. I don't know how to deal with this tricky part.

I used map to store the data because it is more desired for the algorithm to finds matching in the same position in Tdata and Qdata like

Qg5 has a complete match with Tg5 Qg6 has a complete match with Tg6

The final ideal output that I expect in this case is:

Qg1 matches with Tg1 with a wild card("?") (some penalty for wild card)
Qg3+Qg2 matches Tg2
Qg4 matches Tg4+Tg3 (some penalty for missing word
Qg5 has a complete match with Tg5
Qg6 has a complete match with Tg6
Qg7 matches with Tg8+Tg9 (penalty)
and penalty for extra Tg9.

I already tried longest common subsequence and needleman wunsch algorithms they are good in aligning with gaps but I don't know how to mix two parts and match them like the tricky part I mentioned and how to teach algorithm when to mix parts and start matching and when not to?

Sorry for my bad english

I'm currently coding in java.

Any suggestions will very much keep me alive and get going.

Thanks in advance

I have a DAG of N nodes ( say million ) that I will querying for connectivity of two nodes [ isConnected(a,b} ]. I will be querying the DAG M ( say million ) times. Is there a way to optimize the process?

Here are the best approaches that I could come up with.

BFS = O( M * N )

Dijkstra = O( M* E* log N)

Is there any other better approach for this process ?

Dear all,

I am trying to do dual axis solar tracker with seasonal tilt.

Necessary Document:
1)Below links gives us calculation sun elevation/ azimuth angle.
http://www.nrel.gov/midc/spa/[^]
2)i am using Inclinometer to determine actual motion of tracker

Questions:
1) can someone give me algorithm flowchart for Dual axis solar tracker.
2)Dual axis tracker will move either horizontal/ vertical axis .How/when to set motion of motor along its axis.
3)what are the angle we need to taken consideration for calculation.

Hello, I have a variation of the weighted activity selection problem I could use some help with. The problem is that there are activities that have a start time, finish time, and profit. I need to find the maximum profit achievable with the variation that there must be more "short" activities used than "long" activities. Where a short activity is an activity with duration less than 5 (finish time - start time). I have solved the problem without the variation, not sure how to implement the restrictions. This is homework so i am only looking for help with the recursion.

"...there must be more "short" activities used than "long" activities."

In the recursive step (where I assume you add another activity), just skip adding "long" activities when the number of short activities is less than or equal to the number of long activities minus one.

Presumably you are picking the best solution based on the final weight score.

And presumably you have an idea of what "more" means.

Then while spanning the graph you keep track of a count for long and short. Then at the end you provide an additional weight value based on the "more" calculation. So for example if you just need to do 'short > long' for the comparison then you might add a weight of '5' to the total if that is true. Or if you need to do a difference between long and short then you would multiple that difference by '5' and add it to the score. For that latter solution you should consider if you want to deal with a negative difference or not.

Hi I am in a college programming class and I am kind of confused how to write this pseudocode.

It says "Write the pseudocode for problem 9-2.5"

9-2.5-

Prompt the user to input a temperature in the Fahrenheit scale. Then display its equivalent in the Celsius scale. Repeat until a temperature of 9999 is entered.

Example Preudocode:

INPUT length, width
LET area = length * width
OUTPUT area

or

LET count = 1
LET total_area = 0
DO WHILE count < = 4
INPUT length, width
LET area = length * width
LET total_area = total_area + area
LET count = count +1
LOOP
OUTPUT total_area

What exactly are you confused about? What have you tried so far?

The difficult we do right away...
...the impossible takes slightly longer.

I am unsure how to write this pseudocode altogether lol.

It amounts to simply writing down the steps necessary to complete the task. Since it's pseudo code, you don't need to be technically accurate.

What is the first thing that has to happen to solve this problem? What is the second thing?

Hint:
1. User enters number
2. First step to calculate answer
3. Second step to calculate answer

The difficult we do right away...
...the impossible takes slightly longer.

Here's one clue: when you want to have a loop that is guaranteed to be executed once, that construct is: Do ... While. In this case consider:

Do

// code
// code

While (the user has not entered 9999)

"What Turing gave us for the first time (and without Turing you just couldn't do any of this) is he gave us a way of thinking about and taking seriously and thinking in a disciplined way about phenomena that have, as I like to say, trillions of moving parts.

Until the late 20th century, nobody knew how to take seriously a machine with a trillion moving parts. It's just mind-boggling." Daniel C. Dennett

There is no standard for writing pseudo-code, so you almost free to write without bounds of language syntax (however I saw universities with there own standard, and if you have something like this at your college, you should use it).
Read about the idea of pseudo-code - start here http://en.wikipedia.org/wiki/Pseudocode[^]

This is one sample to the '9-2.5' problem...

VB

GET temp_f
WHILE temp_f != 9999
  COMPUTE temp_c = (temp_f - 32) * 5/9
  PRINT temp_c
  GET temp_f
LOOP

I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is (V).

Thanks a lot man! I appreciate it!

You're not supposed to do the work for him!

The difficult we do right away...
...the impossible takes slightly longer.

I believe in innocent. His not asked just because his lazy but because he don't know how to ask even.
So beside to give him some - not very bright - solution I tried to point him to the right direction...

I'm not questioning your powers of observation; I'm merely remarking upon the paradox of asking a masked man who he is (V).

It's quite clear from the original question that this is a college assignment. So by giving him the answer you are not really helping him. It's much better that people like him learn to think for themselves and at least try to work out the answer.

Veni, vidi, abiit domum

I made a website (my master project at Technical University of Graz) where you can find animations of some algorithms.
It is made with SVG/Javascript. You can run/pause/step/back an algorithm and see the pseudo code variables changing in real time.
It should be very helpful for Bsc students and also teachers can use it during lectures.

The site is called: alg0rithms.com (0 = zero)

I'm waiting for your feedbacks...

Perhaps some more algorithms, for example heapsort, bucket sort, counting sort, shell sort, midpoint circle algorithm..

Btw I think this may technically be the wrong forum for this type of question