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
1answer
281 views

Proving that the cover time for graph is exponential in the worst case

How can I prove that the cover time for a directed graph $G$ can be exponential in the size of $G$? The cover time is the expected length of a random walk that visits all vertices.
1
vote
0answers
38 views

constrained cover on biparite graphs [duplicate]

Possible Duplicate: Restricted version of vertex cover Suppose we have a $(A,B,E)$ bipartite graph and a positive integer k. Suppose that k is smaller than $|A|$ and we want to find one of those ...
4
votes
2answers
19k views

Finding the number of distinct permutations of length N with n different symbols

I have one puzzle whose answer I have boiled down to finding the total number and which type of permutation they are. For example if the string is of length ten as $w = aabbbaabba$, the total number ...
9
votes
5answers
6k views

Shortest distance between a point in A and a point in B

Given two sets $A$ and $B$ each containing $n$ disjoint points in the plane, compute the shortest distance between a point in $A$ and a point in $B$, i.e., $\min \space \{\mbox{ } \text{dist}(p, q) \...
8
votes
4answers
10k views

Fastest algorithm for finding the longest palindrome subsequence

First of all we must read a word, and a desired size. Then we need to find the longest palindrome created by characters in this word used in order. For example for size = 7 and word = "abcababac" the ...
17
votes
1answer
3k views

Brute force Delaunay triangulation algorithm complexity

In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm ...
2
votes
1answer
133 views

Algorithm to check the 2∀-connectness property of a graph

A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of ...
21
votes
2answers
5k views

How to describe algorithms, prove and analyse them?

Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only ...
20
votes
3answers
640 views

Problems in P with provably faster randomized algorithms

Are there any problems in $\mathsf{P}$ that have randomized algorithms beating lower bounds on deterministic algorithms? More concretely, do we know any $k$ for which $\mathsf{DTIME}(n^k) \subsetneq \...
22
votes
4answers
4k views

Sorting algorithms which accept a random comparator

Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the ...
0
votes
1answer
2k views

Solve a problem through reduction

I am aware that for a problem to be considered NP-Hard, any problem in NP must be reduceable to your problem (problem which you are trying to prove is NP-Hard). Let's assume that you have proven that ...
2
votes
2answers
1k views

"Flow layouts" inside a GUI -- how do I come up with a good algorithm?

I was trying to write some simple code for a "flow layout" manager and what I came up with initially was something like the following (semi-pseudocode): ...
3
votes
1answer
480 views

Restricted version of vertex cover

I am interested in the complexity of the restricted version of the vertex cover problem below: Instance: A bipartite graph $G =(L, R, E)$ and an integer $K$. Question: Is there $S \subset L$, $|S| \...
9
votes
1answer
1k views

Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
31
votes
5answers
3k views

Finding interesting anagrams

Say that $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ are two strings of the same length. An anagramming of two strings is a bijective mapping $p:[1\ldots n]\to[1\ldots n]$ such that $a_i = b_{p(i)}$ ...
3
votes
2answers
439 views

Generating number of possibilites of popping two stacks to two other stacks

Context: I'm working on this problem: There are two stacks here: A: 1,2,3,4 <- Stack Top B: 5,6,7,8 A and B will pop out to other two stacks: C and D....
3
votes
1answer
176 views

Numbers of ways of expressing the sum of a number between [a,b]

I need an algorithm to calculate the number of ways of expressing a number N as sum of numbers inside the interval [a, b]
1
vote
0answers
54 views

How to use greedy algorithm to solve this? [duplicate]

Possible Duplicate: How to use greedy algorithm to solve this? 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$ ...
2
votes
1answer
2k views

Enumerating all the walks in a graph between a start vertex and a terminal vertex?

I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can ...
6
votes
2answers
8k views

How to find spanning tree of a graph that minimizes the maximum edge weight?

Suppose we have a graph G. How can we find a spanning tree that minimizes the maximum weight of all the edges in the tree? I am convinced that by simply finding an MST of G would suffice, but I am ...
2
votes
1answer
468 views

Point Location Problem in Polygon in Repetitive Mode for a Simple Polygon

I consider Point Location Problem in Polygon in repetitive mode in the case of simple polygon. In computational geometry,Point Location Problem in Polygon problem asks whether a given point in the ...
4
votes
1answer
213 views

Is the following recurrence for this program's runtime correct?

Let $f$ and $g$ be two functions and $p$ a number. Consider the following program: ...
7
votes
1answer
752 views

Alpha-Beta Pruning with simultaneous moves?

I have a game I'm building some ai for that has 2 players making simultaneous moves. In this game there is exactly one move where, if they both make it at the same time, the outcome is different than ...
5
votes
1answer
3k views

Weighted subset sum problem

Given an integer sequence $\{ a_1, a_2, \ldots, a_N \}$ that has length $N$ and a fixed integer $M\leq N$, the problem is to find a subset $A =\{i_1, \dots, i_M\} \subseteq [N]$ with $1 \leq i_1 \lt ...
6
votes
1answer
175 views

Streaming algorithm and random access

Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least one duplicate number, i.e., a number that appears at least twice. I want output some duplicate ...
16
votes
1answer
3k views

How do I test if a polygon is monotone with respect to an arbitrary line?

Definition: A polygon $P$ in the plane is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $P$ at most twice. Given a polygon $P$, is it possible to ...
7
votes
0answers
185 views

What is the proof for the lemma "For every iteration of the Gomory-Hu algorithm, there is a representant pair for each edge"?

For a given undirected graph $G$, a Gomory-Hu tree is a graph which has the same nodes as $G$, but its edges represent the minimal cut between each pair of nodes in $G$. The Gomory-Hu algorithm finds ...
21
votes
4answers
2k 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-...
5
votes
1answer
1k views

Dependency Graph - Acyclic graph

I have a directed acyclic graph where edge (A,B) means that vertex A depends on vertex B. Vertex deletions have the following restrictions: When vertex B is removed, all dependent vertexes should ...
25
votes
1answer
7k views

How to prove correctness of a shuffle algorithm?

I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased). The first method I use is to construct the entire list of elements and ...
1
vote
2answers
820 views

Any very user friendly resources on the Baum-Welch algorithm?

I'd like to understand the Baum-Welch algorithm. I liked this video on the Forward-Backward algorithm so I'd like a similar one for Baum-Welch. I'm having trouble coming up with good resources for ...
5
votes
2answers
6k views

Forward checking vs arc consistency on 3-SAT

If I were to let the variables be the propositions and, constraint be all clauses being satisfied, which technique would be more effective in solving 3-SAT? Forward checking or arc consistency? From ...
6
votes
2answers
222 views

Finding the point nearest to the x-axis over some segment

I have problem with solving the following exercise Given the set $P$ on $n$ points in two dimensions, build in time $O(n\log n)$ a data structure of $P$ such that given a horizontal segment $s$ ...
4
votes
1answer
139 views

Need help understanding this optimization problem on graphs

Has anyone seen this problem before? It's suppose to be NP-complete. We are given vertices $V_1,\dots ,V_n$ and possible parent sets for each vertex. Each parent set has an associated cost. Let $O$ ...
6
votes
1answer
536 views

Algorithm to minimize distance variance between 2D coordinates

I've been looking around for an algorithm that would optimize the distance between 2 list of coordinates and choose which coordinate should go together. Say I have List 1: ...
16
votes
3answers
4k views

Determine missing number in data stream

We receive a stream of $n-1$ pairwise different numbers from the set $\left\{1,\dots,n\right\}$. How can I determine the missing number with an algorithm that reads the stream once and uses a memory ...
2
votes
1answer
361 views

Could someone suggest me a good introductory book or an article on graph clustering?

For my pet project I need to cluster some data which could be easily represented as graph, so I want to use this as an opportunity to educate myself and play with various algorithms. I'd prefer the ...
14
votes
1answer
415 views

Coverage problem (transmitter and receiver)

I try to solve the following coverage problem. There are $n$ transmitters with coverage area of 1km and $n$ receivers. Decide in $O(n\log n)$ that all receivers are covered by any transmitter. All ...
3
votes
2answers
187 views

What does this performance formula mean?

I have to make a quick clustering program but the following formula is gibberish to me: $\operatorname{Perf}(X,C) = \sum\limits_{i=1}^n\min\{||X_i-C_l||^2 \mid l = 1,...,K\}$ where $X$ is a ...
3
votes
1answer
65 views

Block detection in repeated stream

I need to recover a data block from a repeated stream of data. I'm looking to see what algorithms may already exist for this as it does not feel like a novel situation. Here are the specifics: There ...
14
votes
2answers
15k views

When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
7
votes
1answer
413 views

In s-t directed graph, how to find many small cuts?

Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in ...
6
votes
1answer
2k views

Bellman-Ford variation

I have a "smarter" version of Bellman-Ford here; this version is more clever about choosing the edges to relax. ...
23
votes
1answer
5k views

How Does Populating Pastry's Routing Table Work?

I'm trying to implement the Pastry Distributed Hash Table, but some things are escaping my understanding. I was hoping someone could clarify. Disclaimer: I'm not a computer science student. I've ...
5
votes
1answer
79 views

Finding small node sets that can not be avoided on paths from source to sink

In a directed graph with a starting node and an ending node, how to find a small (doesn't have to be smallest. <10 for example) set S of nodes such that every possible path from the starting node ...
4
votes
1answer
9k views

Removing Left Recursion from Context-Free Grammars - Ordering of nonterminals

I have recently implemented the Paull's algorithm for removing left-recursion from context-free grammars: Assign an ordering $A_1, \dots, A_n$ to the nonterminals of the grammar. for $i := 1$ to $n$ ...
8
votes
0answers
2k views

Area of the union of rectangles anchored on the x-axis

I am trying to solve the following computational geometry problem. Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis....
135
votes
4answers
193k views

How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and ...
3
votes
1answer
288 views

Optimal path - best career

I am new and I have to develop an algorithm with a 2d integer array as input to compute the best career path. Lets consider a network with n nodes, which are numbered from $1$ to $n$. All are ...
1
vote
1answer
163 views

Is open adressing with prime steps bijective?

Who can help me with this topic: Probing with a step width that is a prime number. I am struggling with this question about defining a hashing function $h(k, i)$ for open addressing on a table of ...

1
199 200
201
202 203
205