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.
0
votes
1answer
13 views
Writing code to elegantly and efficiently make a graphic bounce around the screen
I'm going to try and write a language-independent description of what I'm trying to ask (although the language I'm trying to do this in is JavaScript and the "screen" will refer to the body of my HTML ...
0
votes
0answers
22 views
Remove duplicates from a list of maps in java
I am having a list of maps in the following format.
List<Map<String, String>>
All the map objects have two keys "ACCOUNT_ID" and "PHONE_NUMBER" where the account id value might repeat ...
0
votes
0answers
16 views
Why does my PRIME1 - SPOJ implementation gets SIGSEGV, even though it runs fine for all test cases in my pc?
Input:
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) ...
2
votes
2answers
35 views
Where is the Sieve of Eratosthenes used today?
I'm doing a research paper on the topic and while I find a lot of examples and discussion about how the algorithm works/should be implemented, I can't find anything on where it's actually used.
Is ...
0
votes
0answers
22 views
Partition function based on Euler's formula
I am trying to find the partitions of a number using the Euler's formula for that:
It produces results like:
P(3) = P(2) + P(1) = 3
P(4) = P(3) + P(2) = 3+ 2 = 5
P(5) = P(4) + P(3) - P(0) = 5 + 3 ...
0
votes
3answers
18 views
Partitioning a list of integers to minimize difference of their sums
Given a list of integers l, how can I partition it into 2 lists a and b such that abs(sum(a) - sum(b)) is minimum. I know the problem is NP-complete, so I am looking for a pseudo-polynomial time ...
0
votes
0answers
13 views
How to efficiently check whether it's height balanced for a massively skewed binary search tree?
I was reading this answer on how to check if a BST is height balanced, and really hooked by the bonus question:
Suppose the tree is massively unbalanced. Like, a million nodes deep on one side and ...
0
votes
3answers
34 views
Optimising F# answer for Euler #4
I have recently begun learning F#. Hoping to use it to perform any mathematically heavy algorithms in C# applications and to broaden my knowledge
I have so far avoided StackOverflow as I didn't want ...
0
votes
1answer
44 views
Find the area of polygon whose sides are known [C++]
I'm trying to the find the area of a shape for which I've only been given the length of the sides.
Considering the shape to be a quadrilateral (having only four sides) for now, what is the method(or ...
1
vote
4answers
81 views
C++ sorting array of true false
I have been assigned two similar tasks which should be pretty easy but I need a clarification on what I can and can't do with c++.
Task 1:
Suppose you have an array of n elements containing only two ...
0
votes
2answers
31 views
Get three-digit numbers where the sum of factorials of the digits equals to the number
I am reading combinatorial book for school and have to do some exercises, this is one of them:
Write a computer program to determine whether there is a three-digit integer abc (= 100a + 10b + c) ...
2
votes
1answer
41 views
How to get every single permutation of a string?
I know how to get the permutations of just the plain string in python:
>>> from itertools import permutations
>>> perms = [''.join(p) for p in permutations('stack')]
>>> ...
1
vote
2answers
63 views
Quick Sort Algorithm - Median of Three
I have the following quicksort algorithm which uses the leftmost as a pivot which is working perfectly well:
public static void QuickSortLeft(int[] array, int start, int end)
{
int left = start;
...
-1
votes
1answer
34 views
Puzzle jump game Complexity
My questions is specific to the problem posed here:
Interview puzzle: Jump Game
The top answer claims that it runs in O(n) time. It says that it can do this
because each element need be ...
0
votes
0answers
12 views
Choosing Best Fitting Image, Responsive Design
I have an algorithm issue which I cannot figure out how to do.
Provided I have device that can be either in portrait or landscape mode.
Provided the device can have multiple resolutions per layout.
...
0
votes
1answer
31 views
Why ball flies through bricks?
I am writing an Arkanoid clone in javaScript and I have a problem with ball/brick collisions. This is how I do rendering (this might be important, I don't know):
function Game() {
//...
this.fps = ...
-1
votes
0answers
29 views
Stuck on USACO's Controlling Companies
First time posting here, so let me know if I'm making any mistakes.
I'm working on a task on USACO and I'm stuck and I can't seem to find what doesn't work in my approach (and the test case is way ...
-4
votes
1answer
15 views
Prove that any minimum vertex cover of a clique of size n must have exactly n-1 vertices [on hold]
How to prove that any minimum vertex cover of a clique of size n must have exactly n-1 vertices?
THx
-1
votes
0answers
26 views
A*Algorithm and State Definition
Assume that the selected route S-A-B-G is taken Where S=Source,G= Goal,
Nodes Locations
A (2,2)
B (4,5)
H (0,0)
O (7,1).
Assume that the vehicle is in one of the roads on the ...
0
votes
0answers
21 views
Track iris using starbust algorithm
I am implementing an eye tracker in emgu CV (Wrapper for openCV), Most research papers recommend to use starbust algorithm.I seared for starbust tutorials on emgu CV , unfortunately i could not find ...
0
votes
1answer
21 views
Space/Time complexity of Binary Tree Equality
I had an interview yesterday that involved a pretty basic tree data structure:
t ::= int | (t * t)
where a tTree is either an integer (leaf) or two t's which represent left and right subtrees. This ...
2
votes
1answer
16 views
General approach to proof of correctness for wait-free algorithms
I have used universal construction to design an algorithm for wait-free binary search trees. I have got linearization points for each of the methods. But I'm not sure on how do I formally prove ...
0
votes
0answers
23 views
python code should perform SJF algorithm but it's not
consider the following code which takes inputs (Burst & arrival) times of the processes and sort them according to sjf algorithm, but the output is wrong, he order the process in other algorithm ...
4
votes
4answers
91 views
Find vector elements with even values
Could you explain how does this code work. It successfully counts vector elements with even values, but it's not clear for me how does binding in this particular case work.
count_if(vec.begin(), ...
1
vote
1answer
38 views
use std::find for case insensetive search without boost libary in vectors
I need to find the string form the vector list through case insensitive comparison. Is there is some easy solution for it. i can't use boost library.
My code i have written for case sensetive search ...
1
vote
3answers
39 views
row sorted column sorted matrix
can anyone suggest an algorithm for generating a row sorted, column sorted 2-D matrix given a list of integers ?
What I mean is that all rows and all columns should be sorted, preferably in asc/desc ...
-1
votes
1answer
23 views
algorithm to compute waiting time for FCFS scheduling in python
Consider the following code that takes input processes and their arrival times and sort them according to FCFS algorithm, so i've been thinking about algorithms to compute avg waiting time but all is ...
0
votes
0answers
43 views
Compiler writing vs Chess programming [on hold]
Has anyone ever tried to learn to write a compiler or a chess game.I am actually trying to chose between which one to start and which one is more educational in terms of Application of Data Structures ...
-2
votes
0answers
14 views
drawing lok sabha(Indian parliamentry) constituencies on google maps [on hold]
I am doing one project in which I have to draw lok sabha(Indian parliamentry seeats) constituencies and to find in which constituency a particular area falls on.It will not be possible to draw all ...
google-maps
0
votes
2answers
17 views
What data structure or algorithm is used for autocompletion?
When we type half the command or name and we press tab, it immediately finds out remaining part. What data structure/algorithm is used underneath to achieve this efficiency?
-6
votes
0answers
39 views
write equivalent c code for a sas code [on hold]
I have a SAS code and I have to implement the same as a C function....It is an ecryption algo..Can someone here please explain to how is it actualy working. The basic idea is getting a entry from a ...
1
vote
0answers
26 views
Studying Skiena. War Story: What’s Past is Prolog
I am reading The Algorithm Design Manual, 2nd Edition. I am the "What’s Past is Prolog" war story.
This war story is available on the web here
I do not follow this statement:
Since the rules were ...
5
votes
6answers
141 views
Effective unique on unordered elements
I'd like to improve the speed performance of my box counting method I use in fractal analysis.
About the task
I have a stream of ints (about n=2^24 long) and I have to calculate how many different ...
0
votes
2answers
32 views
Find way, or other algorithm?
What algorithm I need to use to achieve such a functionality? I had tried to look at longest way finding algorithms, but they are not suitable here. But I dont want give up, which way I need to look ...
1
vote
1answer
23 views
Set operations (union and intersection) on simple polygons in 2D
I am looking for an algorithm for union and intersection operations on simple polygons in 2D.
Every polygon in my application is:
defined by a set of points (point is defined by x and y ...
0
votes
4answers
56 views
Generation of all subsets of strings for a given string
I want a code to generate all the subsets of strings of the given string.
I tried this on my own and came up with this :
public static void main(String[] args){
long startTime = ...
0
votes
2answers
74 views
Minimum of three numbers [duplicate]
I'm working on algorithm that heavily uses min() function to find the smallest number of three numbers. Program is written in C/C++ language. Temporarily I use
min( number1, min(number2, ...
0
votes
2answers
32 views
Blur algorithm with RGB
Im trying to blur an image depending on a user input. If it is 1 then the blur image will average a 3X3 square and put it into the middle one.
P P P All the pixels will be averaged and put into ...
0
votes
2answers
38 views
Max depth of Binary search tree
I want to find the max depth of binary search tree. I found a code.
int maxDepth(struct node* node) {
if (node==NULL) {
return(0);
}
else {
// compute the depth of each subtree
...
0
votes
1answer
61 views
Big O complexity of this algorithm
IsNumberPrime(int num):
if num <= 1: return False
i = 0
end = sqrt(num)
while ArrayOfPrimes[i] <= end:
if (num % ArrayOfPrimes[i]) == 0: return False
i = i + 1
return True
This algo checks ...
1
vote
1answer
48 views
Implementing Peterson's algorithm in chat
I'm having a hard time understanding and implementing Peterson's algorithm for N processes (also known as Filter algorithm). I'm trying to make a chat in C using shared memory. I'm using the version ...
-2
votes
1answer
40 views
Finding Permutations of Strings with no Repeats [duplicate]
I have posted this question already on this forum here, but seeing as no one has answered I decided to try here.
Basically, I'm looking for a way to permute an array of integers given a range with no ...
-6
votes
2answers
79 views
Write a non-recursive algorithm to compute n factorial [duplicate]
I am having problems writing a code in java to compute n! without recursion. I know how to do it in loops, but I am not sure how to do it non-recursively.
procedure factorial
if n = 1 or n = 0
...
0
votes
0answers
25 views
Crowd sourcing algorithm for user's voting weight [migrated]
I am currently thinking of a crowd sourcing algorithm for my application. So I checked out how stack overflow calculates the reputation. Here is what I found on SO website:
your question is voted ...
0
votes
0answers
19 views
Max min fairness with infinite stream
I have a input stream with incoming items that require X(random) amount of resources and I have a max capacity of C. I would like to distribute C fairly while still accounting/leaving Y of C for new ...
1
vote
4answers
65 views
Finding common clusters
I've came across the following problem:
Imagine we have a set of n samples that we want to classify into k classes labeled 1-k. We run M different clustering algorithms and get M different outputs. ...
-4
votes
0answers
33 views
Find algorithms to calculate 2^n-1in given complexity [on hold]
I need to find several algorithms to calculate 2^n -1.
For example, I need one to that is in Theta(n^n) and one in Theta(1).
I am counting 1 arithmetic operation as 1 added "complexity unit".
How ...
0
votes
2answers
19 views
Mathematically how does one compare classification result to clustering results
Is there a standard methodology to compare results (for accuracy) of a classification algorithm against a clustering algorithm? I have data that has only two true labels. Easy enough to check accuracy ...
1
vote
1answer
35 views
Ford-Fulkerson algorithm in a graph with links with weight 1
In a max flow problem, when I apply a ford-fulkerson algorithm to find the max flow, if all the links of the graph have weight 1, the max flow will be the number of paths that I've found in the ford ...
0
votes
1answer
18 views
Ant colony optimisation questions: how to output results correctly, what is the result of algorithm and others
I am doing ant colony optimiztion algorithm. I have got a few questions. I tried to search throw ant-colony, but found nothing.
1 — What is the result of the algorithm?
I have some graph and I need ...
