New answers tagged algorithms
0
The problem is similar to memory allocation, so my propose solution is to use http://en.wikipedia.org/wiki/Buddy_memory_allocation. Using buddy allocator minimise fragmentation from happening in the first place by choosing the smallest contiguous free space in the pipe for a signal.
Using the example, here's how the space will be allocated for size 8 pipe:
...
0
You need to take a representative sample of your real data and simulate different repacking algorithms. At the moment, I don't have enough information to simulate the system so could not check how any algorithm worked.
2
Well, before looking for an answer, you should first define clearly what you want to minimize, that is, what kind of signal repositioning is allowed. Is it allowed
to take one (and just one) signal out of the pipe and add this at another place with no overlappings (and repeat that step n times)?
or to take n signals simultaneously from your pipe and ...
2
Appears as pretty naive attempt to convert RGB to luminosity with some heuristic use of average brightness as a threshold.
You can find correct RGB->LUMA formulas along the lines in this discussion:
http://stackoverflow.com/questions/596216/formula-to-determine-brightness-of-rgb-color
2
You might try a moving average to help smooth out the signal first. Then you could iterate over the signal and replace all values below your threshold with zero.
0
The trick is to use the right data structure for the job, and in this case the right data structure is a multiset. In fact, the multiset is the answer, you don't even need an algorithm.
Here's an example in Ruby:
require 'multiset'
s = 'Hello World Hello Programming Hello World'
Multiset.new(s.split)
# => #<Multiset:#3 "Hello", #2 "World", #1 ...
1
Create a Scanner for your InputStream, Reader, File, String, etc
Iterate over the tokens
If a word doesn't already exist in your Map, add it with a value of 1.
If a word already exists in the map, increment its value.
When done, close the Scanner.
Iterate over the map and display.
Your solution and @parsifal's take a couple of unnecessary steps that are ...
0
The inefficient part of your algorithm is in fact the ArrayList, because it can't be traversed in a efficient way. The appropriate data structure is in your case a binary tree.
A very detailed discussion of binary trees: http://www.shiffman.net/teaching/a2z/concordance/
7
Replace steps 3 and 4 with the following
If string is not in the map, store it in the map with value Integer.valueOf(1)
If is already in the map, get the current value, increment it, and replace the mapping.
-2
Maybe I'm being very Math/Science/Engineering compute specific but one that comes to mind is the FFT algorithm.
I've seen this FFT benchmark thrown around before, and although it is a few years old I think it was well done for what it is: http://www.sharcnet.ca/~merz/CUDA_benchFFT
12
I recommend using the HSV or HSL color spaces, not the RGB color space, because HSV and HSL are better structured for generating colors that look different to humans. You'll have more work in RGB (though conversions back and forth exist, should you need them).
This is what HSV / HSL look like:
When using the HSV or HSL color space you can assume (very ...
1
I believe that this is a variant to the eulerian path problem
each number is a vertex and each tile is an edge connecting the two numbers
if the entire graph is not connected then add tiles until they are (connect odd used numbers to other odd used number if possible)
is there are no or exactly 2 numbers that are used an odd number of times then the ...
0
There is more to the problem than "just the algorithm". You need to think in data structures as well. In this case you have two kinds of structures:
Domino tiles - Two integers
Domino chains - A list of tiles that are connected to each other
Once you figure out how to build the structures you can go over the actual algorithm. Which you can simply do by ...
2
If you want to lump together neighbors with equal values, you can use a disjoint-set (aka union-find) datastructure to efficiently categorize sets of equivalent neighbors.
However, if your matrix values are floating point (as in your example), you should note that comparing floating point data for exact equality is almost always the wrong thing to do.
...
0
Any algorithm can be implemented in any programming language. After all, its not the syntax that matters. But using a high level language like Python do have its own advantages. Less work and less amount of coding. So to implement an algorithm in Python, you shall need fewer lines than what is required in a low level language like C.
Python have most of the ...
3
The basic idea is that JPS allows to throw away many candidate paths early, therefore reducing the amount of computations required.
In many maps, multiple paths with the same cost lead to same destination, such as a game map with large open areas. JSP allows pruning those paths.
An in-depth explanation can be found here.
0
The problem you're having with ant colony algorithms and the reason that no one has applied it to solving crosswords is because ACO poorly suited for the problem of crosswords.
Artificial intelligence is a MASSIVE field of study. There are a ton of methods and approaches. There are also quite a lot of problems out there that can have AI applied to them. ...
1
The counter-question is, what is the apparent probing interval you want to present to your users?
If the apparent probing interval should be the actual probing interval, you should only present actual data points to the user without interpolation or extrapolation.
If the apparent probing interval should be a real-time status, you should extrapolate the ...
0
using System;
using System.Linq;
public class CandidateCode
{
public static string partition(int[] input1)
{
bool[] best_assignment = PartitionValues(input1);
string result1 = "", result2 = "";
int total1 = 0, total2 = 0;
for (int i = 0; i < best_assignment.Length; i++)
{
if (best_assignment[i])
...
2
I once had to solve the exact same problem, as part of commercial image processing software. In the end I opted for a scan-line implementation, because it reads the matrix only once.
Basically, you consider a single row of the matrix and keep track of all 'events' on this scan line. Events are left and right edges of islands. Note that the same island ...
2
If I understand your current algorithm correctly it is:
loop through all n values in your matrix looking for non 0 ones in O(n)
for each of island, flood fill over the m non zero elements and set them to 0 in O(m)
given you matrix is sparse i.e. n >> m then this algorithm is going to be O(n) complexity.
We can get better complexity by using a data ...
0
Sounds like a variation of blob coloring. (Google is your FRIEND!)
You're going to make a list of blobs, initially empty. Scan for a nonzero value. When you find one, do 4-way-connectivity to find the blob pixels, and call the "color" the highest value. When you run out of 4-way-connected pixels, restart your scan to find a new blob.
1
If I understand correctly, it would seem that you're doing it in the most efficient way. Let me try to summarize your algorithm:
Main:
For each pixel in image:
If pixel is non-zero:
Call flood subroutine with pixel.
End
End
Flood subroutine:
Acquire all neighboring pixels of passed pixel of the same height.
Peak = true
For each pixel
If pixel ...
6
O(sqrt(n)) in the magnitude of the number, but only as long as you use int
Note that complexities for prime number related algorithms are often discussed with n as the length (in bits) of the number - and that you cannot assume things like comparing, adding, modulor or multiplying to be O(1), because with arbitrariy-precision numbers these operations become ...
1
Wouldn't this ensure that you do not touch an already placed element again?
for (i = 51; i >= 2; i--) {
swap(arr[i], arr[rand() % i]);
}
swap(arr[0], arr[1]); //just to be safe.
(referring to Watch out for using the same probability for each card... that's a gotcha in this algorithm.)
3
I think you can improve this by looking at the problem as a directed graph of pairs of positions.
For this example I will use the line with values -9, -6, -1, 3, and 5.
Because it's too hard to draw a graph with just text, I'm going to represent the pairs as a table. We can think of the cells as representing the state where all containers between those ...
1
To complement ngoaho91's answer.
The best way to solve this problem is using the Segment Tree data structure. This allows you to answer such queries in O(log(n)), that would mean the total complexity of your algorithm would be O(Q*logn) where Q is the number of queries. If you used the naive algorithm, the total complexity would be O(Q*n) which is ...
1
A simple binary heap can support O(log n) updating of an element if you have a pointer/reference to that element's position in the heap (which can be acquired through an auxillary hashtable if necessary). The O(log n) is actually due to the necessary work to preserve the heap property.
4
There are search/sort algorithms that subdivide not by two, but by N.
A simple example is search by hash coding, which takes O(1) time.
If the hash function is order-preserving, it can be used to make an O(N) sort algorithm.
(You can think of any sort algorithm as just doing N searches for where a number should go in the result.)
The fundamental issue is, ...
33
It does make sense to me that this makes it faster to solve a problem if the two halves takes less than half the work of dealing with the whole data set.
That is not the essence of divide-and-conquer algorithms. Usually the point is that the algorithms cannot "deal with the whole data set" at all. Instead, it is divided into pieces that are trivial to ...
25
Asymptotically speaking, it doesn't matter. For example, binary search makes approximately log_2 n comparisons, and ternary search makes approximately log_3 n comparisons. If you know your logarithms, you know that log_a x = log_b x / log_b a, so binary search only makes about 1 / log_3 2 ~= 1.5 times as many comparisons as ternary search. This is also the ...
4
Here's a solid example.
Some languages have metaprogramming/preprocessing systems that contain code that needs to be evaluated at compile time. This can be simple substitution, like C's macros, or more complex.
There are some cases in which the compile-time code evaluation system is complex enough that it can be shown to be Turing-complete. C++'s ...
1
This is a nice exercise in constraint propagation and combinatorics. Here are some ideas:
Clearly there are result distributions which are impossible. For instance, the total number of of wins must equals the total number of losses, and the total number of draws must be an even number.
If you draw up some example distributions by adding up actual results, ...
0
The best algorithm would be in O(n) time as below
let start, end be the index of the bounds of range
int findMax(int[] a, start, end) {
max = Integer.MIN; // initialize to minimum Integer
for(int i=start; i <= end; i++)
if ( a[i] > max )
max = a[i];
return max;
}
0
try "segment tree" data structure
there are 2 step
build_tree() O(n)
query(int min, int max) O(nlogn)
http://en.wikipedia.org/wiki/Segment_tree
edit:
you guys just don't read the wiki i sent!
this algorithm is:
- you traverse the array 1 time to build tree. O(n)
- next 100000000+ times you want to know max of any part of array, just call the query ...
7
I think you could construct some kind of binary tree where each left child node contains the maximum value in the left half of the range covered by its parent and the child right node the maximum value in the right half.
78
45 78
23 45 78 6
23 17 9 45 78 2 4 6
Then you only need to find ...
0
Well, correlation is your friend.
Make an array of your needs and give them a number out of 10 in accordance of their importance to you.
Now, make similar array for each of the products associating with them your needs and give a number to each according to how well they fulfill your needs.
Now we have two arrays, one of your needs and other one of how each ...
0
Essentially the same as Mason and Mike have already said, but in different words...
If you have no edges, the most (connected) vertices you can have is one. Call this vertex the root.
To add a new vertex to a tree, you must also add a new edge (in order that the new vertex is connected). That edge can (and must) connect to any pre-existing vertex. The new ...
5
Proof by induction:
Every acyclic graph can be represented as a tree, if all the nodes are connected.
So let's think about trees. You've got one root node. Let's look at the simplest, case, in which the tree only has one branch, and so it's a simple linked list.
If there are two nodes, there's one edge between them. Add one node to the end of the ...
3
Consider any minimum spanning tree.
Choose some vertex as the root.
Then each vertex has one parent, except the root.
1
A Haskell-based book:
Algorithms: A Functional Programming Approach, by Fethi Rabhi and Guy Lapalme
ISBN 0-201-59604-0
http://www.iro.umontreal.ca/~lapalme/Algorithms-functional.html
Also, this one seems like a nice little paper. Available online, too:
Jamie Snape, Loopless Functional Algorithms,
Master's thesis, Computing Laboratory, University ...
0
There's no reason why the pivot should be in the middle. If the array is unsorted, then in theory, one item in the list is as good as another, which means we can pick according to what is most convenient for us.
So lets arbitrarily name the right-most item in the list as the pivot. Starting from the left, compare that number with the pivot. If the number ...
2
Basically, corecursion is recursion accumulator-style, building its result on the way forward from the starting case, whereas regular recursion builds its result on the way back from the base case.
(speaking Haskell now). That's why foldr (with a strict combining function) expresses recursion, and foldl/ until/ scanl/ iterate/ unfoldr/ etc. express ...
2
If priority is not a small (3) set of values, and nuances between the priorities is necessary, then it is a larger enumerable set.
How large you make this set is up to you, but it is likely easier to make it very large (1 .. 1024 for example), but then you have to discipline the users to not put everything at max priority anyways. This is often a problem ...
1
To add a bit more information to the comment I left on World Engineer's answer:
This is generally referred to as multi-objective optimisation. Wikipedia has a pretty good summary of the topic, I recommend you go through it. The good news is that it's a very well researched area, with plenty of ideas and algorithms available. The bad news is that it is a ...
1
I am uncertain as to whether you have any additional information that could allow you to optimize the problem. In general, I agree with World Engineer, that it is NP-complete if presented in this general case.
In general, what you can do if you truly have the NP-complete version of the problem to solve is encode it into any other NP-complete problem, with ...
1
You can do this with Linear Programming and Constraint Programming. It's helpful since many of the problems in this domain are NP-Hard. The specific algorithm in this case is typically known as the "Simplex Algorithm".
Some quick summaries:
Of Linear Programming:
Linear programming (LP, or linear optimization) is a mathematical method for determining a ...
1
IANAL, and you should never use legal advice given to you by a stranger on the internet. If you're at all worried contact a lawyer.
Having said that, I doubt very much that Sudoku is under copyright or that it might be possible to copyright an individual puzzle. What is copyrightable is the method of generation; your algorithm. Ensure you make your own up ...
1
This seems a lot like asking: Should I worry that something I write might have already been copyrighted by someone else?
The answer, of course, is that most people just don't worry about it. If you write something of any length yourself, rather than copying it from somewhere else, then the chance that you're going to write exactly the same thing that ...
0
Please read What Have You Tried? and encourage yourself. If you keep this kind of research up, you'll do fine. Programming is about problem solving, and the most interesting problems are the ones that haven't been solved, or ones that need a better solution. The most important skill you could possibly acquire is the ability to refine your own ...
Top 50 recent answers are included
