Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
0answers
8 views

What is the procedure for converting this finite automata into a regular expression?

Could someone provide an explanation of how to convert this DFA into a regular expression? I have found three methods online, ie: How to convert finite automata to regular expressions? but they are ...
0
votes
0answers
4 views

Find equivalent weighted DAG sum of whose weight is minimum

When a given weighted directed acyclic graph represents some object flow, what is the most efficient algorithm to find the equivalent graph sum of which edges is minimum? Here, 'equivalent' means the ...
5
votes
1answer
86 views

Maximum chromatic number of sparse graphs

It is well-known that the chromatic number of a graph can be as high as $n$. But what is the maximum chromatic number of a graph with $m = O(n)$?
0
votes
0answers
6 views

Detecting mulitple polygon intersections (java) [migrated]

Background: This project involves mapping regions in GIS environment. I need to find then the intersection of one set of polygons with another set of polygons. I achieved this by casting my ...
7
votes
2answers
88 views

Arbitrary precision integer square root algorithm?

Are there any known subquadratic algorithms for calculating the floor of the square root of an n bit integer? The naive algorithm would be something like ...
-2
votes
0answers
26 views

Find the $n$th smallest number of powers of $2$, $3$ and $5$

Find an efficient algorithm to find the $n$th smallest number in the set $$ \{2^i \mid i \geq 0 \} \cup \{3^i \mid i \geq 0 \} \cup \{5^i \mid i \geq 0 \} , $$ that is the $n$th number which is a ...
0
votes
0answers
15 views

Extended Compact Genetic Algorithm question

I have a question regarding the ECGA algorithm. This is what I'm currently studying. If ECGA builds a model of the parent pool using the 'minimum description length' (MDL) measure, why cannot we ...
1
vote
0answers
10 views

How to find (real-valued) roots of matrix polynomial

Assume you have a fixed ($d=O(1)$ for that matter) degree matrix polynomial $$P(X)=A_0+A_1\cdot X+A_2\cdot X^2+\ldots+A_dX^d$$ Where $A_0,A_1,\ldots A_d\in\mathbb N^{n\times n}$ are given as input. ...
0
votes
0answers
23 views

Difference between Turing machine end state and halt

Is there a difference between the end state of a Turing machine and the halt state? Especially, for example the Busy Beaver 3. It is said that it is with 3 states but there is also a halt. Is the end ...
1
vote
0answers
18 views

Constructing a TM from empty string

Hey I want to construct a deterministic Turing Machine, which out of an empty string tapes six consecutive 1s when halt. I have a question, is it possible to create such without transitions from final ...
5
votes
2answers
92 views

Efficient algorithm to compute the $n$th Fibonacci number

The $n$th Fibonacci number can be computed in linear time using the following recurrence: ...
0
votes
0answers
41 views

Turing machine from empty string: verification and suggestions

So I must create a Turing machine which records from empty tape six consecutive 1s. I am allowed to use only 3 states. $z_2$ is the final state. Furthermore, it should be deterministic. Here is my ...
4
votes
0answers
15 views

Fastest known complexity for combinatorial ILP algorithm?

I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming? I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. ...
2
votes
0answers
12 views

How are basic feasible solutions in linear programming related to vertices in its corresponding polytope?

In Section 2.3.3 "Polytopes and LP" of the book "Combinatorial Optimization: Algorithms and Complexity" by Christos H. Papadimitriou, Theorem 2.4 establishes the relation between bfs's (basic feasible ...
0
votes
0answers
27 views

where should I begin : I need to predict power consumption of a household?

I have the power consumption values of a household for 2 year. To preserve privacy I am down sampling this data before sending it to the utility company. My goal is to get back the original data from ...
4
votes
1answer
28 views

Computing modular exponent given order

I want to compute $g^{mn}$ mod $n^2$ where $n=pq$ and I know that $g$ has order $kn$ mod $n^2$ where $m<k$. Is there any clever way of doing it utilizing the order? I have tried other methods of ...
-1
votes
0answers
13 views

Alternative to Visual Logic or Raptor [on hold]

Where can I find a good alternative (online) of Visual Logic or Raptor, to create flowchart / algorithms / pseucode. I'm looking for a software (I can use online) that gives me the same capability of ...
1
vote
1answer
23 views

Filling a matrix with the sum of conditional values

I have $P$ vectors of size $N$ with elements in $\{0,1\}$. Each vector $v$ has a value $\alpha_v$. I would like to Fill a square matrix $M$ of size $N\times N$ in the following way: $$\forall i,j ...
1
vote
0answers
21 views

reduction of maxcut problem

Show that if the MAX CUT decision problem can be solved in polynomial time so can the MAX CUT optimization problem by writing an algorithm that solves the optimization problem using an algorithm for ...
0
votes
1answer
31 views

Particle Swarm Optimization Algorithm

I am studying about Particle Swarm Optimization (PSO) and I was wondering what the user-defined constants in the update equations are for. First update equations: $v(t) = w*v(t) + ...
1
vote
2answers
44 views

Complexity of nested loops [duplicate]

I'm trying to figure out the complexity of the following algorithm. ...
5
votes
0answers
144 views

Travelling with the most efficient path

A friend of mine actually asked me a very interesting computer science related question, and I have been stuck on it for a long time. The problem is: you have to travel $1000$ km. The only gas ...
1
vote
2answers
87 views

Fastest possible way to check what of X is in a string

I am trying to speed up one of my application, on of the places where i can speed up is in my test if a string contains an array of strings. example i have the matches "dog", "cat" "apple" And the ...
1
vote
1answer
113 views

Algorithm to find shortest path between two nodes

I want an algorithm similar to Dijkstra or Bellman-Ford for finding the shortest path between two nodes in a directed graph, but with an additional constraint. The additional constraint is that ...
-1
votes
2answers
53 views

which sorting technique is best? [closed]

we have insertion sort, merge sort, quick sort, heap sort and so on. All these have different complexities and some require extra space like merge sort. Can any one provide some useful trick to ...
-2
votes
1answer
41 views

can we make the quick sort algorithm stable one? [on hold]

if an array possess same keys, the positions won't change after sorting. Can we provide stability for quick sort algorithm.
0
votes
0answers
26 views

Simple criteria to know if the p-nary notation of an integer can generate a tree by preorder traversing?

I am treating with a preorder tree traversal structure(which means sequences where the children of each tree node are listed behind it) now for some other problems and the structure is like: ...
0
votes
1answer
22 views

Infix to prefix

According to this algorithm: http://en.wikipedia.org/wiki/Shunting-yard_algorithm when a left parenthesis is found, it is inserted into the stack, and when a right parenthesis is found, we pop all ...
-2
votes
1answer
83 views

A proof that P != NP [closed]

I came up with the following. Am I doing something wrong? Suppose $P=NP$. Let $A$ be an NP hard problem. Let $A'$ be the polynomial reduction of $A$. By the assumtions, the Halting problem holts for ...
2
votes
0answers
32 views

Constructing orthogonal latin square Parker/Knuth method

I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal latin square. The ...
0
votes
1answer
52 views

Efficiently count frequency of n-grams at start of words

I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as: aaaaa aaaab aaaac aaaad ..... and I have a txt file (organized in rows) with all English words. I have to find ...
0
votes
1answer
86 views

Fastest way to find natural solutions to Linear equation

$$ a_i * x_i + b_i * x_j = N $$ $\text{given } a_i, b_i, N \in \mathbb{N}$ i want to find a solution where $x_i, x_j \in \mathbb{N}$ or output if there exists none. What is the fastest way to ...
1
vote
2answers
143 views

Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice

I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid. The only possible moves are right and up. Also, you can't move below the diagonal y=x. e.g if you're at ...
2
votes
0answers
63 views

Marking nodes of a complete binary tree

Suppose that I have a binary tree with $N = 2^h - 1$ nodes, initially all nodes are unmarked Over time via this process nodes became marked. Suppose that nodes have unique identifiers in range of ...
4
votes
2answers
48 views

Selection, crossover and mutation function choice in genetic algorithms

I have been developing a GA for one of the projects I'm working on. I have everything implemented with no problems and I really like how GAs work in general, it's a really cool and relatively new ...
-2
votes
0answers
25 views

Is A* without an admissible heuristic complete? [closed]

Let us refer to A* without an admissible heuristic algorithm A. If A doesn't have an admissible heuristic, is it still complete?
-1
votes
0answers
39 views

Euler Tour of a tree

I wondering How we can calculate the Euler Tour of a tree ? Should I use DFS for making a Euler Tour array
4
votes
0answers
31 views

Do correlated inputs imply existence of efficient communication protocols?

Suppose that I have 2 parties Alice and Bob. Alice gets an input $X$ and Bob gets input $Y$ where $X, Y$ are $n$-bit strings. In the classic communication complexity world, computing a function such ...
2
votes
1answer
32 views

Finding the Best Fitting Plane Given a Set of 3D Points

Suppose that we have $n$ points in 3D. I want to find a plane $ax + by + cz + d$ such that sum of all the orthogonal distances to the plane is minimum. I read this article. However, I need an ...
1
vote
0answers
26 views

Optimize sequence when item costs are interdependent

I'm tempted to phrase this question notationally, but I may be jumping the gun on the exact problem definition as well. So let me start with the real-world scenario and work forward from there. ...
-1
votes
1answer
36 views

Understanding polynomial equality testing using randomized algorithms

A file is downloaded from a server and is represented as $a = \{0, 1\}^n$. The server has that file as $b = \{0, 1\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized ...
0
votes
0answers
16 views

Need clear explanation to Range updates and Range queries in Binary Indexed trees?

I have gone through few tutorials about how to perform range updates and range queries using Binary indexed tree. I have even gone through Range update + range query with binary indexed trees . I'm ...
0
votes
1answer
39 views

Finding undirected cycles in linear time (triangulating graphs while minimizing degree)

In the article ["Triangulating Planar Graphs While Minimizing the Maximum Degree"] by Kant and Bodlaender [1], Section 4 briefly mentions the extraction of elementary cycles (no repeating ...
2
votes
0answers
10 views

Applications for balanced Boolean function satisfiability

Assume the following problem: Input: A Boolean black-box $U$ of a balanced Boolean function (balanced meaning equal number of satisfying and unsatisfying truth assignments) Output: A satisfying ...
14
votes
1answer
282 views

Lost in a “one directional” concert

You and a friend lost each other on the line to a concert, and neither is sure which of you is further ahead. Formally, each is at some integer coordinate and may only walk towards a higher coordinate ...
1
vote
0answers
21 views

What's the name of this multiparty problem?

Suppose I have $k$ players $P_1,\dots,P_k$ that can communicate with each other directly by sending messages. For defining the inputs, we consider a fixed set of names $N$ which are integers in ...
4
votes
1answer
60 views

Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works

I'm still a beginner in the quantum aspect of computer science (self-studying). So please bear with me if this may sound like a stupid question. I know Hadamard gate transforms qubit into a ...
2
votes
2answers
56 views

first intersection of two arrays of integers - double binary search feasible?

I'm interested to find the fastest possible way to find the first element of an intersection of two integers arrays (first match) Looking for the 'fastest' algorithm I have seen different methods ...
2
votes
1answer
39 views

Optimal wagering to minimize expected time to reach a target payoff

Suppose for simplicity we start off with starting amount $S = 1$ and we wish to reach target amount $T$. To do this we sequentially wager a certain amount and then win that amount with probability $p$ ...
1
vote
1answer
45 views

Anagrams solver based on transitions probability

I have an English dictionary (text file) and the frequency of 2-grams, 3-grams and 4-grams as the beginning of each word. I need to write an algorithm that, with a given word, calculates the possible ...