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
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 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 ...
-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&...
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) ...
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. ...
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 ...
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 ...
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+...
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 ...
-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 ...
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 ...
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 ...
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 ...
-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 ...
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 (...
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 ...
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(...
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 ...
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 ...
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 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 ...
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 ...
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 ...
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
3 4
5
6 7
220