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
0answers
16 views
K diagonals for polygon with N vertices
Consider a regular polygon with N vertices labelled 1..N. In how many ways can we draw K diagonals such that no two diagonals intersect at a point strictly inside the polygon? A diagonal is a line ...
0
votes
1answer
12 views
Minimum edges to remove to reach destination
I faced one competition, where I got stuck in one question. Please help me in this.
Directed Graph is given.
Nodes indexes as 0, 1, 2, ..., N.
Starting point - 0.
Ending Point - N.
Contraints :-
...
0
votes
0answers
7 views
Intersection points between 2 discs in 3d
i am trying to find a algorithm or a way to find the intersection between two circle on a sphere (in 3d). For example if i have two circles center at two pointsA(latitude1,longitude1) and ...
-4
votes
0answers
22 views
Bug in SPOJ - BIT2 - count set bits till number N [on hold]
I am facing a bug in the solution of the SPOJ problem -
Problem link: http://www.spoj.com/problems/BIT2/
Problem Statement : You will be given a number N, and you have to tell whether there exist a ...
1
vote
2answers
19 views
how to implement stack decoding algorithm with TDD
I have a fairly complex algorithm I would like to implement with TDD for translation. it is called stack decoding and described here.
When I tried to do that I was able to write and fix some simple ...
1
vote
2answers
27 views
Iterative fibonacci complexity, cannot undersant why it is O(n^2)
Please don't confuse the question with recursive fibonacci, which has the complexity 2^n.
This is the fibonacci iterative code i use :
def f(n):
a, b = 0, 1
for i in range(0, n):
...
2
votes
2answers
24 views
Find close path or region using recursive method
I have a object in 2d array and i want to traverse through them top, left, right for that object acutally i want to check if there are making some loop or better making some closed region. See this ...
0
votes
0answers
25 views
How to calculate average turnaround time in non-pre-emptive scheduling?
Process - Arrival Time - Burst Time
P1 - 0.0 - 7
P2 - 0.5 - 3
P3 - 1.0 - 2
Additional info: Schedule is non-pre-emptive.
...
-1
votes
1answer
16 views
Error in maximum subarray algorithm for crossing array in Python
I have implemented Maximum Subarray algorithm in Python. My code is not giving the right answer for certain inputs.
Here is my code:
A = [-1, -2, 3, 4, -5, 6]
def main():
a,b,c = ...
1
vote
1answer
20 views
Why is a successful search in a chained hash table have a time complexity of Θ(1+(n/m)) on average?
I get why an unsuccessful search in a chained hash table has a time complexity of Θ(1+(n/m)) on average, because the expected number of elements examined in an unsuccessful search is (n/m), and the ...
1
vote
1answer
23 views
NSArray -> Find closest value - fastest way
Lets say I've got an ordered NSArray of NSNumbers:
2, 4, 8, 15, 16, 20 // for simplicity let's treat it as array of int's instead of NSNumbers
Now I need to find closest index to let's say value == ...
1
vote
0answers
28 views
Using REST calls to match range of local objects to server objects
I am connected to an exchange and using REST calls I need to keep a local state syncronized to what is happening on the exchange. Specifically I need to keep updated information about the state of ...
-1
votes
0answers
23 views
A* Algorithm with revisited points
with A* we're not allowed to revisit visited nodes already. However, what if we have a case like so (such that the top left corner is (1,1) ):
http://pastebin.com/p31hdWtf (Note the pastebin link as ...
0
votes
4answers
55 views
Having trouble reversing an array
Here's my code:
#include <iostream>
using namespace std;
void reverse(int *, int);
int main()
{
const int len = 10;
int intArray[len] = {5, 6, 4, 1, 3, 10, 15, 13, 2, 7};
...
0
votes
0answers
24 views
How to improve the performance of K-nn algorithm in R? [migrated]
I am having a digit recognizer data set which has column names as label, pixel0, pixel1...pixel783. pixel values vary from 0 to 255 indicating the lightness or darkness of that pixel, with higher ...
0
votes
1answer
19 views
Quick-Find Union on N Elements
I'm new to algorithms and was hoping someone could explain why the maximum number of id[] array entries that can be changed in one call to union using quick-find is n-1? Preferably in Layman's terms.
1
vote
2answers
52 views
Find the beginning and ending of consecutive numbers in a list
I have an input list:
s = [1, 2, 3, 5, 6, 9, 10, 11]
And I am trying to get the following as output:
lows = [1, 5, 9]
highs = [3, 6, 11]
The lows list contains all the lowest numbers of all the ...
2
votes
1answer
38 views
Counting number of contiguous subarrays with positive sum in O(nlogn) using O(n) transformation
I am interested in finding the number of contiguous sub-arrays that sum to a positive value (sum>0).
More formally, Given an array of integers A[1,...,n] I am looking to count the pairs of integers ...
0
votes
1answer
16 views
How do you denote queue, initialization, and array in topological sort?
I am making an attempt to write an algorithm for topological sort using pseudocode, but how would you denote in pseudocode the initialization of queue (Q) with 0 in degrees at start and an array that ...
0
votes
0answers
32 views
Median of Medians Algorithm Size 3?
I am studying the median of medians algorithm and there's a question in the book that asks why the size cannot be 3; if it is 3, it won't provide linear time complexity.
I worked out the size=5 and ...
0
votes
1answer
41 views
Difficulty in implementing Strassen's algorithm in Python
I don't understand how to call my code recursively. Here is my code so far:
import numpy
B = [[5,5,5,5,5,5,5,5],[6,6,6,6,6,6,6,6],[7,7,7,7,7,7,7,7],[8,8,8,8,8,8,8,8],
[9,9,9,9,9,9,9,9], ...
0
votes
1answer
10 views
Uniform Cost Search: How do I retain the solution?
The algorithm can be found here: http://en.wikipedia.org/wiki/Uniform-cost_search
I am struggling with keeping the solution. I am writing in Python, and my implementation finds the optimal solution ...
0
votes
0answers
20 views
Ransac Algorithm used for Detecting Text in Image? [on hold]
RANSAC Algorithm is often used in computer vision. But i wonder if it is capable in detecting text on images.
It is really possible? and can anyone show me how it done?
0
votes
3answers
25 views
Generate random bridge hands with a certain strength
I am trying to make a java program that deals bridge hands (13 cards from a standard 52 card pack) with a certain number of high hards (Aces, Kings, Queens, and Jacks) in each hand.
I was looking at ...
2
votes
0answers
20 views
Shortest Path Algorithm with Fuel Constraint and Variable Refueling
Suppose you have an undirected weighted graph. You want to find the shortest path from the source to the target node while starting with some initial "fuel". The weight of each edge is equal to the ...
1
vote
0answers
21 views
Is the Naive Bayes classifier a specific algorithm?
I've been looking for the specific algorithm statement of the Naive Bayes but I can't find any. All I found are pseudocodes and implementations in various languages and documentations discussing this ...
0
votes
1answer
22 views
How to fine the worst case and best case running time for any algorithm.? [on hold]
If suppose I am give any problem and I am asked to write the algorithm for that problem..then how do I find the worst case and best case running time for my algorithm.?
1
vote
0answers
51 views
Project Euler #1: Alternative Algorithm
I am a beginner programmer and in order to practice my skills, I decided to work on some of the Project Euler problems. I do realize that many people have asked questions regarding the first Project ...
-1
votes
0answers
25 views
Solving recurrence T(n) = 2T(n/2) + Θ(1) by substitution
So I am pretty sure it is O(n) (but it might not be?), but how do you solve it with substitution?
If you assume T(n) <= c * n, what is the induction steps?
3
votes
2answers
47 views
Sorting and grouping list of objects by type and date with variable size data
I am working on a problem. I have to prepare a destination list that is used to show data on UI. Source list is list returned by external webservice.
source list of objects size can be 0 to 16. ...
0
votes
1answer
27 views
PHP Ranking Algorithm [on hold]
I have a website that is going to rank users based on points they have earned for doing certain activities. This is my database structure:
pointsentered
1. ID
2. Email
3. Code
pointvalues
1. ID
2. ...
0
votes
0answers
16 views
Cryptographic Algorithm using Inverse Modulus Function
I am trying to use the inverse modulus function as provided in the NTL library that can be found here: http://www.shoup.net/ntl/doc/tour.html
Currently I am filling an array with values in a range, ...
0
votes
0answers
43 views
Shortest Path algorithm in line follower robot (Maze solving)
How graph algorithms can be used in line follower maze solving robot. I have solved grid using DFS search but do not know how to implement it actual line follower robot. my shortest path finding ...
1
vote
1answer
33 views
Finding a group of subsets that does not overlap
I am reviewing for an upcoming programming contest and was working on the following problem:
Given a list of integers, an integer t, an integer r, and an integer p, determine if the list contains t ...
-7
votes
0answers
38 views
Many To Many Grouping Algorithm [on hold]
Background Info:
I have a diagram that represents set of nodes that have a many to many relationship with other nodes in the diagram.
The diagram is setup as a list of rows and columns, and the ...
0
votes
4answers
61 views
How to sort random elements of an array efficiently so that similar items appear together
I'm starting to get myself into algorithms and I need help solving this kind of problem.
Task set:
An array contains sheep and goats in random order. Write a possibly
fast method to rearrange ...
-5
votes
0answers
23 views
I need help on FIFO frame diagrams [on hold]
So i needed to do a program involving first in, first out algorith. I wanted to display a frame diagram. With the user entering referrence strings and number of page frames. I can get their input but ...
2
votes
1answer
59 views
Solving recurrence T(n) = T(n/2) + Θ(1) by substitution
So I understand how to do it when the recurrence looks something like this:
T(n) = 2T(n/2) + n
In that case I would guess the answer to be O(nlogn) and then use induction to prove it. But for this ...
1
vote
1answer
23 views
Polynomial time approximation of knapsack
The knapsack problem can be solved in O(n²V) time where V = max(v[i], i = 1,..,n) denotes the maximum value of any item. If we "change units" by a rounding parameter θ = ε/n * V and consider modified ...
0
votes
1answer
24 views
Ordering a List<> of Objects by another Linked Object ID
Given I have a list of objects.
These objects have a property if ID
So var obj = new Object();
obj.ID = 1;
Now these objects have preceding objects, the preceding objects are linked by ID
Like ...
6
votes
3answers
77 views
Interview: Making change for n cents (arbitrary denominations)
This question occurred as part of an increasingly-difficult problem in an interview. It started ever so simply:
(1) Assuming an infinite supply of coins (in the usual 1, 5, 10, 25 cent ...
0
votes
0answers
15 views
android
0
votes
1answer
57 views
Repeat String Recursively [on hold]
This is homework. I get the logic but i got stuck on the code. I've done it with normally way and it takes 1 week to get the code. I need to get repeat string with recursive way in Java.
This is my ...
0
votes
1answer
100 views
Why does this solution fail? Nested and matching brackets
I am still failing tests for
"negative_match: invalid structures,";
"simple_grouped: simple grouped positive and negative test, length=22";
"large1 simple large positive test, 100K ('s followed by ...
0
votes
1answer
27 views
Improving inverse modulo via Euclidean algorithms
Stuck with a question for Complexity class: "You are given a,b in Z_N* and want to complete a^-1 and b^-1 mod N. By now we know how to calculate it via using the Euclidean algorithm twice, with a,N ...
0
votes
1answer
19 views
Trilateration implementation with inaccurate distance data
I am trying to create an android smartphone application which uses Apples iBeacon technology to determine the current indoor location of itself. I already managed to get all available beacons and ...
0
votes
1answer
24 views
X-Y heuristic function for solving N-puzzle
Can somebody please explain this heuristic function, for example for the following arrangement of 4x4 puzzle, whats the X-Y heuristic cost?
1 2 3 4
5 6 7 8
9 10 11 12
0 13 14 15
(0 indicates ...
0
votes
0answers
47 views
Scheduling Algorithm for aperiodic multiprocessor tasks
I've got a System, which is defined as follows:
A limited number of stations is given (n), which can offer different services (for now there are two services). A station can either offer one of the ...
0
votes
1answer
36 views
Ruby : stack level too deep (SystemStackError)
I try to solve this problem http://www.nattee.net/~dae/algo/prob/hw03b_tiling/problem.pdf
So I using divide and conquer method to solve it but when I execute my program I get
tile.rb:7: stack level ...
-5
votes
0answers
51 views
bug in priority queue [on hold]
Here i have implemented a priority queue(especially designed for dijkstra's algorithm ) with function to modify keys. (If priority of any key changes i do not have to remove old key(O(n)) and add new ...
