Tagged Questions
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.
2
votes
1answer
18 views
longest increasing subsequence of a [1 2 .. N] permutation
Here is the problem:
Given an array of N elements (1 to N), sort the array with one constraint: you can only move an element to begin of the array or end of the array. How many moves do you at least ...
0
votes
0answers
8 views
JAVA - USACO Can't Solve - Record Keeping
Here's the problem.
http://www.usaco.org/index.php?page=viewproblem2&cpid=358
I can't find an efficient way of solving the problem. I thought of alphabetically organizing each group of cows, ...
-2
votes
0answers
14 views
LazyHeap Sorting [on hold]
Consider a data structure called LazyHeap that supports the following
operations:
• INSERT(x): Given an element x, insert it into the data structure. It has no cost.
• DELETE(x): Delete x from the ...
0
votes
0answers
4 views
Update Maximum Flow After Adding an Edge
Consider we have a network flow and using Edmond-Karp algorithm, we already have the maximum flow on the network. Now, if we add an arbitrary edge (with certain capacity) to the network, what is the ...
-2
votes
3answers
21 views
Algorithm: Unable to understand this Programming Challenge
I am unable to understand this question.What this question want us to find and what is given.Can anyone just explain it in a naive manner .
Question
The Sheriff of the Hackers' community had a ...
-1
votes
0answers
16 views
MST for n+k edges [on hold]
Let G = (V,E) be an undirected graph such that |V| = n and |E| = n + k where k is a constant.
Find minimum spanning tree in ≈ n + k^100 comparisons.
I am completely stuck on this problem. I tried ...
-2
votes
1answer
14 views
Hungarian Algorithm with Mutual Pairs?
I'm trying to use the following implementation of the Hungarian Algorithm: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm.
I would like the modify this ...
-2
votes
0answers
32 views
C# OOP best practices for method parameters and returning objects [on hold]
I think this question is worth understanding and consideration.. I am trying to work out the best practices in Object Oriented Programming (OOP) regarding when its best practice to..
Pass objects ...
0
votes
2answers
30 views
How to return the correct value when Divide and Conquer Algorithm(for 1-D Closest Pairs) has done its job?
I need to find the closest pair of numbers of an integer array. For example: If I have {25, 13, 59, 7, 16} numbers, my result should be |13 - 16| = 3. So I try to solve the problem using Divide and ...
1
vote
0answers
9 views
FPTAS for bin packing
If an algorithm for bin packing has a guarantee of OPT(I)+log^2(OPT(I)), then there is a fully polynomial approximation scheme for this problem.
I have to prove this statement, but I have no idea ...
0
votes
0answers
11 views
Maximization algorithm representation
Two people start at a start node, s, and end at an end node, t. If we think of the nodes within the graph as cities, each time a person visits a city, a reward rk is gained, corresponding to that ...
-1
votes
1answer
20 views
Why comparison-based sorting algorithm have lower bound of Ω(n log n) for its worst-case running time?
I get that any comparison-based sorting algorithm has a lower bound of Ω(n log n) for its worst-case running time, but why is it so? Is there anyway I can prove it?
0
votes
1answer
15 views
How to calculate RPG Level Progression as percentage
I'm designing an RPG game where a user may accumulate experience points (XP) and level up, based on XP. Calculating the current level is trivial; if else seems to be most efficent.
I would like to ...
0
votes
1answer
16 views
Permute array to make it alternate between increasing and decreasing
An array X[1..n] of distinct integers is wobbly if it alternates between increasing and decreasing: X[i] < X[i+1] for every odd index i, and X[i] > X[i+1] for every even index i. For example, ...
0
votes
0answers
23 views
finding the minimum weight of a graph
i am trying to make a program which calculats the minimum spanning weight using the Kruskal's algorithm,
i have sorted the edges using thier weghts in increasing order and put it in a 2d list .
then i ...
-1
votes
0answers
30 views
JavaScript Fastest Performance Search number in range
What is the fastest way to check if a number is in range in categories? For example,
Category A:
50: 'Red'
20 - 50: 'Orange'
1.5 - 20: 'Yellow'
0 - 1.5: 'Blue'
< 0: 'Green'
Category ...
2
votes
1answer
24 views
Optimization - maximize minimum of weighted contributions
I have a matrix. The constraint is to choose only one element per column. The the row sums are then calculated using only the chosen elements. The objective is to maximize the minimum of the row sums. ...
1
vote
1answer
43 views
Cargo Algorithm in PHP
Honestly, i have a testing calculate how many containers of a given size and weight capacity it takes to pack the specified goods. But i'm really bad at algorithm, so i post this to looking some hint ...
1
vote
3answers
53 views
Finding all unique subsets in array
I have an array containing n integers and I need to print every unique subset.
For instance,if my array {1,1,1,2},the output should be
1,
1,1,
1,1,1,
2,
1,2,
1,1,2,
1,1,1,2,
I have ...
0
votes
1answer
22 views
Minimize cost of bundling updates (reverse knapsack?)
Hey stackoverflow,
For a school assignment I am to create Javacode for the following problem, I would like some tips and help on the pseudocode, not the actual java code. It has to be recursive. ...
1
vote
2answers
42 views
Create combinations of numbers within list prolog
I am developing a program in PROLOG (with restrictions) which is supposed to output a combination of 6 numbers within certain restrictions.
The list must have the numbers from 1 to 4 and will, ...
-2
votes
1answer
33 views
Which c# library or which alghoritms do I need to see if arbitrary two points in directional graph connect? [on hold]
There is a directional (I hope I classified it right) graph given:
B---->| _>A |
| | |__>F
|____| |____|
|
^
C ...
1
vote
1answer
29 views
Schedule Optimization in Python for lists of lists [interval scheduling]
Doing some learning problems in python and I've come across a challenge that I'm having trouble working out.
Reqs
I have a list of lists, where the first and last items are respectively the start ...
1
vote
0answers
18 views
Biclustering using Genetic Algorithm
I am trying to implement biclustering with Genetic Algorithm. I have read few papers but they didn't mention how they implemented it. All they did just shown the experiments results. I know how to ...
0
votes
2answers
59 views
Algorithm of checking special pattern of matrix
I am struggling at this problem.
The algorithm will check a special matrix pattern if it suits or not according to the values we put.Maximum dimension limit is 20x20.
Special pattern : Some term ...
0
votes
0answers
26 views
Retrieve a list of dates intervals from a first interval and removing stop intervals
Sorry for the title, the example will be more explicit :p.
I need your help for an algo.
I want to get a List<Entry<Date, Date>> with a method like this :
List<Entry<Date, ...
0
votes
1answer
20 views
Shannon-Fano code as max-heap in python
I have a min-heap code for Huffman coding which you can see here: http://rosettacode.org/wiki/Huffman_coding#Python
I'm trying to make a max-heap Shannon-Fano code which is similar to min-heap.
Here ...
1
vote
1answer
23 views
Transforming sorting into Dijkstra single source path?
To get a lower bound of nlogn I am taking the sorting algorithm, which is well known to have that, and transforming/adapting it to Dijkstra's single source shortest path problem.
I know you need to ...
-1
votes
1answer
35 views
Algorithm to choose relevant keywords for an article for 50mln keywords and 10mln articles [on hold]
I have 50 million keywords and 10 million articles in mysql db.
I want to choose relevant keywords for each article. 5 keywords per article.
All keywords are unique and I will use one keyword only ...
1
vote
3answers
41 views
IndexError: list index out of range Why?
i know that question has been answer so many times but i can't figure out where my issue is this is my code:
from random import*
def VerificationLongue():
x=randint(0,1000)
...
0
votes
0answers
52 views
Finding a maximum of a subarray [duplicate]
Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
Examples:
Input :
arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}
k = 3
Output :
3 3 4 5 5 5 6
My code:
...
-3
votes
0answers
49 views
Divide an Array into n subarray such that each subarray have equal sum? [on hold]
You are given an array of a given length.
Now we have to determine whether we can Divide the array into n sub-array such that all of them have equal sum .
Note: Each sub-array may or may not have ...
3
votes
1answer
77 views
Efficient algorithm to search a buffer for any string from a list
I am looking for an efficient search algorithm, that, for a given set of strings searches a large buffer for any one match from the set of strings.
Currently i know a few efficient single-string ...
0
votes
0answers
34 views
Best way to detect company in string
I am importing data from different sources and need to compare the company names from this data with a list of defined and cleaned companies, what I have in my DB.
The problem is, that I become the ...
1
vote
2answers
23 views
Find rows with certain time deltas between them
Generally, my task is like that: there are a lot of ID's and timestamps for different actions. I heed to find those ID's where among
A1, A1, A2, A3, ..., An
exists Ai, Al, and Am (1 <= i,l,m ...
0
votes
1answer
30 views
How to write GetEnumerator() for a Binary Search Tree?
I have a BinaryTree class and a BinaryTreeNode for holding nodes, I have already made the tree and write the pre-order, postorder and in-order method for it.
but i don't know how to write ...
0
votes
0answers
16 views
evaluate the accuracy of image segmentation
I am working on medical image segmentation. I want to evaluate the accuracy of the image segmentation technique. I searched about an evaluation method,I found many methods like : mean square error , ...
0
votes
1answer
15 views
left rotation in bst with 4 fields
I have some problem with this and I tried a lot to solve it. I understand how rotation of bst work but I could not conform it to this structure.
Assume that the object Node of the binary search tree ...
1
vote
1answer
31 views
Verification of a different approach for the longest path in an undirected tree
I was trying this problem -
Finding the longest path in an unweighted, undirected tree.
Approach 1
Perform BFS from any node(say X) to the farthest possible node(say Y).
* Then, perform BFS again ...
1
vote
1answer
46 views
Sum of geometric points on large interval
I have a large interval [0 ... 2^32 - 1]. There are approximately 2^20 points with some coordinate and value, for example:
1; 435
5; 5454
345345; 5485;
9999999; 43435
4294967294; 35353
Also I have ...
2
votes
2answers
31 views
Replace element in sorted range
There is an array std::vector of unique elements. It's sorted. It is known, that it contain an element with value From. I want to replace it with unique value To in optimal way keep tracking its ...
0
votes
1answer
53 views
How to get original codes from generated pattern in java?
Suppose I have java.util.Set<String> of "200Y2Z", "20012Y", "200829", "200T2K" which follows the same pattern "200$2$", where "$" is the placeholder. Now which is the most efficient way to get ...
1
vote
2answers
54 views
Select m friends among n colleagues with given constraints.(Coding ques)
Jack has n colleagues and m friends in his office. Jack brought one gift for each of his m friends.
After knowing that, all of his n colleagues demanded gifts from him.
But Jack wanted to give gifts ...
1
vote
1answer
26 views
Alpha Beta Pruning Assumptions
I am learning about game trees(Chess) and was wondering if alpha beta pruning is based on the assumption that the two players playing are 'perfect players'. What happens if a human who is not perfect ...
0
votes
1answer
45 views
algorithm: calculate the starting/ending angle from 2 end points
I need to represent an elliptical arc with starting and ending angle in counter clock wise order.
The ellipse is not rotated.
I have the center coordinate and 2 points (start+end, but we dont know ...
2
votes
2answers
34 views
What are examples of naturally dense graphs?
Graphs are very useful for modeling real-world phenomena and relationships.
Broadly, graph data structures and algorithms are divided into two categories:
Those useful for sparse graphs (e.g. ...
1
vote
0answers
36 views
Search in and across paragraphs
I am trying to develop a function which will highlight the text in a page based on search keywords. I have bounding boxes of all the words in the page and all the words are arranged in ascending order ...
0
votes
0answers
44 views
Algorithm to find heart beats per minute
I am using a Polar Equine Heart beat detector along with a micro-controller. The Polar device will give a pulse for each heart beat. But the output of that is not stable. If the electrode is not ...
-4
votes
1answer
42 views
Is this algorithm for the function correct?
The question I'm trying to solve is...
What is the value returned by the following function? Express your answer as a function of n.
int v = 0;
int n = 100;
for (int i = 1; i <= n ; i++) ...
0
votes
0answers
22 views
Whats the difference between Minimum Spanning Tree and Dijkstra's algorithm? [duplicate]
They both seem very similar and I am studying graph theory, can someone tell me in what situation's would I use either one. I understand that Dijksta is a shortest path algorithm but they seem to ...
