texts:
Given a list $C=[c_1,c_2,\dots,c_k]$  of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total value $n$. The order within the handful does not matter, and there is an infinite supply of each variety of coin.
What is the state-of-the-art algorithm to compute $f(n,C)$?

Equivalently, $f(n,C)$ is the number of ways to choose non-negative integers $x_i$ so that $n=\sum_{i=1}^k x_ic_i$.
The list $C$ can have repeats, and the interpretation is that there are two varieties of coin with the same value. For example, $f(3,[2,1,1])=6$. Letting $A$ and $B$ be the coins of value $1$, and $C$ be the coin of value $2$, the $6$ possible handfuls are
$$
(A,A,A),(A,A,B),(A,B,B),(B,B,B),(A,C),(B,C)
$$
I can think of two solutions. Which is faster depends on $n$ and $C$.

Dynamic programming: Let $C'$ denote $C$ with its last entry removed. A use-it-or-lose-it argument gives $$f(n,C) =  f(n-c_k,C)+f(n,C') .$$ This lets you compute $f(n,C)$ by filling out an $n\times k$ DP table, which takes $$\boxed{\Theta(nk)}$$ additions and look-ups.

Matrix exponentiation: I will illustrated in the case $C=[2,3,4]$. Letting $a_n=f(n,C)$, then $a_n$ satisfies the recurrence (see https://cs.stackexchange.com/a/87810/24590)
$$
a_n = a_{n-2}+a_{n-3}+a_{n-4}-a_{n-5}-a_{n-6}-a_{n-7}+a_{n-9}
$$
Any linear recurrence can be solved by computing the $n^{th}$ power of a certain matrix. In this case, the recurrence has order $c_1+\dots+c_k$, so this algorithm takes
$$
\boxed{O(\log n \cdot M(c_1+\dots+c_k))}
$$
arithmetic operations, where $M(k)$ is the number of arithmetic operations required when multiplying two $k\times k$ matrices (naively $M(k)=k^3$, state of the art is $k^{2.3728639}$).  We get $\log n$ by using exponentiation by squaring.

The second algorithm is asymptotically much better as $n\to\infty$, but the first is better when the sum of $C$ is large.

Are there any known faster algorithms?


texts: Proving DPATH is NP-complete by a reduction from HAMPATH

texts:
I have a language DPATH that I'm trying to complete is NP-complete.

DPATH = {<G, a1,...,an>|G is a digraph with a directed path that covers the sequence
a1,...,an}

All of the nodes in the sequence has to be visited exactly one time, but it doesn't matter in which order they are visited.

I am trying to show a reduction from HAMPATH to DPATH but I'm having some difficulties. When given input <G, s, t> I have to create a computable function f, that outputs <G, a1,...,an>. Can i say that a1 = s, and an = t, and that each node that the hamiltonian path goes through is labeled with a node from the sequence? My problem with this, is that what if the HAMPATH graph has more nodes than the sequence? Do I have to take this into account when creating the reduction?


texts: Definition of a reachable ancestor (Skiena TADM 2nd ed section 5.9.2)

texts:
In The Algorithm Design Manual section 5.9.2, covering graphs and articulation vertices, Steven Skiena writes

  Let reachable_ancestor[v] denote the earliest reachable ancestor of vertex v,
  meaning the oldest ancestor of v that we can reach by a combination of tree edges
  and back edges.

This phrasing is ambiguous.  On the errata page of his website, he clarifies:

  it is clearer to say:
  "denote the earliest reachable ancestor of vertex v, meaning the
  oldest ancestor of v that we can reach from a descendant of $v$
  by using a back edge."

But to me, this phrasing is still somewhat ambiguous.  Consider the following four-vertex graph G:

    A
    |
+ - B
|   |
|   C
|   |
+ - D

We conduct an alphabetical depth-first search (DB is a back edge).  According to Skiena's revised definition, it would seem that A is a reachable ancestor of C as follows:  D is a descendent of C, and we can reach A from D using a back edge by following the path DBA.  However, execution of Skiena's code for finding articulation vertices via depth-first search on G results in reachable_ancestor[C] = B, not A; therefore I don't think he intends for A to count as a reachable ancestor of C.

Might it be more accurate to say that reachable_ancestor is the
oldest ancestor of v that we can reach from a descendant of v
by using a back edge but without passing through any other ancestors of v?


texts: undefined alphabet of observations in HMM

texts:
how to represent an observation matrix if we do not have a defined observation alphabet?
I'm working on extraction of data in a text.


texts: Normalizing edge weights and the effect on Dijkstra's algorithm

texts: If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would finding the minimum weight (most negative weight) $w$ and adding the absolute value to every edge's weight preserve the shortest path, and get rid of the possibility of a negative cycle in one fell swoop? I can't seem to find any good literature on this, which makes me think that it can't be true.


texts: Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?

texts:
According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved versions.

Also according to my lecture, an approximation scheme is called "fully polynomial time approximation scheme (FPTAS)", if its run time is polynomial in $1/\epsilon$ and polynomial in the encoding length of the instance (usually, the input size is denoted by $n$, such that the encoding length would be $\log n$).

The algorithm has running time $\mathcal{O}(n\log(n))+\mathcal{O}(n + (1/\epsilon)^2)$. I do agree on this being polynomial in $1/\epsilon$, but how is it polynomial in the encoding length of $n$?

The part $\mathcal{O}(n\log(n))$ of the run time is due to sorting the list of $n$ items. As far as I'm capable of judging this, this is polynomial in $n$, but not polynomial in $\log n$.

Where am I wrong?


texts: Special Monotone SAT problem: NP complete?

texts:
Say we have the set $X=\{ x_1, x_2, \dots \}$ of variables. Then we consider the following problem: Is the formula
$$\bigwedge_{(a,b,c) \in A}(a \vee b \vee c) \wedge \bigwedge_{(a,b,c) \in B}(\neg a \vee \neg b \vee \neg c)$$
for $A,B \subset X^3$ satisfiable.

This problem has been called Montone-3-Sat before and it is known to be NP-complete.

My question is: If we assume that $A=B$ has to hold, is the problem still NP-complete? I.e. we ask if we can color vertices in such a way that always specific three of them do not have the same color.

The results I have found on the internet confuse me a bit, because I believe the definitions of Monotone-Sat, Not-All-Equal-Sat are not always the same.  The definitions of NAE3SAT I've seen allow arbitrary 3-CNF-formulae as input, so this doesn't seem the same as that.


texts: Building a context-free grammar for this language

texts:
I have a hard time creating a context-free grammar for the language

$$L=\{(a^n)^*(b^m)^*y\mid y\in\{a,b\}^*,\ |y|=n+m \}\,.$$

Any help breaking down the problem is appreciated, since I'm getting nowhere with this one...


texts: What is the difference between speculative execution & branch prediction?

texts: In computer architecture I'm confused between speculative execution & branch prediction. Are the same or different?


texts:
Kriegspiel chess is a variant of chess in which each player is not aware of where the opponent's pieces are. In a human match, a trusted intermediary relays piece losses, legality of moves etc. This is, of course possible on a computer as well. What would a peer to peer implementation of Kriegspiel look like, in terms of algorithms for authentication, one in which:

There is nobody sending or receiving information besides the two players.
Each player can independently verify the information sent is true (storing previous data is of course allowed)
All the functions of the intermediary are filled (players are aware of invalid moves, and of when pieces are taken.
No player is sent information which makes him certain of information he shouldn't know (e.g the position of the opponent's pieces) besides logical means, of course.

I have looked into zero knowledge proofs somewhat, and was interested in a way they could be implemented in a situation like this.

How would a cheat-proof version of P2P Kriegspiel be implemented?

or, alternatively since that question was deemed too vague

What computer science concepts, protocols, and general algorithms would go into the implementation of such a game?


texts:
(This is taken from the book Semantics with Applications)

I'm trying to determine the fixed points for the following block:

while (x!=1)  { y = y *x; x = x -1; }

As I understand, a fixed point g has to satisfy the following:

F g s = g s

where s is a state, F is a functional.

The functional F, in this context, would be defined like so:

if (s x = 1): F g s = s[x ->1]
otherwise: F g s = g s[y -> y*x, x -> x -1]

So now I'm trying to come up with a valid fixpoint g.

My attempt is this:

if (s x >=1): g s = s[x -> 1]
otherwise: g s = undefined

I think it's valid since it satisifes  F g s = g s

Am I on the right track and thinking correctly?

(I'm reading the books Semantic with Applications and the lack of solutions has made it very difficult to verify my thinking)


texts: Is it always enough to prove that a subset $L'$ of a language $L$ is unprovable in order to prove that $L$ is undecidable?

texts:
Given a language $L$, I sometimes try to find a subset of $L' \subseteq L$ which I can prove is undecidable. I conclude that if a subset of $L$ is undecidable, then $L$ must be undecidable as well. Is this correct for arbitrary languages $L$ and $L' \subseteq L$?

What if someone said: $L'$ could be empty (we don't know due to the undecidability of $L'$), and we cannot conclude anything about $L$ from $L' = \varnothing$, therefore the proof is insufficient. Is this a valid point?

For example, in order to prove that the language
$$L = \left\{ w : M_w \text{ halts on a a finite set of inputs} \right\}$$
is undecidable ($M_w$ is a turing machine constructed from $w$), I use the fact that $L \text{ is undecidable} \iff L^c \text{ is undecidable}$. $L^c$ can be described as
$$L^c = \left\{ w : M_w \text{ halts on an infinite set of inputs} \right\}$$
and
$$L' = \left\{ w : M_w \text{ halts on all inputs } \Sigma^* \right\}$$
can be considered a subset of $L^c$. Using reduction, I can then prove that $L'$ is undecidable. If my assumption about subsets is correct, then $L^c$ must be undecidable as well, and therefore $L$ is undecidable.

(I know that the undecidability of the above language can be proven simpler, but I need an example for the use of subsets.)


texts: DBMS: MINIMUM NUMBER OF TABLES REQUIRED TO REALIZE THIS ER MODEL

texts:
I was following a discussion on a forum where they have posted a question like this-->

Some people are saying that we can merge A,B,C in a single table and m:n relation of A and C in another table having foreign key. Thus 2 tables are required. Where as another person is saying that A,B,C cannot be merged as if we merge A,B,C then it means that the A and C sharing the same row must have relation. So we need at-least 3 tables, one for AB another for BC and another one for AC. So which is correct? 2 tables or 3 tables. I am pretty much confused with this.


texts: Context Free Grammar for $\{A^nB^nC^n | n \in \mathbb{N}\}$

texts:
Is $L = \{A^n B^n C^n \mid n \in \mathbb{N}\}$ a context-free language, e.g. $AAAABBBBCCCC \in L$

If so, what's that context-free grammar that produces it?


texts:
I'm working on proving that the following language is regular:

B = {x|for some y, length(x) = length(y) and xy are in A}

where A is a regular language.

Since A is regular, we know that there is an FSA that describes it. My plan is to modify this FSA, M,  into M' using jumps, to prove that for certain strings of x, that it is possible/not possible to land in an accept state. However, the empty string has a length of 0 and so I'm confused as to how to go about this.

Any help would be appreciated! Thank you!


texts:
I'm really trying to wrap my head around vectorization but I can't seem to understand it. I don't know if I don't understand how to vectorize, or if I don't understand the array notation that's being used. An example of a loop I'm working on with school is below:

for (M=0; M< number_of_iterations/2; M++){
   for (i=2; i<n-1; i++)
      for (j=1; j<n-1; j++)
          y[i][j]= (x[i-1][j]+x[i][j-1]+x[i+1][j]+x[i][j+1]+x[i-2][j])/5.;

I'm not sure I quite understand the whole thing on dependencies - Is there a way to vectorize this using array notation as is, or do I need to adjust it somehow to account for dependencies throughout?


texts: What is the best heuristic function for evaluating the state in game of sprouts?

texts: We are developing game of sprouts bot using min-max algorithm. We need a good heuristic function for evaluating the state of the game/player. Can someone please suggest?


texts:
I have this practice problem that I was given.

I am trying to solve a specific recurrence equation

T(n) = 4 when n <= 2

T(n) = 3T(n/3) + 5 when n > 2

how would i go about to solve such a problem since I only really know how to solve Master Theorem and Divide and Conquer using the a and b but don't really know how to solve a problem like this.

I'm trying to get an exact answer as well


texts: Does the head of TM M ever move into cell x when processing Input I?

texts:
The question is whether this is recursive or not. I first thought that it wasn't but then I read this question which seems similar and is recursive.

Is it decidable whether a TM reaches some position on the tape?

I think it's a slightly different question though (?) and so I have tried to show that it isn't recursive by reduction from the halting problem.

Ignore the below if it is recursive!

So for an instance  of the Halting problem we can use 2 tape TM M' as follows:

on input (code(M)code(x)) to M'

M' copies code(x) to tape 2
M' simulates M on tape 2
If M halts on the input x then......

I am not really sure what to do now. I thought that I could get M' to only enter a certain cell if M halts on x and then use this to show that if we could decide the problem above then we could decide the Halting problem (by seeing if M' enters that particular cell)

But I am not sure what cell I can use to guarantee that it won't have already been entered? The two tape thing is kind of confusing me -do I need to pick a cell that won't be entered on either tape 1 or tape 2?

Any help appreciated!


texts: Concatenation property of regular languages

texts: If L is the empty set and therefore a regular language, I know that L concatenated with sigma star is equal L;  Are there any other languages that, when concatenated with sigma star will result in the same language?


texts: Is $L_p$ decidable when p is a trivial property?

texts:
If

$\qquad\displaystyle L_p = \{ \langle M \rangle : p \in P(L(M)) \text{ s.t. } p \text{ is a specific trivial property} \}$,

where a trivial property is a property that is shared by all recursively enumerable languages or is not a property of any recursively enumerable language, is it implied that $L$ is decidable?


texts: Does This Prove $P \neq NP$? (Randomly Populated Binary Tree)

texts:
Suppose a binary tree with $n$ levels and exactly $2^n-1$ nodes.

The nodes are random and their value does not determine their position in the tree at all. This isn't demonstrated in the picture, because I couldn't find a better image to use.

The task is to find the path to a given node. Since the nodes are random, we'd have to visit each node until we find the target. This should be $O(2^n)$ with the best case being $\Omega(1)$ (the target node is the root node). The output is at most an $n$-bit value, each bit specifying whether to traverse the left or right child node. When there are no more bits to be read, we know we've reached the target node. Therefore, the output can be read and verified in $O(n)$. Are there any flaws with this?


texts:
I have a collection of intervals and I want to sort them so that the order is interpreted as a sort of "z-index". That is, a given interval may or may not be "visible" depending on whether the merge of the intervals to its left (i.e. preceding it in the given order) contains it.

I am looking for an algorithm to search the optimal ordering, that maximizes the number of visible intervals.

Context: the intervals are spans of text (that all contain a given keyword) and I want to color them using CSS cascading behavior so that all regions are at least partially visible.

Example

A phrase: "The quick brown fox jumps over the lazy dog"

The intervals: ["quick brown fox", "fox", "fox jumps over", "fox jumps over the lazy dog"].

An optimal sorting: ["fox", "quick brown fox", "fox jumps over", "fox jumps over the lazy dog"] (all 4 intervals are "visible")

Non optimal sortings: for instance, any sorting where "fox" is not the first element (so there'd be at most 3 visible intervals).


texts: Does having more bus in the computer increasing speed?

texts: Whát i mention here is for having 2x bus will increasing 2x memory access speed like 3x will have 3x memory access speed like that !


texts: An algorithm which efficiently generates random samples without replacement, from a large range [0-N], N ~ 10^12?

texts:
I want an algorithm which generates random integers, without replacement, from a large range [0-N], N~10^12.

However, the whole range should not be stored in memory. The memory footprint should be O(1) relative to N. The algorithm can (probably must) retain state after every sample request.

The randomness should be "strong" in the cryptographic sense.


texts: How to proof a function is not computale

texts:
I wish to undestand how to proof a function is/is not computable. I found this example online (without solution) beacuse I was thinking was easy to understand, but I am stuck in understanding how to set the proof.

Given $M_n$ the nth Turing Machine produced in output by an enumeration algorithm for Turing Machines. Let $f_n$ the computable partial function compute by $M_n$.

Now, we consider the $g:\mathbb{N}^3 \longrightarrow \mathbb{N}$. Proof g is not computable.

$g(x,y,z) = \left\{\begin{matrix}
1 & ,if \ f_z(x)=y\\
0 & ,otherwise
\end{matrix}\right.$

My solution idea is based on the Church-Turing Thesis for Computable Functions: A function $f$ is effectively computable is, and only if, there is a Turing Machine that computes $f$.


texts:
Imagine two machines of different architecture which produce output of a standard format.

If you have a program for one machine and can observe it's operation and output, what techniques exist to automatically produce an equivalent program for the alternate architecture?

By equivalent I mean produces equal output (by some equality relation) for equivalent input.


texts:
I'm preparing for an exam, and on a sample one provided (without solutions), we have this question: Is the following solvable or non-solvable: Given a turing machine $T$, does it accept a word of even length? - Given a deterministic 1-tape turing machine $T$, does $T$ ever read the contents of the 10th cell?

Thanks! -


texts: Is $\Omega^\infty (g(n)$ a more general version of $\Omega(g(n))$?

texts:
In CLRS, one question defines $\Omega^\infty(g(n))$ such that:
$$f(n) = \Omega^\infty (g(n)) \iff \exists c \in \mathbb{R}^+ : \text{for infinitely many integers } n, 0 \leq cg(n) \leq f(n) \ .$$

My question:
What does it mean by "infinitely many integers"? Does it mean $\{n : n \in \mathbb{Z}\}$ or does it just mean some infinite subset of $\mathbb{Z}$ (say, for instance, every odd positive integer)?

If the latter is true, then why is $\Omega^\infty$ even useful? I'm struggling to find out what knowing the behaviour of $f(n)$ for some arbitrary infinite scattering of integers could possibly achieve.

If the former is true, why do we care about what a function $f(n)$ does for small $n$ (i.e. for $n < n_0$)? Isn't the whole point of asymptotics that we're looking for the behaviour of functions as they approach infinity?

Can someone give a bit of context to the definition of $\Omega ^\infty$, because at the moment, it just seems a very contrived definition.


texts: What is the purpose of a single input, single output, bidirectional shift register?

texts:
(source: edu.au)
This is the sort of bidirectional shift register, I'm talking about.
I understand why the normal right shift is useful, but when you shift it left, all you're really doing is sending the data input straight to the output.
Is there a useful reason for shifting bits in this manner?
EDIT-
I'm trying to understand how the when shifting to the left, the value int left most register is outputted at the right most end. It makes no sense.
Shouldn't the output be what the input is when shifting left?
Thanks!


texts: Why have quantum circuits won out over quantum Turing machines?

texts:
As I understand it, quantum circuits as a model are equivalent to quantum Turing machines, or at least they can be simulated on each other.

So my question is, why have quantum circuits become the chosen implementation rather than quantum Turing machines, such as in the IBM Q?

Is it related to entanglement and reversible gates? I wondered if quantum Turing machines could not take full advantage of entanglement.


texts: What is the significance of the following equation in computer vision?

texts:
Say I have a set of sample measurements of a one dimensional curve in the image plane $f(x)$. What is the purpose of minimizing the following functional
$$E(S) = \int \left[\lambda(S''(x))^2 + (f(x) - S(x))^2 \sum_k \delta (x - x_k)\right]dx$$

I believe it has something to do with energy minimization and snakes.


texts: Are there Dynamic programming speedups for $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$

texts:
I am wondering if there are dynamic programming speedups for the minimization problem $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$. Now I understand that its highly unlikely that such thing would exist for any arbitrary function $f$, but are there any speedups that can be applied if a certain condition is satisfied by $f$?

I am looking for any speedups that would make this DP a sub-$O(n^2)$ solution.

EDIT:

I have an array of $\{(a_1, b_1), ..., (a_n, b_n)\}$ tuples. I am trying to find a pair $i, j$ that minimizes $-\frac{|a_i-a_j|\times b_i \times b_j}{\max(|b_i|, |b_j|)}$ and hence my question.


texts: Do the classes $P$ and $NP$ include problems faster then polynomial?

texts: I have being reading up on complexity classes (in Rieffel & Polak, 2011; pg149). I am slightly confused about something. Does for example $P$ (DTime($n^k$)) include all problems that can be solved faster then polynomial in time (e.g. logarithmic) on a deterministic Turing? And likewise for e.g. PSpace (DSpace($n^k$)) and NP (NDTime($n^k$)) etc.?


texts: Median of distribution with memory constraint

texts:
Task
I want to approximate the median of a given distribution $D$ that I can sample from.
A simple algorithm for this, using $n$ samples, is:
samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

However, I am looking for an algorithm that requires less than $O(n)$ space.
Ideas
I have looked into these algorithms:

Median of medians: Needs $O(n)$ space, so it does not work for me.
Randomized median: It seems like this could be easily generalized to an algorithm that uses $O(n^{3/4})$ space.

Are there any other algorithms that use less then $O(n)$ space that could solve my problem? In particular, I was thinking there may be an algorithm that uses $O(m)$ space by generating batches of samples from $D$ of size $m$...
Details

Ideally, I am looking for a reference to an algorithm that also includes analysis (success probability, expected runtime, etc).
Actually, I need an algorithm to estimate $D$'s $p$-th percentile for a given $p$, but I am hoping most median-finding algorithms can be generalized to that.
I would like to achieve the same accuracy as the simple algorithm shown above. One way to achieve this is by using an algorithm whose output distribution is the same as the sample algorithm (but maybe the new algorithm may fail in rare cases)


texts: Tarjan's Algorithm failure case, what am I missing?

texts:
I'm having a little trouble with Tarjan's Algorthm.

So here's my problem:  I have a graph such that these nodes are directionally-connected as shown:

A: B C D E
B: D E
C: B D E F
D: C E
E: B
F: A B D E

My problem is Tarjan's Algorithm never revisits nodes, apparently.  If the node isn't on the stack, it's not checked.

So here's what's happening:

My algorithm is going A, D, E, B.  B checks D.

A(id=0, link=0), D=1, E=2, B=3
-> D is visited, D is on stack, D's id is 1, B(id=3, link=1)

Cute.  B checks against E (cycle—it's a tie), which has an ID of 2, and is on the stack, no change.

B is out of neighbors, doesn't have a neighbor, returns out of the recursion so E can continue.

E, upon return from DFS of B, checks B's low-link value.  It's lower, so E's low-link value becomes 1.

A(id=0, link=0)
B(id=3, link=1)
C(undefined)
D(id=1, link=1)
E(id=2, link=1)
F(undefined)

Now return to D.  D's id and low-link value are 1, so no change.

Now here's the fun part.

D proceeds to check C.  C checks F.  F checks A, which has been visited and is on the stack.  A has an ID of 0, so D updates.

F(id=5, link=0)
C(id=4, link=0)
B(id=3, link=1)
E(id=2, link=1)
D(id=1, link=0)
A(id=0, link=0)

A proceeds to check the rest of its neighbors.  B and D have higher link values and IDs and are on the stack, so A doesn't update.

Every node has been visited.

There's a path from D to E to B to D, meaning those are part of the same SCC (in fact, all of these are in the same SCC—it's one SCC).

The stack is {A, D, E, B, C, F} with F at the top.

The two SCCs are {B,E} and {A,C,D,F}.

…you can reach A from B, and you can reach B from A.

What am I missing here?


texts:
What we know is that π is infinite and quite likely it contains every possible finite string of digits (disjunctive sequence).

I've seen recently some prototype of πfs which assume that every file you've created (or anybody else) or you will create, it's already there so it's a matter of extracting it. There is also piFile which can convert your files to pi metadata.

There is already BBP type formula (as part of experimental mathematics) which allows us to compute nth binary digit of pi. So storing position of our start and length of the data, we can theoretically extract the data of our interest. There are some arguments against it that our metadata (e.g. the offset to our data) could be larger than the extracted data. The matrix symbols and π can be encoded in base-256 to make it more efficient (see the joke).

Based on above, my main question is:

Are there any compression algorithms based on PI?

If not, does it make sense? Or were there any researches in that area?

Or maybe π is not the right one, so what about Euler's constant or Tau (τ)? Would it make any difference?

Image credits: Dinosaur Comics

See also:

Can any finite bit string be found in pi within a reasonable amount of time? at SO
Wouldn't storing the index into π be as big (or bigger) than the original data? at GitHub


texts: Is this language a context-free language?

texts:
I'm currently trying to figure out whether this language is context-free using the pumping lemma.

$\qquad L = \{ v_1 v_2 v_1 v_2 \mid v_1 \in \{a, b\}^*, v_2 \in \{a, c\}^* \}$

I'm having trouble because I don't know how to use the bound $m > 0$.


texts:
Here's the code for the algorithm:

Foo(n)
   lcm = 1
   for i = 2 to n
       lcm = lcm*i/Euclid(lcm,i)
return lcm

The running time of Euclid$(a, b)$ is given as $O(\log(\min(a, b)))$

So the running time of the for loop will be $O(n)$, so would this be the final running time? or do I have to take the $O(\log(\min(a, b)))$ into account as well?


texts: Decide the set of all Turing machines with $L(M)=\left\{\langle M\rangle\right\}$

texts:
How can I prove that the language $L=\left\{\langle M\rangle\mid L(M)=\left\{\langle M\rangle\right\}\right\}$ is not decidable?

When trying to use a diagonal argument, I cannot conclude from $L(M)\ne\left\{\langle M\rangle\right\}$ that $\langle M\rangle\not\in L(M)$.

Also, it seems that I cannot apply Rice's theorem because I can't say anything about the machines' encodings $\langle M\rangle$ in the definition of the set $\mathcal{S}$.

Is there an easy reduction to a known undecidable language?


texts:
I need to work on a optimizer for a language whose operator are second order functions.

They are the well known ones filter, map, reduce, fold, foreach etc. etc.

I need to formalize as much as possible the language. I mean I would like to have at the end a description such this:

"Filter is function from this domain to that codomain, it has this and that properties, under some condition also this property holds"

Can you suggest me some publication/book where this work has been (at least partially) done?


texts: Why is fail[1] in KMP Algorithm always 0?

texts: I'm studying KMP Algorithm. In the failure function (or the sp table), why do we always assign the value 0 to the first element (character) of the pattern? I understand about the later elements of the pattern, as we assign the sp values according to length of correctly matched suffixes and prefixes, but why does the sp value of the first element has to be 0?


texts:
Taken from site "Geeks For Geeks".
The lemma: "A concatenation of pattern(regular) and a non-pattern(not-regular) is also not regular language."

example: $\left \{L={a^{n}b^{2m}|n\geq 1,m\geq 1} \right \}$

I think I managed to build dfa (q2 is an accepting state) for language. perhaps I'm wrong...


texts:
I'm a little bit confused about the analysis of binary search.
In almost every paper, the writer assumes that the array size $n$ is always $2^k$.
Well I truly understand that the time complexity becomes $\log(n)$ (worst case) under this assumption. But what if $n \neq 2^k$?

For example if $n=24$, then we have
5 iterations for 24
4 i. for 12
3 i. for 6
2 i. for 3
1 i. for 1

So how do we get the result $k=\log n$ in this example (I mean of course every similar example whereby $n\neq2^k$)?


texts: Using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant?

texts:
I would like to get some opinions about using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant skills.

When developing these skills one has to provide a large number of sample utterances, i.e. sentences with which a user could try to invoke a particular feature of the skill. So when the skill is about ordering chocolate I would have to provide sentences like...

i would like to buy chocolate
i would like to order chocolate
we would like to buy chocolate
we would like to order chocolate

...and so on. the number of these sentences tends to grow almost exponentially, yet even with hundreds of them they still often become the bottleneck of the entire skill because users tend to come up with new formulations that weren't anticipated.

There are some tools available that can generate these sentences from simple patterns, i.e. this

{i|we} would like to {buy|order} chocolate

would produce the four variations given above. The drawback of this approach is that usually not all permutations of the pattern are valid (in most cases it is only a small subset of them) and one would thus need another "grammar" on top of these patterns to tell which are. The patterns are also not standardized and thus tied to one particular tool.

So I was looking for a better way to generate these sample utterances, and came across an approach that generates sentences from a context free grammar. This looks very promising to me, and in a small test script I was able to generate a large number of sentences from a very small grammar, with limitations on the sentences structure that I would have been able to include in the patterns of the existing tools.

I am however not a exactly an expert in Theoretical Computer Science and would like to ask a few questions before exploring this further:

My understanding is that a CFG is basically a "pattern" in the form of a tree. It would thus work similar to the patterns described above, but with the additional benefit of having the rules about which permutations of variables are legal embedded in the pattern itself. Is that correct?
If the CFG really is just a more complex pattern that would also mean that this approach (generating sentences from a CFG) can not produce grammatical variations of the generated sentences, e.g. it would not be able to generate pluralized forms like i would like to see _my_ shopping cart -> we would like to see _our_ shopping cart. Is that right?
More generally: From the hierarchy of formal languages, is a CFG really the best solution to this problem, our should I experiment with other types of grammars?

As I've said, it is entirely possible that I am misunderstanding some fundamental things about CFGs here, I am really just looking for some external feedback on this idea before investing more time in it. Thanks!


texts: Binary heap of size $n$ splitting to 2 heaps of size $n/2$

texts:
Input: A binary heap of size $n$. $n$ is even.
Output: 2 binary heaps of size $n/2$ each.

I found this question in a solved algorithms test and the solution said: "There is no better solution than to build 2 completely new heaps using BuildHeap() - $O(n)$ time."

I have thought about taking out the root out of the original heap, and then we have 2 sub-heaps, one with  $\lfloor n/2 \rfloor$ values, and one with $\lfloor n/2 \rfloor +1$ values.
Now we just add the element we took out to the bigger heap of the two sub-heaps.
How do we know which heap is bigger?
We traverse the heap with 2 pointes, Left and Right.
Left that goes only left, and Right that goes only right, and every pointer has a counter that counts the number of elements is has passed.
The bigger heap will be denoted by the max counter of the 2 pointers.
This works because a binary heap by definition is full in all of it's levels, aside the last level, which is full from left to right.
That sums up to $O(log n)$.

My question is: Am I right, or is the solution right?

Edit: My solution is wrong. I have tough about adding it a fix but it makes it $O(n)$.


texts: Why the $\textbf{PCP}(\log n, 1)$ construction of completeness $c$ and soundness $s$ for an $NP$ language $L$ implies $s/c$ inapproximability for $L$?

texts: In the introductory chapter of $\textbf{PCP}$ in Arora and Barak, I read the proof that why a $\textbf{PCP}(\log n, 1)$ of completeness 1 and soundness 1/2 for an $NPC$ language $L$ will imply that there exists a $\rho$ for which $\rho$-approximation algorithm for MAX-3-SAT does not exist unless $P = NP$. But in the paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf authors say that "We construct a PCP that reads two bits from the proof and accepts if and only if the two bits are unequal. The completeness and soundness are $c$ and $s$ respectively. This implies that MAX-CUT is $NP$-hard to approximate within any factor greater than $s/c$." What is the proof for this?


texts: What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates

texts:
In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the first layer consists of OR (or AND) gates, then the second layer consists of AND (or OR) gates, the third layer consists of OR(AND) gates, and so on, what is the proof of this conclusion? Or any reference? I remember the proof that the PARITY problem needs exponential circuit complexity used this fact when using Håstad switching Lemma. Thanks!

Note: we don't need CNF(or DNF) here, because that corresponds to 2 layers and exponential number of gates. In general, the circuit above can be arranged as multiple layers, so CNF(DNF) is not necessary.


texts:
This is the code:

j=2
while j<(n*n)
     j=j*j

At first my approach was to treat this like this loop

i=1
while (i<n)
    i=i*2

Which generates on $i$ various powers of $2$  ($i=2^0, 2^1, 2^2....2^k$).

At a certain $k$ iteration, $i$ is equal to or exceeds $n$.
So $2^k=n$ is the time when the while stops.

We find $k=log_2(n)$ which is the number of times the entire while loop has been executed, so $T(n)=\theta(log_2n)$.

So my idea for the first algorithm was this:
j=j*j generates on $j$ different powers of himself, so you can describe it as $j^2$. The problem is that I can't shove in a $k$ iterations in the counting.

The solution for this is actually $log(log(n))$.

Why is this? Can I improve my logic?


texts:
The famous 4-sum problem is to find 4 elements at unique indices in an array which sum to a given X. I was looking at one solution I found:
findFourElements(A[1], ..., A[n], X)

create hashtable mp
for each 1 ≤ i < j ≤ n:
   mp[A[i] + A[j]] ← (i,j)     // (i,j) is an ordered pair
end for
for each 1 ≤ k < l ≤ n:
   if mp contains A[k] + A[l]:
      (i,j) ← mp[X - (A[k] + A[l])]
      if i ∉ {k,l} and j ∉ {k,l}:
         return A(i),A(j),A(k),A(l)
      end if
   end if
end for

It is working fine on some test cases I tried. But I have a doubt: in the hashtable we are just storing one occurrence of each pair, but there can be a case in which a solution exists, but since we stored only one occurrence of each pair, we only have overlapping occurrences, and we may miss the non-overlapping ones. But still I am not able to produce any test case to fail it. Is this algorithm correct, or does it fail for some test case?


texts:
Consider this question: A program has 1M instructions and 30% of them are SQRT with CPI=8. The CPI of the rest of the instructions are 3. If we reduce the CPI of SQRT to 2, how much speedup is obtained?

I have two solutions for that:

1- Using Amdahl's law, We have

              1
 S= --------------------
      (1-alpha) + alpha
                  -----
                    n

So, we have 1/(0.7+(0.3/4)) where 0.7 is the fraction that is not affected. and 4 is the speedup of reducing CPI of SQRT from 8 to 2. That speedup will be 1.29.

2- We can calculate

CPI_avg = sigma( I * CPI_class )

and we know SQRT instructions are 300K and the rest are 700K. So

CPI_old = (300000*8 + 700000*3) / 1000000 = 4.5
CPI_new = (300000*2 + 700000*3) / 1000000 = 2.7

So, the speedup will be 4.5/2.7 which is 1.66

The question is, which one is correct? 1.29 or 1.66?


texts: Is a register machine built out of automata of some sort?

texts:
I am looking at register machines like the Random Access Machine. Wikipedia says:

Random-access machine (RAM) – a counter machine with indirect addressing and, usually, an augmented instruction set. Instructions are in the finite state machine in the manner of the Harvard architecture.

Does this mean the instructions are somehow encoded as a finite automaton? Or how exactly is a register machine implemented (theoretically and practically, at a high level). Where do automata fit into the picture?
I am wondering because I realize automata are pretty limited in what they can do, and once you need to "parse" something but have access to an entire database of information at each step of the parse, and then the result of parsing is a complicated object graph, you are no longer dealing with automata (as far as I can tell). Automata are basically recognizers returning a yes or no answer, with very little access to "data" to make their transition decisions. But I like the idea of "state machine", where it transitions around state to state.
So I'm wondering what a so-called "state machine" with access to a large database to figure out how to make each transition might be called, and if this is what a register machine could/would be.
My understanding is that a complex register machine is closer to something like x86, where you have instructions and data. But it seems that you might somehow be able to encode these instructions as a state machine somehow. Is this true? What am I missing from this picture? Is a register machine compiled down to automata of some sort, or otherwise built out of automata, or if not, how is it different from automata?


texts:
Given function $\max\colon \{0, 1\}^{n} \times \{0, 1\}^{n} \rightarrow \{0, 1\}^{n}$ that returns the maximum of two binary $n$-vectors (interpreted as encoding numbers in the range $0,\ldots,2^n-1$), find a communication protocol for two parties having vectors $x$ and $y$ such that both parties will get the vector $\max(x, y)$.
It's easy to get trivial bounds for the complexity of any protocol for maximum: $n \leq \texttt{CC}(\max) \leq 2n$, but how can we use only $\frac{3n}{2} + c$ bits for some constant $c$?


texts: Why shift means push terminal symbol and state into the stack? Why not push only state?

texts:
Shift means that you need to put the status and terminal symbol on the stack. But what is the terminal symbol used for? After all, if the reduce command is executed, both the state and the terminal symbol are deleted and the terminal symbol will never be used.

Why not push into the stack only state?

(English is not my native language, so please be kind to my mistakes)


texts:
Let us define a "root universal family" as a family of hash function which for every two items $k_i,k_j$ the probability $P(h(k_i)=h(k_j)) \le \frac{1}{\sqrt m}$ where $m$ is the size of the table.

Now, let us have $|U| = n$ -  (the size of the given universe, note that it is perfect hash).

Define an efficient perfect hash algorithm, for which the total sizes of the tables is $\le O(n^2)$.

Now, we note that if we have a table of size $n^2$, then the expected number of collision of a random hash function from that family is $\le \frac{n}{2}$. This is because:

$$\mathbb E[\text{number of collisions}] = \sum_{\{k_i,k_j\} \subset U, k_i\ne k_j}P(h(k_i)=h(k_j)) \le \frac{\binom{n}{2}}{\sqrt {n^2}} \le \frac{n}{2}$$

So, we define the "first-level" hash table to be of size $n^2$. The expected number of hash function we need to draw in order to have less than $n$ collisions is $2$ (since it is a geometric variable).

Now, this is where I get stuck:

After a hash family that satisfies less then $n$ collisions is chosen, for each table that has items colliding, we make a "second-level" table of size $|\text{number of collisions in table}|^4$. (It is easy to prove that in order to get no collisions when the size is $x^4$ we need again two draws for the second function.

The problem I having is showing that all the "second-level" tables + the "first-level" tables are $O(n^2)$ of total size. Would like help in proving that, Thanks!


texts:
A tree is provided which has $n$ nodes and each edge of that tree has a certain length. There are $M$ persons on the tree, numbered 1 through $M$. For each valid $i$, person number $i$ starts at time $t_i$ from vertex number $u_i$ and runs straight to vertex number $v_i$ with constant velocity $s_i$. Before time $t_i$, the person is not considered to be present in the tree. So the question is, for each vertex, what is the first time that a person is present at this vertex. Here $n$ and $m$ are of order $10^5$.

Although I have worked out the basic brute force solution, that doesn't work for the original constraints. What would be a better approach for this problem?


texts:
I was just wondering why are are new generation microprocessors faster at the same clock speed as the old ones.
For instance a 2.66Ghz dual core i5 is faster than the a device with clock speed of 2.66Ghz but core 2 dual.


texts: Improving MSE as fitness function for a genetic algorithm

texts:
I am implementing an autoencoder neural network in matlab, the weights of which are being optimised by a genetic algorithm.

At the moment I am working on the first layer, trying to get an improved reconstruction from it by using the genetic algorithm.

Using the genetic algorithm, I am able to get about a 30% improvement in fitness before the population converges, compared with the random data that it starts with; which is a reasonable improvement I thought, however it doesn't seem to make a difference with the actual reconstruction.

I will illustrate with a screenshot of my data:

At the top is shown the original data (using MNIST data), followed by the reconstruction of the data by the fittest, median and least fit individuals (at this stage the population had converged, so there is no difference between the three)

Below that is a plot of the fitness function on the y-axis (it is a minimising problem) against epochs on the x-axis for those three data points, as you can see, the fittest individual starts with a value of about 120 and finishes around 80 without improving much on the reconstruction.

My problem is with my fitness function I think. I am using the sum of the squared differences between the (normalised from 0 to 1) pixel intensity values of the original and reconstructed data - but the more I think about it, the more it seems that it will probably favour offspring that reconstruct a purely black image, as that will have a pretty low value using that heuristic; and indeed it appears to tend toward that as I watch the reconstructions evolve.

So my question is: what can i use as an additional fitness metric to try and make my algorithm favour offspring that produce less noisy reconstructions?

some I have thought of are:

proportion of light pixels to dark pixels;
difference between histograms of original and reconstruction;
putting additional weight for very light pixels or very dark ones.

And that's about it. Would any of those be useful? can someone suggest anything better? I don't have much of a background in image processing, so any help would be greatly appreciated.

EDIT:
In response to deong's replies;

My network goes 784 -> 500 -> 250 -> 100, training each layer one at a time as in the geoff hinton code before moving on to the next layer.

I have tried population sizes of 10-200, with many in between, i am using tournament selection and have tried k values of 2 to around 40, with a mutation rate of 0.01 - which selects a random block of 10000 values and replaces it with another 10000 random values.

As far as crossover goes; i have tried 1, 2, 3 and 4 point, uniform crossover with blocks from 100 values to 100000 values - and many variations of all of those methods, but none really seemed to make any difference, it just changes the speed at which it converges to the same thing.

I have also tried using particle swarm optimisation, and that gives me pretty much the same results - the overall mean squared error goes down over time, but the reconstruction just tends to a uniform black image, which makes sense that the mean squared error would be lower for an all black image than a random noise image because the original image is predominantly black itself.

do you have any suggestions as to what i should try next? I have started working more on the PSO algorithm lately, as it is much simpler to implement than the GA and has less variables that i need to try.


texts: Minimal number of nodes needed to connect a disconnected graph

texts:
Given a graph $G = (V, E)$ with $V = U \uplus T$ (let's say the vertices are
labelled $U$ or $T$), I am looking for the smallest set $U' \subseteq U$ such
that $G[U' \cup T]$ is connected.

If we eleminate all the type-U nodes from the graph, the type-T nodes (terminals) might form several disconnected subgraphs.
That is, the graph $G[T]$ on only the "terminal nodes" might be disconnected,
and I want to pick as few vertices from $U$ as possible to make the graph
connected again.

What kind of graph problem does this relate to?


texts: How to estimate the number of elements inserted to a Bloom filter

texts:
A Bloom filter is a probabilistic data structure that allows encoding sets with false positives.

Parameterized by the number of bits $m$ in the array $A$ (initialized to zeros), and number of hash functions $k$, an insertion of an item $x$ corresponds to setting $A[h_i(x)]=1$ for $i=1,\ldots,k$.

Similarly, for testing if an item $x$ was inserted, we return True iff $\forall i\in[k]:A[h_i(x)]=1$.

  Given a Bloom filter $A$ (and denote the number of hash functions by $k$), how can we estimate the number of elements added to the set so far?

If $k=1$, estimating the number of elements corresponds to the Linear Counting algorithm. What can we do for a larger $k$?

One possible way seems to invoke the Linear Counting estimator and divide it by $k$. Can we do any better?


texts:
Say I have variables $w_1, \dots w_n, h_1, \dots h_m \in \mathbb R$, constants $W, H$, functions $f_1, \dots f_k : \mathbb R\times\mathbb R\to\mathbb R$ from some family $F$ and for each function $f_i$, a pair of intervals $x_i \subseteq [1, n]$, $y_i \subseteq [1, m]$. All quantities $\geq 0$.

I want to find the $w_i$ and $h_i$ to minimize $\sum f_i \Big(\sum _{j\in x_i} w_j, \sum _{j\in y_i} h_j \Big)$ with constraints $\sum w_i = W$ and $\sum h_i = H$. Approximations are perfectly fine.

Informally, this is a grid with column widths $w_i$ and row heights $h_i$ and cells that may span multiple rows and columns, that have costs $f_i$.

My question is, for what families $F$ does this problem have reasonably efficient solutions? The set of affine functions should work. What about step functions? Piecewise linear? Smooth monotonic? Smooth functions in general?


texts: Is {| L(M) ∩ (ab)∗ is infinite} in D, SD/D, or not in SD?

texts:
Are these languages in D, SD/D, or not in SD?

$$L_1 = \{\langle M \rangle\mid L(M)\cap (ab)^*\text{ is infinite}\}$$

I kind of understand decidability and undecidability problems, but the "$\cap(ab)^*$" here threw me off a little. but I'm thinking that maybe I should deal with this as if it's just $L(M)$ basically since the intersection of a regular language with an arbitrary language could be anything; in other words, reduce $\neg H = \{\langle M, w\rangle\mid \text{TM }M\text{ does not halt on }w\}$ to $L_1$, and conclude that there isn't a machine to semi-decide $\neg H$, so $L_1$ is not in SD.

So basically, since $(ab)^*$ is infinite, we could run $L(M)$ on an infinite $(ab)^*$ string, but since it may never halt and accept, this language is not even semi-decidable.

What about

$$L_2 = \{\langle M \rangle\mid L(M) \cap (ab)^∗ \neq\emptyset\}\,?$$

If my idea of intersection is right, I believe that this is in SD\D (Turing enumerable, but not decidable), and that can be proven by reducing
$A = \{\langle M\rangle\mid L(M)\neq\emptyset\}$ to $L_2$.
Does this sound right?


texts: How to keep track of changes done to concurrent stacks?

texts:
I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions:

add-int(a: int, b: int): a b +
add-float(a: float, b: float): a b +

and I have two stacks with the following:

Int [1 2 3]
Float [4.0 5.5]

I can just do:

add-int add-float

and the new stacks will be:

Int [1 5]
Float [9.5]

Everything works well there, but if I were to add parametric polymorphism with this function:

add-num(a: num, b: num): a b +

Then it would not work as one would expect. Is it going to add the two integers or the two floats? or perhaps one from each?

To solve the issue, I added a new stack Num that keeps the address of every number pushed into the other stacks to keep a sense of history, but it created two new issues.

First, memory addresses take a lot of space, sometimes more than the data itself, and this would only get worse if I were to add new number types like ratios and complex.

Second, what if I wanted to pop a number that is on top of the stack for its type but way behind in the Num stack.

For example:

> 1 2 3.14 4.0 5/5  -- This is the expression.
Int [1 2]  -- These are the stacks.
Float [3.14 4.0]
Ratio [5/5]
Num [&Int[0] &Int[1] &Float[0] &Float[1] &Ratio[0]]

> add-int  -- Then I do this.

If I call the function above, there is no issue popping the two integers, but what about deleting the two pointers in the Num stack? It can get pretty expensive to look for the element and remove it every single time a number is popped.

I have realized that this approach is not pretty effective in terms of space consumption and performance, so is there an alternative, more efficient way of keeping track of the changes done to these stacks?


texts: How to give an approximation algorithm for this unusual bin packing problem?

texts:
The usual bin packing problem can be formulated as:
\begin{align}
 & \underset{x,y}{\min}
 & & B = \sum_{i=1}^n y_i\\
 & \text{subject to}
 & & B \geq 1,\\
 & & & \sum_{j=1}^n a_j x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}\\
    & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\
\end{align}

where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$

I have a similar problem that is formulated as:

\begin{align}
 & \underset{x,y}{\min}
 & & B = \sum_{i=1}^n y_i\\
 & \text{subject to}
 & & B \geq 1,\\
 & & & \sum_{j=1}^n a_{kj} x_{ij} \leq V y_i,\forall i \in \{1,\ldots,n\}, \, \forall k \in \{1,\ldots,n\}\\
    & & & \sum_{i=1}^n x_{ij} = 1,\forall j \in \{1,\ldots,n\}\\
    & & & y_i \in \{0,1\},\forall i \in \{1,\ldots,n\},\\
    & & & x_{ij} \in \{0,1\}, \forall i \in \{1,\ldots,n\}, \, \forall j \in \{1,\ldots,n\},\\
\end{align}

where $y_i = 1$ if bin $i$ is used and $x_{ij} = 1$ if item $j$ is put into bin $i$.

You can see that constraint 2 is no longer the same as in the usual formulation. Now, it must be satisfied for each item $k$.

In my problem the items influence each others (by constraint 2). Each item should be packed into a bin (by constraint 3). The objective is to minimize the number of bins used (by the objective function).

How can I solve this problem? Or how can I design an approximation algorithm for it?

I tired to apply the known approximation algorithm for bin packing such as (Next Fit, First Fit, etc.) but I failed because of constraint 2. (For example, I failed to give a proof of the approximation ratio 2 of Next Fit.)

Could you give me some directions where I should go (e.g., is this problem known) and how to solve this problem?


texts: Implementing abduction over first order theories

texts:
I am interested in implementing abduction over a full first order theory ie it may be non-Horn. (Aside: Almost all the references I've seen for abduction operate over Horn theories eg "Modeling Abduction over Acyclic First-Order Logic Horn Theories in Answer Set Programming: Preliminary Experiments". Is there a reason for this other than lack of minimal hypotheses?) Are there frameworks that might be suitably modified for my purposes? Alternatively, does anyone know of a way of coaxing a SMT solver into perhaps giving me something close to what I need?

thanks!


texts: LIP - Minimum Spanning Tree Cutset Formulation

texts:
I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation).

This is the definition:

$x_{ij}$ is defined to be $1$ if the edge $ij$ is in $T$.

What exactly does the optimum value represent here? Is it the number of edges that are used in our MST? If so, how does knowing the # of edges help us in forming the MST?

How does this LP "work" to find the MST problem? Thank you.


texts: Proving whether an input sequence is in a given RE language

texts:
I've learned this a few years ago that this is impossible unless one simply 'executes' (in a modern computing sense) the input with the language rules, but I have some problems in just using this statement.

The fundamental doubt is that the statement itself is well-stated. If I'm using the term 'execution' to describe the act of matching the rules one input element by one, is this statement valid?
Is this statement (deciding whether an input sequence is in a language is impossible without an execution) not exactly limited to RE? In other words, I wonder this statement also holds even for the languages in other classes.
I'm not even sure how I can search for this statement and confirm from the external source.

(By RE, here I indicate the recursively enumerable languages, not the regular expression)


texts: Difference between fractional knapsack & greedy solution

texts:
I am trying to understand what the difference is between the fractional knapsack problem using dynamic programming, and the greedy solution version. Im looking at an example of the fractional problem which looks like:

What's the difference between that and the greedy solution? Are you not just taking the value-per-pound in this example too but it's just not explicitly stated?


texts: Induction Proof on Independent Set Variation Algorithm

texts:
So I am given this blackbox algorithm, in which given a Graph G and a integer k, it returns yes if there is an independent set of size k, no otherwise.

My algorithm is suppose to output impossible if there is no independent set of size k, or output an independent set of size k if it exists.

How might this be approached?


texts: Fundamentals of sampling without replacement

texts:
I would like to ask a question about fundamentals that are used intuitively in
solving a simple probabilistic task about sampling with replacement. However, when I start to think about underlying fundamentals, things become complicated.

Consider a bucket with three balls: two red (R) and one black (B). We randomly select two balls. What is the probability to select two red balls?
Additionally, assume that the sample space $S$ is: $\{~\{R, R\}, \{R, B\}, \{B, R\}~\}$.

When I was a student, I would say the following (and I assume that most of the people reason the same way).
To select two balls, we first select the first ball and then the second one.
The probability that the first ball is red ($P(\mathrm{Ball}_1 = R)$) is $2/3$.
The conditional probability that the second ball is red given the first ball is red = $1/2$.
Thus, the probability of both balls to be red is $1/3$.

It always bothered me, that here I implicitly use two sample space when I select balls.
Specifically, $S_1 = \{R, R, B\}$ when select the first ball and $S_2 = \{R, B\}$ when I select the second one.
Specifically, I conclude that $P(\mathrm{Ball}_1 = R) = 2/3$ using the sample space $S_1$.
Similarly, I conclude that $P(\mathrm{Ball}_2 = R) = 1/3$ using the sample space $S_2$.

But -- and here is my main problem -- the sample space of the task is $S$.
And I must use (to be formally correct) only $S$ to find probabilities $P(\mathrm{Ball}_1 = R)$ and $P(\mathrm{Ball}_2 = R)$. Of course, I can prove that $P(\mathrm{Ball}_1 = R) = |\{\text{outcomes where the first ball is red}\}|~/~|S| = 2/3$.
Analogously, I can show that
$P(\mathrm{Ball}_2 = R | \mathrm{Ball}_1 = R) = |\{\text{outcomes where both balls are red}\}| / |\text{outcomes where the first ball is red}| = 1/2.$

However, this way of reasoning is cumbersome and requires a lot of cognitive efforts to solve a simple task. Could you please tell me what is correct theoretical justification to use the first approach? To be more precise, how to justify theoretically that I use sample spaces $S_1$ and $S_2$ to derive probabilities defined on the sample space $S$.

Thank you very much for the help. If you will be able to answer my question you fixed my brain :) !


texts: Flow-based vs. Reactive programming paradigms

texts: I am reading Concepts, Techniques, and Models of Computer Programming and came across Flow-based (FBP) and Reactive programming paradigms. Now I have found the following article from J. Paul Morrison, the person who invented FBP. I am also some what familiar with Reactive programming. But I am having hard time to differentiate this two paradigms. Both belong to Declarative and also under Dataflow paradigm. But what really sets them apart? I would like a concise answer with greatest distinction between these two approaches outlined.


texts: Difference between equivalence and implication

texts:
In terms of CTL formulae, what is the difference between equivalence and implication?

(prop = some proposition, && = conjunction, AG = CTL syntax for "globally holds")

E.g. AG (prop1 && prop2) versus (AG prop1) && (AG prop2)

Are those two formulae related by implication i.e. the left hand side implies the right hand side? Or are they actually equivalent?


texts: Lambda Calculus: How do evaluation contexts "work"

texts:
In the pure lambda calculus, we have the inductively defined set of terms (the grammar):
$$e::= x \mid \lambda x . e \mid e_1 e_2$$

Under the call-by-value evaluation strategy, we have the inference rules for beta-reduction and rules on how to evaluate applications (congruence rules). I am trying to understand how evaluation contexts can replace the congruence rules without actually changing the syntax of the language. Without evaluation contexts, we have the following:

$$
\frac{e_1 \rightarrow e_1'}{e_1e_2 \rightarrow e_1'e_2}
$$
and
$$
\frac{e_2 \rightarrow e_2'}{ve_2 \rightarrow ve_2'}.
$$

This makes sense, since if we have an instance of an expression $t = (\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w$, it is clear that it is of the form $e_1e_2 \rightarrow e_1'e_2$ and thus $$(\lambda f . \lambda x. f x)((\lambda y .y)\lambda z .z)\lambda w.w \rightarrow (\lambda f . \lambda x. f x)(\lambda z .z)\lambda w.w$$

If we replace the congruence rules with evaluation contexts:
$$E::= [\cdot] \mid Ee \mid vE$$
then we need only a single rule to express the congruence rules of the language:
$$
\frac{e \rightarrow e'}{E[e] \rightarrow E[e']}.
$$

I am confused as to how evaluation contexts can tell us how to evaluate the expression $t$ from above without changing the syntax of the language. I don't understand how the evaluation context "works" without rewriting $t$ as

$$E_t = (\lambda f . \lambda x. f x)[\cdot]\lambda w.w$$

where $t = E_t[((\lambda y .y)\lambda z .z)]$. There is no obvious a priori reason to evaluate $t$ under call-by-value without knowledge of $E_t$. I really have no idea where I am going wrong. Can someone help correct my thinking?


texts:
Today I presented about IP address during my online class based on Computer Networks by Andrew S. Tanenbaum and during QnA session, I was asked about private IP Address range.
10.0.0.0 – 10.255.255.255
172.16.0.0 – 172.31.255.255
192.168.0.0 – 192.168.255.255

The questioner asked my why private IP address is determined in such range. I haven't really think much about the range because I accept it as something that had been decided by the people who came up with this technology but I eventually have to present again because I couldn't answer the questioner's question. Perhaps there are reason behind why the private IP address is determined in such ways?
For example why it starts with 10 and not 9? or why it starts with 172 and not 173?
I tried to read in RFC 1918 but I couldn't really find the answer about why they chose 10 or 172 or 192.
If anyone can share link that I could refer to or know the answer, I would highly appreciate it.
Thank you.


texts: How to find the LCP of string pairs in a set

texts:
I have a set of $k$ strings of $n$ length each. I need an algorithmic strategy that finds the LCP (Longest Common Prefix) of each set's string pair. In addition, I need time complexity $O(k*n+a)$, where $a$ must be the sum of all LCPs.
Any tip/paper/help will be much appreciated.


texts: How to understand the Bellman Equation in plain English terms?

texts:
So on my course we're dealing with a more basic, simple varition of the Bellman Equation.

V(S) = max a(R(s,a)+yV(s'))

As far as I can tell...

V(S) = Value of a state

max a = Maximum over all the actions

R(s,a)  = Reward of a state and action

y = Gamma (Discounting factor)

V(s') = The end state

So how I've always understood equations is by translating them into simple English so please indulge me.

Here's what I think this equation means and I'd like someone to tell me if I'm right or wrong and if I'm wrong rephrase the correct perspective in plain in English as well  if possible.

V(S) = max a(R(s,a)+yV(s'))

"The value of a state is equal to the maximum over all the actions, multiplied by the reward of a state and action, added to the discounting factor multiplied by the end state."

Is that correct?

Additional Questions:

(1.) Can "V(s)" be any state or is it the state closest to the end state?

(2.) Presuming you found "V(s)" for the state right before the end state and you wanted to find the value of the previous state before the one you just found. Can you reuse the the equation and make the value of the state you just found the new end state or "V(s')"?

(3.) What does the equation mean by the maximum of all the actions? Does it mean you get all the values of the actions and add them up or instead does it mean do you only take the highest value of all the actions and use that one exclusively?


texts: Does the SIFT feature be calculated in the original image or the corresponding octave(s)?

texts:
Given there are 4 octaves(the 1st octave is the original image, the 2nd octave is half size of the original image, and so on.), does SIFT calculate the keypoint's orientation in the original image or the octave the keypoint extracted from?
For example, there is a keypoint found in the 3rd octave. Does SIFT calculate its orientation in the original image or in the 3rd octave (one fourth of the original image size)

Similar to 1st question, does SIFT calculate the keypoint descriptor in the original image or the octave the keypoint extracted from?


texts: Single tape TM that converts numbers from binary notation to unary

texts:
I need to construct a TM that converts a number from binary notation to unary and calculate time complexity.
I have done the first part.
The idea is as follows:

binary number is decremented by 1 until it reaches 0. At each
decrement an additional 1 is written on the left side.

e.g.

111 -> 1111111
111x (TM goes to the end of the binary number and writes x)
110x1
101x11
100x111
011x1111
010x11111
001x111111
000x1111111
1111111 (TM removes zeros and x; end)

And now comes the time complexity part. So far I have:
(1) TM will do $n$ (length of the binary number) steps to reach the end of the input word, additional  1 for writing x and 1 for moving back, so $n+2$;
(2) there are $2^{n}-1$ decrements, at that time TM will take in total $2 \times \frac{(2^{n}-1) (2^{n})}{2}$ steps on the left side, plus $2\times (2^{n}-1)$ for the x's. (no idea how many on the right side).
(3) TM will take $2n+1$ steps for removing unnecessary zeros and x at the end.
I don't know how to put this all together, plus some missing information in (2). Can anyone tell me if I'm computing correctly and how to proceed.
Any help will be much appreciated.


texts:
From http://en.wikipedia.org/wiki/Superscalar

  In Flynn's taxonomy, a single-core superscalar processor is classified as an SIMD processor (Single Instructions, Multiple
  Data),

Flynn's taxonomy is based on number of instruction streams and
number of data streams.

A superscalar processor can run more than one instructions at a
time, so why isn't it MIMD?

If there is a valid reason for a superscalar processor to be SI,
then why isn't there a similar reason which makes it single-data (i.e.
SISD)?
Instruction pipeline also runs more than one instruction at one
time. Is it SISD or SIMD?
Does "SI $\equiv$ only one CPU core"? Or only one implies the other?

Does "MI $\equiv$ more than one CPU cores"? Or only one implies the other?

Thanks.


texts: Why can't we solve the dinner party problem by finding a maximum matching?

texts:
Consider the following dinner party problem:

  Given a list of acquaintances, and a list containing all pairs of individuals who are not on speaking terms with each other, find the largest set of acquaintances you can invite to a dinner party such that you do not invite any two who are not on speaking terms.

I have read in Arora-Barak that is not possible to find an efficient solution for the dinner party problem. I'm confused because I thought that it was easy to solve with Edmond's Blossom algorithm (it finds a maximum matching).

This is what I thought (of course it must be wrong):

We create a graph where vertices are acquaintances, and edges are "not on speaking terms with each other".
We exchange vertices with edges.
We find a maximum matching, and these edges are the guests I can invite.

EDIT: I explain it better:

We create a graph where  edges are acquaintances and vertex are "not on speaking terms with each other" If the resulting graph has edges at the ends (it could be possible) we add extra vertex at these ends.
We find a maximum matching, and these edges are the guests I can invite.

But I'm not sure why I'm wrong.


texts: What is the minimum acceleration of a macro machine?

texts:
In the context of Turing machines, consider a $k$-sized macro machine (k-MM) which operates on groups of $k$ symbols at once. This is a common optimization in the search for Busy Beavers, explained e.g. by Holkner: Acceleration Techniques for Busy Beaver Candidates, 2004.

Holkner writes:

  The number of shifts required to halt the macro-machine with an underlying machine $M$ halting in $s(M)$ shifts will be less than or equal to
  $$
\frac{s(M)}{k}
$$
  and is typically far less.

If the machine passes over a whole $k$ sized block in each step, this result it obvious, as it must (internally) perform at least 1 operation on each of the $k$ symbols in that group.

However, it might also, for instance, change directions early and step out of the block, using less than $k$ operations. Repeating this requires exactly two symbol groups. As there are already $|Q||\Gamma|^i$ distinct configurations of $i$ symbols and $Q$ states, this is not just a small constant, but may be substantial for $i = \Theta(k)$.

Considering this, how is $\frac{s(M)}{k}$ still an upper bound for the required shifts?


texts: Is there an algorithm to find the smallest set of the shortest prefix substrings of a continuous numeric sequence?

texts:
Before anything I want to preemptively thank anyone who drops by for their patience, I don't have any formal CS background so I'm probably going to use some of these terms wrong.

I have a puzzle: Given two numbers which define a set of continuous counting numbers of the same number of digits, between roughly 5 and 12 digits long (IE 50000 and 60000, 32325600000 and 32399999999), what's the fastest and most efficient way to condense this down to a set of prefixes which "contain" all permutations of subsequent digits?

The approach we've been using is a hybrid of treating these as numbers and character strings. First remove any pairs of matched 0's and 9's at the end of the start/end. Second create the full sequence copied to two columns, where the second column is always a substring with the rightmost digit removed relative to the first column. From there I can recursively count how many times any given one-digit-shorter substring occurs, keep the items where N-count<10, and where N-count>=10 remove another digit from both columns and repeat.

What I'm wondering is if there's a quicker and more efficient way to do this. String operations instead of math was an obvious quick fix, but the general approach still relies on recursively grouping and chopping off characters. I've considered making a full series of Prefix and N-count columns going back to the highest digit but at least instinctively that feels like it would be less efficient than operating recursively on a decreasing pool of numbers.

IE
Input:
Start=50000000
End=55399999

which becomes
Start=500
End=553

Cycle one creates two sequence columns like this:

String   Prefix     N-Count
500        50          10
501        50          10
etc..
510        51          10
etc..
550        55          6
551        55          6
552        55          6
553        55          6

Cycle two keeps everything where N-count<10 the same, but reduces the rest by 1
digit each and recalculates N-count (while getting rid of duplicates).

String   Prefix     N-Count
50        5          5
51        5          5
52        5          5
53        5          5
54        5          5
550       55         4
551       55         4
552       55         4
553       55         4

Output:  50,51,52,53,54,55,550,551,552,553
```


texts: Change a matrix into lower triangular matrix

texts:
I have a matrix over integer of size (50,50). I want to know whether it is possible to exchange rows and columns in such a
way so that the transformed matrix is a lower triangular whose diagonal entries are non zero.
Is there any algorithm which can determine this efficiently?


texts: Function problems and $FP \subseteq FNP$

texts:
I find it hard to find formal definitions of function complexity classes. Here are two from Wikipedia.

  A binary relation $P(x,y)$ is in FP if and only if there is a
  deterministic polynomial time algorithm that, given $x$, can find some $y$
  such that $P(x,y)$ holds.

The definition above seems to imply that for all relations in FP it holds that for every $x$ there exists at least one $y$ which its length is polynomial in the length of $x$. However, it does not seem to restrict that there exists more $y$ for that $x$ so that $P(x,y)$ holds while $y$ is exponentially longer than $x$.

  A binary relation $P(x,y)$, where $y$ is at most polynomially longer than
  $x$, is in FNP if and only if there is a deterministic polynomial time
  algorithm that can determine whether $P(x,y)$ holds given both $x$ and $y$.

This definition implies that for a relation in FNP it need not to be true that there exists at least one $y$ for every $x$ so that $P(x,y)$ holds. It implies however that if $P(x,y)$ holds, $y$ has to be at most polynomially longer than $x$.

In literature, one can read that FP $\subseteq$ FNP. As far as I do (or do not) understand, this can not be true. It is possible that for some relation $R(x,y) \in$ FP there exists a $(x,y)$ so that $R(x,y)$ holds and $y$ is exponentially longer than $x$. Because of this, this relation does not belong to FNP and therefore FP $\not\subseteq$ FNP.

Are the definitions on Wikipedia incomplete? Am I missing something?

Either way, what are some good sources to read up on function problems (I deem myself knowledgeable of decision problems)?


texts:
I am working on edge detectors: Canny, Sobel, Prewitt, and Roberts. These edge detectors work with conventional kernels to compute the edge. The kernel values are multiplied with the pixel values of an image, and then we compute an average value.

Suppose my average pixel value is 12, while the old value (of the original image) was 10. I know how these edge detectors work, but how do I determine using the gradient value that an edge is present in the image or not? I am pretty confused with these matrix calculations, specifically about angles of edges.


texts: Does Cook and Ruzzo's result also hold for logspace-uniform AC0?

texts:
In Cook's famous paper on $\mathsf{NC}$, he cites the following result:

  PROPOSITION 4.7 (Cook and Ruzzo, 1983). $\mathsf{AC}^k$ consists of those
  problems solvable by uniform unbounded fan-in circuit families in $O(\log^k n)$ depth and $n^{O(1)}$ size.

where $\mathsf{AC}^k$ here is defined for $k \ge 1$ as the class of problems solvable by an ATM in $O(\log n)$ space and $O(\log^k n)$ alternation depth. (Of course, the definition of $\mathsf{AC}^k$ usually goes the other way around, but given the equivalence it is all just a matter of presentation.)

Note the above is the logspace-uniform version of $\mathsf{AC}$. It was later acknowledged that for $\mathsf{AC}^0$ the more restrictive dlogtime-uniformity is preferable. There is also an interesting result regarding the (in)equality of dlogtime- and logspace-uniformity of $\mathsf{AC}^0$. We also know that dlogtime-uniform $\mathsf{AC}^0$ is characterizable as the class of problems solvable by ATMs in $O(\log n)$ time (instead of space above) and $O(1)$ alternation depth.

Given that dlogtime- and logspace-uniformity most likely does make a difference for $\mathsf{AC}^0$ I am interested whether the Cook and Ruzzo result can be extended to the case of $k = 0$ and logspace-uniform $\mathsf{AC}^0$.
Unfortunately, in Cook's paper, "Cook and Ruzzo, 1983" is only listed as "unpublished theorem," so I was unable to check whether the proof also works for $k=0$ (and whether Cook and Ruzzo had simply neglected it for some reason).


texts: Sources on dictionary learning and related algorithms

texts: In the context of signal processing and sparse representation of signals, there is a topic called dictionary learning which is basically about how to's of the selection of basis functions used for sparse representation. I am looking for sources explaining the topic with a section on dictionary learning algorithms and probably a comparison made among them.


texts: Approximation algorithms for NP-complete problems

texts: Given two NP NP-hard functional problems, A and B, one can find a reduction of A to B. Is it possible to find a reduction that would honour approximations? That is, if you have an approximation algorithm for B that yield approximate solutions within accuracy $\delta$, is it possible to reduce A to B in such a way that one would be able to derive an approximate solution of A within accuracy $\epsilon = \epsilon(\delta)$?


texts:
I am studying formal languages and playing with writing my own parsers for them. I have a context free grammar parser already that works well. I am wondering if anyone can point me towards actually implemented examples of rewriters. For example, suppose I had the rules

WORD: [A-Z]+

QUOTE: "

And I wanted to input a lot of words,put quotes around each one, and write out the string. Or go back and forth. Something like this:

(WORD [' '])+   <--> (QUOTE WORD QUOTE [' '])+

That seems kind of possible to implement automatically without ambiguity, but I was hoping someone had seen something along that line that already exists.


texts: Matching Upper Bound for Online Problems

texts:
I have an online problem and I want to prove that no deterministic online algorithm is competitive.

Let $\texttt{ON}$ be an online algorithm and $\texttt{OPT}$ an optimal offline algorithm (an adversary). Given a sequence of $n$ inputs $\sigma=\sigma_1\sigma_2\cdots\sigma_n$ revealed in an online fashion, let $v(\texttt{ON}_\sigma)$ and $v(\texttt{OPT}_\sigma)$ be the values achieved respectively by $\texttt{ON}$ and $\texttt{OPT}$.

What I proved is this: let $\sigma=\sigma_1\sigma_2$ be an 2-input sequence. If $\texttt{ON}$ acts on $\sigma_1$ with action $a$, then I could find an input $\sigma_2$ such that $$\frac{v(\texttt{OPT}_\sigma)}{v(\texttt{ON}_\sigma)},$$ is unbounded.

The problem is that, if the action $a$ changes, then the above ratio could be equal to $1$.

Is it sufficient to prove that the ratio is unbounded for some action $a$? Or must it be true for any $a$?


texts: Reading CLRS analysis of hashing with chaining

texts:
I'm currently reading an analysis hashing with chaining, and it goes over two examples:

  In the first, the search is unsuccessful; no element in the table has
  key k. In the second, the search successfully finds an element with
  key k.

(This is all under the assumption of simple uniform hashing). I understood the analysis for the first case, but the second confuses me. The book goes:

  The situation for a successful search is slightly different, since
  each list is not equally likely to be searched. Instead, the
  probability that a list is searched is proportional to the number of
  elements it contains.

The above sentences are what confuses me. Why is each list not equally likely to be searched if both operate under assumption of simple uniform hashing? And why in the world would the number of elements a list contains have any effect at all on the probability that the list is searched? I would think it's the opposite...the number of elements searched in a list depends on the probability that a key is hashed to a particular index (where the list is).


texts:
Let suppose that there exists deterministic polynomial algorithm $A$ that  approximates the probability that a given boolean circuit $C$ accepts random input with an error at most $\frac{2}{5}$. More precisely, for a boolean circuit $C(x_1, .., x_n)$, $A$ computes a number $A(C)$ such that

$$|\Pr[C(U_n) = 1] - A(C) | \le \frac{2}{5}.$$

$U_n$ is a uniformly distributed random variable with values in $\{0,1\}^n$.

I want to prove that under that assumption $P=BPP$.  How can I do that?

Obviously, the problem is with $BPP \subseteq P$.
I see that I should create a boolean circuit for "coin tosses", but how?


texts: Do you have to do reduction both ways to prove a problem is NPC?

texts: Also, what's the difference between transforming a problem into another problem and doing a reduction? They sound synonymous to me. Thank you!


texts: Number of nonnegative solutions of linear Diophantine inequality

texts:
Given inequality $Ax + By \le C$, where $A, B, C$ are integers, $A$ and $B$ are coprime and $C < AB$. I need to find number of non-negative integer solutions of it.

Is there exists algorithm which run in polynomial time? For example if $A \le 10^{10}, B \le 10^{10}$ it should work less than a second. Thanks in advance.


texts: Partial recursive function with no total recursive extension

texts:
We define a partial recursive function $f:\{0,1\}^* \longrightarrow \{0,1\}^*$ to be semi-good if we can define a total recursive function $g:\{0,1\}^* \longrightarrow \{0,1\}^*$ from $f$, such for all $x \in \{0,1\}^*$ either $f(x) = g(x)$ or $f(x)\uparrow$.

Now I want to prove that there exists a partial recursive function that is not semi-good.

I must make a partial recursive function that is not semi-good for example $f_1$ ,but my problem is that I must show that I can not define any total recursive function $g:\{0,1\}^* \longrightarrow \{0,1\}^*$ from $f_1$.

I don't have any idea how can I show this. Can I use the fact that a specific language like $L$ is not recursive so its characteristic function $\mathcal{X}_L$ is not total recursive function? How can I make the partial function from this fact?


texts: Is a non-deterministic turing machine that both accepts and rejects the same input valid?

texts: I.e. - if a TM accepts the word 0011100 on one path, while on another the same word is rejected. Do we say that 0011100 is part of the language, or do we say that it is not a valid TM?


texts:
Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$.

Prove or disprove:
The value of a maximum flow for $N$ can’t be $56$.

I'm trying to figure out how to definitely prove this.
I think that this is not possible because of no combination of $12X + 18Y$ (where $X$ and $Y$ are integers) will ever $= 56$. Is there a better way of saying this?
Am I right to say that an integer solution to $12X + 18Y = 56$ is what the Fold-Fulkerson algorithm implies?


texts: Applying Johnson's algorithm on undirected graph with negative edge weights

texts:
Currently we are discussing applying Johnson's algorithm on undirected graph with negative edge weights. And the graph may contains cycles, but the sum of weights of any cycle is guaranteed to be non-negative.

If we consider the undirected graph as bi-directed, then any negative-weight undirected edge will create a negative cycle in the bi-directed graph, and violate the prerequisite of Johnson's algorithm.

Is there any altered version of Johnson's algorithm can handle such scenario?

-- update 2017/12/30 --

Sorry, I forget to mention an additional constraint for the path: the path should be simple, which means one edge could only be travel for once.


texts: Algorithmic consequences of algebraic formula for partition function?

texts: Bruinier and Ono have found an algebraic formula for the partition function, which was widely reported to be a breakthrough. I am unable to understand the paper, but does it have any algorithmic consequences for fast computation of the partition function?


texts: Finding perfect matchings with as few database queries as possible

texts:
I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows:

There are an equal number of men and women.
Each man has a perfect match with one and only one other woman.
No two men have a perfect match with the same woman.
A perfect matching is a set of matches where all matches are perfect (as above).
There exists a database that can determine how many matches are perfect in any set.  You can query the database with a set to learn how many matches are perfect in that set, but you don't learn which matches.

I'm looking for an algorithm that finds a perfect matching that matches all the men and women, while querying the database the least amount of times.

Is there an efficient algorithm for this problem?


texts: Is the spigot algorithm for $\pi$ useful for computing all the digits of $\pi$?

texts:
I'm asking the question here because it's not a purely mathematical question and the answer also depends on how computers work. I think that according to the Wikipedia article Bailey–Borwein–Plouffe formula, there is a spigot algorithm for quickly computing in terms of any natural number $n$ expressed in binary the $n^{th}$ binary digit of $\pi$ after the decimal place in polynomial time. Combining information from the Wikipedia articles Computational complexity of mathematical operations and Fürer's algorithm, I figured out that there exists an algorithm that computes every digit of $\pi$ in order within the time $O(n (log(n))^2 2^{(2 log * n)})$ where $log*n$ is the super root of $n$ to the base 10. I also think that according to this answer, there is an algorithm that for any natural number $n$ computes with the binary notation of $n$ as input, the $n^{th}$ binary digit of $\pi$ after the decimal place in time $O(n^3(log(n))^3)$ of the number of binary digits of $n$.

I believe both of those algorithms have a decimal analogue. If so, it seems that using the Spigot algorithm for each decimal digit of $\pi$ one at a time is slower than doing other algorithm for computing all of the digits. You might be wondering how it's possible to compute it faster than can be done by using any Spigot algorithm on each digit one at a time. Because the faster method of computation keeps some of the statements it previously computed and uses it to shorten the length of time it takes to compute the next digit to less time than it would have taken using the spigot algorithm. My question is not "Is the asymptotically fastest way to compute all the decimal digits of $\pi$ in order faster than the method of computing all its decimal digits by using the asymptotically fastest spigot algorithm for $\pi$ for each digit one at a time in order?" The reason is because I haven't thought of a proof that an asymptotically fastest algorithm for either task even exists. Here are my 2 questions:

Is there an algorithm for computing all the decimal digits of $\pi$ that's asymptotically faster than every method by finding a spigot algorithm for a single decimal digit of $\pi$ and using it on every digit one at a time in order?
If not, then is the fastest way to grow a copy of all the decimal digits of $\pi$ up to a certain point bigger and bigger on Earth to use such a spigot algorithm.

In the real world, computers are a certain size so the spigot algorithm might save memory so it might be faster to do it using the spigot algorithm for that reason. On the other hand, the faster method might only require an amount of memory that varies as the log of the number of digits that have so far been computed.

The real meaning of question 2 is quite complex and depends on what people consider feasible to build so I can't figure out a way to explain really clearly what I mean by it, but I believe that even after showing that the answer to question 1 is no, it's still not easy to figure out whether the answer to question 2 is yes or no.


texts: first order logic to normal form order of operations

texts:
∃y∀x [A(x) ∧ B(y) -> C(x,y)]
 ∃y∀x [¬(A(x) ∧ B(y)) v C(x,y)]
 ∃y∀x [¬A(x) v ¬B(y) v C(x,y)]

I need to convert the above to conjunctive normal form. I'm a little confused about the order of operations in the case of both existential and universal quantifier and which part of the expression they apply to.
From the last step, would I skolemize y across the entire expression meaning:
∀x [¬A(x) v ¬B(S(x)) v C(x,S(x)]

or do I take the universal quantifier first?


texts: Lower bound on the covering radius of a code

texts:
Let $C$ be a $[n,k]$ linear code over $\mathbb{F}_q$.

Suppose that $\rho$ is the covering radius .

I want to show that $\rho \geq \frac{n-k}{1+ \log_q{(n)}}$.

Could you give me a hint how we could show this?


texts: NP Completeness: definition of search problem: Existence and Infinite Search space

texts:
For NP completeness proofs/reductions, I need to establish that the problem is a "search problem"...

However, the definitions seem to be somewhat vague.  If the definition of the search problem is:

Search problem is a problem which has the following input/output form: Given instance I (graph G), we are asked to find a solution if one exists and if no solution exists we output No.

Aditionally, solution must be verifiable in polynomial time.

The part bracketed between the H-lines is where I am confused.  Is this definition for a requirement for a non-deterministic polynomial time algorithm stating that the algorithm actually knows when the search has been completed?

In other words, what guarantee is there that the solution exists at all, and that the solution has been found?

Take for example an infinite search space.   No matter how many random guesses I make, there is still a chance that I never discover the solution, never know that the search space has been comprehensively searched, and never return "NO."

So: two questions:  how does one include the word exist in the definition--this seems like something that cannot be proven...

And: How does the non-deterministic search problem search the infinite (unbounded) search space?  Why do I not also have to establish that the space is also finite? (incidentally, all the search spaces I have encountered in Dasgupta's book are, in fact, finite: TSP, Knapsack, Clique, etc.

So I'm really confused by the use of these words, and the lack of assumptions surrounding this definition.  How does it actually work?


texts: Minimizing $E_{out}$ theoretically in linear regression

texts:
Related to linear regression with noise I've been given the following functional, depending on the function $h$:

$$ E_{out}(h) = \int \int (h(x)-y)^2 dx dy$$

I want to prove that the function that minimizes $E_{out}$ is

$$h^*(x) = \int yp(y|x)dy$$

But I don't have any math tools to do it. Which things should I know to be able to solve this problem? I know a little variational calculus in one variable and I see this similiar, but I don't know any results about multiple variables. Is this a good approach or it is better to think about other tools? Also, I haven't been given any information about the term $p(y|x)$ in the second integral. Any help about the meaning of this expression would be appreciated too.


texts:
The PCP-Theorem states that $PCP(log(n), 1) = NP$. So can anyone explain, where $PCP(1,1)$ is located in relation to other classes?
My thoughts:

$P \subseteq PCP(1,1) \subseteq PCP(log(n)) = NP$
Is there some theorem like "$P \neq NP \implies PCP(1,1) ...$"
What is the relation to the probabilistic classes like $BPP$ and $RP$?


texts: Is there a concept called "white waveforms" in computer science?

texts:
It sounds like the lecturer is speaking

  If you for example want to play a
  music file, mp3 file, well you know, given
  that you've taken a programming course
  before, all right? How would you do this?

  Well, you would look up on Wikipedia, what
  are the specifications of an mp3 file,
  and then you would sit down over a long
  weekend and you could probably write
  something in Python or in C, takes the file decodes it generates
  the white waveforms and so on.

  and it's
  not a big deal right after a couple days
  you will have a program that takes that
  date and generates the output, that's fine.

The lecturer used a term "white waveforms".

I know the visual of a waveform may look like this figure.

I also know .wave is one type of audio filename extension.

I am trying to figure out what "white waveforms" is.

I understand the approximate meaning that the lecturer is trying to say is playing mp3 file.

So, what is "white waveforms"?


texts: How to show MULT={a#b#c| a,b,c binary natural numbers and a ✕ b = c} is in Log Space?

texts:
Let MULT$=\{a\#b\#c| a,b,c \text{ binary natural numbers and } a\times b=c\}$

Prove that MULT $\in L$

How do I show that this language, MULT, is computable in Logarithmic space?

Let us assume a#b#c is on the input tape, we now need away of multiplying a with b and checking if the product is c, while using only $log(n)$ space while n is the length of the input.


texts: Determine if the sequence of numbers is a post order traversal of a binary tree

texts:
The question is: given a sequence of numbers, find an algorithm that determines if the sequence of numbers is in post order traversal of a binary search trees.

Up to now, I have understood the following:

In the post order traversal of the binary tree it follows Left, Right, Root. So the Left value has to be less than the Right value.
The last element of the sequence is the root, assuming the sequence was in the post order traversal.

I do not know how to progress further with this. Also, is there a way to create a Divide and Conquer algorithm for this?


texts: Communicating Sequential Processes: SQUASH

texts:
In C.A.R Hoare's Communicating Sequential Processes (1978), he presents the SQUASH problem:

  Replace every pair of consecutive asterisks "**" by an upward arrow "↑". Assume that the final character input is not an asterisk.

The given solution is:

X :: *[c:character; west?c →
  [c ≠ asterisk → east!c
   ▯c = asterisk → west?c;
     [c ≠ asterisk → east!asterisk; east!c
      ▯c = asterisk → east!upward arrow
]]]

He then challenges the reader to adapt this process to deal with input that ends in an odd number of asterisks.

It seems that this can be done by making the second west?c an alternative command, such that if getting next input from west fails, we output c to east:

X :: *[c:character; west?c →
  [c ≠ asterisk → east!c
   ▯c = asterisk → [west?c;
     [c ≠ asterisk → east!asterisk; east!c
      ▯c = asterisk → east!upward arrow
     ▯east!c
]]]]

Is this correct? Is there a better solution?


texts: Quasigroups, congruences and recognizable subsets

texts:
My question refers to the draft of Mathematical Foundations of Automata Theory, IV.2.1 (pages 89ff in the pdf). I will repeat everything necessary nevertheless:

Let $M,N$ be monoids and $\varphi: M \rightarrow N $ a monoid morphism. We say that a subset $L$ of $M$ is recognizable by $\varphi$ if there is a subset $P$ of $N$ such that $L = \varphi^{-1}(P)$. As is known, the rational languages are precisely the recognizable subsets of $\Sigma^\ast$.

Furthermore, we define an equivalence relation $R_\varphi$ by $u R_\varphi v :\Leftrightarrow \varphi(u)=\varphi(v)$.
This relation is a congruence relation, that is $\forall s,t,u,v \in M:s R_\varphi t \Rightarrow usv~R_\varphi~utv$.

We say that a congruence relation $R$ saturates $L$ if for all $u \in L$, $uRv$ implies $v \in L$.
Then in the above document, the following proposition (IV.2.2, page 90) is stated:

Let $\varphi : M \rightarrow N$ be a monoid morphism and let
$L$ be a subset of $M$. The following conditions are equivalent:

(1) $L$ is recognised by $\varphi$

(2) $L$ is saturated by $R_\varphi$

(3) $\varphi^{-1}(\varphi(L))=L$

Proof. (1) implies (2). If $L$ is recognised by $\varphi$, then $L=\varphi^{-1}(P)$ for some subset $P$ of $N$. Thus if $x \in L$ and $x R_\varphi y$, one has $\varphi(x) \in P$ and since $\varphi(x)=\varphi(y), y \in \varphi^{-1}(P)=L$.

(2) implies (3). If $x \in \varphi^{-1}(\varphi(L))$, there is $y \in L$ such that $\varphi(x) = \varphi(y)$, that is $x R_\varphi y$. Thus, $x \in L$, and $\varphi^{-1}(\varphi(L)) \subseteq L$ follows. "$\supseteq$" is trivial.

(3) implies (1). Let $P:=\varphi(L)$, then $\varphi^{-1}(P)=L$.

I want to weaken the assumptions made in the proposition. Namely, assume tgat the  $N$ in the above definitions is a proper groupoid (in fact, I need to deal with loops), that is, associativity and identity are lost. Further, $\varphi$ need not be a morphism (the relation $R_\varphi$, defined in the same way as above, a priori need not be a congruence anymore) and we restate (1) accordingly (as formally, the notion of a "recognable subset" is not defined for groupoids).
Then my questions are

  (1) Is $R_\varphi$ still a congruence if we demand $\varphi$
  to be a morphism of groupoids (loops)?

  (2) Does the proposition still hold? Does it if we assume that $R_\varphi$ is  not a congruence?

  (3) What other sources (preferably monographs) are there that you recommend as comprehensive introductions to algebraic automata theory, esp. concerned with the role of monoids, semigroups (and maybe more general structures as groupoids) and their connection with automata and languages?

Personally, I think they are both true, as for (2), neither the morphism properties, nor associativity nor congruences seem to be used in the proof. And for (1), I don't see where one would need associativity to prove it.
But it may well be that I overlooked something (which is why I ask...).


texts: Language whose intersection with a CFL is always a CFL

texts:
Prove or disprove: If the language $L$ is such that for every context-free language $L_0$, the language $L \cap L_0$ is context-free, then $L$ is regular.

I haven't managed to prove this, but I'm pretty sure there is no counterexample.


texts:
Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself.

I've tried thinking what would be the best for m to define it but couldn't get anything specific.

Maybe $\mbox{Number of sorts =}\prod\limits_{x\in \mbox{children}}\mbox{Number of sorts}(x)$
Meaning that starting at the root I call the the method recursively multilying each result by the previous children's result. When we reach a node with size 1 we assume that there's just 1 topological sort;

If this is correct I'd really appreciate some help with proving correctness and if not a explanation why and a clue could be nice :)