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.

Filter by
Sorted by
Tagged with
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 ...
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)
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 ...
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.
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 ...
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 $...
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 ...
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. ...
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)$? ...
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 ...
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 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 (...
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 ...
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 ...
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 ...
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 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

1
2 3 4 5
220