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.

706 questions
20k views

Big O: Nested For Loop With Dependence

I was given a homework assignment with Big O. I'm stuck with nested for loops that are dependent on the previous loop. Here is a changed up version of my homework question, since I really do want to ...
564 views

What is the name of this logistic variant of TSP?

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
4k views

Updating an MST $T$ when the weight of an edge not in $T$ is decreased

Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$. Now we decrease the weight by $k$ of ...
3k views

Correctness of Strongly Connected Components algorithm for a directed graph

I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$....
470 views

Explaination for Variation of Boyer-Moore Majority voting algorithm

Boyer-Moore's majority vote algorithms can be used to determine the majority element in a linear time and constant space. The intuition behind finding the majority element is understandable as it ...
7k views

Number of submatrices with a particular sum

Given a $n\times n$ matrix A[0...n-1][0....n-1] where all entries are non-negative integers, and a non-negative integer K, I ...
2k views

Algorithm Request: “Shortest non-existing substring over given alphabet”

I'm looking for an (efficient) algorithm to solve the following problem: Given a string $S$ and a set of characters $M$, find the shortest string composed only of characters in $M$ that is not ...
3k views

Optimal algorithm to traverse all paths in the order of shortest path

I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path. The simplest way that comes to mind is to do a depth-...
369 views

Reconstructing a screen of permuted pixels

Reconstructing a screen of permuted pixels Summary Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture? Let: ...
5k views

Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
5k views

How do I find the max and min value of an array in 3n/2−2 comparisons?

So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers ...
189 views

state of the art of subset, set containment and partial match queries

The subset query problem is defined as: Given a list D of size N where the entries are subsets of a universe with ...
873 views

Best improvements to do to the DPLL SAT algorithm

As part of a college class, I'm asked to improve the performance of a basic DPLL sat solver. I'm already provided a basic, slow working version (essentially the DPLL algorithm; furthermore, to select ...
778 views

Is there a $O(n^2)$ algorithm to resolve isomorphism between two weighted $n$-vertex graphs? This is a much easier problem than graph isomorphism. Basically take an real edge weight set $\{w_1,\dots,... 4answers 1k views How to use a greedy algorithm to find the non-decreasing sequence closest to the given one? You are given n integers$a_1, \ldots, a_n$all between$0$and$l$. Under each integer$a_i$you should write an integer$b_i$between$0$and$l$with the requirement that the$b_i$'s form a non-... 4answers 740 views Is every linear-time algorithm a streaming algorithm? Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear ... 1answer 1k views Is this a generic way to convert any recursive procedure to tail-recursion? It seems that I've found a generic way to convert any recursive procedure to tail-recursion: Define a helper sub-procedure with an extra "result" parameter. Apply what would be applied to the ... 3answers 1k views PRNG for generating numbers with n set bits exactly I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some$0 < n < ...
4k views

Wikipedia lists the time complexity of addition as $n$, where $n$ is the number of bits. Is this a rigid theoretical lower bound? Or is this just the complexity of the current fastest known ...
620 views

Error in the use of asymptotic notation

I'm trying to understand what is wrong with the following proof of the following recurrence $$T(n) = 2\,T\!\left(\left\lfloor\frac{n}{2}\right\rfloor\right)+n$$  T(n) \leq 2\left(c\left\...
1k views

Is there a way to test if two NFAs accept the same language?

Or at least generate a set of strings that one NFA accepts, so I can feed it into the other NFA. If I do a search through every path of the NFA, will that work? Although that will take a long time.
990 views

Cutting equal sticks from different sticks

You have $n$ sticks of arbitrary lengths, not necessarily integral. By cutting some sticks (one cut cuts one stick, but we can cut as often as we want), you want to get $k<n$ sticks such that: ...
7k views

What does the 2 in a 2-approximation algorithm mean?

Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?
10k views

If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?

If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in linear time? Intuitively this sounds correct, as ...
535 views

How many strings are close to a given set of strings?

This question has been prompted by Efficient data structures for building a fast spell checker. Given two strings $u,v$, we say they are $k$-close if their Damerau–Levenshtein distance¹ is small, i.e....
1k views

$O(n \log n)$ algorithm for disjoint segment visibility problem

Consider we have $n$ disjoint segments and a point $P$ which is not on any segment. I want to find an $O(n \log n)$ algorithm to check which segments are visible from $P$. A segment is visible from $P$...
411 views

How to find a subset of potentially maximal vectors (of numbers) in a set of vectors

I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats). I say a vector u "covers" a vector v if, in every dimension 1..d, u[i] >= v[i]...
11k views

Finding paths with smallest maximum edge weight

I need to find the easiest cost path between two vertices of a graph. Easiest here means the path with the smallest maximum-weigth edge. In the above graph, the easiest path from 1 to 2 is: ...
4k views

Do I understand pseudo polynomial time correctly?

The running time of knapsack is $O(n*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time ...
97 views

202 views

149 views

lower bound proof with adversary argument

We have to run a song on a Walkman, for that we need 2 full batteries. Let's say we have a mixed set of 30 batteries (15 are empty and and 15 are full) and then only way to test if the battery is full ...
For a connected undirected graph $G$, given a particular vertex $v$, is there a known (efficient) algorithm to find all simple cycles in $G$ that contain $v$? In my case, I have weights for every ...