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,988
questions
0
votes
1
answer
29
views
turing machine to add each number with the one next to it
im trying to make a turing machine that adds a number with the one next to it on the right. and after, it replaces that number with the result of the addition.
for example if input is 1012, 1+0=1 (...
- 1
1
vote
3
answers
94
views
Problems Solvable in Poly time but not verifiable in Poly time
I was just wondering if there exists problems that are solvable in polynomial time (a correct solution can be found in polynomial time) but not verifiable in polynomial time. My professor says no, but ...
1
vote
2
answers
52
views
Distinct edge weight assumption in MST algorithms
My lecture notes for minimum spanning trees say that:
A graph can have several minimum spanning trees but if the edge weights are distinct then the minimum spanning tree is unique. Without loss of ...
- 391
-1
votes
1
answer
77
views
Finding All Anagrams in a String
Problem: find all anagrams in a string such that one substring can be formed from another substring by rearranging its letters. Given a string $s$, find the number of pairs of substrings of the string ...
- 481
1
vote
1
answer
37
views
Is there a sub-NP algorithm to satisfy or prove unsatisfiable a set of a<b<c OR c<b<a constraints
This problem's been stumping me for the better part of a week:
You're given a set of triplets of variables. The variables are all distinct and ordered. Each triplet $a,b,c$ means that either $a<b&...
- 280
1
vote
1
answer
22
views
How to generate spatial scale-free nwtworks?
I want to generate spatial scale-free networks for my project. Are there any python libraries that enable it?
I read about the BA model (https://www.science.org/doi/pdf/10.1126/science.286.5439.509) ...
- 13
4
votes
2
answers
986
views
Does T(n) = 2 · T(2n) + n apply to Master method?
I'm trying to apply the master method to the following recurrence:
$$T(n) = 2 \cdot T(2n)+n.$$
We have $a=2$ and $b=1/2$.
Also,
$f(n)=n$
and
$n^{\log_b a} = n^{\log_{1/2} 2} = n^{-1}$ since $\log_{1/2}...
- 99
0
votes
0
answers
36
views
Can I find the smallest vertex cover
so this is my question:-
If I manage to find a vertex cover which has ....let's say 100 more vertex than the minimum vertex cover. Can I find the minimum vertex cover in polynomial time from this ...
0
votes
0
answers
22
views
Analyzing Parallel Matching Algorithm - Why it takes O(n+m) time and work?
Using the algorithm provided by this paper, they said that:
The algorithm defines a single phase of the local max algorithm. Each step of the phase takes at most O(log(m + n)) = O(logn) time and O(n +...
0
votes
0
answers
12
views
How do I implement x2 and ÷2 in Digital, and what does this exactly mean in terms of circuits? This question is for the arithmetic unit
So the first picture is an example arithmetic unit I have to implement using Digital.
The second picture is all the work I have done, however I am stuck on the meaning and implementation of x2 and ÷2.
...
- 103
1
vote
0
answers
14
views
DC3/Skew Suffix Array Algorithm doesn't work for specific cases
When applying the DC3/Skew algorithm to the string yabadabado, I can't quite get it to sort correctly. This issue happens in other cases, but this is a short example to show it.
This first table is ...
- 111
0
votes
0
answers
40
views
Minimum Heap - Add k to all left keys and heapify efficiently
I've been trying to solve this problem:
Given a minimum heap $H$, which contains $n$ elements, where each of its keys contain natural numbers, as well as $k\in\mathbb{N}$.
Add the value $k$ to each ...
- 113
0
votes
0
answers
10
views
Worst case circuit size of a high level program/algorithm
Please be patient as I am revisiting some fundamentals which might be obvious for most of you but I have some doubts:
A Turing Machine is a mathematical model of computation that operates on an ...
- 35
0
votes
0
answers
30
views
Proof that Path with admissible edges is shortest
Consider an unweighted and directed graph G(V, E). Suppose, for every vertex v ∈ V we assign a vertex label y(v).
We say that the vertex labeling is valid if for every edge (u, v) ∈ E that is directed ...
0
votes
1
answer
37
views
Given a list of pairs (cost,points) and a number k, find the maximum sum of points with sum of costs less than or equal to k
Given a list of $n$ pairs (cost,points) and number $k$ ($0 \le k$), find the maximum possible sum of points s.t their sum of costs no more than $k$. return the maximum possible sum of points and their ...
- 228
0
votes
0
answers
40
views
algorithm that determines if there are $a_1+a_2+\dots a_{k-1} =a_k $
Let $A_1,A_2 \dots A_k $ be sets of integers such that $\left|A_{1}\right|+\left|A_{2}\right|+\dots\left|A_{k}\right|=\mathcal{O}\left(n\right) $
Find an algorithm that determines if there are $a_1+...
- 212
1
vote
1
answer
30
views
Finding all zero sums of length m and checking for zero subsums on an abelian group (generalization of the sub sum problem?)
Let $G$ be an abelian group. We say that $G$ has property $V_n$ if for every $m > n$ and a list $L\subset G$ of $m$ elements s.t. $\sum_{g\in L}g=0$ there is a proper subset $\emptyset\neq L'\...
0
votes
0
answers
20
views
How does parallel marching algorithm work?
For the following graph and graph representation:
V set: An array of n elements, where each entry V[i] = Pj<i deg(vj).
A set: An adjacency array representation of a graph, where entries A[V[i]] ...
- 1
1
vote
2
answers
59
views
Shortest path algorithm on graphs with non-numerical weights
TL;DR: Floyd-Warshall algorithm seems to also accept "is-a" and "has-a" relationships as edge weights. I want to know exactly why this is fine, and how to generalize this notion of ...
2
votes
1
answer
40
views
Searching an algorithm to generate Tectonic/Seguru puzzle
I'm trying to write a program that generates a Tectonic/Seguru puzzle, and I'm struggling to find an algorithm that can generate them
The rules of the puzzle are here, but basically, it involves a ...
- 21
1
vote
1
answer
92
views
Finding minimal moves to move boxes into m floors
Assume a tower with $n$ floors.
Each floor contains $C_i$ boxes such that $C_i>0$ for all $1\le i\le n $
Moving $C_i$ boxes from floor $i$ to floor $j$ where $i>j$ costs $C_i\cdot(i-j)$ and we ...
- 212
-2
votes
1
answer
30
views
How to prove that it is NP-complete?
I was trying to do this exercise, but I don't know how to solve this problem is NP-complete, what reduction to do.
There is a network N of n people, in which every person i is associated with a subset ...
0
votes
3
answers
125
views
Maximum, delete and insert fastest data structure
The runtime to find a max element in max heap is $O(1)$. It takes $O(\log n)$ time to delete an element and $O(\log n)$ time to insert a new element in the heap.
Does there exists a data structure in ...
- 123
0
votes
1
answer
43
views
Is returning pointers to nodes for a list (doubly linked list) implementation a leaky abstraction? and is it bad?
I've been studying closely about the List abstract data type - As I understand it can be implemented with linked-list and/or arrays, and really maybe with any other data types as well.
But to satisfy ...
- 13
1
vote
1
answer
51
views
Big O analysis of a sorting algorithm that counts smaller elements
How do I prove the runtime of an algorithm with Big O notation? I don't know much about O notation, I just I know how to compare sets of functions with each other and I'm also familiar with the master ...
- 13
0
votes
1
answer
60
views
How do I prove correctness of my algorithm that finds a pair of integers in an array that have a sum of 0?
I have designed an algorithm (up to making a pseudocode) that accepts a sorted array as input and finds in $O(n)$ time if there's a pair of elements (integers) in the array that have a sum zero.
What ...
- 225
1
vote
2
answers
36
views
Layout algorithm for resource timings
I'm trying to come up with a performant layout algorithm for web resources timings. For now, all that is relevant is that resource timings include a startTime ...
- 125
0
votes
1
answer
43
views
Algorithm to distribute group of connected nodes in a graph
Given something similar to this.
Where you have blocks (the squares) and entries (the circles). Each block has a rating (the number inside the blocks) and is connected to other blocks. This topology ...
- 1
2
votes
0
answers
31
views
Algorithm for finding the set of minimum, bounding $n$-spheres that covers a finite set of points in $\mathbb{R}^n$
Let $P$ be a non-empty, finite set of points in $\mathbb{R}^n$. I want to know if there is an algorithm that can find the most optimal set of $n$-spheres $S$ that follows these properties:
Each $n$-...
- 21
2
votes
1
answer
105
views
Approximating the median of the complement of a set
Given an integer $n$ and a tree set $S$, I would like to find the approximate median $x$ of the integer set $T := \{i \in \mathbb N : i < n \wedge i \notin S\}$. There are no constraints to the ...
- 133
1
vote
1
answer
44
views
Aggregate method for dynamic table (amortized analysis)
For amortized analysis (aggregate method), dynamic table insertion cost can be divided into:
if no expansion, then cost = 1
if we expand the table, then cost = i (if i-1 is an exact power of 2)
then ...
- 113
1
vote
1
answer
36
views
Relationships between path width and clique size of interval graphs
I faced the following claim on wikiepdia about interval graphs (https://en.wikipedia.org/wiki/Interval_graph):
The pathwidth of an interval graph is one less than the size of its maximum clique.
I ...
- 13
-1
votes
1
answer
91
views
Maximum Flow algorithm. How to prove the following statements
Good Evening,
So I am trying to solve this exercise which is a paticular case of maximum flow algorithm. Here the graph must have all even edges and 1 odd edge and it must have a maximum flow that is ...
- 25
1
vote
1
answer
24
views
Letter Boxed Puzzle - Is a minimum set cover plus additional constraints solution viable?
Upfront, I'm not a computer science or mathematics graduate. I am a dabbler/recreational programmer and I find some problem/solution scenarios intellectually stimulating to attempt. Sometimes (...
- 13
2
votes
1
answer
413
views
How is the input to a BROUWER algorithm done
The Brouwer fixpoint theorem states that any continuous mapping $f$, from a convex, compact set to itself will contain a fixpoint.
The Brouwer algorithm finds these (approximate) fixpoints. But how is ...
- 39
2
votes
1
answer
90
views
Information sharing in group
I have a group with n members. These are distributed members. It is basically a group chat. A new member is added to the group and the existing members are informed about this.
Now I want the new ...
- 123
0
votes
2
answers
110
views
Proof showing when Dijkstra’s algorithm fails for negative edge weights
How do I show the correctness proof of Dijkstra’s algorithm for negative edge weight
$\textbf{indicating the point in the proof where it breaks or does not hold}?$
I tried proving it like this, but i ...
- 33
0
votes
0
answers
39
views
Points in convex d-dimensional polytope
Given a set of points, and a convex d-dimensional polytope represented only by a set of its' vertices, I need to query in order to check for each point if it's inside the polytope. I know of the O(log(...
- 13
0
votes
0
answers
23
views
Maximize flow through a graph, where edges can be added subject to restrictions
I'm doing a course in algorithms and I'm stuck on this problem.
Given a set of vertices on a grid. Every vertex has a coordinate (x,y).
An source and a sink has ...
- 103
1
vote
1
answer
297
views
Minimal number of positive intervals to cover all positive elements
I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray&...
- 295
0
votes
2
answers
23
views
Chord Ring with limited table size of 3
In the normal case of a chord ring the big O notation of the look up is O(logn) because of long haul pointers of the Finger Table (or Routing Table).
In this question what if the Finger Table has a ...
- 111
0
votes
0
answers
52
views
Simple solution to 1000n^3> 2^n without Lambert and "W"
I need to determine for what range of n the algorithm that costs $1000n^3$ is faster than one that costs $2^n$, now I solved it on wolfram alpha and I know the answer is >= 24.
The issue is I have ...
- 1
1
vote
0
answers
37
views
What is the literature implementation of self-organizing lists?
I'm trying to implement self-organizing lists DS to publish as a public module. Over the course of Algorithms, we learnt that if you add a new element to the list, it should still do the huriectics. ...
- 223
2
votes
2
answers
100
views
FFT algorithm for arbitrary $n$
In section 30.2 of CLRS (third edition), they given an algorithm for computing the fast Fourier transform of a vector represented as an $n$ dimensional array when $n$ is a power of $2$. They say that ...
- 295
0
votes
2
answers
45
views
Reduction from SUBSET SUM to COIN CHANGING
The COIN-CHANGING problem is NP-complete, but I am having difficulty finding a proof for its NP-hardness in the form of a reduction from another NP-complete problem ...
- 3
-1
votes
1
answer
41
views
What is the algorithm where you rotate around a board in a clockwise pattern?
I'm sure this question has been asked before, but I have no clue what I'm trying to achieve is called and couldn't find anything helpful.
I'm trying to find the name of an algorithm that starts at a ...
0
votes
1
answer
110
views
Proving why decreasing an edge weight in a graph may change it's MST by one edge
I'm working on understanding graphs and graph algorithms.
The problem is from: https://courses.engr.illinois.edu/cs374/fa2020/labs/sol/lab_12_b_sol.pdf
(Q 1.D)
Describe an efficient algorithm to ...
- 33
2
votes
3
answers
114
views
Algorithm: Optimal selection of subset of nodes in undirected graph to minimize score
Apologies if this question exists somewhere. I'm sure it's been asked, but I don't know how to search for it. This is not a homework question but rather a scientific problem I ran into. If this is a ...
- 123
0
votes
1
answer
34
views
LP Approximation for Vertex Cover Problem
In Cormen's Introduction to Algorithms, he states the the LP relaxation for the minimum vertex cover approximation problem is $ \begin{align*}
&\sum\limits_{v \in V}w(v)x(v) \...
0
votes
3
answers
172
views
Sort doubly linked list with just manipulating pointers
Given doubly linked list $L$ that contains $n$ elements of numbers. Between QuickSort, and MergeSort and InsertionSort, which algorithm preferred to sorting $L$ by just swapping links of $L$?
I think ...
- 1,556