# 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.

8,141 questions
Filter by
Sorted by
Tagged with
3k views

### Solving system of linear inequalities

I am trying to solve a system of inequalities in the following form: $\ x_i - x_j \leq w$ I know these inequalities can be solved using Bellman-Ford algorithm. ...
506 views

### From Whence the Randomization in Randomized Quicksort

Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph): Using a random number generator to choose the positions is ...
2k views

### FFT implementation using Danielson-Lanczos Lemma

I am trying to understand FFT algorithm explained here ...
13k views

### Explaining why FFT is faster than DFT for the general public?

How would you explain why the Fast Fourier Transform is faster than the Discrete Fourier Transform, if you had to give a presentation about it for the general (non-mathematical) public?
264 views

### How hard is it to solve for $P$ in $A = PBP^{-1}$?

From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that $A = P \times B \times P^{-1}$ So, to solve the problem, if two graphs are ...
1k views

### Size of maximum clique given a fixed amount of edges?

Given an undirected graph $G = (V,E)$, what is the clique number $\omega(G)$ given $|E|$, i.e., the size of the largest clique in a graph with $|E|$ edges. I think this is doable after realizing that ...
236 views

### Transforming an arbitrary cover into a vertex cover

Given is a planar graph $G=(V,E)$ and let $\mathcal{G}$ denote its embedding in the plane s.t. each edge has length $1$. I have furthermore a set $C$ of points where each point $c \in C$ is contained ...
365 views

### Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?

Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? ...
834 views

### What's harder: Shuffling a sorted deck or sorting a shuffled one?

You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits (...
24k views

### Finding shortest and longest paths between two vertices in a DAG

Given an unweighted DAG (directed acyclic graph) $D = (V,A)$ and two vertices $s$ and $t$, is it possible to find the shortest and longest path from $s$ to $t$ in polynomial time? Path lengths are ...
504 views

### Space filling between random 2D lines

Note that I had asked this question in GIS forum, although it has gotten many up-votes, still has not received any answer. Hope you can break the silence, some collaboration :) Consider a region (...
3k views

### How to find the minimum number of vertices whose removal make the graph disjoint

Given a graph $G = (V,E)$. Is there any algorithm which finds the minimum number of vertices to be removed from $G$ so that every vertex in the graph becomes disjoint, i.e., every vertex is ...
104 views

### Extracting the set of chains from a partial order

Given a partial ordered set (poset) $S$, is there a known procedure or algorithm to find the set of chains (i.e. subsets of $S$ where every two elements are comparable)? Note: I am asking here ...
117 views

4k 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$....
1k views

### Bridge determination in undirected graphs [closed]

A bridge (critical edge) in an undirected graph is an edge whose removal increases the number of connected components. I need to determine all critical edges in an undirected graph, in $O(V+E)$ time. ...
2k views

### What is a computer year?

In one of the text book its mentioned that 'running time of this algorithm is 200 computer years'. Can somebody please explain what is the meaning of a computer year?
2k views

### The physical implementation of quantum annealing algorithm

From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum ...
2k views

### Given a tree, find a vertex which maximizes the minimum distance to any leaf

If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf. I am sure this problem has been studied before. Does anybody know the ...
918 views

### Parallel merge sort using hypercube connection template

I've been reading about hypercube connection template for parallel algorithms. The general scheme is explained in Designing and Building Parallel Programs by Ian Foster and it's pretty clear. What I ...
34k views

### How to check whether a graph is connected in polynomial time?

I have to solve the following problem: Consider the problem Connected: Input: An unweighted, undirected graph $G$. Output: True if and only if $G$ is connected. Show that Connected ...
992 views

### Space complexity for finding the minimum number outside the list of numbers

We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$. We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$. What is the ...
328 views

### Circles covering a rectangular, how to verify it?

This may be basic to some of you, but excuse my inexperience with comp. geometry: Given a set of $n$ circles with centers $(x_i, y_i)$ for $1 \leq i \leq n$ and each having radii $r$. Also given a ...
126 views

### numerical integral vs counting roots

I have a problem that can be viewed in two different ways: Compute an $n$-dimensional integral, numerical context. The domain of integration is an $n$-dimensional hyper-cube of side $L$. Count (just ...
2k views

### Tarjan's Strongly Connected Component algorithm

I am trying to understand Tarjan's strongly connected component algorithm and I have a few questions (the line numbers I am referring to are from Algoritmy.net): On line 33 why is ...
1k views

### Average length of s-t (simple) paths in a directed graph

Given the fact that $s$-$t$ path enumeration is a #P-complete problem, could there be efficient methods that compute (or at least approximate) the average length of $s$-$t$ path without enumerating ...
448 views

### Relaxed Bin Packing Problem

The problem I have is like this bin packing problem, but instead I have $n$ bins and a collection of items with discrete masses. I need to put at least $m$ kg of stuff in each bin. Is there an ...
465 views

### Independent set where two vertices need to have distance >= c

An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices. I am interested in the generalization $c$-IS where two nodes in $V' \subseteq V(G)$ need to have ...
13k views

### How to master Dynamic Programming? [duplicate]

I am having hard times learning Dynamic Programming. I looked around the web and found many tutorials with examples. Each time I tried to figure out how to solve a new problem before looking at the ...
51k views

### Difference between cross edges and forward edges in a DFT

In a depth first tree, there are the edges define the tree (i.e the edges that were used in the traversal). There are some leftover edges connecting some of the other nodes. What is the difference ...
94 views

### Node-weighted CSP in Prim's algorithm?

I'm looking for an algorithm which would find a minimal spanning tree given certain constraints (CSP) about importance of some nodes, e.g. consider a graph with next distance matrix:  \left[ \begin{...
596 views

### Optimized algorithm to compare templates of two websites

My task is to compare templates of two websites. I am ready with my algorithm. But it takes too much time to give a final answer. Here, "template" means the way any page presents its contents. ...
262 views

9k views

### Colour a binary tree to be a red-black tree

A common interview question is to give an algorithm to determine if a given binary tree is height balanced (AVL tree definition). I was wondering if we can do something similar with Red-Black trees. ...
191 views

### Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?

A graph $G$ is chordal if it doesn't have induced cycles of length $4$ or more. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ ...
450 views

### Variation of interval scheduling algorithm with several job categories, only one from each can be used

I have a problem similar to the interval scheduling algorithm. The differences are: The jobs have the same length. There are several categories of jobs and only one job from each category can be ...
6k views

### Sort array of 5 integers with a max of 7 compares

How can I sort a list of 5 integers such that in the worst case it takes 7 compares? I don't care about how many other operations are performed. I don't know anything particular about the integers. ...
4k views

### All paths of less than a given length in a directed graph between couple of nodes

Counting all possible paths, or all possible paths with a given length, between a couple of nodes in a directed or undirected graph is a classical problem. Attention should be given to what all means, ...
Here is the problem: we are given vectors $v_1, \ldots, v_k$ lying in $\mathbb{R}^n$ which are orthogonal. We assume that the entries of $v_i$ are rational, with numerator and denominator taking $K$ ...