Questions tagged [algorithm]

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.

algorithm
23,767 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
7 votes
2 answers
2k views

Efficient algorithm for removing loops from polylines

I have a polyline, given as an ordered set of (X,Y) coordinates, that may cross over itself to form one or more loops. From this, I want to extract a polygon that has the loops removed, which will ...
SmacL's user avatar
  • 22.7k
7 votes
2 answers
13k views

How can you implement a condition variable using semaphores?

A while back I was thinking about how to implement various synchronization primitives in terms of one another. For example, in pthreads you get mutexes and condition variables, and from these can ...
templatetypedef's user avatar
7 votes
0 answers
10k views

Sound frequency detection

I am currently attempting to create a sound frequency detection application on the iPhone. I have been informed that the algorithm I need for frequency detection of a single frequency is the goertzel ...
123hal321's user avatar
  • 2,090
7 votes
4 answers
4k views

Smallest substring that can be replaced to make the string have the same number of each character

I'm trying to solve a problem that is almost exactly that. In particular I'm given a string s such that s.Length % 4 == 0 and each s[i] is one of 'A', 'C', 'T' or 'G'. I want to find the smallest ...
user6048670's user avatar
  • 2,891
7 votes
3 answers
2k views

Part 2 Resilient backpropagation neural network

This is a follow-on question to this post. For a given neuron, I'm unclear as to how to take a partial derivative of its error and the partial derivative of it's weight. Working from this web page, ...
Nutritioustim's user avatar
6 votes
2 answers
362 views

Find min(A[L], max(A[L+1], min(A[L+2],...,a[R]))) in range

Give array A consist of N (1 <= N <= 10^5) positive integer less than 10^6. Given Q (1 <= Q <= 10^5) queries, for each query of the form (L, R) (1 <= L <= R <= N), print out: min(...
little.dinosaurs's user avatar
6 votes
0 answers
114 views

Is there a performant algorithm to reduce unneccessary large loop in Traces to its minimum?

Currently I am working on an algorithm to reduce the number of loop iterations in traces to what is minimum necessary. More exactly, this: trace = ["a", "b", "b", "...
Diana's user avatar
  • 377
6 votes
0 answers
220 views

How to cover a rectangle area with irregular shapes and no holes

I have detailed, highly irregular shapes like these: and I'm looking for a way to make them cover a rectangle area with no holes and minimal blend/cover between shapes. Limited up-scaling and free ...
Hubert Rzepinski's user avatar
6 votes
1 answer
369 views

Standard Algorithms to implement Transliteration and Transliteration Suggestion

I have constructed an algorithm to transliterate from English to multiple languages, Since we should show them appropriate suggestion for the words they have entered, I have made logic to search in ...
Sab's user avatar
  • 61
6 votes
1 answer
3k views

In a Max Flow problem, how to find all possible sets of paths that give max flow?

I understand that Ford-Fulkerson Algorithm can find the maximum flow that can flow from source (s) to sink (t) in a flow network. But is there an algorithm that finds all possible sets of paths that ...
Allen's user avatar
  • 2,325
6 votes
1 answer
554 views

Finding Longest Path Grid

I am working with a uniform cost grid that only allows movements in the orthogonal directions. This is used as a base for the game snake where the snake must constantly move and try to eat apples on ...
Cobey Hollier's user avatar
6 votes
2 answers
1k views

Function to generate flight trajectory (list of 3D points, lat, lon, alt)

I am looking to generate some 3D trajectory data for an aircraft simulation. The idea is that the aircraft takes off at some location x and continues to ascend at some average ascent velocity a_v and ...
pookie's user avatar
  • 3,924
6 votes
0 answers
499 views

permutation optimization in tensorflow

Problem setup I have a batch of 4x4 matrices, containing real valued entries. L = tf.placeholder('float32', shape=[None, 4, 4], name='pairwise-loss') I'd like to find a batch of 4-permutations such ...
Kh40tiK's user avatar
  • 2,306
6 votes
1 answer
2k views

NLP bag-of-words/TF-IDF for clustering (and classifying) short sentences

I want to cluster Javascript objects by one of their string key values (description). I already tried multiple solutions and would like some guidance on how to approach the problem. What I want: Let'...
Tomasz Gałkowski's user avatar
6 votes
2 answers
4k views

Finding all possible paths in graph

I'm looking for some algorithm which will help me find all possible paths in a graph. Everything I found so far is not fully satisfying. Let's imagine we have a graph (tree) like this one: And let's ...
cojoj's user avatar
  • 6,465
6 votes
1 answer
3k views

Unique hash with maximum of 4 characters?

What is the best method to create a hash of String, if the hash may not have more than 4 characters, and those 4 characters may only be lowercase letters or digits? The strings I want to hash have 1-...
membersound's user avatar
  • 84.1k
6 votes
1 answer
809 views

Arrange segments in rows without overlapping

There is a set of segments {(a_i,b_i) with i = 1, ..., n} with 0 <= a_i < b_i <= 1 that has to be arranged on N lines [0,1] without overlap. For example, if a set can consist of {(0.35,0.41),...
andrea.ge's user avatar
  • 1,967
6 votes
1 answer
479 views

How to aggregate a data set of geocodes to reduce there numbers for a heat map?

I have a data set of Latitudes and Longitudes for populating a heat map. The data is too large and will keep on increasing day by day. I need to reduce the amount of data without much affecting the ...
user avatar
6 votes
3 answers
4k views

Matrix Multiplication using Divide and Conquer, Time Complexity

I understand that the algorithm uses 8 multiplications and 4 additions with time-complexity: The multiplication is done on every n/2 * n/2 matrices. I have few questions on this : Does every n * ...
sagar_jeevan's user avatar
6 votes
2 answers
221 views

Given a digit from each of K consecutive integers recover the sequence

A series of N consecutive positive integers starting from X is written down. Then exactly one digit from each number is chosen and written in the same order. We need to find the smallest X for which ...
Artur's user avatar
  • 591
6 votes
2 answers
3k views

Is there an algorithm to find minimum cut in undirected graph separating source and sink

I have an edge-weighted undirected graph and 2 nodes (often called source and sink). I need to find a set of edges of minimum possible weight, which separates these 2 nodes into 2 weak components. I ...
Youda008's user avatar
  • 1,918
6 votes
1 answer
238 views

Minimum area calculation algorithm (Place tiles on edge only)

I have different dimension of small rectangles (1cm x 2xm, 2cmx3cm, 4cm*6cm etc). The number of different type rectangles may vary depending on case. Each type of different rectangles may have ...
Charles Tang's user avatar
6 votes
1 answer
3k views

How to efficiently retrieve top K-similar document by cosine similarity using python?

I am handling one hundred thousand(100,000) documents(mean document length is about 500 terms). For each document, I want to get the top k (e.g. k = 5) similar documents by cosine similarity. So how ...
user1024's user avatar
  • 1,022
6 votes
0 answers
1k views

The Facebook News Feed Algorithm Formula

I am asked to make an existing basic newsfeed code in PHP a little smarter. Maybe with relevancy and diversity. The client is not sure himself, he just wants something smart (kinda) like Facebook's ...
Ip ziet's user avatar
  • 307
6 votes
1 answer
2k views

Create binary tree in level order from array

I am working on a small algorithm that builds a binary tree in level order. I am given an array and I must use the values in it to build a binary tree in level order. Example: arr inarr[5]={1,2,3,4,5};...
JustaRedShirt's user avatar
6 votes
4 answers
2k views

Build a tree from file paths

I'm trying to create a tree view from file paths, which can be added and removed dinamically, for instance: A/B/C/D/file1.txt A/B/D/E/file2.txt A/B/D/G/file3.txt A/B/D/G/file4.txt My tree, however, ...
John Smith's user avatar
6 votes
2 answers
324 views

How should graphing tool behave in case SNMP counter has smaller value than previous reading?

I'm building a small monitoring solution and would like to understand what is the correct/best behavior in situation where previous reading is larger than current reading. For example ifHCOutOctets ...
Martin's user avatar
  • 1,057
6 votes
1 answer
413 views

Multiple depot vehicle scheduling

I have been playing around with algorithms and ILP for the single depot vehicle scheduling problem (SDVSP) and now want to extend my knowledge towards the multiple depot vehicle scheduling problem (...
Allasea's user avatar
  • 61
6 votes
1 answer
2k views

What's the worst-case valid sudoku puzzle for simple backtracking brute force algorithm?

The "simple/naive backtracking brute force algorithm", "Straightforward Depth-First Search" for sudoku is commonly known and implemented. and no different implementation seems to ...
farter's user avatar
  • 96
6 votes
0 answers
747 views

Implementing split() function in Rcpp

I am trying to implement native split function in R in c++ for Vector,Matrix and Data Frame separately.For example the function below serves the purpose of splitting a vector. using namespace Rcpp; ...
gman's user avatar
  • 1,242
6 votes
2 answers
3k views

The best way for finding the closest line segment to a point

As can be seen in figure below, I have some lines (finite length) between any two joints (red points), such as the line between joints J1 and J2. I have also some points such as P1 and P2. I have ...
ard24ie's user avatar
  • 181
6 votes
1 answer
457 views

NP-Complete? Optimal graph embedding for a graph with specific constraints

I have a grid based graph, where nodes and edges occupy cells. Edges can cross, but cannot travel on top of each other in the same direction. Lets say I want to optimize the graph so that the ...
ddriver1's user avatar
  • 733
6 votes
1 answer
2k views

Copying Books UVa Online Judge Dynamic Programing Solution

I can solve Copying Books Problem using binary search method as it is easy to implement. But I have just started solving Dynamic Programing problems and I wanted to know Dynamic Programing solution ...
coder hacker's user avatar
  • 4,839
6 votes
1 answer
1k views

How to create a mind map from paragraph of a book

Today I tried to write a program that would take in a paragraph of text and create a graph showing relations between different words. Everything went well, except that I don't know how to find out the ...
user avatar
6 votes
1 answer
1k views

Most rewarding path in a graph

I'm faced with the following problem: Given An undirected graph, where each edge E has: Et - the time it takes to traverse E Er - the reward for traversing E Goal: Problem 1: Given time period T,...
Lior Kogan's user avatar
  • 20.3k
6 votes
1 answer
1k views

Using disjoint-set data structure, graph theory

I'm practicing solving programming problems in free time. This problem I spotted some time ago and still don't know how to solve it: For a given undirected graph with n vertices and m edges (both ...
xan's user avatar
  • 1,053
6 votes
3 answers
271 views

Feedback on ranking algorithm options for my website

I am currently working on writing an algorithm for my new site I plan to launch soon. The index page will display the "hottest" posts at the moment. Variables to consider are: Number of ...
HockeyRef45's user avatar
6 votes
1 answer
2k views

Find longest common substring of multiple strings using factor oracle enhanced with LRS array

Can we use a factor-oracle with suffix link (paper here) to compute the longest common substring of multiple strings? Here, substring means any part of the original string. For example "abc" is the ...
Ray's user avatar
  • 1,655
6 votes
2 answers
5k views

Minimum over a sliding window

Is there specific algorithm that allows me to maintain a min/max over a small/medium sized sliding window (typical size is 600, with all elements being integers)? The window is really the last N ...
KS1's user avatar
  • 165
6 votes
1 answer
8k views

Can you help me with my Clarke and Wright algorithm implementation?

I am trying to implement the Clarke and Wright algorithm to construct an initial VRP solution. It seems to run properly but for some reason the solution's quality I get is not the expected one. Here's ...
user avatar
6 votes
1 answer
1k views

Generating quadrilateral mesh from Mathematica surface mesh

I am trying to make a quadrilateral mesh from a surface mesh (which is mostly triangular) generated by Mathematica. I am not looking for high quality mesher but a simple work around algorithm. I use ...
PlatoManiac's user avatar
  • 1,442
6 votes
1 answer
3k views

Coalesced Hashing Deletion Algorithm

Can someone show me an example of deletion algorithm for a coalesced chained hash table? My insertion algorithm is like this: Insert (key) int p = hash(key) if d[p] = NIL then d[p] =...
Bogdan's user avatar
  • 672
6 votes
1 answer
5k views

Iterative Closest Point Implementation

I am currently using the following pseudo code to implement the ICP algorithm in C#. Obtained from ICP Powerpoint function ICP(Scene,Model) begin E` = + ∞; (Rot,Trans) = In Initialize-Alignment(...
Rick's user avatar
  • 73
6 votes
2 answers
2k views

how to compare two list and find out `added` `deleted` `unchanged ` part

I want this: def compare_list(old, new): new_set = set(new) old_set = set(old) return new_set - old_set, old_set - new_set, new_set & old_set old = [1, 2, 3] new = [5, 4, 2, 3] ...
JustWe's user avatar
  • 4,339
6 votes
1 answer
357 views

minimum-size Vec3 that move Physics object to make penetration = 0

Here is an example (see image) :- The 2 reddish rectangles are static objects (i.e. it can't move). The bluish ball is dynamic object. So far, I manage to get all penetrating information. ...
cppBeginner's user avatar
  • 1,100
6 votes
1 answer
998 views

How to attack this tiling puzzle?

[The 1000 point problem on SRM 209, Div I] At some stage, the problem reduces to the following: Given blocks of three square units, like below, which can be rotated in any manner, how many ways are ...
Moeb's user avatar
  • 10.6k
6 votes
3 answers
764 views

Finding number of possible sequences in an array, with additional conditions

There is a sequence {a1, a2, a3, a4, ..... aN}. A run is the maximal strictly increasing or strictly decreasing continuous part of the sequence. Eg. If we have a sequence {1,2,3,4,7,6,5,2,3,4,1,2} We ...
Peter's user avatar
  • 2,749
6 votes
1 answer
4k views

Minimum number of boxes required for n objects

There are n objects having different weights. We have to find the minimum number of boxes required to pack all weights where each box can have the maximum weight of K. Boxes can have any number of ...
Praveen's user avatar
  • 77
5 votes
2 answers
148 views

Removing overlap between convex hulls

In two dimensions, we are given two sets of points A and B and their respective convex hulls C_A and C_B. Assume that C_A and C_B overlap. What is the best algorithm to find the minimal set that must ...
A. Roy's user avatar
  • 376
5 votes
1 answer
93 views

Search unique fours for the defined sum

I have a task to find four unique elements , sum of which is defined. So I have as input data : data array of n elemeents, elements can be duplicated, and 's' is sum. I have two cycles , first i in ...
Gosha Efimenko's user avatar