# All Questions

31,062 questions
13 views

### What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not

Provide any polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not. For example, consider the following two ...
17 views

### Help with figuring out if MAX(L) is a CF language

We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as: $MAX(L)$ = {$w_1 \in L$|...
28 views

22 views

48 views

### Thought process for the following problem?

We are given a 1-d array and we have to return the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or ...
26 views

### Substituting a term for a variable in a context

At this link you can read Nicola Gambino's slides on one way to approach the formal syntax of Martin-Löf dependent type theory. (They are concise and very readable.) On slide 10, he gives a standard ...
8 views

### An LALR(1) parser for a grammar G can have shift-reduce (S-R) conflicts if and only if The LR(1) parser for G has S-R conflicts [on hold]

This is an interesting property, I have given the explanation below.
25 views

### Space(n) and Space(n^2) implications

I've a problem where I have to prove the following statements: (i) if $SPACE(n) \subseteq P \implies SPACE(n^2) \subseteq P$ (ii) if $P = SPACE(n) \implies SPACE(n) = SPACE(n^2)$ For the Space ...
19 views

### Determining the DP subproblem given a problem

I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems. For example, consider 2 similar problems. Given a set of 1, 2, and 3 steps you can take, ...
8 views

### Apache server runs only in debugging mode [closed]

I have a code base in Java and I am using Intellij Ultimate edition. When I run the server normally, it fails and gives exception due to TimeoutException. When I run the server in debug-mode and place ...
26 views

### One-taped RAM vs Multi-taped RAM

In Turing Machine, we know that there's (fine-grained complexity) difference between one-tape, 2-taped and multi-taped TM, even though they could be simulated efficiently. (Well, actually I'm not ...
17 views

### Operator Precedence Parsing

In operator precedence parsing we have the rule that no production is allowed to have two adjacent non-terminals or an epsilon production. Hence, the production $S \to ab$ is allowed but not $S \to AB$...
49 views
+50

### What is the generating algorithm for the “komb” instances found on satcompetition.org?

For the 2017 and 2018 Random SAT Tracks of the SAT Competition ran by the International Conference on Theory and Applications of Satisfiability Testing there are small, yet difficult, random 3-SAT ...
15 views

### Go Back N question(netwrok)

Hello I am trying to understand the GBN protocol and I encountered the following question during my homework. Assume that we have GBN protocol with a window size of 20. The sender sends 15 packets ...
100 views

### Matching Algorithm - How to maximize matched quantity with unique matching rules?

Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules: \begin{aligned} A\leftrightarrow B\\ C\leftrightarrow D\\ B+C\leftrightarrow F\\ D+A\...
20 views

### Permutation to maximise strings' common prefix

Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix. Given a set $S=\{(s,w)\}$ of pairs of ...
30 views

### Is There A Difference Between Search And Optimization?

Is one a subset of the other? Two differentiable processes? The same thing? In the textbook "AI: A Modern Approach", the terms seem to be used interchangeably.
12 views

### Balanced $\epsilon$-separated partitioning by a hyperplane

Suppose we have $m$ points in $R^n$ and $\epsilon>0$ is a given constant. How can we find a hyperplane that the number of points that are $\epsilon$-close to it is minimum, with the constraint that ...
21 views

### Why does an extended transition function not work if the string does not result in a final state? [on hold]

If I am not wrong a string is only accepted by a finite automata if the string results in a final state. Why is that? With symbols we can transition into another non-final state, why is that not ...
25 views

### Prove Subset-Sum is NP-complete - Alternative reduction?

It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the ...
125 views
+100

### How does a Turing machine with one tape read its input?

It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that ...
40 views

57 views

### Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
21 views

### Why does paging not have external fragmentation?

I have read that paging does not suffer from external fragmentation as the frames and the pages are all of the equal sizes, but when we store a last level page table in a frame at that time it may not ...
68 views

### Is computer science really a branch or sub-branch of physics? [closed]

Given that a computer is basically an electronic machine, is computer science really a branch of electronics, which is in turn a branch of physics?
27 views

### count all possible paths of length n in an undirected graph with use of dynamic programming [duplicate]

Given is an infinitely large grid graph. Use dynamic programming to calculate the number of possible paths of a given length n from a given start node, so that fjor every path applies: a) no vertex ...
9 views

### Is it possible to compute a whole convolution layer at once?

I have an input of 32×32×3 and I want to feed it to a convolution layer that output 32×32×16 feature maps. I know that I can compute a single feature map as matrix multiplication. But my question is, ...
42 views

### pseudo-polynomial reduction from 3-Partition to Partition

A problem $\Pi'$ is pseudo-polynomially reducible to the problem $\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially ...