Questions tagged [algorithms]

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning.

156 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
332 views

Concurrent fault-safe data structure

I am building an application that aims to process ~10M data items per second. Each item is exactly 42 bytes small (including a sorting key) which means the total data rate will not be big 420 MB/s. ...
4
votes
0answers
1k views

Fast fixed-size (256 bit) integer modulo/division

What is the fastest way to divide two 256-bit integers? They are represented as an array of 26-bit words, each stored in 32-bit integers. I have access to a 64-bit type if that's useful. It seems ...
3
votes
3answers
454 views

Aggregation of data from two Microservices

I have two Microservices A and B. B Microservice has a large set of an entity called User. A Microservice stores the User entity in its own DB if User is configured by an agent. There is no flag ...
3
votes
0answers
127 views

Some “intent”-related questions vis-à-vis Operational Transformation and CRDTs

I’m a little unclear on some questions relating to the "intent" part of concurrent collaboration algorithms (operational transformation and conflict-free replicated data types). Please help! Strings ...
3
votes
0answers
658 views

Creating a better mouse dragger function

I originally posted this to code review, not knowing incomplete code was off-topic and was pointed to post here. I don't believe this question is a good fit for stack overflow because the code I ...
3
votes
0answers
345 views

Smallest number of rectangles covering marked parts of grid

I have an N by N grid of cells, and certain blocks are marked: +--+---+---+---+ | | | | | | | x | x | | | | x | x | | | | | | | | | | | x | +--+---+---+---+ I would like to ...
3
votes
0answers
200 views

Incorporating custom Algorithm in SOLR-LUCENE , before Indexing?

CURRENT FLOW: I am using a custom algorithm(presently in php) to rank the MYSQL records before INDEXING it to SOLR . WHAT I WANT : Is it possible implementing this ALGORITHM(may be in JAVA) inside ...
2
votes
1answer
116 views

Can Mean Shift Algorithm used in color quantization?

I have a problem with deciding algorithm for color quantization. The image that I want to do color quantization is an RGB image with resolution 512 x 512. I want to reduce the color value in the pixel ...
2
votes
2answers
147 views

Cumulative sum of overlapping increase/decrease over time

I am looking for an efficient way to handle a calculation. I have lots of timestamped events, representing loading and unloading of trucks. I need to construct the filling rate of these trucks over ...
2
votes
0answers
138 views

How do large scale permission systems work with membership expansion?

Let's say you have a permission system with which you can specify things like: user U is a member of group A, which is a subgroup of group B, which is a subgroup of group C, and all members of group C ...
2
votes
0answers
180 views

Weighted job scheduling algorithm to minimize load

I have a set of jobs that start by querying an external server for a payload. On receiving the payload, the internal server takes a variable amount of time to complete the job, hence the 'weight'. ...
2
votes
1answer
125 views

Spreading objects in bags and bags' compartments

We have 10 bags. Each bag has 5 compartments numbered from 1 to 5. We have 100 objects to fill all the compartments and bags. Compartment number x in a bag is identical to compartment of the same ...
2
votes
0answers
80 views

Direction-free optimal encoding

Consider an alphabet of k symbols and a requirement to optimally encode a series of values of known frequency. The obvious choice for this is to use Huffman coding, which is known to be optimal for ...
2
votes
0answers
71 views

What's the most practically efficient way to store differences in adjacent matrix values?

I am implementing a certain algorithm that works like this: Create a closed contour (list) of elements in a matrix, where closed means that the last element is adjacent (by row, column) to the first. ...
2
votes
0answers
129 views

Possible to find intersections between a line segment and a disjoint set in log2(n)?

Given a set S of disjoint 2D line segments, is there a way to pre-process S into a data structure that can check if a single arbitrary segment L intersects any segment in S in log2(n) time, as well as ...
2
votes
0answers
112 views

Sort numbers into three groups s.t. their sums are close to a certain value

I have a list of numbers (let's call it L) and I need to split this list into three groups (A, B, and C) such that the sum of the numbers in each group (sum(A), sum(B), sum(C)) is as close as possible ...
2
votes
0answers
131 views

String Pattern Matching from Lookup Table - Non-Exponential Solution?

Given the problem... Given a String comprising of non-alhpabetical symbols, and a Lookup Table where a subset of those symbols may equate to a single alphabetical character, output all possible ...
2
votes
1answer
111 views

Optimal Simplification of Transposition Products

I am looking to take a product of a large number of transpositions, and boil it down to a smaller number of products. I have the following code, and would like some input on efficient ways to boil ...
2
votes
0answers
63 views

Most efficient way of allocating participants to conference tracks

I am redesigning a system by which conference participants can choose which track they want to attend. Participants express their track preferences arranging them in order and submitting them at a ...
2
votes
0answers
44 views

How would I identify a gap in a set of curve data, and get its value?

I have a set of 2-D data (x,y) and it produces a set of curves, and sometimes the set of curves do not overlap, and there is a distinct separation between the groups of curves, how would I identify ...
2
votes
0answers
112 views

Polygon simplification that encloses original set of points

I have been trying to implement an optimization for 2D sprite rendering to fight the problem of limited fillrate on mobile devices. The idea is to render textured polygons instead of quads that will ...
2
votes
0answers
973 views

Find all paths in a tree type of structure

The language I am using is C#, but I am looking more for help with the algorithm more than I am concerned with which language. I have been trying to develop this algorithm for a while now and I can't ...
2
votes
0answers
585 views

Predicting package delivery schedules

I'm trying to solve the following problem: A delivery man has N packages to deliver, already sorted. He starts the route at start_time, he works until end_time. I have historical data of his delivery ...
2
votes
0answers
58 views

Project a piece of image cut by N-vertex shape to a different N-vertex shape

I have an N-vertex shape that I cut out from an image, and I want to project it onto another shape with the same amount of vertices, but different. So, the image will get changed inside the projection....
2
votes
0answers
133 views

Optimizing trigram look ups with wildcards

I am working on creating a spell-checking service for Android (note: this is a platform- and language-neutral question) for Asturian, a minority Romance language. We're using hunspell as the base but ...
2
votes
0answers
139 views

Asking questions to the user based on results of previous questions

I have to select a question that would help me make me sure the user knows about a given subject. As an example, let's assume the user hasn't answered any question yet. Every question has a scope (...
2
votes
0answers
309 views

What algorithm is this?

I have some vague recollections from my algorithms courses, but nothing specific comes to mind. let S be a multiset of things we are interested in. As input, we get T, s1, s2, ... sn, all of which ...
2
votes
0answers
177 views

Design an algorithm with network flow

Given a matrix A with 0 and 1 entries. Neighbours of a[i,j] are a[i-1,j], a[i+1,j], a[i,j-1] and a[i,j+1] (if exists any). Tow neigbour entries are an Improper pair if they have not equal values. if ...
2
votes
0answers
380 views

Walk Tree vs Zhang and Sasha Algorithms

I need some help understanding how two tree comparing algorithms differ. I am working with Microsoft's XmlDiffPatch (http://msdn.microsoft.com/en-us/library/aa302294.aspx) which compares two xmls. The ...
2
votes
0answers
2k views

How to find minimum weighted vertex cover of a tree, and confused about a solution

Studying for my algorithms test by spamming Algorithm Design Manual exercises, but I'm stuck on this one. I know I have to keep score somehow. Let G = (V,E) be a tree with arbitrary weights ...
2
votes
0answers
368 views

Colour curves tool for “value” channel

I'm trying to write a program to read GIMP curves files and apply them to an image. I have successfully implemented the curves for the red, green and blue channels, but I can't get it working for the ...
2
votes
0answers
344 views

Match buyers and sellers based on date ranges and quantity of shares

NOTE: This is in reference to the question I asked on Stack Overflow but was told to post this here I'm building a trading application that matches buyers/sellers that own subscription. Subscriptions ...
2
votes
0answers
343 views

Solving geometric constraints with Minion

I am doing research on squares, and I thought of using constraint-satisfaction-problems solvers for proving or disproving some conjectures. As a simple example problem, consider the following task: ...
2
votes
0answers
298 views

Generate complex (non-convex) polyhedron UV mapping

I need to find an approach to the problem of generating texture maps for non-convex polyhedrons without using a design tool like Maya. Specifically, I am mapping simulation results data onto a 3D ...
2
votes
1answer
252 views

Data Structure for “Intuitive” Text Matching

I've noticed that text editors and such have a more-than-prefix/suffix-based pattern matching algorithm going on behind the scenes. And StackOverflow's tag matching algorithm does more than just ...
2
votes
1answer
204 views

Programming conundrum - most efficient path

I have a non-language-specific problem which I'm having trouble finding a workable answer for. I have a 10x10 grid containing integer values from 1-10. Each value represents the cost of travelling ...
1
vote
0answers
33 views

What is the most efficient way to find filesystem changes in percentage?

I am planning to write a program that will produce digest logs for file changes in a particular directory. The idea is that whenever a file is deleted in a particular directory, it will show up in the ...
1
vote
0answers
37 views

What algorithm to count user click/read/turnover for a period of time?

We tried to develop a kinda-real-time statistics module to measure how hot/trend a content is. We know it is hard to achieve high end stuff like youtube/FB/twitter, our goal is simpler : Count click/...
1
vote
0answers
49 views

How to join two sets of 6 tables and select the list into another set of 6 tables

A1 |__A2 |__A3 |__A4 |__A5 B1 |__B2 |__B3 |__B4 |__B5 C1 |__C2 |__C3 |__C4 |__C5 Given a list of A and a list of B, we want to "join" ...
1
vote
0answers
112 views

tea bag flavors mixing algorithm

I bought three boxes of tea bags with different flavors (A, B, C). I wish to mix them in such a way that - there is never two consecutive bags of the same flavor (ABCCAB is avoided) ; - the mixing is ...
1
vote
0answers
40 views

Logfile correlation finder (for j4Log)

I'm currently analyzing a problem in a old "distributed" system, that only occurs sporadically - as the system does not support other means of debugging help I have to rely on the logs (I did not ...
1
vote
0answers
133 views

phonetic algorithms for words that aren't surnames?

I've been doing a little research into algorithms for matching spelling mistakes in names. From Soundex through to metaphone and Beider-Morse. All of these algorithms generally focus on last names ...
1
vote
0answers
57 views

Decision tree for storing subscription info

I have a system in which user creates an entity. Now this entity has attributes which are dependent on many external systems. We have all those pipelines in backend which updates these entities when ...
1
vote
0answers
29 views

Sorting a list of objects with re-ordering and different views

The problem I have is this: I have a list of items. Each item has multiple properties. I have a view where I display all items and I have a view where I display the items based on values in properties....
1
vote
0answers
55 views

Laying out all the relations in an n-dimensional array

I have two types of objects: M and N, identifiable by a name. Additionally, multiple Ms can be grouped into one or more M-Group (also identifiable by a name), same for Ns. (If it makes your life ...
1
vote
0answers
83 views

What algorithm / data structure for managing exclusion on a given set of feature options?

Imagine I have to manage products. Products have features , features maybe have free input option, or set of limited options, not all the probabilities will be available: options01/features01 * ...
1
vote
0answers
132 views

Algorithm to find region with least-probable density

Consider the following boolean array where dark == true: In this scenario the probability that a cell is dark or light is 50/50, but this may not be true for the general case. Maximizing only on ...
1
vote
0answers
307 views

Minimum cost perfect matching (Using General graph)

This is a continuation of the problem described in this topic: Optimized algorithm to match entities together based on heuristics. I've come a little closer as to what might be the best solution. I'...
1
vote
0answers
38 views

Check if a point is deviating from a path made by a set of line segments

I'd like to know or have other ideas --other than my solution-- about how to check if a car on a given position (lat, lng) is getting away (let's say a distance D away) from the path where the car ...
1
vote
0answers
229 views

Sorting Lower Bound in the Comparison Model (Nuts & Bolts Problem)

Problem: Assume that we are given n bolts and n nuts of different sizes, where each bolt exactly matches one nut. Our goal is to find the matching nut for each bolt. The nuts and bolts are too similar ...