An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
0
votes
0answers
10 views
AVL Tree: Finding the key with the smallest data values in keys between two values in O(logn) time
So I'm given an AVL tree. And im trying to figure out at least the pseudocode to find the key with the minimum data values among all of the keys between two values k1 and k2. This is assuming that ...
-4
votes
0answers
12 views
Make heights of all elements of array equal.Solution?
Jon has N columns of ground. Each column has it's height . Jon can choose any column and increase its height by 1 using 1 cube.
Jon wants to spend exactly M cubes. Can he make this in such way that ...
0
votes
0answers
8 views
Graph Traversal Algorithm with discount
I have a directed graph with weighted edges and I would like to find the all pairs shortest paths in my graph. But I want to be able to take discounts into consideration.
For example:
A->B ...
0
votes
2answers
9 views
Divide and Conquer to merge j sorted lists
I am trying to come up with a divide and conquer algorithm for merging j sorted lists with n number of elements but I'm stuck; I don't know how to divide this problem into smaller sub-problems. I want ...
0
votes
1answer
11 views
Faster cycle detection in a polytree
I have a program in Ruby 1.9.3 that constructs a RubyTree (specifically, my data looks like a polytree -- at least it should, despite users' best efforts to foil my program with bad data) dynamically ...
0
votes
0answers
19 views
solving Recurrence equation
I have a recurrence relation of the form
an = 2*an-1 | when n is even
an = an-1 + 1 | when n is odd
Actually this is an programming puzzle, and for which i have a brute force ...
-1
votes
1answer
59 views
Why do we use bitwise operator? [on hold]
For this question http://www.codechef.com/COOK49/problems/SHOOTING/. I couldnt solve it so i followed this solution http://www.codechef.com/viewsolution/4619933. Can you exlplain these steps
int ...
0
votes
1answer
41 views
Getting median of an unsorted list with selection algorithm
I have a list of integers, and I want to use selection to find the median of this unsorted list. This is what I have so far but I am not getting any out put for my test list [140, 240, 180, 400, 340]. ...
0
votes
0answers
11 views
Lennard Jones Molecular dynamics simulation blows up
I am trying to modify a file for molecular dynamics by following link implemented in MATLAB:http://people.sc.fsu.edu/~jburkardt/m_src/md/md.m
and the running script: ...
0
votes
0answers
35 views
Finding subsets of size k from a larger set using decrease-and-conquer
Disclosure: This is homework. I'm attempting to provide all of the information required to meet SO's rules; I apologize if I miss something.
I'm using Python, and I need to generate all subsets of ...
0
votes
0answers
23 views
Implementing Bentley–Ottmann Algorithm with an AVL tree
I'm having a problem implementing this method in java. I'm specifically implementing the algorithm FINDINTERSECTIONS in Computational Geometry 3rd Edition using an AVL BST tree for the status. The ...
1
vote
0answers
22 views
How to implement A* with minimum number of nodes on path?
I have implemented my A* algorithm such that it finds the shortest path to goal, given that it can move only to neighboring/adjacent cells. (Assume nodes are cells in a grid). So there's 8 surrounding ...
-4
votes
0answers
15 views
Create an algorithm of Markov [on hold]
Can help me write a Markov algorithm, which in the alphabet {a, b, c} doubles the penultimate letter "a", if the word has the letter "c."
For example:
abababbc = abaababbc
Thank in advance!!!
0
votes
0answers
31 views
Recursion - Finding Combinations/Permutations of an Array of Strings(java)
So I'm trying to make 2 recursive methods. One that calculates all combinations of an array of strings and returns them as an ArrayList. for example ["dog", "fish", "cat"] will return:
Combinations ...
0
votes
1answer
26 views
Binary Search Tree cant compare node to null
Im trying to do method that removes node from Binary search tree and I know my programming logic is right but I cant compare my focus node to the node's parent's left child. It has to be sometimes ...
0
votes
0answers
25 views
Ranking Fixed Length Search Results [on hold]
I have currently written a way to rank fixed length DataSets however I am looking for additional methods which can be used to improve the ranking and results.
See the dataset below with the test ...
0
votes
4answers
65 views
Algorithmic help in Python, find pair (x,y) where y/x > const
I'm building a rather huge real-time odds system, and my bottleneck right now is the actual computation. I have a huge amount of sorted lists, and for each list, I need to find each pair (x,y) where ...
-1
votes
0answers
18 views
Changes in Wagner-Fischer algorithm to increase its efficiency
The complexity of Wagner-Fischer algorithm is O(mn) .
But if I am given with an upperbound i.e. max limit of edit distance then it can be made faster
According to this article: ...
1
vote
0answers
29 views
Implementation of the following algorithm for sorting and computing median [on hold]
For my assignment, I was to right two programs that perform the same task. One does the task slowly, and the other quickly using the fast select algorithm below. I have written the slow program but I ...
0
votes
2answers
33 views
Solving a first degree equation - code optimization
I have an equation which shows up like this:
where A and X are two vectors of numbers and N > 2 an user input (different each time) while G is a numeric constant and Y is the variable I'd like to ...
2
votes
2answers
46 views
OpenCL Cholesky Decomposition
I implemented the following Cholesky decomposition algorithm using OpenCL. The code is exhibiting random behavior. It matches the cpu output only some times. Can someone please help me to figure out ...
0
votes
1answer
9 views
How to determine the next POI in a navigation route?
I have a route (MKPolyline derived from an MKRoute retrieved from Apple's MKDirections API) and a bunch of points of interest (array of MKAnnotations) that are close to the route.
I would like to ...
0
votes
1answer
40 views
Comparison of the runtime of Nearest Neighbor queries on different data structures
Given n points in d-dimensional space, there are several data structures, such as Kd-Trees, Quadtrees, etc. to index the points. On these data structures it is possible to implement straight-forward ...
0
votes
1answer
20 views
Understanding A* Search on Tropical Island
I am working on an online MOOC on AI and I am now working to understand A* better.
Basically, right now I am working on a problem where: we live on a tropical island and we're trying to navigate ...
1
vote
1answer
37 views
Represent long numbers in matlab
I am doing a algorithm for wireless comunications in Matlab that calculates the lost and the deviation of a logarithmic model when calculating the looses at different distances.
Everything works ...
0
votes
4answers
55 views
Complementary Hash function
Is there a type of Hashing that satisfy the following equation:
Hash(Hash(X)+Y) = Hash(X+Y)
Context:
I'm working with a append-only database that has to be synced across realms.
To guarantee ...
-4
votes
1answer
62 views
Find all Possible pair combination of 2 arrays
EDIT: Please note, this question is not the same as "Generating all Possible Combinations" Im not looking for a simple Cartesian Product
I need to write a function that produces array of all possible ...
-1
votes
1answer
35 views
Conditional selection of values between columns
There is a matrix:
A B
0 36
0 4
4 24
0 13
0 11
11 13
0 6
6 20
0 12
12 20
0 11
...
1
vote
2answers
93 views
Power set of a set
I am new to algorithms and found this question on net:
Given a sequence of N numbers S1, ..., SN (-20,000,000 ≤ Si ≤ 20,000,000), determine how many subsets of S (including the empty one) have a sum ...
0
votes
0answers
16 views
Can hava a fast binary integer division in MIPS code? [on hold]
I want to divide 2 binay integer (32bit) in MIPS, I use Sequence division to divide it. But I hear that SRT Algorithm can perform faster than sequence division. But i can't find a good document to do ...
0
votes
0answers
67 views
Most efficient way to search in an ArrayList of objects Android
I am currently working on an android game that revolves around words. There is a database in the background that contains the words along with an integer and 2 more substrings, containing ...
android
-3
votes
0answers
42 views
spoj bishops runtime error [on hold]
What is wrong in the following code for problem bishops on spoj ?
I am programming in c++ and since it does not have a big integer data type, I was trying to do it using arrays.. i am getting runtime ...
0
votes
0answers
22 views
Fit [x,y] dataset to a power law curve of the form y = ax^b + c in C# [on hold]
Just wondering if there is any free open source implementation of an algorithm to fit [x,y] data to a power law curve in the form y = ax^b+c where a, b and c give the best fit in the LSE sense.
I've ...
0
votes
2answers
27 views
Proof of stream reservoir sampling
I'm quite familiar with Reservoir Sampling algorithm and I'm thinking what if the total size N is given. What benefit can we get under this situation? As a result, here's the algorithm:
Let n be the ...
-1
votes
0answers
15 views
Can anyone reccomend a good active contour library [on hold]
I am looking for a good active contours library (snakes not level-set) in c++.
Anyone please?
0
votes
1answer
22 views
Modifying A* to find a path to closest of multiple goals on a rectangular grid
The problem: finding the path to the closest of multiple goals on a rectangular grid with obstacles. Only moving up/down/left/right is allowed (no diagonals). I did see this question and answers, and ...
0
votes
1answer
19 views
flood_fill algorithm in Matlab - works, but doesnt stop
Im developing a flood_fill algorithm in MATLAB right now, and I have a little problem that cost me a lot of time:
function [ homoPoints ] = area2Points( matrix )
%AREA2POINTS makes an area of one's ...
0
votes
0answers
32 views
Optimal sequence for arbitrary sort order in a table
I'm sure there has to be a mathematical algorithm for this.
I'm creating a drag-and-drop UI for SQL tables which have an integer "sort order" field. The ones that, at present, users have to type a ...
1
vote
4answers
60 views
Finding perimeter of a recursively modified square
I have a square of side length 1 . Now, after each second, each square of side L will break into four squares each of side L/2.
I need the compute the total perimeter of the resulting figure, where ...
0
votes
1answer
54 views
manhattan skyline cover failing some test cases
I am doing exercises on codility. I have spent two days on this problem with no improvement in my score. I get 100% on my correctness score, but fail some performance tests because it returns the ...
0
votes
1answer
21 views
Algorithmic Upper Bound for my solution
I'm working on some homework and I want to make sure my analysis of the upper bound for the solution is correct.
Here's what I do.
1) I read n characters from an input string. // O(n)
2) Construct a ...
0
votes
1answer
54 views
MATLAB program takes more than 1 hour to execute
The below program is a program for finding k-clique communities from a input graph.
The graph dataset can be found here.
The first line of the dataset contains 'number of nodes and edges' ...
0
votes
2answers
61 views
Sorting algorithm efficiency comparison
I was playing around with simple sorting algorithms to become more familiar with them, and tried to create insertion sort from the description of the algorithm rather than the pseudocode. I made an ...
0
votes
1answer
20 views
How to calculate Run-Time efficiency of this program?
I'm a little new to Big-O analysis so I need some help!
How do you calculate big-O run-time efficiency of this program if the algorithm "doIT" has efficiency factor of 5n?:
for(i=1; i<=n; i++)
...
-3
votes
0answers
39 views
what algorithm does hasmap.get(key) uses for searching?
I am writing a solution for one of the algorithm question. I'm using map in that.
and I'm using get(key) method for searching, before inserting a new <key, value> pair.
so I am just curious to ...
0
votes
0answers
32 views
Data structure in objected-oriented world? [on hold]
For example, to implement a binary tree or a heap, the common way seems to store the nodes in an array, and access each node by calculating the index. However in the objected-oriented world what the ...
0
votes
3answers
30 views
Algorithm for seating firefighters in vehicle seats
I’m doing a project which involves placing volunteer firefighters, in seats when they arrive at the fire station to take the trucks.
Also some firefighters has drivers license some haven’t and some ...
0
votes
2answers
20 views
Big O Run Time for nested loops?
How do you calculate the big O run-time efficiency for this code? My gut tells me it is O(n^3) but I'm not sure, as I'm not really sure if the loops are independent or dependent.
for (i=1; i<=n; ...
0
votes
3answers
47 views
Get a list of strings that contain a specified character from an array of string
I just had an interview, and the interviewer asked me the following question:
From an array of String (English words), write a function that returns all the words that contain a character.
I ...
0
votes
5answers
48 views
Copy array using Regular Expression in Java
I'm trying to copy a String array into another String array. However the copy has to contain only parts of each string of the original Array.
For example, If we have
String[] originalArray = ...
