Algorithms

Rui__Silva26-Jun-15 0:55

Rui__Silva

26-Jun-15 0:55

Tanks ppolymorphe

I was always looking at trees and not graphs.

After your tip i did some research and i think my solution fits more or less in Direct Acyclic Graph more than oriented graph. The image (of the Hasse diagram) in this site is prety similiar with my solution https://en.wikipedia.org/wiki/Directed_acyclic_graph[^]

I am going to read some more about this.

Patrice T26-Jun-15 3:53

Patrice T

26-Jun-15 3:53

Rui__Silva wrote:
Tanks ppolymorphe

You're welcome.

Rui__Silva wrote:
After your tip i did some research and i think my solution fits more or less in Direct Acyclic Graph more than oriented graph.

Oriented is a direct translation from French, the right translation is Directed Smile | :)

Glad you found what you were looking for.

- If you consider my answer useful, you can up vote it (green arrow when the mouse is on left at beginning of answer).
- If you think the problem solved, change the tittle of your question and add Answered or Solved

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Richard Deeming1-Jul-15 7:41

Richard Deeming

1-Jul-15 7:41

Anonymous down-vote countered. Smile | :)

"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer

Optimal trajectory of area exploration

Patrice T1-Jul-15 7:53

Patrice T

1-Jul-15 7:53

Thanks you ! Thanks you ! Thanks you all up voters Smile | :)

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

modified 1-Jul-15 14:36pm.

Viktor Grabarchuk21-Jun-15 21:38

Viktor Grabarchuk

21-Jun-15 21:38

Hello, everybody.

I've got next problem. There is three objects:

1. first one, with next characteristics: circular area of view, speed, drag coefficient;
2. wind (or water current, doesn't matter; some sort of resistance) with some strength and direction;
3. polygon, concave (in general case).

I need to build path of first object inside this polygon, which will:

1. cover whole polygon by view area;
2. be optimal by travel time;
3. takes into account wind direction and strength.

In other words, I need to carry out exploration in a given area on optimal trajectory while scout can be drift away.

Thanks, Viktor.

Re: Optimal trajectory of area exploration

Sascha Lefèvre22-Jun-15 3:30

Sascha Lefèvre

22-Jun-15 3:30

Do you have a question?

If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson

Re: Optimal trajectory of area exploration

Viktor Grabarchuk22-Jun-15 4:04

Viktor Grabarchuk

22-Jun-15 4:04

My question, actually, is: what algorithms should I use to build this trajectory?.. I know, that maybe this is strange. I investigate this problem last few days and already have some sort of solution. I just want to find some people who might solve this task earlier.

Re: Optimal trajectory of area exploration

Eddy Vluggen22-Jun-15 12:18

Eddy Vluggen

22-Jun-15 12:18

Viktor Grabarchuk wrote:
I just want to find some people who might solve this task earlier.

The thing has a location, a direction (vector, some arrow) and a speed (velocity in them expensive manuals)

Once you have those three things in an oject, you can introduce "forces" like gravity.

Do keep in mind that you are asking for something rather complex; there is a huge difference in resistance between wind and water, also depending on the shape of the object it hits, any currents that form due to that shape, any contaminations and other stuff. Other stuff like temperatures of below 0 where water does not tend to flow Smile | :)

Start out with something fun one can easily play with; have a ball bounce on the screen and change the gravity to be equal to the moon. Once you have one force, introducing a new one should not be hard.

Bastard Programmer from Hell Suspicious | :suss:

If you can't read my code, try converting it here[^]

Which algorithm to use for searching on basis of different values

Member 96143523-Jun-15 1:04

Member 9614352

3-Jun-15 1:04

I have a an array of values like:

array(0.2,0.0,0.4,0.7) min: 0.0 , max: 5.0

and every value represent something and I have some attributes in the database that corresponds to these values. Now what I need to do is I need to search the records from database on the bases of above mentioned array. Kindly suggest me an algorithm that would do something like this. I need something like machine learning that would be able to do this thing with flexibility. What I have found from my research that following algorithm is closer to what I am looking for:

http://www.econ.ohio-state.edu/jpeck/Econ501aL4.pdf

http://www.solver.com/k-nearest-neighbors-classification-example

For Example: Configuration array => ('attr1'=> 0.2, 'attr2'=>0.54, 'attr3'=>0.66, 'attr4'=> 0.78)

Records:

| attr1 | attr2 | attr3 | attr4 |

1) 0.45 0.33 0.55 0.66

2) 0.32 0.12 0.34 0.99

3) 0.78 0.41 0.10 0.74

4) 0.88 0.12 0.74 0.10

5) 0.72 0.02 0.00 0.55

Now I need an algorithm which can get me results (records) using the above mentioned array.

Re: Which algorithm to use for searching on basis of different values

Matt T Heffron3-Jun-15 7:38

Matt T Heffron

3-Jun-15 7:38

If you really want to learn about Machine Learning and Classification systems, check out the Free, introductory Machine Learning online course from Caltech![^]
It won't give you the code, but you'll learn lots about how to do it yourself!
If you try taking the course, I suggest using Octave (a free Matlab-compatible system)[^] for practicing and homework.

"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton

Design and Analysis of algorithms math

jason007thomas2-Jun-15 13:29

jason007thomas

2-Jun-15 13:29

I have a quick question.
Which type of math subjects should i refresh myself on for algorithms class??
Is there any Direct recources i can find for this??

Thankyou

PIEBALDconsult2-Jun-15 14:07

PIEBALDconsult

2-Jun-15 14:07

Euclidean math.

Sascha Lefèvre2-Jun-15 14:52

Sascha Lefèvre

2-Jun-15 14:52

There's no specific math subject that would be more important than others for algorithms in general. The most important skill for developing or understanding algorithms is logical thinking and the ability to break a problem into smaller parts. Unless, of course, if you're going to deal with algorithms for a specific problem domain in particular - like graphics or sound processing - then certain math subjects will certainly be more helpful than others.

If the brain were so simple we could understand it, we would be so simple we couldn't. — Lyall Watson

Amarnath S2-Jun-15 22:10

Amarnath S

2-Jun-15 22:10

Not just for algorithms, but for Computer Science in an overall sense - Mathematics for Computer Science[^]. You'll also find video lectures there.

modified 5-Jun-15 1:48am.

problem in Theta-θ Notation

Patrice T19-Jun-15 18:31

Patrice T

19-Jun-15 18:31

I would say Boole Algebra.
Everywhere you have a condition, it is Boole Algebra.

Patrice

“Everything should be made as simple as possible, but no simpler.” Albert Einstein

Arjun Tirumalasetty25-May-15 2:21

Arjun Tirumalasetty

25-May-15 2:21

Hi friends,

find the θ bound for f(n)=n2/2-n/2?

we need to find the upper bound and lower bound.

If anybody know please send the solution with explaination.

Thanks,
Arjun

Geometry domain problem in Competitive algorithm

Chaitanya Pai23-May-15 1:34

Chaitanya Pai

23-May-15 1:34

modified 23-May-15 13:46pm.

Re: Geometry domain problem in Competitive algorithm

Richard MacCutchan23-May-15 2:09

Richard MacCutchan

23-May-15 2:09

Chaitanya Pai wrote:
I have tried a lot to arrive at the solution.

Show what you have tried and explain what does not work, and people will try to help you. But no one is going to hand you a complete solution.

modified 23-May-15 8:16am.

Base 36 value math problem

stoneyowl25-May-15 7:41

stoneyowl2

5-May-15 7:41

I am having a major 'head against wall' problem here...
Given two base 36 values ('A0ZWS0P' and 'A0ZWS9P', for example) and a third (random) value,
how would you go about determining whether the random value was 'between' the starting and ending values?

I am working in 2012 VB.Net

Matt T Heffron5-May-15 8:12

Matt T Heffron

5-May-15 8:12

It depends on how you're (internally) representing the values.
If you're using regular .NET integer types (e.g., Int32, Int64) then just compare the values.
If you're using strings to represent the values, then
1. if necessary, pad the strings to the same length (leading spaces or zeros)
2. use a case-INsensitive string comparison.

The string representation is a very poor design for something like this!

A positive attitude may not solve every problem, but it will annoy enough people to be worth the effort.

stoneyowl25-May-15 9:33

stoneyowl2

5-May-15 9:33

My bad, I elided some details....
The values are part of numbering sequences for ticket books. Say I have a book with a number range of '9ER78Y' to 9ER79J', stored as strings ('start and 'end') (not my design, it was inherited). Now I am given a ticket number of '9ER79A' I need to find the book of tickets that contains this ticket.
The only way I can see to do it is a brute force table scan, of over 500,000 books Frown | :(

I am not sure an index would help, unless I added a discriminator column to represent the book start and end range

Matt T Heffron6-May-15 7:49

Matt T Heffron

6-May-15 7:49

Do you need to do this within a DB query (SQL), or is the "search" in-memory?
Are there any other constraints on the problem space that might be used to simplify things?
(E.g., are the ranges all exactly the same size? or a multiple of some size?)
If you need to do significant numbers of checking at a time, then some pre-processing of the data while loading into memory is a good tradeoff.
If these are one-off checks against the DB, then pre-processing is probably not worth it.

A positive attitude may not solve every problem, but it will annoy enough people to be worth the effort.

Daniel Pfeffer6-May-15 21:21

Daniel Pfeffer

6-May-15 21:21

You can implement this with a form of binary search.

[Preparation] Sort the strings representing the first ticket in each book in ascending order:
a. zero-pad any short strings (e.g. "ABC1" should be padded to "00ABC1"
b. sort the strings using a case-insensitive sort
c. pad the list with a dummy ending value (e.g. "ZZZZZZ").
d. pad the list with a dummy starting value (e.g. "000000").
[Eliminate low values] Use a binary search to find the location of largest value less than or equal to the target string. If the result points to the starting dummy value, then no such value exists.
[Eliminate high values] Use a binary search to find the location of the smallest value larger than the target string. If the result points to the ending dummy value, then no such value exists.

The range [low, high) contains your result. If low != high, the range should contain a single element that is the desired ticket book. If low == high, no ticket book was found.

Note that you can handle missing books in the sequence by adding dummy book starting values to the array.

If you have an important point to make, don't try to be subtle or clever. Use a pile driver. Hit the point once. Then come back and hit it again. Then hit it a third time - a tremendous whack.

--Winston Churchill

Gerry Schmitz5-May-15 9:53

Gerry Schmitz

5-May-15 9:53

C# (sorry; I don't do "VB")...

   IsInBetween( "A0ZWS0A" );
   IsInBetween( "A0ZWS0P" );
   IsInBetween( "A0ZWS7P" );
   IsInBetween( "A0ZWSAP" );

private static void IsInBetween( string value ) {

   string s1 = "A0ZWS0P";
   string s2 = "A0ZWS9P";

   bool isInbetween =
      value.CompareTo( s1 ) == 0 ||
      value.CompareTo( s2 ) == 0 ||
      ( value.CompareTo( s1 ) > 0 && value.CompareTo( s2 ) < 0 );

   Console.WriteLine( "Is {0} between {1} {2}? {3}", value, s1, s2, isInbetween );
}