# All Questions

11 views

### Is “Fill-in” word puzzle NP-complete?

So "fill-in" is a game where an $n \times n$ board is given with certain cells removed, and certain remaining cells are filled in with letters. Then a list of words is given. The problem is to fill in ...
7 views

### Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two (sets of, possibly) points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. ...
17 views

### Categorizing scanned documents by searching for a special text [on hold]

I have thousands of scanned images and a limited number of categories. Each image sits in a category. Images are text documents and their category is detected by document title or a text found in all ...
6 views

### Worst-case recursion depth for guessing numbers in a Sudoku puzzle when certain polynomial-time deduction rules are used

So for an arbitrary $n^2 \times n^2$ Sudoku puzzle, there are rules for inferring values and auxillary information in cells that run in polynomial time, e.g. using the filled in values to check to see ...
23 views

### What is the term for this set

I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set? A common practical use case would be ...
8 views

### Xampp installation [on hold]

Windows7 and Windows8 are installed on separate drives C: and E: respectively on my destop PC. XAMPP is installed on C: where Windows7 is installed and running. Can I install XAMPP on E: where ...
7 views

### How to Integrate Our laptop Webcam with our JSP page.? [on hold]

How to integrate my jsp Page with webcam.
52 views

### Conceptual question about entropy and information

Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
26 views

### Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square?

This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula ...
50 views

### What kind of construct is this? [on hold]

Just for fun, I wanted to define a function in Python that you call like this: add(1)(2)() = 3 add(1)(2)(3)() = 6 I put this together: ...
42 views

### Non Deterministic PDA accepted language not clear

This is a PDA from the lecture slides I'm using: They say it accepts all words that contain double a's. While it makes some sense it's not full proof. What prevents the second a to be read in the ...
30 views

### Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes?

So I was thinking about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with $2 \times 1$ dominoes. If $m \leq n$, then we can use recursion on $n$ ...
48 views

### Edit distance (Levenshtein-Distance) algorithm explanation

I want to calculate the edit distance (aka Levenshtein-Distance) between two words: «solo» and «oslo». According to this site we'll get the result matrix: What I don't understand is: In case of ...
24 views

### Turing degree of incomputable definable reals [on hold]

What would be the turing degree of incomputable definable real numbers and would every incomputable definable real numbers share same turing degree?
27 views

There is a logical address 87536 which needs to be translated into physical address. Here is the page table Page table:(page # - Page Frame #) ...
12 views

### What are Pairwise intensity comparison in binary image descriptors?

Recently many binary descriptors have come u like BRIEF, ORB etc. A common ste in such descriptors is to chose a sampling pattern and perform pairwise intensity comparisons for constructing the binary ...
73 views

### Unable to understand an inequality in an application of the pumping lemma for context-free languages

The problem Prove that the language $\qquad L = \{a^n b^j \mid n = j^2\}$ is not context free using pumping lemma. Approach taken by the book To prove such statements, the book takes the ...
39 views

### Can Turing machine, when ran for infinite time, check whether the tape is written infinite times? [on hold]

So let there be some ordinary Turing machine. Now the machines run for infinite time, just writing some non-empty symbol to one space (state) of the infinite tape and moving to the next space (state). ...
32 views

### Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?

Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that ...
165 views

### Is it possible for a graph to have two different minimum spanning tree

I am suppose to create a minimum spanning tree from this graph below I got this answer However this is my textbook answer Based on what i have learnt , I think my answer and the textbook ...
32 views

### Is there a vanishing gradient in RNN training? [on hold]

One of the often cited issues in recurrent neural network training is the vanishing gradient problem [1,2,3,4]. However, I came across several papers by Anton Maximilian Schaefer, Steffen Udluft and ...
43 views

### Variable Length Encoding of Integers

I was just researching Fibonacci encoding of integers. Numbers are encoded in binary and where no two consecutive bits are equal to 1 - other than to terminate the number. Now other schemes are ...
10 views

### Can I customize the phoneme structure of a word by Festival TTS? [on hold]

I am using Festival TTS for getting monophone structure of a word. Festival is using predefined set of phonemes, which differs from the phoneme list I have create my ASR HMM Model. Can I modify the ...
36 views

### Is there a limit on the length of queries for the oracle?

Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My ...
30 views

### What are the minimum memory requirments a microprocessors must have to perform any calculation?

Please excuse my ignorance in low level things. A lot of the written below might be very wrong. As far as I understand (and I might be very wrong), there are two types of memory locations a ...
63 views

### Graph isomorphism problem for graphs with colored directed edges

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
37 views

### Get up to speed with algorithms [on hold]

Does anyone have any advice about how I can fast track my understanding of what these types of algorithms mean: http://en.wikipedia.org/wiki/Monad_(category_theory) I don't want to have to sit 3 ...
29 views

### Why is it not decidable if a TM writes a given symbol?

The problem Does a TM M on input w ever writes a particular symbol on its tape? is undecidable but we can always check if the TM ever writes that particular symbol on the tape when input string ...
43 views

### Progressive discrete multifunction optimization

I have a set of functions $F$. The functions effectively take a set $S$ that is always a subset of a global set of all possible values $G$, where $|G|>1000$. (alternatively, they could take a ...
19 views

### What difference does it make when universal classical gates in quantum computation are reversible but not unitary?

As I've come across Grovers algorithm I dont understand why when computing F(X), which is an oracle function people use classical reversible circuits(toffoli, fredkin) to evaluate the circuit. Why ...
30 views

### Proof of Strong Duality Via Farkas Lemma

I am trying to prove what is often titled the strong duality theorem. There is a hint in the book that I'm following, and I want to follow the method they have outlined for me. I will outline the ...
73 views

### Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
47 views

20 views

### Worst/Best cases [on hold]

For the two functions, would their worst/best Big O cases change compared to each others? If so, how would they change. I believe that when dealing with Big O, order is the only thing that matters, so ...
27 views

### Big O notation for Python [on hold]

I am unsure of the order of growth for these two procedures in Python. Can someone please explain: def modten(n): return n%10 and ...
40 views

### How Google generates its questions

When you use google, beside the web sites that it shows you it shows you some searches related to yours at the bottom of the page. Does anyone have any ideas how Google generates those ones?
19 views

### State of optimal substructure? [closed]

My teacher has told me that I need to do the proof of the optimal substructure exaplaining the "state". I have no idea what a state is . I have chosen the matrix chain product as a dynamic programming ...
59 views

### Does #$P$-Completeness imply approximation hardness?

Let $\Pi$ be some counting problem which is known to be #$P$-Complete. Does it imply that $\Pi$ is $APX$-hard (i.e. no PTAS for the problem exists unless $P=NP$)?
13 views

### Lexicographical position of a string in its type class

I have the following problem: Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists ...
102 views

### Does programming language detection need more input than natural language detection?

I wonder which one of the two needs a larger input to achieve a decent accuracy: programming language detection or natural language detection? More details: Definition of Language detection: ...
37 views

### Does FACTORING have optimal substructure or analog to it?

Is there any approach to FACTORING that can leverage optimal substructure allowing the problem to be decomposed into smaller subproblems? That is, perhaps being unnecessarily verbose, until an easily ...