All Questions

Filter by
Sorted by
Tagged with
4
votes
3answers
390 views

Concept of reduction and algorithm

Suppose that someone found an algorithm A for a NP problem (that is not NP-complete) that uses an algorithm B for PSPACE-complete or #P-complete problem during execution. (Remaining part of the ...
4
votes
1answer
172 views

Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$?

Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial ...
8
votes
1answer
19k views

Left recursion and left factoring -- which one goes first?

if I have a grammar having a production that contains both left recursion and left factoring like $\qquad \displaystyle F \to FBa \mid cDS \mid c$ which one has priority, left recursion or left ...
16
votes
2answers
4k views

Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
4
votes
1answer
296 views

Vertex coloring with an upper bound on the degree of the nodes

Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices ...
13
votes
2answers
2k views

Is Karp Reduction identical to Levin Reduction

Definition: Karp Reduction A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if ...
0
votes
1answer
703 views

Time series probability and mutual information

There is a time series of say $100$ data points. I wish to assign symbols of $0, 1, 2$ for each unique data point. The issue is I have tried but got stuck since no matter I specify the symbols, the ...
20
votes
1answer
1k views

Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
5
votes
1answer
631 views

Algorithm for type conversion / signature matching

I'm working on an expression typing system and looking for insights on what algorithms may be available which solve my problem -- or a proof that its complexity is too high to be reasonable to ...
5
votes
1answer
286 views

The $\text{k-key}$ problem

Given an undirected graph, I define a structure called k-key as a path containing $k$ vertices which are connected to a simple cycle which contains $k$ vertices as well. Here's the k-key problem: ...
1
vote
2answers
548 views

Existence of a route following one-way streets

I am trying to understand the approach for this problem: "If all streets are one way, there is still a legal way to drive from one intersection to another" The question is to prove that it can ...
6
votes
1answer
250 views

regular expression given the language

The language is: $$ L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \} $$ My attempt at an answer: $$ (a \cup b)^{3k} $$ This will work if the a OR b can change for each instance in the string that is (...
10
votes
1answer
1k views

Prove that a boolean function computable in T(n) by a RAM machine is in DTIME(T(n)^2)

The question is exercise 1.9 from Arora-Barak's book Computational Complexity — A Modern Approach: Define a RAM Turing machine to be a Turing machine that has random access memory. We formalize this ...
4
votes
1answer
7k views

Is finding the longest path of a graph NP-complete?

The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of ...
21
votes
3answers
10k views

How hard is finding the discrete logarithm?

The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$. I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what ...
5
votes
3answers
396 views

Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
1
vote
2answers
194 views

How do we distinguish NP-complete problems from other NP problems?

I just learned that when we have a polynomial algorithm for NP-complete problems, it is possible to use that algorithm to solve all NP problems. So, the question is how we then distinguish non-NP-...
5
votes
2answers
3k views

NP-completeness and NP problems

Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not ...
1
vote
1answer
535 views

A regular expression for a given formal language

I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and ...
23
votes
2answers
2k views

Collectively pay the bill problem

There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars. Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm. First, ...
5
votes
1answer
384 views

Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order: $\qquad \displaystyle a \leq b \iff (a,b)...
11
votes
2answers
155 views

An $\mathbb F$-algebra as input to an algorithm

I want to specify, what it means to give an algebra as input to an algorithm and didn't find very much literature about it. So first I want to ask if you can recommend a book or paper that deals with ...
4
votes
1answer
140 views

Witness for the $EU(\phi_1,\phi_2)$ using BDDs

I wanted ask if you know an algorithm to find the witness for $EU(\phi_1,\phi_2)$ (CTL formula "Exist Until") using BDDs (Binary Decision Diagram). In pratice you should use the fixed point for ...
32
votes
1answer
2k views

Does there exist a Turing complete typed lambda calculus?

Do there exist any Turing complete typed lambda calculi? If so, what are a few examples?
8
votes
1answer
926 views

Historical relation between computer science and the theory of dynamical systems

I have asked this question at math.stackexchange, but I have been redirected here. My question is, if there is any historical relation between the fields of Dynamical systems (and related fields such ...
5
votes
1answer
677 views

NP-completeness of graph isomorphism through edge contractions with an edge validity condition

Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
1
vote
1answer
521 views

NP-completeness of scheduling to minimise tardy tasks with release times

In "Computers and Intractability A Guide to the Theory of NP-Completeness" textbook pp 236, "Sequencing to minimize tardy tasks" is NP-complete. To be specific the problem is as follows: For each ...
3
votes
1answer
2k views

Queue that can sort by multiple priorities?

I have a high interest in priority-queues (E.g., see my answers on: Does there exist a priority queue with $O(1)$ extracts?), and was wondering if there is a priority-queue or similar data-structure ...
14
votes
1answer
16k views

Expected number of swaps in bubble sort

Given an array $A$ of $N$ integers, each element in the array can be increased by a fixed number $b$ with some probability $p[i]$, $0 \leq i < n$. I have to find the expected number of swaps that ...
8
votes
1answer
509 views

Is this language Context-Free?

Is the language $$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$ context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.
3
votes
1answer
244 views

What is the significance of the semi clustering formula in the Google Pregel paper?

Semi clustering algorithm is mentioned in the Google Pregel paper. The score of a semi cluster is calculated using the below formula $\qquad \displaystyle S_c =\frac{I_c - f_BB_c}{\frac{1}{2}V_c(V_c -...
15
votes
2answers
22k views

Prove that every two longest paths have at least one vertex in common

If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common. I think that that common vertex ...
5
votes
1answer
233 views

When does the function mapping a string to its prefix-free Kolmogorov complexity halt?

In Algorithmic Randomness and Complexity from Downey and Hirschfeldt, it is stated on page 129 that $\qquad \displaystyle \sum_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$, where $K(\sigma)\...
4
votes
1answer
508 views

Using hash tables instead of lists for buckets in hash tables

Say instead of using a linked list as buckets for a hash table of size $m$, we use another hash table of size $p$ as buckets this time. What would be the average case for this problem? I looked up ...
4
votes
1answer
357 views

Is there a search engine over Artificial Intelligence and Machine Learning -related sites?

Sometimes it is necessary to dig into Artificial Intelligence or specifically Machine Learning problems to make a research. Common googling (in my own experience) usually doesn't help much due to a ...
0
votes
3answers
1k views

What is the average search complexity of perfect hashing?

The lookup time in perfect hash-tables is $O(1)$ in the worst case. Does that simply mean that the average should be $\leq O(1)$?
3
votes
1answer
610 views

How to random-generate a graph with Pareto-Lognormal degree nodes?

I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution. Where can I ...
23
votes
3answers
3k views

Is rejection sampling the only way to get a truly uniform distribution of random numbers?

Suppose that we have a random generator that outputs numbers in the range $[0..R-1]$ with uniform distribution and we need to generate random numbers in the range $[0..N-1]$ with uniform distribution. ...
10
votes
2answers
3k views

What's the complexity of Spearman's rank correlation coefficient computation?

I've been studying the Spearman's rank correlation coefficient $\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$. for two ...
10
votes
1answer
159 views

Is this language Context-Free? [duplicate]

Possible Duplicate: Is this language Context-Free? The language is defined by $$(a+b)^*-\{(a^nb^n)^n\mid n \geq1 \}$$ is Context-Free Language? I believe that the answer is that it is not a CFL'...
7
votes
2answers
530 views

Balanced weighting of edges in cactus graph

Given a cactus, we want to weight its edges in such a way that For each vertex, the sum of the weights of edges incident to the vertex is no more than 1. The sum of all edge weights is maximized. ...
3
votes
1answer
347 views

Operations on OBDD: negation through Shannon's expansion

I have a problem with the application of the Shannon expansion for to obtain the negation of a formula boolean, than will need for implement the negation operator on OBDD (Order Binary Decision ...
4
votes
1answer
332 views

Time complexity version of the Church-Turing Thesis

There's a lot of debate about what exactly the Church-Turing thesis is, but roughly it's the argument that "undecidable" should be considered equivalent to "undecidable by a universal turing machine." ...
6
votes
4answers
3k views

Finding the Largest "Ordered" Difference in Elements of an Array

Suppose we are given an array of positive integers $P = [p_1, p_2, \dots, p_N]$ where each $p_i$ represents the price of a product on a different day $i = 1 \dots N$. I would like to design an ...
8
votes
1answer
652 views

How to detect stack order?

We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current ...
2
votes
2answers
4k views

Partition of a set of integer into 3 subsets of approximately equal sum

I'm having a very hard time trying to figure out how to solve this problem efficiently. Let me describe how it goes: "A hard working mom bought several fruits with different nutritional values for ...
11
votes
4answers
4k views

Most efficient algorithm to print 1-100 using a given random number generator

We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50. We may use only this random number generator to ...
5
votes
3answers
1k views

Finding the $k$th largest element in an evolving query data structure

Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element ...
1
vote
1answer
2k views

3-dimensional matching approximation algorithm (implementation details)

I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below: How can I construct the maximum matching M_r in S_r in linear time in line 8? $X, Y,...
39
votes
4answers
9k views

Worst case $O(n \ln n)$ in place stable sort?

I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources? Just a reminder, in place means it uses the ...

15 30 50 per page
1
821 822
823
824 825
838