0
votes
0answers
2 views

Interpreting a $k$-state $r$-symbol Turing machine as a 1D CA

If I have a $k$-state $r$-symbol Turing machine, and I wish to directly emulate this TM with a 1D CA having a transition function that can only take as input the color of a given cell and its ...
0
votes
0answers
3 views

A BST can be broken by accessing one of its nodes, how can I always make sure this happens?

I have an assignment that asks for this. So I am not looking for the answer itself but a hint on how to find a value that will always break the BST condition by myself. If I have access to any node N ...
0
votes
0answers
3 views

Heuristic for sokoban puzzle problem

I am trying to write IDA* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast.My heuristic is to consider ...
0
votes
0answers
3 views

Time Complexity proof for Segment Tree implementation of the ranged sum problem

I understand that segment trees can be used to find the sum of sub array of A. And that this can done in O(logn) time according to the tutorial here. However I'm not able to prove that the querying ...
0
votes
0answers
6 views

Proving $CVal$ is $RP$-hard

Let CVal be the language of all $<C,s>$ where $s:\{x_1,...,x_n\} \rightarrow \{0,1\}$, such that $C$ is a variable-free Boolean circuit (gates $\wedge$, $\vee$, $\neg$, $0$, $1$), and it outputs ...
0
votes
1answer
5 views

Problem on Floating Point Representation

Consider the floating-point representation 31-24 : Exponent 23-0 : Mantissa The exponent is in 2's complement representation and mantissa is in the sign ...
0
votes
0answers
9 views

A Problem on Set represented as Linked List

Suppose each set is represented as a linked list with elements in arbitray order. Which of the operations among union, intersection, membership, cardinality will be the slowest? (a) ...
-2
votes
1answer
15 views

Can i install Firefox OS apps in android? [on hold]

I saw some cool apps in the firefox webstore & i want them in my android.please can anyone help me with this.
5
votes
1answer
52 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)$?
-1
votes
0answers
7 views

Help with my random story generator [on hold]

I am trying to make a program in c++ which gives a new story every time it is executed. I do not know where to start with. Could some one please help me?
0
votes
1answer
8 views

A Combinational circuit Problem

A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000, 1 by 0001, …, 9 by 1001. A Combinational circuit is to be designed which takes these 4 bits as input and ...
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 ...
0
votes
0answers
4 views

What is the difference between Strict 2Phase Locking and 2Phase Locking?

I have read some notes about the two but yet still confused about why there is a need for the strict 2phase locking. Based on some slides, Two Phase Locking and Strict Two Phase Locking They have ...
0
votes
0answers
11 views

How to solve a priority encoder truth table?

I am stuck in understanding the solution of the following problem. I wish to understand how one would start to solve it. I know the different truth table of each of the four operations but don't get ...
0
votes
0answers
6 views

Attributes value distributed over a range, find number of tuples returned by a given query

Consider the selection of the form $S_{A \leq 200}(r)$ where $r$ is a relation with $1000$ tuples. Assume attribute values of $A$ among the tuples are uniformly distributed in interval $[1, 500]$. ...
0
votes
0answers
8 views

Histogram equalization - to increase “punch” and to limit local gain

The exercise 3.6 (Histogram Equalization) in Szeliski's Computer Vision - Algorithms and Applications asks: Convert the color image to luminance (Section 3.1.2). Compute the histogram, the ...
4
votes
1answer
17 views

How to identify periodic pattern recognition

I'm dealing with a time series that consists of one year's data of the result of some measurement. The time index is in second and the result of the measurement is a non-negative integer. Interestly, ...
0
votes
0answers
14 views

non-regular context free language with logarithmic stack usage [duplicate]

Can you suggest a context-free language $L$, which is: non-regular has a PDA which accepts all $w\in L$ and uses maximum stack space of $\log(|w|)$.
1
vote
1answer
37 views

Can we build a Nondet. decider PDA using two PDAs accepting $L$ and $L^c$

The title pretty much says everything. When talking about turing machines, it can be easily shown that starting from two Machines accepting $L$ and it's complement, one can build a machine which can ...
-1
votes
0answers
10 views

is $g(n)\geq h(n)$ if $g(n)\in \Omega(h(n))$? [duplicate]

Let $g$ and $h$ be any functions $N\rightarrow (0,\infty)$. Then $g(n)\in \Omega(h(n))$ implies there is some $N\in\mathbb{N}$ such that $g(n)\geq h(n)$ for all $n\geq N$. I can't seem to find a ...
4
votes
1answer
25 views

Common method for solving satisfiability problems which lie in P

I know from Schaefer's Dichotomy Theorem that only a few types of satisfiability problems are in P and any other problem is NP-complete. However, all of the algorithms I know for them use specific ...
0
votes
2answers
26 views

Listing all possible train routes

I'm interested whether there is the standard solution to the following problem. Some number of train routes is given: Route1: First City -> Next City -> ... -> Last City Route2: ... ... We need to ...
1
vote
1answer
6 views

Finding a solution to the following conditions?

So for these 5 conditions, I am trying to find the solution/formula for them. What would $a_n$ equal basically? If it helps, the recurrence relation these 5 conditions were generated from was $a_n = ...
2
votes
1answer
20 views

Proving $DTime(n^3) \subset PSpace$

It is pretty obvious that $DTime(n^3) \subseteq PSpace$, since $DTime(n^3) \subseteq DSpace(n^3) \subseteq PSpace$, but I fail to see how to find such a language $L$ so that $L\in PSpace\,\,\,$ yet ...
9
votes
1answer
74 views

Why is this argument for $P\neq NP$ wrong?

I know its silly, but i managed to confuse myself and i need help settling this Suppose $P=NP$, then clearly for every oracle $A$ we have $P^A=NP^A$ which contradicts the fact that there exists some ...
-2
votes
0answers
19 views

I need code of C for this function: [on hold]

I need code of C for this function: unsigned int shi (unsigned int x, unsigned int y); Description: The function shi returns the result of shifting the argument x to the right by the value passed in ...
0
votes
0answers
21 views

NXOR for 2 inputs on a turing machine, in P?

Question: L is the language of $\langle M,x,y\rangle$ s.t TM $M$ accepts both inputs $x$ and $y$ or doesn't accept either. Prove that given some $M$, finding 2 inputs $x$ and $y$ s.t. $\langle ...
0
votes
1answer
36 views

Turing Machine notation

I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class. The question gives us a string α ϵ {0,1}* and the function int(α) that changes a binary ...
0
votes
1answer
16 views

Sorted-greedy for Load Balancing Problem

In load balancing problem we have $m$ machines and $n$ jobs, each taking processing time $t_j$. Total processing time on the machine $i$ is $T_i =\sum_{j\in A(i)}{t_j}$, where $A(i)$ is the set of ...
0
votes
0answers
14 views

¿Are operations with very large variables posible? [on hold]

¿Could a 64-bit processor calculate the graph of a fourteenth degree polynomial function whose constants [a; o] are all aprox. as big as 2^999? And if so, ¿how would it do it?
2
votes
1answer
28 views

the meaning of relativization

I don't understand the notion of relativization. I expose with an example. Consider a class A that contains P, e.g. NP. Why P^A is not necessarily equal to A? I can naively think that if one can ...
7
votes
0answers
49 views

Who coined the term “machine learning”?

I'm trying to figure out who coined the term "machine learning". An ancillary question is from where is Arthur Samuel cited as defining the field of "machine learning" in 1959 as: the field of ...
0
votes
0answers
10 views

Why cannot a string be initialized through a for loop and an array? [on hold]

I used a char str[10]; Then got number of characters through scanf. Then used for(i=0;i
1
vote
0answers
7 views

Difference between BSP model and synchronous round model in distributed computing

I've recently learned about distributed computing and the synchronous model where, assuming a complete network and no crashes, in each round the following happens: every node can send a message to ...
2
votes
1answer
28 views

2-SAT or 3-SAT or k-SAT in AC-0

This may be an elementary question, but I'm new to circuit complexity. Does 2-SAT in CNF form belong to the complexity class AC$^0$? It seems simple enough to construct an AC$^0$ circuit of depth 2 ...
0
votes
1answer
26 views

Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$?

Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$? Also, why is $f(n) = \Theta(g(n))$ where $f(n) = n^{\log_49}$ and $g(n) = 3^{\log_2 n}$? I know what notations ...
0
votes
3answers
29 views

Complexity of BST

I have the following pseudo-code for printing all nodes of a BST : ...
3
votes
1answer
174 views

What is the exact meaning of a Predicate, decidability and computability?

In the Computability, Complexity and Languages book written by Davis in page 5 he defines a predicate as: By a predicate or a Boolean-valued function on a set ...
0
votes
1answer
18 views

Reweight general weighted graph to distinct graph for using Borůvka's

Is it possible to re-weight a generally-weighted graph to a distinctly-weighted graph to apply Borůvka's algorithm (wiki) for minimum spanning tree to it? I can't seem to think of a way to make a ...
-2
votes
1answer
15 views

Language L and its complementary both not recursively enumerable?

Is it possible to proof for a Language L and its L-complemented to be both not recursively enumerable? Can be useful to consider the (Ld) diagonalization Language? thank you.
2
votes
0answers
24 views

What are the fundamental principles/algorithms on the process of equation solving?

I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For ...
7
votes
2answers
85 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
1answer
45 views

Why is the complexity of this nested for loop not $O(n^2)$?

I have the following pseudo-code: mystery(n): if n <= 50 : for i = 1 ... n : for j = 1 ... n : print i*j else : mystery(n-1) For ...
3
votes
0answers
15 views

Birkhoff-von Neumann theorem for bistochastic digraphs

A weighted digraph (with loops) is bistochastic, iff the weights are non-negative, for all non-sink nodes, the sum of the edge weights of the out-edges is $1$, and for all non-source nodes, the sum ...
-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
1answer
69 views

What is meant by the notation L(…)?

I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of. I have a question to find out the relationship ...
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
9 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. ...
4
votes
1answer
90 views

Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$. Obviously, this class is a ...
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 ...

15 30 50 per page