Questions related to design and analysis of algorithms
1
vote
1answer
15 views
What is a “wasteful” execution? And a “schedule”?
I'm trying to understand what this text means in my textbook about distributed leader election algorithms, but I can't make any sense of it. Either they didn't explain what was meant, or I missed it ...
1
vote
0answers
25 views
Insertion sort Proof by Induction
I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below.
Consider the correctness of insertion sort, which we ...
2
votes
1answer
35 views
Finding least number of line segments with length $L$ that cover $N$ points
The problem is defined as:
Given $N$ points on an infinite line, find the least number of line segments of length $L$ that cover all points (including endpoints) after changing one point.
That ...
2
votes
0answers
26 views
Convex Hull on a Spherical Surface
Is there any convex hull algorithm that can be extended to non-euclidean metric, such as the geodesic distance on the surface of a sphere?
0
votes
0answers
20 views
Aproximation algorithm for histogram
This is my first question, so please, be soft on me.
I have a following problem:
I'm a programmer not a mathematician, I don't often understand pure mathematical language and marks or symbols, I ...
2
votes
4answers
89 views
Elegant approach to finding largest $n$ such that $n\lg(n) \leq 10^6$
I'm studying CLRS, and solving problems listed after each chapter. I'm curious about problem 1-1. That is right after Chapter 1.
The question is, what is the best way to find the largest integer $n$ ...
1
vote
1answer
61 views
Efficient algorithms for finding a region in $\mathbf R^2$
This question is an extension of a previous question I've asked.
Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 ...
2
votes
2answers
45 views
Looking for the English name of algorithm using a precomputed array for interval sum computation
I am looking for the English name of the following algorithm:
We are given an array a with numbers and we need to be able to efficiently retrieve the sum of a ...
4
votes
0answers
50 views
Compressing Graphs with combinatorial functions
I am working on a project that its goal is text compression. First by using Lampel-Ziv algorithm, I turned text to numerical codes. Then map this codes to a data structure (Graph or tree) and solve it ...
3
votes
1answer
25 views
How approximate are “approximate” nearest neighbor (ANN) search algorithms?
Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are.
If I have a (more or less) randomly distributed point ...
2
votes
2answers
83 views
Complexity of an algorithm for bounding a region in 2D
First I apologize if the title is unclear, but I didn't find anything better.
I'm solving a differential equation that has two parameters , here denoted by points of a plane.These parameters are real ...
1
vote
1answer
56 views
Preventing oversell, allocation of limited resources with overlapping properties
I am trying to solve problem of preventing oversell of limited resources.
Consider resources (people) who are described by set of properties where each property belongs to different category (example ...
2
votes
2answers
101 views
Can a Boolean circuit be considered an algorithm?
Can a Boolean circuit by itself be considered an algorithm (a single step algorithm if you like)? For instance say you have a simple tree circuit with two AND gates as the input gates feeding a single ...
-2
votes
0answers
25 views
Use analytical solution to find the starting value [closed]
I wanna setup the starting value as the analytical solution in my 'AdamsBashforth4' solver. And the analytical solution is x(t)=e^t*cos(t)-2*e^t; y(t)=e^t*sin(t)-e^t
Below is what I have so far, how ...
-1
votes
1answer
57 views
Find the weight of the lightest path from u to v
Find the weight of the lightest path from u to v the goes through node a or/and b.
Do you have a suggestion on how it can be done?
3
votes
3answers
82 views
Is there an algorithm to find the best strategy for a game?
Let,
game be the state of a 2-player, turn based game
actions game player -> [move] be a function that gets the state of a ...
1
vote
2answers
53 views
Number of PCP queries
While it is easy to prove that $P=PCP(O(\log n),0)$ , proving that $PCP(O(\log n),1)\subseteq P$ i.e. PCP that uses $O(\log n)$ random bits and read 1 bit of the proof is less obvious, what I tried ...
-1
votes
0answers
27 views
Bellman-Ford and Dijkstra - Differences after k Iterations
I have a small statement I need to prove and I'm not sure how to start.
Introduction:
Let G be a directed graph.
Let w be a non-negative weight function on the edges of G.
Let s be the ...
2
votes
2answers
73 views
Algorithm to determine whether two regexes are equivilent
Given two arbitrary regular expressions, is there an "efficient" algorithm to determine whether they match the same set of strings?
More generally, can we compute the size of the intersection of the ...
2
votes
0answers
22 views
Finding all vertices on negative cycles
Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a ...
3
votes
1answer
48 views
Longest path in grid like graph
This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:
Find the length of the longest ...
7
votes
2answers
116 views
Practical Applications of Radix Sort
Radix sort is theoretically very fast when you know that the keys are in a certain limited range, say $n$ values in the range $[0\dots n^k -1]$ for example. If $k<\lg n$ you just convert the ...
4
votes
0answers
43 views
Overlap Maximization problem
Here's the problem:
I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
-3
votes
3answers
53 views
Algorithm for the k-coloring problem [closed]
Is there a generic algorithm that I can use in an application to solve the $k$-coloring problem for any $k$ colors? I understand that such an algorithm would likely be inefficient, I just need an ...
3
votes
1answer
35 views
Randomized convex hull
I've been recently studying Monte-Carlo and other randomized methods for a lot of applications, and one that popped into my mind was making an (approximate) convex hull by examining random points, and ...
2
votes
2answers
56 views
Are those definitions of universal hash family equivalent?
I've seen two definitions of a universal hash family, and my questions is if those are equivalent, i think they are and will explain why but i'm not sure if it is.
Definition 1:
$H$ is a universal ...
0
votes
1answer
41 views
Bounding rectangle of a line
[Input]: the begin and end points of an arbitrary line (small red points) and the line width (green line)
[Example]: begin=(20,20), end=(100,50), width=5
[Output]: The set of pixels (not the total ...
2
votes
2answers
42 views
Correctness-Proof of a greedy-algorithm for minimum vertex cover of a tree
There is a greedy algorithm for finding minimum vertex cover of a tree which uses DFS traversal.
For each leaf of the tree, select its parent (i.e. its parent is in minimum vertex cover).
For each ...
1
vote
2answers
174 views
Shortest path with odd weight
Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.
We are looking for an algorithm for finding the weight of the shortest odd ...
3
votes
2answers
114 views
Modeling the problem of finding all stable sets of an argumentation framework as SAT
As a continuation of my previous question i will try to explain my problem and how i am trying to convert my algorithm to a problem that can be expressed in a CNF form.
Problem: Find all stable sets ...
0
votes
1answer
40 views
In flow networks, may source/sink have incoming/outgoing edges?
I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ?
Flow-networks are always pictures with no ...
3
votes
1answer
83 views
Hanoi tower with forbidden direct move from source to destination
I want to know what is algorithm and time complexity of Hanoi tower with forbidden direct move from source to destination (it means you cannot move disk from source to destination directly and you ...
2
votes
1answer
178 views
Finding the path of a negative weight cycle using Bellman-Ford
I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, ...
0
votes
0answers
46 views
Algorithm to solve job assignment problem
Can someone suggest an algorithm to solve job assignment problem with condition?
With condition means that some jobs cannot be done by some workers. For example table as shown below:
In this table ...
2
votes
1answer
148 views
Shortest paths candidate
Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. ...
1
vote
0answers
44 views
how to prove this unsolvable problem about halting problem (turing machine) [duplicate]
Show that the problem of deciding, for a given TM M, whether M halts for all inputs within n^2(namely n square ) steps(n is the length of the input) is unsolvable. You can use the fact without proof ...
5
votes
1answer
100 views
Algorithm to find a line that divides the number of points equally
I have recently been asked in an interview to devise an algorithm that divides a set of points in a coordinate system so that half of the points lie on one side of the line, and the rest on the other ...
2
votes
0answers
29 views
Why does Shellsort work well on Sorted and Reverse ordered lists?
I've ran some tests and found that Shellsort runs much faster on ordered and reversed lists compared to random lists and almost ordered lists.
...
7
votes
2answers
173 views
Converting (math) problems to SAT instances
What I want to do is turn a math problem I have into a boolean satisfiability problem (SAT) and then solve it using a SAT Solver. I wonder if someone knows a manual, guide or anything that will help ...
2
votes
2answers
103 views
The sum of all integers less than n with a zero
For example, if n=14, the output should be 10; n=22, the output should be 30=10+20; n=102, output=(10+...+100)+101+102=5703
In this problem, n is smaller than $10^{18}$ , and the algorithm should ...
8
votes
3answers
156 views
Graph Has Two / Three Different Minimal Spanning Trees?
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
1
vote
1answer
46 views
Find longest common subsequence in limited space
Given three strings $x$, $y$, and $z$ over an arbitrary finite alphabet, I need to determine their longest common subsequence (LCS).
Example: A longest common subsequence of ...
3
votes
1answer
39 views
Is this simplified consensus problem easier than the original?
There is a famous Consensus Problem in Distributed Computing.
Let's consider and try to find the best possible algorithm for a simplified version of the consensus problem.
Assumptions: a process ...
2
votes
1answer
76 views
Shortest sub-sequence of one string, that's not a sub-sequence of another string
Given two strings $x$ and $y$ over the alphabet $\{A,C,G,T\}$, I'm trying to determine a shortest string $z$ such that $z$ is a subsequence of $x$ and not a subsequence of $y$.
Example: a shortest ...
4
votes
1answer
87 views
Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?
Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional ...
3
votes
2answers
76 views
MAX 10-SAT Algorithm
The MAX k-SAT problem is:
“Given a set of clauses C1,…,Ck, each of length k, over a set of
variables x1,…,xn, find a truth assignment that satisfies as many of
the clauses as possible.”
I'm ...
1
vote
0answers
36 views
In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search?
In the Hopcroft-Karp algorithm for bipartite matching, I don't understand the purpose of the breadth first search. I think it's used to find a set of vertex disjoint augmenting paths, but I'm not ...
5
votes
2answers
98 views
Understanding why the polynomial $p(n) = \sum_{i=0}^{k} a_in^i$ is in $\Theta(n^k)$
Hi I've read this lemma in my book:
Lemma 2.1. Let $p(n) = \sum_{i=0}^{k} a_in^i$ denote any polynomial and assume $a_k > 0$. Then $p(n) \in \Theta(n^k)$
Proof. It suffices to show that ...
1
vote
0answers
35 views
Solving a variant of interval scheduling problem
I am trying to solve a problem of finding compatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.
I have a ...
-1
votes
1answer
34 views
Reducing from Hamiltonian Cycle problem to the Graph Wheel problem cannot be proved vice versa [closed]
I saw a proof by Saeed Amiri,
We will add one extra vertex v to the graph G and we make new graph G′, such that v is connected to the all other vertices of G. G has a Hamiltonian cycle if and only if ...
