Questions tagged [algorithms]
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 design and analysis of algorithms.
10,997
questions
1
vote
0
answers
10
views
Is there an elegant algorithm for applying multiple simultaneous search-and-replace operations to a string?
The operation I'm interested in is a slight twist on your standard search-and-replace operation, in that instead of a single pair of arguments (replaceme and ...
- 245
1
vote
0
answers
16
views
Finding the shortest path with Bellman-Ford [duplicate]
I feel this is a basic question but have been stuck at this for days. Consider an undirected graph with positive weights on its edges. The goal is to find is to get the shortest path between any two ...
- 257
0
votes
0
answers
8
views
How to calculate transition areas of biomes in an image
I'm generating biomes for my game and I would like to store them in a single RGB image like the one below. A color hue can then be mapped to an ID through a table lookup. The problem I face is that I ...
- 101
0
votes
0
answers
12
views
Creating a partial order from a total order with a concurrency oracle
My goal is to turn a strict total order of labeled elements into its strict partial order representation, given a concurrency oracle, that tells me, which pairs of labels are concurrent. Auto-...
- 121
0
votes
3
answers
32
views
How is a direct address table different from an array?
I found this from this PDF (https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture9.pdf)
- 159
0
votes
1
answer
52
views
Ackermann Decision Problem
I have been studying the Ackermann function, specifically the two-argument Ackermann–Péter version.
With the Ackermann function, I developed a problem I call the "Ackermann Decision Problem"
...
- 143
1
vote
1
answer
29
views
Placing K gas stations among n cities to minimize distance
There are $n$ cities on a highway with coordinates $x_1$
, . . . , $x_n$ and we aim to build $K < n$ gas stations
to cover these cities. Each gas station has to be built in one of the cities, and ...
1
vote
0
answers
39
views
Reconstructing a string from two its partitions into substrings of varying size
Given two unordered partitions of the same string over a finite alphabet into substrings, how hard is it to reconstruct the original string? If multiple solutions exist, any one will suffice.
Under an ...
- 151
0
votes
3
answers
60
views
Details of sqrt.c library source code
Have seen library code for finding square-root, using the Newton Raphson method.
It uses a table of 256 entries, whose significance is unclear, as the initial guess should be dependent on the quantity ...
- 155
0
votes
0
answers
19
views
How to generate all possible colour vectors generated by greedy colouring on a graph?
How to generate all possible color vectors that could be generated via greedy coloring.
- 292
0
votes
0
answers
27
views
Dividing a list of files with constraints
I don't know if a solution to this problem is too complicated to figure out, but I've been banging my head on it for a couple weeks, so I'm hoping for an outside point of view.
I have a list of 88 ...
- 101
2
votes
1
answer
28
views
Checking forbidden moves in Renju
I am trying to detect forbidden moves for black in a game called Renju. First, here is an explanation of how Renju works.
Renju is a board game played on a 15x15 Go board. There are two players in the ...
1
vote
0
answers
15
views
Identifying problem category of balancing resources in transport networks
The question is originally posted here https://or.stackexchange.com/questions/10140/identifying-problem-category-of-balancing-resources-in-transport-networks, but I wanted to post it on this stack ...
1
vote
1
answer
21
views
Writing an Algorithm to Represent a Bit Matrix in Minimal Operations?
I am trying to come up with an algorithm to find the minimal representation of the transformation from a zero matrix to a target matrix.
Specifically, I have an empty matrix and can perform operations ...
- 11
0
votes
0
answers
17
views
Recurrence relation for TSP using recursion
This is a Python algorithm using recursion to solve Travelling Salesman Problem, consider $G$ a complete graph:
...
- 101
2
votes
1
answer
46
views
Finding the Equation for Potential Method and Amortization Analysis
I am trying to figure out the solution to this problem:
In this problem we consider two stacks $A$ and $B$ manipulated using the
following operations ($n$ denotes the size of $A$ and $m$ the size of $...
- 23
2
votes
1
answer
30
views
Finding the smallest subset s.t. all elements satisfy condition, using as few tests as possible
I'm having a hard time describing this problem without an example, so let's go with this: Say you have a program that is made up of many files. There are some files you could delete, and, while it ...
- 21
1
vote
1
answer
32
views
The extent of NP-Completeness
I am told that if a decision problem that is in NP Complete can be solved in polynomial time, then P=NP. However, would this mean that we would instantly have an algorithm to solve any NP problem. ...
- 117
1
vote
0
answers
45
views
How to assign tasks to a set of machines, given that the more tasks you assign to a machine the slower they will run? Bin covering with merging bins?
Intro
I need to design an algorithm that will distribute a known set of tasks with a known RAM requirement to a known set of machines with known RAM capacities. The tasks require a certain amount of ...
- 111
0
votes
0
answers
21
views
proof that the longest processing time rule computes an optimal schedule
I want to prove that:
Theorem 2.8: For any input to the problem of minimizing the makespan on identical parallel machines for which the processing requirement of each job is more than one-third the ...
- 29
-1
votes
1
answer
33
views
Find $T(n)$ from $T(n^3)$
Consider
$$\begin{align} T(n^3)&=T((n-1)^3)+n\\
T(1)&=1
\end{align}$$
According to the substitution method, $T(n^3)=O(n^2)$ (please if I wrong, correct me). Now, what is the answer of $T(n)$? ...
- 1,556
0
votes
0
answers
59
views
Deletion of a node from a BST
Placed exactly the code and the explanation of the book : Introduction to Algorithms Third Edition
In order to move subtrees around within the binary search tree, we
define a subroutine TRANSPLANT, ...
- 111
1
vote
3
answers
40
views
Generate a set of X int numbers positive and negative that add up to target value
I want to generate a set of X int numbers, were 4 <= X <= 100, both positive and negative that add up to target value.
The numbers are between -6 and 4 and there needs to be at least 2 negative ...
1
vote
2
answers
39
views
The existence of solution of a multivariate polynomial
Given a multivariate polynomial of degree 4 on $v$ (real) variables such that there are $N$ terms in the polynomial. Is there an efficient algorithm to verify if it has a solution?
Not aware of any ...
- 35
1
vote
1
answer
32
views
Determine bijective mapping using minimal number of lookups in subset mapping - standard problem / perspectives?
This seems like it should be a "textbook"/standard problem but I wasn't able to find anything about it, so I'd like to know if anyone else has seen something like it before or can suggest ...
- 113
1
vote
1
answer
19
views
Route planning on line segments which can be connected or not
I have several lines that are shown in different colours, do not know which are connected to each other in advance. I want to do path planning only using these lines, i.e., route planning. If I am ...
- 111
-4
votes
0
answers
21
views
CCN BASE HEART DISEASE PREDICTION USING CARDIAC MRI IMAGES [closed]
AM using cardiac MRI Images to predict heart disease using convolutional neural network.i got confused how to go about it. pls help me.
- 1
1
vote
1
answer
19
views
Subquadratic multiplication of polynomials in the max-plus/tropical semiring
Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $(\mathbb{Z}\cup\{-\infty\}, \max, +)$ which is faster than the trivial one? I'm interested in the ...
- 13
27
votes
6
answers
5k
views
Is there a "Standard Algorithm" language, as used in academic papers?
In many academic papers algorithms are described. They seem to use similar "syntax".
Is there a standard for this language? If I want to describe an algorithm, would I improvise my ...
- 391
0
votes
1
answer
35
views
$m-$way merge sort, extended merge sort
Consider Merge-sort algorithm that we modify as follow:
Suppose we extend it to divide the input array into $m$ not necessary equal and after sorting each of them, merge them. Now can we conclude that ...
- 1,556
0
votes
0
answers
20
views
If the data that I input for locality sensitive hashing is sensitive, should its resulting hash also be considered sensitive?
Is it correct to assume that if the input that I hash is sensitive, that I should also consider the locality-sensitive hash generated for that input to be sensitive? I presume that, if an attacker has ...
- 121
0
votes
0
answers
49
views
Degree of a vertex
We have an undirected graph $G = (V,E)$ and let $|V| = n$.
Suppose edges of a graph are coming in a stream and the clustering is done in the following way. Here $N(u)$ denotes the neighborhood of ...
- 43
1
vote
4
answers
108
views
Prove optimality of greedy strategy for fewest number of stops
Here is the problem. Suppose you have to drive from Eindhoven to the south of France. Your start and destination are fixed and the route is fixed as well. You start with a full petrol tank, but since ...
- 17
0
votes
0
answers
58
views
Compute the schedule which gives the maximum number of points
Here is the problem statement. Let $E_1,...,E_n$ be a set of $n$ exercises, each taking 1 day to solve, and suppose we have $n$ days available to solve the exercises. Each exercise $E_i$ has a ...
- 17
2
votes
1
answer
48
views
Why is this proof that CHESS is in EXPTIME correct?
I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by ...
- 23
0
votes
0
answers
38
views
What is Triangular bottom database?
For algorithm design course, the teacher gave a question, but i don't understand it at all, specially the triangular bottom database which i searched about it but couldn't find any result. However the ...
- 111
0
votes
1
answer
30
views
Trying to understand the time complexity of IDDFS
I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out.
For BFS it is ...
- 1
0
votes
1
answer
31
views
Is there an algorithm to test for an acyclic undirected graph, using edge data, not node data (e.g. adjacency matrix)
Given an adjacency matrix or other data based on the nodes, there are many algorithms for determining whether the graph is acyclic (e.g. row reduction or leaf trimming).
If I have only a set of edges (...
- 257
1
vote
1
answer
49
views
Given required total area and capacity, choose an amount for each of three given modules
Suppose you have three modules $m_1,m_2$ and $m_3$, each with a capacity of $c_i$ and area $a_i$. You are also given $A$ and $C$. How can you find some of the solutions to choose an amount of each ...
- 11
1
vote
2
answers
66
views
$n$ students want to exchange books among themselves
This is a problem from my Algorithms course in uni
There are $n$ students, each have a single book. They come into a party to exchange books among themselves. Each have a list of students that have ...
- 33
0
votes
1
answer
47
views
How to avoid costly square root operations in A* algorithm?
As a reminder, in an A* algorithm, vertices in the priority queue are sorted according to their priority $f = g + h$, where $g$ is the cost of getting to this vertex from the start vertex, and $h$ is ...
- 665
0
votes
1
answer
30
views
Memory allocation algorithm over a growing storage
I am going to story data in a growable persistent storage. I need to implement allocation/deallocation (like malloc/free and possibly realloc but in Rust) of continuous regions of memory on this ...
- 413
3
votes
1
answer
86
views
Find the largest caterpillar subtree
I have a problem to solve, but I am having some issues with it...
Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
- 31
0
votes
2
answers
68
views
Why is there no polynomial time verifier for N Queens
The N-Queens in question is referring to the one where it is interested in finding all solutions for some natural number n. I just read about the idea of a verifier being an algorithm that verifies ...
3
votes
2
answers
77
views
Race condition, my doubt on Peterson's algorithm vs. C
I have seen this C code showing an implentation of Peterson's Critical Section algorithm. It is obviously skeletal and hardwired for two threads but the logic is supposed to be correct in detail.
...
- 133
0
votes
1
answer
52
views
NP-hardness of particular problem
Suppose given two sets $\{a_1,a_2,\dots,a_n\},\{b_1,b_2,\dots,b_n\}$ of positive real numbers.
We try to find a subset $I\subseteq\{1,2,3\dots,n\}$ such that:
$\sum_{i\in I}b_i$ maximized and $\sum_{i\...
- 1,556
1
vote
1
answer
23
views
Partition an array in two groups while keeping the relative order within groups
I came across the following problem in the book "Elements of Programming Interviews in Python".
Given an array A of n objects with Boolean-valued keys, reorder the array so that objects ...
- 111
0
votes
0
answers
39
views
Application of a formal definition of $max, min$ to evaluate an expression
For an Algorithms course we are studying propositional calculus. As an excercise we are given formal statements which we are to explain in natural language first and then evaluate with specific values....
- 111
0
votes
0
answers
29
views
Creating a PRNG to replicate the LIbrary of Babel
I had asked a question here about this before but it had a lot of vagueness to it, so I'll rephrase the entire thing.
I'm trying to create a PRNG that would replicate Borge's Library of Babel, i.e. ...
1
vote
1
answer
51
views
How to schedule ELO-based, fair games with n players and dynamic teams?
The setting is the following: There are n players that want to compete in a specific game over the course of an event. A game is played between 2 teams of 2 players each (so a 2v2). Each player as a ...
- 13