Problem Detail: I have a multilayer perceptron. It has an input layer with two neurons, a hidden layer with an arbitrary number of neurons, and an output layer with two neurons. Given that randomboolean and targetboolean are random boolean values, and Read More …
Category: Uncategorized
[Solved]: Paper with proof that $L={ a^n b^n mid n geq 0 } cup { a^n b^{2n} mid n geq 0 }$ is not Deterministic Context Free?
Problem Detail: These lecture slides sketch a proof that $L={ a^n b^n mid n geq 0 } cup { a^n b^{2n} mid n geq 0 }$ cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give no references as Read More …
[Solved]: Find hamilton cycle in a directed graph reduced to sat problem
Problem Detail: I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn’t find a working solution, I found a paper that describes how to construct a Read More …
[Solved]: How can I sum pixel values over a rotated rectangle?
Problem Detail: I have an optimization problem in which I need to sum pixel values in an image over a rectangular region. This is a core component of the optimization so it will be done often and the naive solution is Read More …
[Solved]: Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?
Problem Detail: Karlheinz Brandenburg depicts a MP3 encoder like this: Source: MP3 and AAC Explained I marked the FFT as I’m not quite sure why it is actually necessary to perform one. Why can’t the psychoacoustic model be applyed to the Read More …
[Solved]: What does it mean to be Turing reducible?
Problem Detail: I’m confused about what it means to be Turing reducible. I thought I understood what it meant, but apparently not. $A leq B $ Means that A is Turing reducible to B. This means that given an oracle for Read More …
[Solved]: How to Convert a Directed Graph to an Undirected Graph (Adjacency Matrix)
Problem Detail: Given an adjacency matrix, what is an algorithm/pseudo-code to convert a directed graph to an undirected graph without adding additional vertices (does not have to be reversable)? similar question here Asked By : Ibrahim Answered By : Irvin Lim Note that Read More …
[Solved]: How to calculate or estimate how long it takes to solve a recurrence relation?
Problem Detail: I am trying to understand how to solve complex recurrence relations and whether there is a general method or technique to help me. That being said I am not talking about recurrence relations that can be solved using the Read More …
[Solved]: Is DSPACE properly contained in NSPACE?
Problem Detail: It may be a dumb question, but is $mathsf{DSPACE}(f(n)) subset mathsf{NSPACE}(f(n))$ or is $mathsf{DSPACE}(f(n)) subseteq mathsf{NSPACE}(f(n))$? In other words, is the containment relation proper or not? Wikipedia says the first one, while the ComplexityZoo says the other one. Asked Read More …
[Solved]: How to partition a set into a given number of disjoint subsets subject to some conditions?
Problem Detail: I am given a set $Atriangleq{1,ldots,k}$, an integer $sleqslant k$, and non-negative integers $a_{ij}$. My problem is to find $s$ disjoint subsets $S_j$ of ${1,ldots,k}$ such that: $bigcup_{j=1}^s S_j=A$; and $|S_j|leqslant a_{ij}$ for all $iin S_j$ and $j=1,ldots,s$. How Read More …
