Questions related to design and analysis of algorithms
0
votes
1answer
17 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 to ...
0
votes
0answers
16 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 ...
1
vote
0answers
18 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
38 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 ...
6
votes
2answers
68 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
40 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 ...
2
votes
1answer
32 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
54 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
37 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
74 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
87 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
37 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 ...
2
votes
0answers
48 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
164 views
+50
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
39 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 ...
1
vote
1answer
49 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
43 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
94 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.
...
6
votes
2answers
143 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
96 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
138 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
44 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
38 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
74 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
83 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
0answers
54 views
Game Theory: Regret Minimization
I try to get some intuition behind regret minimization in game theory by reading Learning, Regret minimization, and Equilibria by A. Blum and Y. Mansour.
The main problem is I am sort of confused by ...
3
votes
2answers
73 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
31 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
93 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
32 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
32 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 ...
4
votes
1answer
75 views
Issues with using greedy algorithm (Interval scheduling variant)
I am trying to solve a problem of finding incompatible 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 ...
3
votes
0answers
52 views
Issues with an optimization problem
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.
I want to find the ...
0
votes
0answers
30 views
Relinquishing criteria for operating systems
What is meant by relinquishing criteria for a scheduling algorithm such as First in fist out? I know this algorithm choses the first process to be executed by the scheduler. Is it non pre-emptive ...
1
vote
2answers
63 views
Finding the required value of an algebric expression
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.
I want to find the ...
1
vote
1answer
105 views
Finding cycles in a graph
Given a directed weighted graph $D = (V, A, w)$ with weight function $w \colon A \to [0,\infty)$ and a source vertex $s$. How can I find, for each vertex $v \in V$ a shortest (with respect to $w$) ...
4
votes
1answer
66 views
Find the longest subsequence of two strings
I want to know which is the best way to find the longest common subsequence of two strings
3
votes
2answers
95 views
Show that it is undecidable if two Turing Machines accept the same language
I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown' that two Turing machines which accept the same language is undecidable. This is not a ...
-2
votes
0answers
39 views
How many trees are possible? [closed]
We are given two integers $p$ and $q$.
We have to find how many different $T$-trees are possible.
Definition of a $t$-tree
It is a tree with $q \cdot p$ nodes. The nodes are numbered from 0 to $q ...
6
votes
1answer
79 views
Efficiently finding key sets
A few years ago I participated in German highschool computer science competition. One of the problems was this (slightly abbreviated):
A somewhat unusual electronic lock consists of $n$ switches ...
1
vote
2answers
54 views
Finding largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$
I need to find largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ where $N$ can be as large as $10^{18}$.
I tried this approach , but is too slow.
Finding the just smallest prime number to $N$, ...
1
vote
2answers
78 views
What is the fastest to find just smallest prime number to a given number N where N can be as large as 10^18?
During a programming contest I was asked to find just smallest prime number to given number N.
As Sieve cannot be used and brute force also doesn't work.
So, I was wondering is there any other faster ...
2
votes
1answer
60 views
Euclidean Steiner Tree Question in Approximation Algorithms
Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$.
...
2
votes
1answer
38 views
Solving a problem related to convolution
I have this confusion related to solving this problem
You’vebeenworkingwithsomephysicistswhoneedtostudy,aspartof their experimental design, the interactions among large numbers of very small charged ...
1
vote
1answer
39 views
Finding the lower bounds of an algorithm
I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.
For eg, I have the following algorithm
...
0
votes
1answer
46 views
What's the vertex cover of the null graph?
Let $N(G)$ be the null graph. What's the number of vertex cover for this graph? I wanted to modify the reduction from SAT to vertex cover by adding vertices that are not connect to any vertices.
1
vote
2answers
39 views
Can we have a general function of any function this way?
Lets say we need a function to add two numbers and another function to multiply two numbers.
To take a trivial example, consider the function $F(a, b, c, d) = a \cdot (c+d) + b \cdot (c\cdot d)$
If ...
0
votes
0answers
17 views
Interval Scheduling Optimization type of Problem, optimal order of manufacture
We wish to manufacture n distinct hardware items. Each item needs to go through 3 stages of processing. The first stage called design can only be performed by our master designer who works by starting ...
