# All Questions

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
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.
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)$?
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?
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 ...
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 ...
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 ...
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 ...
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]$. ...
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 ...
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, ...
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|)$.
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 ...
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 ...
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 ...
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 ...
6 views

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 ...
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 ...
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?
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 ...
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 ...
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
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 ...
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 ...
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 ...
29 views

### Complexity of BST

I have the following pseudo-code for printing all nodes of a BST : ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...