-1
votes
0answers
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 ...
1
vote
0answers
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. ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-2
votes
0answers
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 ...
-1
votes
0answers
7 views
2
votes
2answers
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 ...
2
votes
0answers
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 ...
-3
votes
0answers
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: ...
1
vote
1answer
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 ...
2
votes
1answer
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$ ...
1
vote
2answers
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 ...
-2
votes
1answer
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?
-1
votes
0answers
27 views

Translating a logical address into a physical address [on hold]

There is a logical address 87536 which needs to be translated into physical address. Here is the page table Page table:(page # - Page Frame #) ...
0
votes
0answers
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 ...
1
vote
3answers
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 ...
-1
votes
0answers
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). ...
3
votes
1answer
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
2
votes
5answers
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 ...
5
votes
0answers
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 ...
0
votes
1answer
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 ...
-2
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
8
votes
1answer
47 views

Is path induction constructive?

I'm reading through the HoTT book and I have a hard time with path induction. When I look at the type in the section 1.12.1: $$\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}} ...
-3
votes
1answer
34 views

Find an unambiguous grammar [on hold]

S → aS | aSbS | (empty) where the alphabet is {a,b} in other words, the set of strings where any prefix has at least as many 'a's as 'b's.
4
votes
1answer
41 views

What is $Prop$ in the calculus of constructions?

I'm looking at the Calculus of Constructions and its place in the Lambda Cube. If I understand correctly, each axis of the cube can be thought of as adding another operation involving types to the ...
0
votes
0answers
47 views

Parallel single source shortest path algorithm

Is there a deterministic parallel single-source shortest path algorithm (for graphs with non-negative edge-weights) that runs in sublinear time? The number of processors may depend on $n$ or $m$ ...
2
votes
2answers
79 views

Quickly locating nearest rectangle from a point

The problem is as follows: There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the ...
3
votes
0answers
23 views

Does $\#W$[1]-hardness imply approximation hardness?

Let $\Pi$ be a parametrized counting problem, where the parameter is the solution cost, e.g. counting the number of $k$-sized vertex cover in a graph, parametrized by $k$. Assume that $\Pi$ is ...
4
votes
2answers
35 views

Incorporating newline-as-statement-terminator heuristics into context-free languages

Several block structured languages (Scala, Go, Ruby, Julia, Quorum, ...) use semicolons as statement terminators, but allow newlines instead of semicolons under certain circumstances. My question is: ...
3
votes
1answer
47 views

Meaning of type inference rule for abstraction in lambda-calculus

Below is a snippet about simply typed lambda-calculus from CS152: Programming Languages Lecture 9 | Simply Typed Lambda Calculus, on printed‑page 15, indexed 23. $$ \frac {\Gamma, x: \tau_1 \vdash e: ...
-2
votes
0answers
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 ...
-1
votes
0answers
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 ...
0
votes
0answers
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?
-1
votes
0answers
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 ...
7
votes
1answer
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$)?
3
votes
1answer
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 ...
2
votes
3answers
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: ...
3
votes
1answer
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 ...
3
votes
0answers
19 views

Visualization of Lamport's three-dimensional “space-time diagram” with introduced “tick lines”

In the third page (the third paragraph in the right column) of the paper "Time, Clocks, and the Ordering of Events in a Distributed System" by Leslie Lamport, it says that The reader may find it ...
0
votes
1answer
46 views

Calculate winding number

How can one calculate the winding number of a polygon given as a list of vertices in some (counter-clockwise or clockwise) order? The complexity of the algorithm must be linear time.

15 30 50 per page