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
6
votes
4answers
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. ...
4
votes
2answers
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 ...
3
votes
1answer
2k views

FFT implementation using Danielson-Lanczos Lemma

I am trying to understand FFT algorithm explained here ...
6
votes
4answers
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?
8
votes
2answers
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 ...
4
votes
1answer
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 ...
16
votes
1answer
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 ...
2
votes
1answer
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? ...
18
votes
2answers
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 (...
14
votes
2answers
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 ...
6
votes
0answers
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 (...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
1
vote
1answer
117 views

Finding the element that occurs more often than the other

I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements. Example : $aaaaaabbb$ Here $a>...
8
votes
4answers
8k views

Find non-overlapping scheduled jobs with maximum cost

Given a set of n jobs with [start time, end time, cost] find a subset so that no 2 jobs overlap and the cost is maximum. Now I'm not sure if a greedy algorithm will do the trick. That is, sort by ...
44
votes
3answers
48k views

Longest path in an undirected tree with only one traversal

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
3
votes
2answers
1k views

Finding no. of leaf nodes for each node in a BST

A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is $\qquad \min(\#\text{...
8
votes
2answers
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$....
1
vote
0answers
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. ...
3
votes
1answer
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?
6
votes
4answers
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 ...
7
votes
2answers
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 ...
5
votes
1answer
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 ...
6
votes
4answers
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 ...
5
votes
4answers
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 ...
7
votes
1answer
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 ...
7
votes
2answers
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 ...
5
votes
1answer
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 ...
11
votes
1answer
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 ...
7
votes
1answer
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 ...
6
votes
1answer
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 ...
6
votes
1answer
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 ...
11
votes
3answers
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 ...
1
vote
0answers
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{...
2
votes
1answer
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. ...
5
votes
1answer
262 views

Find interval sums with minimum number of operation

Input: A list $A=a_1,\ldots,a_n$, with $\oplus$ a associative operation on $M$, and $A\subset M$. pairs $(s_i,t_i)$ for all $1\leq i\leq m$. Output: The list $b_1,\ldots,b_m$, where $b_i = \...
0
votes
1answer
703 views

Proving correctness of the algorithm for convex polygon minimum cost triangulation

I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be ...
11
votes
2answers
498 views

Fair cake-cutting when players join late

The usual statement of the fair cake-cutting problem assumes that all $n$ players get their share at the same time. However, in many cases the players arrive incrementally. For example, we may divide ...
3
votes
1answer
108 views

Comparing variations of A*

I am running some experiments with a maze, and trying different variations of A*. Based on my experiments, I have been able to form some opinion (that at least in those cases, graph checking is better ...
11
votes
1answer
588 views

How to detect sunshine on a photo

How would you algorithmically detect for any given photo whether the sun was shining when the picture was taken? Examples A sample from this webcam at a mountain top: Clearly the sun is shining. ...
-1
votes
1answer
259 views

WP pseudocode for Dijkstra does not work

I mean Dijkstra's algorithm for the shortest path. In all descriptions that I saw (including wikipedia), on every step, it always selects the nearest neighbor based on examining their weights. ...
3
votes
1answer
3k views

Differences between Fuzzy C-Means and EM

When clustering a set of data points, what exactly are the differences between Fuzzy C-Means (aka Soft K-Means) and Expectation Maximization? In slide 30 and 32 of this lecture I found, it says that ...
4
votes
1answer
2k views

Algorithms with polynomial time complexity of higher order

I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting. Linear Search - with time complexity $O(n)$ Matrix Addition - with time complexity $O(n^...
16
votes
2answers
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. ...
10
votes
1answer
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$ ...
4
votes
0answers
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 ...
19
votes
2answers
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. ...
8
votes
1answer
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, ...
6
votes
2answers
4k views

Understanding DPLL algorithm

I'm trying to understand DPLL algorithm for solving SAT problem. And here it is: ...
4
votes
2answers
117 views

Can you complete a basis in polynomial time?

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

1 147 148 149 150 151 163