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.
-1
votes
0answers
34 views
Development of algorithm for matrix multiplication
Multiplication of n*n matrix takes order of n^3 with the standard multiplication algorithm. We can improve the time component of matrix multiplication to order of n^w where w= log(7)/log(2).
Using ...
3
votes
1answer
38 views
Data structure for determining intersection between line and polygon in 3D
I have a collection of non-self-overlapping simple polygons P. In actuality, they are 2D triangles in 3D-space.
I'm looking for a data structure which, given a line L, has a relatively fast lookup ...
2
votes
1answer
45 views
Matrix multiplication range queries
I have a huge list of matrix i.e A = {M0, M1, M2 .. Mn}.
I have a task to find the product of all the matrices in a given range {x,y} i.e Mx * Mx+1 * Mx+2 ... * My.
I would like to know if there is ...
1
vote
0answers
16 views
Create unique buckets for stream of entities based on constraints on the entity attributes
I have stream (magnitude 10s of millions) of entities, say Item which is modeled as below:
class Item {
String id;
Double price;
Double profitPercentage;
Country originCountry;
Country ...
1
vote
1answer
142 views
Complexity of recursive calls
my brain is a little stuck as I am trying to compile an example for my blog. I am presenting an algorithm that draws a number from an array, adds it to a sum and calls itself recursively.
func ...
-2
votes
0answers
22 views
How to find the algorithmic complexity of this program? [duplicate]
I have the following program which finds out all the prime factors of a given number.
Algorithm:
Divide by 2 until the number is odd, for each successful division add 2 to list of prime factors. ...
0
votes
2answers
135 views
Check if list has a list of values
I have been trying to figure out an efficient algorithm that can check if a list of values contains a list of values. Both lists are sorted in ascending order.
For example:
Check if
var ...
0
votes
1answer
35 views
Mapping match-up combinations into an integer
First of all, I want to say I wasn't sure if I should post this here or in math.stackexchange but I think the question is too programming-related to belong to the latter community. Definetly not a SO ...
-1
votes
1answer
67 views
Find largest subset where two elements share a property
I have a set of numbers S and I want to find the largest subset S' such that for any two elements x,y in S' property(x, y) == True in_relation(x,y) == True.
How could I find it? Bruteforcing is an ...
1
vote
1answer
28 views
Why use last column of Burrows-Wheeler-Transform
The Burrows-Wheeler-Transform takes a string with length n, creates a matrix with n rows by shifting this string one position to the left for each row. Then the rows are sorted by the first column in ...
0
votes
0answers
45 views
How to solve min cost max flow program with brute force
I have a use case where I need to solve min cost max flow problem for nodes < 5.
Implementing Cycle canceling or some other min cost max flow problem seems like a over kill for this, is there some ...
-1
votes
0answers
86 views
How to solve water-jug problem using Extended-Euclidean algorithm? [closed]
Problem:
Given two vessels,
one of which can accommodate a liters of water
the other - b liters of water,
determine the minimum number of steps required to obtain exactly c liters of water in one ...
-2
votes
0answers
38 views
Minimal merge array algorithm problem? [closed]
Given an array of integers (can be negative) you can do only one operation on it: "merge" two elements, which is replacing two neighbouring elements of the array by the sum of them. Find lowest number ...
-1
votes
0answers
43 views
How to calculate number of bipartite graphs on n vertices [closed]
You are given a number N.
Your task is to find the number of Bipartite Graphs on N vertices. It is possible that the number can be calculated using recurrent formula.
The algorithm should ...
1
vote
1answer
111 views
How to implement k-means algorithm on RGB Images?
I want to apply the k-means algorithm on an RGB image data-set. I don't know how to proceed. You can mention basic step by step flow to proceed. I do know basics of Image Processing & OpenCV.
-1
votes
0answers
39 views
Unbounded knapsack with range of size
I am trying to write a program to find all combinations (allowing repetitions) of items from a set of items which will fit the knapsack.
Here are the constraints :
Capacity of the knapsack is not ...
2
votes
0answers
43 views
Are there any generic algorithims or Python functions to help find the longest item in a JSON document?
I am trying to log a JSON error message to Google's Cloud Logging platform. Unfortunately, the maximum size message you can log is 8000 bytes and some of the JSON documents I want to log are larger ...
0
votes
1answer
104 views
One font OCR for meme images
I'm coding an Optical Character Recognition specifically for the Internet meme images. This is a school project and it should be coded in C.
I'm currently having trouble with the method/algorithms I ...
-2
votes
0answers
50 views
Sum of squares of distances on a weighted graph O(n)
Given a weighted tree with n nodes. We have to find for each node sum of squares of distances towards every other node. Complexity should be O(n).
I am looking for an algorithm to solve the problem. ...
1
vote
2answers
54 views
How to represent complex permissions system in single hash or set of characters?
Eve Online, a game I used to play, had an interesting "permissions" system for account interactions with other apps.
The permissions encompassed dozens of individual permissions, each under a ...
-2
votes
1answer
73 views
Unable to Solve Dynamic Programming
I had an assignment on dynamic programming due last night, but I had to turn it in unfinished because i could not understand how to solve the last problem:
The state wants to monitor traffic on a ...
1
vote
0answers
105 views
Which 3D algorithms does Windows 10's “3D Builder” application use?
Windows 10 ships with "3D Builder", a Universal App that contains utility functions to prepare STL, OBJ, 3DS, and other files that represent geometries for 3D printing.
The utility looks like this:
...
1
vote
1answer
123 views
Best two-way compression algorithm for 32-bit numbers
I need to compress an id for marketing campaigns. The current campaign id is 32-bit integer but obviously this is too long for a customer to type by hand. I would like to compress this to minimum ...
1
vote
3answers
125 views
How do I generate multiple hashes that can be resolved to a single value?
I need multiple "random" URLs that just mask the original URL, i.e.:
/ABC
/CBA
/CAB
All resolve to /6
I came up with matching a letter to a number and then you can sum them to the single value.
A ...
1
vote
1answer
72 views
tiling algorithm for maximum size of equal-sized tiles
I'm trying to fit an arbitrary number of HD videos on screen so that they all have equal size, maximizing the size of the videos, with no scrollbars appearing.
Given N number of tiles of equal ...
5
votes
1answer
100 views
Algorithm to find span intersections in a sorted set
I have a set of items strictly ordered on time. Each item can either be single (no Next, no Previous) or part of a span (with either 1 or 2 further endpoints). For example in the picture A is part ...
24
votes
5answers
2k views
Is there any good search algorithm for a single character?
I know several basic string-matching algorithms such as KMP or Boyer-Moore, but all of those analyze the pattern before searching.However, if one has a single character, there is not much to analyze.
...
-2
votes
1answer
146 views
How to find complexity of T(n) = 8T(n/2)+n^2.93(log n)^93?
I believe we have to use a variant of master theorem...can someone suggest me how to find complexity of such equation which doesn't directly fit into Masters theorem.
0
votes
1answer
37 views
Partition edges into areas
If I have a series of edges that branch and curve, such as in a road network, is there an algorithm that will identify the areas (defined by sequence of geographic points) defined between those lines?
...
3
votes
1answer
104 views
Dynamic Programming - Largest arrangement of bookcases
I'm trying to solve a problem, so I'm not looking for code, but for similar algorithms so I can solve it myself.
I am given n bookcases each with a size amount of books inside. I am to move some of ...
0
votes
0answers
57 views
How do I determine the image direction [closed]
if I have two pictures, say A and B respectively, A was taken at time t1 and after that the camera was moved slightly to the left and then B was taken at time t2.
Is there any algorithm that I can ...
5
votes
0answers
61 views
Algorithm to generate all sets of m points in n x n x n cubic lattice which are unique under symmetry
I am implementing an algorithm which is going to be quite computationally complex, and want to try to make sure I'm not doing unnecessary work.
There is an n x n x n cubic lattice, e.g. if n=2 this ...
-4
votes
0answers
37 views
Surface-fit algorithm for logarithmic function with 2 independent variables
In my application I need to find the best-fit surface for a sample of data points with n ranging from dozens to a few hundred. The function that I need to fit is:
f(x,y) = C0 - 20log( sqrt[(C1 - x)2 ...
2
votes
2answers
125 views
Design for autocompleting words in search engine?
I'm trying to implement an autocomplete feature for a search engine. I have a database of words(stemmed) that occur in the documents that I have for users to search.
What I am thinking of doing is:
...
1
vote
2answers
103 views
Algorithm for finding all empty tiles in rectangular grid?
I have a rectangular grid of square tiles, some of which are blocked/filled. I start at a random tile inside the grid with the blocked tiles, randomly placed. I can turn in 90° steps and check whether ...
2
votes
0answers
49 views
Restricted randomization of a binary vector
Suppose I have a binary vector of sample size N with each of the two possible values (e.g., 0 and 1 occurring equally often).
For example, if N=10, the binary vector is: 0 0 0 0 0 1 1 1 1 1
Suppose ...
1
vote
1answer
45 views
Keeping track of the number of nodes in the subtree in black and red trees
I was wondering, if I have a black and red tree and I want to keep track of the number of nodes in the subtree, what is the most effective way to do so?
I mean how do I work with these values while ...
7
votes
1answer
148 views
Finding all possible ways of inserting a pattern into a string
I've been thinking about this problem for a while, and I can only find a recursive solution but I'm feeling that there is a dynamic programming way to do it, I just can't figure it out. Is this a ...
3
votes
2answers
146 views
How to match up courses with requirements
I have a list of courses taken by a student, as well as several requirements. Each requirement consists of a list of courses that fulfill that requirement and the number of such courses that must be ...
1
vote
0answers
41 views
List all intervals made by inherited array of intervals
i have a grading system which works like this:
You have a array of intervals with grades:
[9, Inf) => A; [7, 9) => B; ... (-Inf, 1) => F
But you can create also inherited grading system ...
3
votes
1answer
151 views
Neighbourhood points (2d)
I have a 2d coordinates system with some points on it, like this one:
Now I am looking for an algorithm (or just some approach) to find neighboured points.
So, if you have the coordinates of one ...
1
vote
1answer
71 views
Determine what to draw based on neighbour tiles?
I have a tilemap and I want to add walls to it. I painted 16 images, one for each possible combination. For example:
A lone wall tile would get a image that has walls around.
A corner would get ...
0
votes
0answers
69 views
Extract significant locations from GPS readings
I'm writing an app that continuously monitors user location 24 hours a day using a mobile phone with readings every 5-30 mins (about 50-300 readings a day).
How do I cluster readings and extract user ...
3
votes
1answer
125 views
How to find the closest vector to a given vector?
Let's say I have several points / vectors (in 2D to keep it simple, but could be of any dimension)
[x1, y1]
[x2, y2]
[x3, y3]
....
[xn, yn]
If I pick some point [x', y'], how do I ...
2
votes
2answers
101 views
Generate pips on a die based on value
Is there an algorithm to generate the pips on a die or domino?
I know that there is usually an odd number of columns and even number of rows (unless the max number of pips is not a perfect root).
...
4
votes
2answers
486 views
Why do textbooks use pseudocode rather than real languages?
In colleges and in algorithm textbooks, it is quite common for the teacher and author to explain control flow in pseudo-code. With the advent of more expressive languages like Python and Haskell among ...
1
vote
2answers
117 views
Algorithm to detect if a list of strings need delimiters
I need to write a function to detect if a set of strings needs delimiters when concatenated in any order.
For example, the strings ("A","B","C") do not need a delimiter: "ABCBB" -> ...
1
vote
1answer
43 views
Patching data by identifying and copying repeating pattern
I have a dataset sampled with a specific pattern (timestamps). The very first repetition of the pattern is damaged, meaning that the values are nonsense.
To exemplify, my data looks like this:
data = ...
1
vote
1answer
29 views
Sorting algorithm for Provides/DependsOn objects
I have a set of type rewriters, each modifies a given C# type in a different way. Examples are:
Add the XYZ attribute to each property of the class
Add an ID property
Add two properties and some ...
2
votes
2answers
185 views
Merge sort and O(n log n) mystery
I read every explanation here but still not convinced. I think mergesort is n * n and I know I am wrong but not sure where. Here is what I think:
Suppose we are sorting 8 elements and this is the ...
