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.
2,140
questions
0
votes
0answers
36 views
Implementing something similar to the logic of a cascading style sheet engine
I am trying to implement something similar to the logic of CSS: a set of rules define which attributes every objects should have based on the state of the object and its ancestors.
After spending ...
0
votes
2answers
88 views
Finding similar objects in a large data set
I have a large collection of (C#) objects and these objects have a large number of properties, mostly strings and numbers. This collection is stored in a database. When a new object is about to be ...
0
votes
3answers
148 views
How to deal with forward references in a compiler?
I'm creating a very simple compiler PoC that only has
Procedures
Calls to procedures.
The syntax of the language is really simple:
Main
{
Call("Proc1");
}
Proc1
{
// Empty
}
I ...
7
votes
2answers
445 views
Why are sort() and reverse() JavaScript methods in-place?
Which are the technical reasons/considerations for the sort() and reverse() JavaScript array methods to be in-place operations instead of returning a new array without modifying the original one, like ...
2
votes
1answer
216 views
Multiple if condition optimization
Often I find conditional statements such as:
if (life_max < max):
if (expand):
do life_max = max
else:
if (life_max > max) and not (expand):
do life_max = max;
Although readable, ...
2
votes
2answers
1k views
How can the size of a heap be less than its length?
I am studying the heap sort algorithm from the book Introduction to Algorithms by Thomas H. Corman. It differentiates between the length of the array, A.length, as
"the number of elements in the ...
2
votes
2answers
131 views
Is there a simple algorithm for generating unit tests given a function's code? [closed]
Given the abstract syntax tree (AST) of each line of a function's code, I am asked to generate code for that function's corresponding unit tests, similar to what Microsoft's IntelliTest tool does here:...
3
votes
1answer
203 views
What is the most suitable data structure for IPv4 addresses with intersecting ranges?
Mostly in all routers and operating systems the Longest Prefix Match algorithm is used for searching the trie of IPv4 addresses.
Packet filters like Iptables don't need some special data structure for ...
0
votes
0answers
36 views
Strategies for updating a database with multiple inserts and updates
I have experienced the issue of updating a database considering multiple sources a few times, each time I wonder if there isn't a better way of doing so.
Brief example:
An application needs to keep ...
-5
votes
3answers
452 views
Does H correctly decide that P (source-code provided) never halts?
Does H correctly decide that P stops running?
(The C/x86 source-code for P is provided below)
Halting problem undecidability and infinitely nested simulation
The x86utm operating system was created so ...
2
votes
2answers
84 views
Optimal sequence of recipes
I assume the following is/reduces to a known problem, but I haven't been able to find it.
I have a sequence of recipes with associated costs. Each recipe converts a set of resources to another set of ...
0
votes
1answer
87 views
Counting primitive operations on recursive functions
I'm reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given ...
1
vote
1answer
122 views
Algorithm to find efficient swaps between nodes
I have the following problem:
There is an amount of nodes each containing elements of different kinds. Each node has a max amount of elements it can hold. I want to sort the elements between the nodes ...
-1
votes
1answer
83 views
How would I detect a physical attack in video form? [closed]
I hope this question isn't too vague because it's more a discussion than a question. I want to write a code which can detect physical violence in a scene (with the end result being the prediction of ...
1
vote
4answers
115 views
How to find all combinations of all items in a set? [closed]
Let's say, there's a Product data-model. Product has the attribute - colour, which can, in this case, be red, black, yellow, white, orange. And which in total amounts to 5 different Products.
Now I ...
-1
votes
1answer
58 views
search message in a conversation like messenger
I want to implement a search feature in my chat application like a messenger, skype, whatsapp has done. What they have done is when we search a word then it would not only show the message with that ...
0
votes
1answer
69 views
Understand implementation of exponential moving average (in case of unix load average)
The UNIX load average gives 3 numbers over 1/5/15 minute time intervals. It's supposed to be an indicator of how busy a UNIX machine is. The global load average is an exponentially decaying average of ...
-1
votes
1answer
191 views
Binary search is not fast
I am trying to put in practice an algorithm for binary searching and compare it with linear searching:
linear search:
public static int linearSearch(ArrayList<Book> books, int searchedId) {
...
-3
votes
3answers
182 views
Find the longest sequence of words where first 2 letters of a word are same as last 2 letters of previous word, sequence ends if word ends with "xx"
This is example of the problem (sequence ends if last 2 letters are "te")
lasagna nato top operation online nervous usable levitate -> end word ended with "te"
There are around &...
4
votes
5answers
326 views
How can you ensure order of execution in concurrent tasks?
Here is what I am specifically doing:
I have a thread-safe queue
One 'write' thread constantly writes to the queue with data that comes from another service
Multiple 'read' threads take from the ...
0
votes
0answers
98 views
Calculating time complexity of a code snippet
I am trying to calculate the time complexity of the below code snippet
def func()
{
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j=j+i)
{
print("hello")
}
}...
1
vote
1answer
130 views
Full, 2-way table synchronization
I need to synchronize tables of data between two different systems. This is a multi-master setup; data can get changed in either system. After a synchronization runs I'd like the data in each table to ...
1
vote
1answer
55 views
Minimize volume of cylinder that covers a clusters, with constraints
A few hours ago I turned in my entrance exam, and i am very curious about this last problem.
Given a cluster of stars each x, y, z range between -1000 to 1000. No four stars are coplanar.
Find the ...
-4
votes
1answer
59 views
Calculate math function depend on N value [closed]
I have method with the following prototype :
R[] = method(k,n)
which :
n = ordinal value 0 <n <10^9
k = math function depend on n value : i.e n^6
R = array of computed values
For example :
n = ...
11
votes
5answers
3k views
Pros and cons of representing routes as legs or stops?
What are some pros and cons of representing routes as legs or as stops?
A leg is a departure and arrival location, a departure time and a duration (or an arrival time and a duration).
A stop is an ...
0
votes
1answer
296 views
What's an edge case in email validation, and algorithms?
An edge case is usually defined as what Wikipedia would say,
An edge case is a problem or situation that occurs only at an extreme (maximum or minimum) operating parameter. For example, a stereo ...
-3
votes
2answers
80 views
What design pattern / class / interface should I use for encapsulating a program? [closed]
I am building a chess - related application, and I want to use a pre-compiled program called Stockfish as my chess engine. I am wondering what is the best practice to encapsulate the usage of the ...
0
votes
2answers
308 views
Possible trajectories with time travel
I'm trying to calculate a trajectory in the presence of time travel.
In the following picture, there is a character traveling toward the right in a straight line (like a billiard ball). If the ...
7
votes
5answers
385 views
How to implement a dirty flag on a complex object hierarchy?
I've got an object with a complex hierarchy, something like:
Document
Paragraphs
Paragraph
Words
Word
and I need to implement a dirty flag on the Document object. In general, ...
1
vote
1answer
183 views
How does the GLL parsing algorithm work?
I'm very interested in the topic of parsers, especially in the topic of parser combinators like Superpower. The problem with them is that the grammars that they can work with are a bit limited. For ...
2
votes
2answers
123 views
Clean algorithm for generating Scrabble tile sequences
I am trying to come up with an algorithm that generates every possible combination of Scrabble tile sequence on a player’s rack. I want the sequence to be comprised of n number of indices depending on ...
1
vote
2answers
181 views
Efficient set method in run length encoded C++ map
I have been designing a C++ class that maps an integer to an integer using a vector. Because there is a lot of repetitive data (for example 11115555666222), I am using a compression scheme where I am ...
-3
votes
1answer
59 views
Why sort the points acc to y coordinates in closest point divide and conquer method?
The divide and conquer strategy for closest point problem sorts the points according to x coordinates so that the median could be found. But what does sorting the strip (strip array contains all the ...
1
vote
4answers
203 views
Software-design for algorithm engineering
I'm currently working on an program that solves a graph optimization problem.
I know the "standard" software-design principles like information hiding, modularization, etc. What I'm ...
39
votes
10answers
9k views
Difference between Algorithm and Code
A few days ago I had a conversation with a Civil Engineer with a background in Pascal and BASIC, and we talked about programming in Python. When I was talking, I used the term "code" to ...
2
votes
3answers
117 views
Efficient way to detect duplicates in a stream of up to 20M numeric strings
I have a stream of documents, each having an ID which is a 64 bit unsigned long given as a (maximum length is 20) string.
Sometimes an ID appears multiple times in the stream. I don't want to process ...
-1
votes
1answer
146 views
What kind of bin packing problem is this?
I have a problem formulation but it does not resemble the usual packing problem I find in the literature but it is a usual problem in the packing industry. I just do not know the name for it.
The ...
-1
votes
2answers
96 views
1D coordinate to 2D coordinates without defining a stride
I'm in a situation that basically boils down to storing values based on 2 ID's. The ID's are sparse, from different ID pools and pretty much unpredictable so the naive approach is to just store the ...
0
votes
0answers
121 views
Is it possible to run an Excel macro-powered file on a server?
I've an Excel file (offline, on my computer) that elaborates medium-large amount of data using VBA Macros. Basically, this Excel macro-powered file works with a person that adds the data to an Excel ...
0
votes
1answer
87 views
How should I apply dynamic programming on the following problem
I have an array of events where events[i] = [startDay_i, endDay_i, value_i]. The ith event starts at startDay_i and ends at endDay_i, Attending the ith event, I will receive value_i. Also given an ...
0
votes
2answers
132 views
Drawing all lines from right to left - fast
I have several drawings from SVG files which basically contain basic outlines of figures. They are constructed in segments of various shapes (lines, ellipse arcs, Bezier curves ect.) Something like ...
-4
votes
1answer
62 views
How to write a sporadic metronome?
I already asked this question on stackoverflow -- I am posting it here as well, because I think many of you will have encountered an analogous problem. I would appreciate even a link as a reference, ...
2
votes
2answers
175 views
How to use chebyshev polynomials to calculate exponents (antilogs)?
I am trying to write an algorithm to accurately calculate exponents (antilogs) for a variable precision floating point library I am working on. The base is not relevant since I can convert between ...
6
votes
2answers
602 views
some misunderstanding in concept of Huffman algorithm
What is difference between Average length of codes and Average length of codewords in Huffman Algorithm? is both the same meaning? I get stuck in some facts:
I see a fact that marked as False:
for a ...
1
vote
2answers
145 views
(Algorithm) Maximum Binary String After Making Changes
I am given a binary string binary consisting of only 0's or 1's. There are two allowed operations (can be re-used any number of times):
Operation 1: If the number contains the substring "00",...
1
vote
3answers
121 views
Algorithm – Number of strings containing every string of a given set a strings
I have a given set S of strings, and a length l, and I am looking for the number of strings of length l that contains every string of S. A naive approach would be to generate every string of length l (...
1
vote
0answers
82 views
What algorithm can I use to spread a workload between two processor with fixed resources?
I need to write an algorithm to allocate x number of tasks to 2 processors per day.
I know the following:
Exact amount of time it will take to complete each task
The exact amount of time available ...
0
votes
0answers
25 views
Forecasting future batch sizes to balance throughput capacity?
I've a data streaming platform (Nifi) where I need to transfer tables of data between databases on given schedules. I want to be able to calculate in advance the optimum batch/schedule size i should ...
5
votes
4answers
347 views
Processing a 2D matrix - need to speed up my O(n^4) algorithm
I have an n x n matrix which I need to convert into a list sorted by value. Starting with the maximum value cell at (row x1, col y1), I must immediately exclude all cells where (x >= x1, y <= y1)...
1
vote
2answers
114 views
Does a microcontroller provide better accuracy for comparing algorithms' run-times?
I have a set of algorithms to choose from based on their execution speed. I know that it is very hard to get an accurate measurement due to the process scheduling, the time that is actually consumed ...
