Algorithms

17-Jun-15 18:37

I would simply pad the 3 strings on left with '0's so that all values have same length.
After that, it is a simply string comparison problem.

From other answers, I see that you have 500000 books
I guess you have a database, and that books contain consecutive numbers
- make sure all first ticket number of books have the same length by padding 'o' on left.
- make this field an index
- search the base to find the first book with number <= random

Patrice

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

PIEBALDconsult25-Apr-15 7:46

PIEBALDconsult

25-Apr-15 7:46

What? Unclear, and probably not related to algorithms.

pt140125-Apr-15 8:39

pt1401

25-Apr-15 8:39

By magic. If you want more detailed answers, please post more specific questions.

Richard MacCutchan25-Apr-15 20:54

Richard MacCutchan

25-Apr-15 20:54

In pseudocode, the general C4.5 algorithm for building decision trees is:

1. Check for base cases
2. For each attribute a
   2.1. Find the normalized information gain ratio from splitting on a
3. Let a_best be the attribute with the highest normalized information gain
4. Create a decision node that splits on a_best
5. Recur on the sublists obtained by splitting on a_best, and add those nodes as children of node

Kornfeld Eliyahu Peter25-Apr-15 21:01

Kornfeld Eliyahu Peter

25-Apr-15 21:01

To understand C4.5 you have to learn to read...
http://en.wikipedia.org/wiki/C4.5_algorithm[^]

Skipper: We'll fix it.
Alex: Fix it? How you gonna fix this?
Skipper: Grit, spit and a whole lotta duct tape.

Sascha Lefèvre25-Apr-15 7:37

Sascha Lefèvre

25-Apr-15 7:37

Please read: How-to-get-an-answer-to-your-question[^]

As I have a feeling you won't actually do it, here's the important part:

Quote:
Be specific! Don't ask "can someone send me the code to create an application that does 'X'.

Have you heard about Google?

And please stop posting the same question again.

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

algorithm

Deepak Pundir17-Apr-15 9:10

Deepak Pundir

17-Apr-15 9:10

Can someone explain this question please

There are 2 types of tiles: Type 1: ** * Type 2: ** (where each star is a square block) Each tile can be rotated or flipped in all ways. There is a box with 2-by-n dimensions. So, for example, if n=10 then the box dimensions are 2 X 10 as shown below. ****** ****** You have infinite supplies of Type 1 and Type 2 tiles. You have to cover the box with the tiles that you have. You can use any number of type 1 tiles and type 2 tiles. You can choose to use all tiles of same type and none tiles of the other type. But you cannot overlap the tiles. Also, when you cover the box with tiles, none of the tiles should be out of the boundaries of the box, and no part of the box should be empty (no block shud be empty). The tiles should perfectly cover the box with no holes and no protrusions. Your task is to write a program in python that will count the number of different ways (configurations) in which u can cover the box with tiles. 2 cofigurations of covering a box are different if the type or orientation (or both) of any tile of those 2 configurations are different. To clarify things further, there are following configurations of the tiles: 1) ** 2) * * 3) ** * 4) ** * 5) * ** 6) * ** If there are 2 tiles in the configuration that are of same type and placed in same orientation, then if you swap the positions of these 2 tiles, it WILL NOT be counted as a different configuration because all tiles of same type and same orientation are identical. Write a program that will accept an input, n, and produce an output, the total number of different configurations to cover the box of dimensions 2 X n. Example: If n=2, output should be 2. Because 1 configuration could be 2 type-1 tiles placed vertically, and another configuration could be 2 type-1 tiles placed horizontally. If n=3, output should be 5

Sascha Lefèvre17-Apr-15 9:48

Sascha Lefèvre

17-Apr-15 9:48

That's a task, not a question. And your post is not a question that fits the purpose of this forum. You didn't ask for an explanation of a specific part of this task, so do you want the whole thing explained in even more words than it already consists of?

I suggest you try a bit harder understanding it and, if needed, come back with a more specific question.

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

harold aptroot17-Apr-15 9:54

harold aptroot

17-Apr-15 9:54

It would help if you fixed the formatting, but I get the general idea.

Unsurprisingly, it's a tiling problem. There is a rectangle that you have to fill with these shapes, filling it perfectly. Then you have to count in how many distinct ways that can be done, with "distinct" meaning exactly what you'd expect (but they spell it out for good measure).

Algorithm for finding the best “route” of tasks

PIEBALDconsult15-May-15 14:42

PIEBALDconsult

15-May-15 14:42

Research bin-packing and knapsack algorithms.

And we won't do your homework for you.

Nino Cotec2-Apr-15 5:50

Nino Cotec

2-Apr-15 5:50

Hi,

I have the following problem:
Lets say I'm in a city with some friend we have a bunch of tasks to do. All persons start on a different position, for example (0/0), (10/5), (-20/0), ... , and every person can move x corrdinates per second.
Every task has:

A coordinate where it can be completed (for example (40/50))
A importance value ranging from 0 - X (for example importance = 5)
A time that is needed to complete this task

Also, some tasks can only be done if others are already completed.

Now comes the tricky thing: The group has a certain time, in which they can complete tasks. They now need to choose which tasks they want to complete, the goal is that the summarized "importance value" of the completed tasks is as high as possible. The group is also allowed to split up.

I tried to solve the problem in the past hours but i haven't come far and i'm burnt out. Please help Frown | :(

Re: Algorithm for finding the best “route” of tasks

C^hris L^osinger2-Apr-15 9:41

C^hris L^osinger

2-Apr-15 9:41

this sounds something like the Job Shop Scheduling[^] problem.

image processing toolkits | batch image processing

Re: Algorithm for finding the best “route” of tasks

Patrice T25-Jun-15 8:44

Create continuous path from multiple segments

25-Jun-15 8:44

Hi,

Your problem is hard to solve as data grow. The general family is Graph.

It is related to classical problems:
- TSP Travelling salesman problem, if only one guy.
- Delivery round, it is a daily problem for every UPS agency.

It may not be your specific problem, but it is the same area/family.

Patrice

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

Member 115731191-Apr-15 3:38

Member 11573119

1-Apr-15 3:38

I have an array of several segments of a path with known start / end point. Direction of each segment is not known. It can be from start to end point or vice versa.
Each segment object is something like this:

Connection: {
 PointA = p1
 PointB = p2
 pointA_is_connected = true (false for the first or last segment)
 pointB_is_connected = true (false for the first or last segment)
}

I want to create a path from one end to another in one direction with all segments that can be connected to each other. All the segments in an array are segments of a ONE path.
Here is an image of what I have (in red) and what I want to have (in green)
What's the best way to achieve this?
http://pgtehran.euphrat.es/pic.png[^]

Frankie-C2-Apr-15 1:27

Frankie-C

2-Apr-15 1:27

You need to define a property that have to be 'comparable' and from wich result you can decide which segment choose.
I.e. defining coordinates for each starting and ending point of each segment you can choose an arbirtary small circle and search for those segments that are closer to your endpoint. The closest will be 'connected', then you will repeat the search with the opposite end of last connected segment until there are no more segments available.

Member 115731192-Apr-15 6:47

Member 11573119

2-Apr-15 6:47

Thanks,
Start and end point does have coordinates property.
Why choose an arbitrary small circle for checking? why don't check if the next point is exactly same as the start/end point of the current segment?

Frankie-C2-Apr-15 7:29

Frankie-C

2-Apr-15 7:29

To allow for small coordinates errors, especially if they are floating point or come from float calc. In that case the comparison could fail for very small differences.

When dealing with floats the best test for comparison is:

C++

if (fabs(float1-float2) < epsilon)

in this case we say that the comparison is satisfied if the absolute value difference between the two floats is less than the approximation (epsilon).
BTW you can do as you like... Laugh | :laugh:

Member 115731192-Apr-15 7:34

Member 11573119

2-Apr-15 7:34

Good point, Thanks.

Patrice T28-Jun-15 16:58

Is there a way to accelerate the following algorithm for hamming distance calculation? By assembly language?

28-Jun-15 16:58

This a classical Graph traversal family problem.
You need to give a "cost" to each segments in order to do so kind of optimization.

Patrice

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

ECDSA FOR A NOOB

Reversedme28-Mar-15 5:16

Reversedme

28-Mar-15 5:16

Now i'm very much what you guys would call a total amateur
when it comes to math algorithms and any form of cryptography but i was just wondering if elliptic curve private keys usually rely on static values for all encrypted binaries being signed and verified
can a atacker not recover K if DA shares the same public and private exponent?

prime_tang23-Mar-15 23:40

prime_tang

23-Mar-15 23:40

The following code is a basic algorithm for hamming distance calculation, but due to the design of my application, it requires many times to use this algorithm, in order to improve application efficiency, I want to improve the efficiency of this algorithm, is there any appropriate methods? Assembly language possible?

C++

unsigned dist(const unsigned char *vec1, const unsigned char *vec2, unsigned dim)
{
    const unsigned char popCountTable[] =
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
    unsigned dist_ = 0;
    for (unsigned i = 0; i != dim; ++i)
    {
        dist_ += popCountTable[vec1[i] ^ vec2[i]];
    }
    return dist_;
}

Re: Is there a way to accelerate the following algorithm for hamming distance calculation? By assembly language?

harold aptroot24-Mar-15 1:16

harold aptroot

24-Mar-15 1:16

Yes, well it depends which assembly language.
The most obvious thing is to use __popcnt64[^] to do 8 times as many popcnts in a cycle. Haswell can sustain 2 reads, a xor, a popcnt, an add and a fused sub/branch pair (hopefully the compiler will rewrite the loop logic) all together once per cycle, so that's pretty good.
You can also try the pshufb trick[^], the benchmark there shows it's a bit better. That takes more effort to make it really fast, doing as much vertical work as possible before doing a horizontal reduction and so on. May work better with AVX2, hard to say in advance.

Re: Is there a way to accelerate the following algorithm for hamming distance calculation? By assembly language?

Patrice T30-Jun-15 14:41