texts: How can one find a job after working as a freelancer?

texts:
I was looking for a StackExchange site that would be the best for this question, so if this isn't the best place, please feel free to redirect me elsewhere.

I have worked as a Freelancer somewhat out of concern that I would flop on the quote coding interview unquote.  I ran across a book called the self-taught programmer who learned skills over a year's time and then got a job.  I have heard something similar one a training website.  It seems that such persons would not have the same exposure to the skills taught in a full 4+ year Computer Science or Software Engineering degree program.

How would you, if you were in my position, find a job and feel confident going into an interview.  How could people like those mentioned above, feel confident when going into an interview or how would they know what to expect in an interview?  To answer this, I should add a few details.  My studies and work as a freelance Web Developer/SW Engineer/Programmer have been spread over the past several years.  When I got my degree in Computer Engineering in 1989, I didn't have a course on Algorithms.  I worked in a different field and then returned to this technology field several years ago.

In order to feel confident with Algorithms, I felt that I needed to review Calculus, Probability and Statistics.  I also learned Discrete Math.  Because of an interest in Machine Learning, I also studied Linear Algebra, and etc.  Now, I can better approach the study of algorithms.  The point is that it would be hard to imagine learning various languages, developing applications, learning all this math and then learning Algorithms.  Certainly all that could not be done in just one year.  In addition, these stories I heard on some training websites mention various success stories, and yet none of those sites have any courses on Algorithms, Design Patterns or even Math.

Since, I am only now able to jump into studying algorithms, initially, I need a job that does not require a "coding interview."  How can I find the jobs that will not make me look unskilled?  Maybe I need to find recruiters and say this is where I am and this is my limitation.

Thanks in advance for any direction,
Bruce


texts: Is there an algorithm for algorithms time/space complexity optimisation?

texts:
In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of algorithms?

For example an implementation of bubble sort as an input for such an algorithm would produce an implementation of a sorting algorithm with time complexity closer to $O(n\log n)$.


texts: Is purely functional programming in some situations less efficient than imperative programming?

texts:
I am used to implementing algorithms in imperative languages. Many of the algorithms I have implemented use hash maps, hash sets, mutable arrays, heaps, doubly linked lists, etc. I understand that some of the data types don't exist in functional languages. For example, it may be hard to implement hash data structures or mutable arrays.

With that in mind, is purely functional programming in some situations algorithmically more expensive than imperative programming? For example,

If I want to implement timer heap with O(1) peeking of next timer to expire, O(log N) removal of next timer to expire, O(log N) addition of new timer, O(log N) removal of arbitrary timer and O(log N) adjustment of timer expiration time, can I implement the timer heap in a purely functional programming language?
If I want to implement a timer wheel, can I do so in a purely functional programming language?
If I want to implement O(1) lookup in a set or a map, meaning in practice hash structures are needed, can I do so in a purely functional programming language?
If I want to implement a ring buffer for efficient communication between threads in a producer-consumer pattern, can I do so?
If I want to maintain a a list of free TCP ports in a firewall, doubly linked list would be a suitable O(1) data structure for that, allowing O(1) removal of an arbitrary port, but can I do so in a purely functional language?
If I want to have a fast and efficient O(1) bit set, can I have such a construct in a purely functional language?

Note I'm not interested in large vs small constant in the runtime. I'm interested in runtime becoming fundamentally different, e.g. O(log N) instead of O(1). Of course functional algorithms may be less efficient due to the extra overheads of added abstraction in terms of runtime constant.


texts: Meaning of # in descriptions of languages

texts:
This is a very simple question, but I cannot find the answer anywhere, mostly because I don't know how else to ask about what I'm looking for. I have a homework assignment that has to do with pumping lemma, which asks me to use the pumping lemma to prove that the language given is not regular.

{x₁#x₂#x₃|x₁, x₂, x₃ ∈ {a, b}* and x₂ = x₃ᴿ}.

My only question is this — what does the # mean? My teacher is currently unavailable, so I'm unable to ask him.

If someone has a link to a list of notations and their descriptions, I'd very much appreciate it, but if you're only able to tell me what # means, that's fine as well.


texts: Question about "Type checking a multithreaded functional language with session types" by Vasconcelos et al

texts:
I have been reading the paper[1] in the title. But there are some parts of it that are unclear to me, more specifically the way you typecheck a lambda. I have attached the typing rules below as images[2] [3] Typing them all in Mathjax would have been a lot of work.

I will explain the issue I am having by means of an example.

Given the program in listing 1, we first apply the rule C-Let. This means that we typecheck the first binding, namely new !Int.End which yields the type [!Int.End].  $\Gamma$ now contains a mapping $x \rightarrow [!Int.End]$. Then we typecheck the next let, using C-Let once more. This time we typecheck accept x, which first makes sure that $x$ is of the proper type. $\Gamma$ contains this mapping so that is indeed the case. This yields the type Chan c. Note that when you look at the typing rule for accept, $c$ in this case is a so-called "fresh" variable. The rule C-Accept also inserts the session type into $\Sigma$. So $\Sigma$ contains a mapping $c \rightarrow\ !Int.End$ and $\Gamma$ contains two mappings, namely $\Gamma = x \rightarrow [!Int.End] , v \rightarrow Chan \ c$

We then proceed to typecheck the last body of the most-inner let. The first statement is a send statement so we apply rule C-SendD. Typechecking the number $5$ yields type Int, so that part is correct. $v$ yields the type $Chan\ c$. $\Sigma$ indeed contains a mapping $c \rightarrow\ !Int.End$. So the rule C-SendD finally yields the type $\Sigma;Unit;c:End$ where the first part of the entry in $\Sigma$ has been consumed, leaving the session type for $c$ to $End$.

Finally we can apply the rule C-Close which also typechecks properly.

Listing 1

let x = new !Int.End in
let v = accept x in
  send 5 on v;
  close v;

We can now transform the above example to the following:

Listing 2

let x = new !Int.End in
let v = accept x in
let f = (Lambda x:Int . (close v))
  send 5 on v;
  (f 1);

Listing 2 shows that instead of just calling close on the channel we have stored that operation inside a lambda. We will play typechecker one more.

The first part of the typechecking is the same as above. So we have arrived at typechecking the body of the second let, namely let f =.... At this point $\Sigma = c \rightarrow\ !Int.End$ and $\Gamma = x \rightarrow [!Int.End] , v \rightarrow Chan \ c$.

The body of the lambda uses a channel that is defined outside of the lambda, namely $v$. According to the paper, the required $\Sigma$ should be embedded in the type signature of the lambda. However, this is where things get unclear. If I follow the typing rules I would have written down the lambda as $(Lambda\ [c \rightarrow End,\ x:Int]\ .\ (close\ v))$. But this is impossible, I think.

Recall that the rule C-Accept uses $fresh$ to "generate" a symbol that will be the identifier in $\Sigma$ and the second part of the type of the channel (e.g., $Chan\ c$). This means that it is impossible for the programmer to write down this identifier. Unless, of course, the channel is the parameter of the lambda itself. Then we can use $\alpha$-renaming. But this is not the case here, the channel is simply captured by the lambda and the parameter is $x$ which is ignored in the body of the lambda.

So, there are two options the way I see it. The text in Listing 2 is illegal for the reason that you can not capture a channel that has not been passed to the lambda as a parameter. However, the paper shows an example of this at page 9. So this reasoning is probably faulty.

The second reasoning I can come up with is the following. At the time the lambda is typechecked (as the binding to $f$), the typechecker will error because we are calling close on a channel that has session type $!Int.End$ in $\Sigma$. But, this could then be resolved by delaying the typechecking of the lambda until the point that it is invoked. But then, this does not require the programmer to write down the $\Sigma$ in the type signature of the lambda.

I hope the problem I have sketched here is clear. Any feedback is appreciated.

[1] Paper discussed in this question


texts:
I am a little confused by the complexity proof of Radix Sort.
For counting sort, the complexity reported is $O(n+R)$, where $n$ is the number of items and $R$ is the range.
But this is not entirely correct, right? To do binary arithmetic on numbers as big as $R$, I need $\log_2 R$ operations for any deterministic hashing function. So the complexity of counting shot should be $O(\log_2 R \cdot (n+R))$.
Then the complexity of radix sort with base $b$ should be $O(\log_b R \cdot \log_2b \cdot (n+b))$, which is equivalent to $O(\log_2R \cdot n)$. For range $R = \Omega(n)$, this is $\Omega(n \log n)$ and thus not $O(n)$.
Can someone point out where I am going wrong in my proof? As far as I know, radix sort is $O(n)$ for $R = O(n^c)$.


texts: Shuffling a collection too large for memory

texts:
I have a set that is too large to hold in memory but I have a function that I can use to compute a value within the set given an index.  I'm curious if there's a standard way to shuffle this set, a pseudo-shuffle is acceptable and expected.

I imagine a function that is initialized with some parameters, including the size of the set to be shuffled, and that I can call repeatedly, getting unique and pseudo-random indexes each time that I can use to generate the corresponding value in my set.  I also imagine that this function is periodic and repeats after I've gone through all values once (so there's some mod relation).

This function need not be cryptographically secure but rather be easy to construct and hold in memory so that the next "random" value of the set may be generated.

Here's a concrete formulation of the problem. I want to iteratively generate "random" colors in the RGB spectrum without repeats. I don't want to create an array of 256^3 elements and shuffle them. I want a function that on each call provides an index in the range that I have not yet received, until I've exhausted the range.

How might you construct a function that satisfies the above?


texts:
I've been given the following values to add to a binary search tree (in the order given)

56, 35, 55, 58, 29, 15, 16, 5, 71, 92, 69, 95

and this is what my tree ended up like:

but apparently it's wrong?


texts: What is the maximum possible degrees of a vertex of an MST

texts: What is the number that a minimum spanning tree can have a vertex with degree at most? Is there any rule? Is it related to the number of vertex or edge? Or not?


texts: How are these problem variants that ask about the size of optimal solutions in NP?

texts:
I just started reading Vazirani's book "Approximation Algorithms". It is legally available online here.

On page 5 (23 in the pdf), it says that the following decision problems are in NP:

Is the size of the minimum vertex cover in $G$ at most $k$?
Is the size of the maximum matching in $G$ at least $l$?

I can't see why this is true. If, say, the first problem is in NP, then each valid instance (graph) has a Yes certificate which proves that the graph has a minimum vertex cover of size at most $k$.

But, how can one deduce from a certificate something regarding the size of the minimum vertex cover?


texts: Exercise 11 of section 3.2.2(The art of computer programming)

texts:
I'm asking about its part a.

a) If $f(z),\space a(z),\space b(z)$ are polynomials with integer coefficients, let
us write $a(z)\equiv b(z) (\operatorname{mod} f(z)\space and\space m)$
if $a(z) = b(z) + f(z)u(z) + mv(z)$. Prove that the following statement
holds when $p^e>2$ (p prime) , $f(0)=1$:
If $z^\lambda \equiv 1 (\operatorname{mod} f(z)\space and\space p^{e})$ and $z^\lambda \not\equiv 1 (\operatorname{mod} f(z)\space
and\space p^{e+1})$ then $z^{p\lambda} \equiv 1 (\operatorname{mod}
f(z)\space and\space p^{e+1})\space but\space z^{p\lambda} \not\equiv
1 (\operatorname{mod} f(z)\space and\space p^{e+2})$

Here's my reasoning:
We have $z^\lambda$ has the form of
$$f(z)u(z) + p^ev(z) + 1$$
where $p^{e+1}|f(z)u(z),f(z)|p^ev(z)$ and $v(z)\not\equiv 0(\operatorname{mod} p)$  (*)
Or we can just simplify it as: $z^\lambda = Z + 1$, where Z is a multiple of $f(z)$ and $p^e$ but not $p^{e+1}$'s one.
So:$$z^{p\lambda} = 1+{p\choose 1}Z+{p\choose 2}Z^2+...$$
$z^{p\lambda}-1$ is certainly divisable by f(z). Also, we can see that ${p\choose k}Z^k(1\leqslant k\leqslant p-1)$ is a multiple of $p^{e+1}$ and $p^{e+2}|Z^p$(due to the fact $p^e>2$,$p^{pe}|Z^p$ implies $p^{e+2}|Z^p$). We now can conclude:
$$z^{p\lambda} \equiv 1 (\operatorname{mod}
f(z)\space and\space p^{e+1})$$
Next, it's easy to establish: $p^{e+2}|p^{(e+1)k}$,where $k\geqslant$ 2. And that shows:
$$z^{p\lambda} \equiv 1 + p^{e+1}v(z) (\operatorname{mod} p^{e+2}\space and\space f(z))$$
Due to (*),$1+ p^{e+1}v(z) \not\equiv 1(\operatorname{mod} p^{e+2})$, completing the proof

My proof is based on the answer of excercise 11. And the difference between it and mine makes me confused.

If $p^{e+1}v(z) \equiv 0 (\operatorname{mod} f(z)\space and\space p^{e+2})$, there must exist $a(z)$ and $b(z)$ such that $p^{e+1}(v(z) +pa(z)) = f(z)b(z)$.
Since $f(0)=1$, this implies $p^{e+1}|b(z)$(by Guass's lemma 4.6.1G); hence $v(z) \equiv 0 (\operatorname{mod} f(z)\space and\space p)$, a contradiction.

So, my questions are:
1. Why is the above argument necessary?
2. Is the Gauss's lemma 4.6.1G the one in wikipedia?


texts: Consider a $2$-party communication model in which $A$ wish to send to $B$ an $n$-bit string. It is very easy to prove that any deterministic protocol for this problem requires $\Omega(n)$ bits to be transmitted. It is also well-known that any randomized protocol for this problem also requires $\Omega(n)$ bits to be transmitted. Although this considered to be a trivial fact, I failed to formally prove (or find a formal proof) for this. So my question is: how to show that any randomized protocol for this problem requires $\Omega(n)$ bits to be transmitted?


texts:
In Sipser's book of Theory of Computation, related to Reducibility, it's written

  if A is undecidable and reducible to B, B is undecidable.

The confusion is, only a solution to B determines a solution to A, if i'm not wrong.
So, for instance if B is decidable and A is undecidable, what does it mean? Here B isn't undecidable.

Hope you got it.


texts: How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?

texts:
In the context of languages (not grammars), I know following:

  $LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$
  $LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)$
  $LL(0)\subset LR(0)$
  $LL(n)\subset LR(1)$ for all $n$'s

How does $LL(n)$ languages compare with $LR(0)$, for $n>1$?


texts: What do functions look like, if I stated out with the categoical model of my type theory?

texts:
I see how objects in a category stand for types, but where do I find the terms and more specifically the rules which tell me which of them are allowed? When I e.g. consider a Cartesian closed category as model of a type theory, how are term constructors represented?

I guess this is the same as asking how do I know or specify appropriately what the homsets of this category are, which I assume are in bijection with the lambda terms. The Curry–Howard–Lambek correspondence as presented at the end of the Wikipedia page Curry–Howard–Lambek correspondence presents all terms conventionally as in a type theory, but if I start out with a category, the model, then I must have specified them in a more algebraic sense.

And once given, does the model also represent $\beta$ and $\eta$ conversion? I actually read on the (quite too high level for me) nLab that morphisms relate to substitutions. Then I guess the lambda terms are somehow elements of the objects.


texts: How to derive the size of $k = \log n$ base from $\frac{1}{2^k} = O(\frac{1}{n})$?

texts:
"We need $k$ to be large enough so that $(\frac{1}{2})^k = O(\frac{1}{n})$, and to do this we can choose $k = \log_2 n$. Thus, when $k = \log_2 n$, the size of the active region has been reduced to a constant, at which point the recursion bottoms out and we can search the remainder of the array directly in constant time."

Im not certain on how they determine that $k$ needs to be $\log_2 n$ from $(\frac{1}{2})^k = O(\frac{1}{n})$. Can someone please clarify the logic for this please?


texts: Justification for the pumping lemma of context free languages

texts:
I understand intuitively why the pumping lemma for regular languages must hold. That is to recognize a infinite string with a finite amount of states you must repeat states and you can "pump" those repeated states as many times as you wish.

However for the context free language version I can't seem to come up with the same intuitive understanding for why the lemma holds. My textbook mentions abusing the fact every CFG can be put into Chomsky normal form and then using some properties of binary trees to show productions can be pumped but Im having a hard time following why this would lead to repeated states, let alone two repeated states.


texts: Can Floyd-Warshall algorithm be used in an undirected graph with negative edges?

texts:
So i know that it cannot be used if the directed graph has negative cycle, but what about the undirected graphs with negative edges?

is it going to always work, or sometimes or never?


texts:
If the running time of an algorithm scales linearly with the size of its input, we say it has $O(N)$ complexity, where we understand N to represent input size.

If the running time does not vary with input size, we say it's $O(1)$, which is essentially saying it varies proportionally to 1; i.e., doesn't vary at all (because 1 is constant).

Of course, 1 is not the only constant. Any number could have been used there, right? (Incidentally, I think this is related to the common mistake many CS students make, thinking "$O(2N)$" is any different from $O(N)$.)

It seems to me that 1 was a sensible choice. Still, I'm curious if there is more to the etymology there—why not $O(0)$, for example, or $O(C)$ where $C$ stands for "constant"? Is there a story there, or was it just an arbitrary choice that has never really been questioned?


texts: What is a min-max theorem in graph theory?

texts:
I'm currently studying a paper which uses extensively the term 'min-max theorems' in graph theory, and claims to present a tool allowing to generalize these theorems. (here is the link to the paper if needed)

Among those, we can find for example :

The max-flow-min cut theorem.
Edmond's disjoint arborescences theorem (link).

I have some intuition about what a min-max theorem would be, but I can't come with a concise and precise definition.

My question is : what would be a definition of such a family of theorems ?

And a second question along : is this min-max theorem concept always linked to the strong duality theorem, meaning that they mainly state that one problem is actually the dual of the other, like the max-flow-min-cut is ?


texts: What is the relationship between entropy rate and quantization?

texts:
I have a totally random source of signal data that looks like a typical normal distribution.  I've included an image as I like pictures:-

The source has a mean of 0, and a standard deviation of 1.  It's analogue and therefore of infinite resolution. Very typical.

I then sample the signal with a Tricorder and record the raw data.  Clearly as the original signal is random, irreducible information entropy is accrued at some rate, and will be smaller (in bits) than the raw data. My particular Tricorder model has a sample resolution setting, so for example I can record at anything from 1 bit resolution /sample to say 48 bits /sample. You might think of this as a quantization setting.

The crux of my question is:  what is the relationship between the recorded entropy rate and the level of quantization? I'm hoping for either a formula or an example calculation such as 4.5 bits /sample with 10 bit quantization.

There is (perhaps) a similar question at Compressing normally distributed data, but I'm not sure and it doesn't really deal with sample bit depth in the same way. I'm developing the argument that real world entropy is generated by the observer, not the underlying process.

PS. Read analogue to digital converter for Tricorder.


texts:
I am learning about serializability and I am not sure that if view serializability bidirectional or unidirectional. What I am meaning that, if S is view equivalent to S', is it always true that S' is also view equivalent to S? I think I have a counter example to that but I am not sure if I am missing something.

Suppose we have two transactions T1, T2 and T3 where R(x) denotes a read and W(x) denotes a write operation on x:

S: T3:R(x), T3:R(y), T2:W(x), T2:W(y), T1:R(x), T1:R(y)
S': T3:R(x), T3:R(y), T1:R(x), T2:W(x), T2:W(y), T1:R(y)

View equivalence has three conditions:

If a data item is read by a transaction first, then it must be read by the same transaction first for all other schedules
For each Write -> Read conflict on the same item, order must be preserved
If a data item written by transaction last, then it must be written by the same transaction last for all other schedules.

Now if we check if S' is view equivalent to S:

T3 reads first for both the x and y in S'. Also in S.
T2 writes last for both the x and y in S'. Also in S.
R(y) operation in T1 appears after W(y) on T2 in S'. By rule 2 it must be preserved in S. It is in fact preserved in S.
Since there is no other Write to Read conflict, then S is view equivalent to S'.

Now if we check the other direction, if S is view equivalent to S':

For conditions 1 and 3 are the same, they are satisfied.
Write to read conflict in the previous case also present here. But also there is another write to read conflict on x because in S T2 operates before T1. But in S' read on x appears before T2. So the order is different between S and S'. Therefore S is not view equivalent to S'.

If what I am doing is correct, then view equivalence is not bidirectional. But I am not sure if I did no mistakes. Does my example correctly shows that property?


texts: Proving worst-case running time is in $\Omega(n^2)$

texts:
I was given the following method to argue that an algorithm $A$ has a worst-case running time of $\Omega(n^2)$:

  We need to argue that there exists an input $x$ of size $n$, the
  running time of $A$ with input $x$, i.e., $t(x)$, is at least
  $cn^2$, where $x>0$ is a constant.

If you find a single input of size $n$ that gives A a running time of exactly, $n^2$, then couldn't there still exist a different one that is less than $n^2$, since we're only specifying one input and not all inputs?  I'm having difficulty understanding the logic.


texts:
Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have:

$T(m,c)\in O(m^2)$ for any constant $c$.
$T(c',n)\in O(n^2)$ for any constant $c'$.

What can we say about $T(m,n)$?


texts: Is there a way to tell a picture has been resized?

texts: I need to evaluate if the picture was resized (upscaled). Are there any approaches to that already? If not, what do you recommend me to start with?


texts: What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques?

texts:
Bron-Kerbosch is an algorithm to find maximal cliques in a undirected graph. In pseudocode it's the following (taken from wikipedia):

BronKerbosch1(R, P, X):
   if P and X are both empty:
       report R as a maximal clique
   for each vertex v in P:
       BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

I have read that the time complexity of some modified versions of this algorithm is $O(3^{n/3})$, but I can't seem to find the running time complexity of the simple version anywhere.


texts: suggestion for optimization problem with $\ell_{2,1}$ norm and Frobenius norm

texts:
Suppose I derive my application problem as the following type of optimization problem:
$$\min_X ||X||_{2,1}+||X^\top||_{2,1}+||X-A||_F,$$ where $X$ is a (square) matrix, $A$ is a constant matrix.

I am wondering is there any current optimization algorithm can solve this optimization problem (better with some convergence or theoretical guarantee)?


texts: How to scale down parallel complexity results to constantly many cores?

texts:
I have had problems accepting the complexity theoretic view of "efficiently solved by parallel algorithm" which is given by the class NC:

  NC is the class of problems that can be solved by a parallel algorithm in time $O(\log^cn)$ on $p(n) \in O(n^k)$ processors with $c,k \in \mathbb{N}$.

We can assume a PRAM.

My problem is that this does not seem to say much about "real" machines, that is machines with a finite amount of processors. Now I am told that "it is known" that we can "efficiently" simulate a $O(n^k)$ processor algorithm on $p \in \mathbb{N}$ processors.

What does "efficiently" mean here? Is this folklore or is there a rigorous theorem which quantifies the overhead caused by simulation?

What I am afraid that happens is that I have a problem which has a sequential $O(n^k)$ algorithm and also an "efficient" parallel algorithm which, when simulated on $p$ processors, also takes $O(n^k)$ time (which is all that can be expected on this granularity level of analysis if the sequential algorithm is asymptotically optimal). In this case, there is no speedup whatsover as far as we can see; in fact, the simulated parallel algorithm may be slower than the sequential algorithm. That is I am really looking for statements more precise than $O$-bounds (or a declaration of absence of such results).


texts: Construct context-free grammars that generate for the languages L(G) = {01(110)^n 10 (11)^n : n >= 0}

texts:
I have given this question as home assignment. I tried a lot to solve it but couldn't found any solution. Please help
Thanks in Advance!


texts: Why shortcutting euler circuit creates a hamilton circuit in Christofides algorithm

texts: In step 6 of the Christofides algorithm it is implicitly suggested that there is an invarient that the euler circuit can always be shortcutted to an hamilton circuit, what exactly assures us that? e.g (let u,v,w be vertices in the graph.) in the euler circuit, if vertex v has already been visited once, and is being revisited after visiting u and right before visiting w what makes the shortcut edge u-w to always exist?


texts:
Consider the following language:

$$L = \{ \langle M \rangle \ |\ M \text { is a TM that decides the halting problem} \}$$

  determine whether or not the language is in $R$.

Now, from my understanding an $\langle M \rangle \in L$ doesn't necessarily returns the right answer but rather halts for every $\langle P, x \rangle$ where $p$ is a program (=TM) and $x$ is an input for the program.

I am guessing the language isn't decidable and can be showed as such by some reduction, but couldn't think of something useful.

I'll be glad for help.


texts:
Given the following recursive equation

$$ T(n) = 2T\left(\frac{n}{2}\right)+n\log n$$ we want to apply the Master theorem and note that

$$ n^{\log_2(2)} = n.$$

Now we check the first two cases for $\varepsilon > 0$, that is whether

$n\log n \in O(n^{1-\varepsilon})$ or
$n\log n \in \Theta(n)$.

The two cases are not satisfied. So we have to check the third case, that is whether

$n\log n \in \Omega(n^{1+\varepsilon})$ .

I think the third condition is not satisfied either. But why? And what would be a good explanation for why the Master theorem cannot be applied in this case?


texts: Showing that Independent set of size $k$ can be decided using logarithmic space

texts:
An independent set $I$ is a subset of the nodes of a graph $G$ where: no 2 nodes in $I$ are adjacent in $G$. For natural number $k$, the problem $k-\text{IND}$ asks if there is an independent set of size $k$.

I'd really love your help with showing that $k-\text{IND} \in {\sf L}$, i.e., can be decided using deterministic logarithmic space.


texts: Variation on weighted set cover, cover by consecutive pairs

texts:
Input: A set $N = \{1, \dots, n\}$, subsets/consecutive pairs $S_1 = \{1,2\}, \dots, S_n = \{n,1\}$ with associated costs $c_1, \dots, c_n \in \mathbb{N} \cup \{0\}$, and a subset $B \subseteq N$.

Output: A collection $\mathcal{S} \subseteq \{ S_1, \dots, S_n \}$ that minimizes $\sum_{S_i \in \mathcal{S}} c_i$ and covers $B$, that is,
$$
B \subseteq \bigcup_{S_i \in \mathcal{S}} S_i.
$$

Questions: Is there an efficient alternative to solving this as an integer program? If so, is the problem much harder if $x$ covers more consecutive elements (like $x$, $x+1$, and $x+2$)?

I guess that this is related to the consecutive-ones property and total unimodularity, and the integer program is efficient. But I am still interesting in alternative algorithms.


texts:
The lemma 13.1 of CLRS proves that the height of a red black tree with $n$ nodes is

$$h(n) \leq 2\log_2(n+1)$$

There's a subtle step I don't understand. The property 4 reported at the beginning of the chapter states:

  If a node is red, then both its children are black.

And because of such property it is later stated

  According to property 4, at least half the nodes on any simple path from the root to a leaf, not including the root, must be black. Consequently, the black-height of the root must be at least $h/2$.

I can intuitively agree, but as exercises I'd like to prove it, but I can't manage how to actually do it. Why is that property true? I'm not actually neither able to set up the problem, the only think I could think of was that I if I have $r + b = h$ nodes, where $r$ is the number of red nodes and $b$ is the number of black nodes I can have a total of

$$
k = \frac{h!}{r!b!}
$$

And I'd like to prove from here that if $b < r$ than I have the contradiction, but I need something more that this probably. Any help?


texts: Are SAT problems with at most two false clauses NP-complete?

texts:
Is the problem of deciding whether a SAT instance, where at most two clauses are false (that is, any given variable assignment will either lead to all clauses being true, all but one, or all but two), is satisfiable solvable in polynomial time?

This is a follow-up from my previous question. The problem presented in that question (at most one false clause) was solvable in polynomial time, because we could take advantage of the fact that the set of truth assignments that make a clause false is disjoint to that of any other clause. With two or more clauses, the sets that make a clause false can overlap with each other. Does this mean that problems with at most two (or more) false clauses (when I say "or more," I do not mean that the number can change with the problem size. A problem with five clauses where at most five are false is a trivial version of regular SAT, but what about a problem of a few million clauses where are most five can be false?) are NP-complete, or are all versions of SAT where you limit the number of false clauses solvable in polynomial time?


texts:
I've converted this NFA to a DFA and I get a similar soultion automata but I'm not sure if I really understand everything.

Please correct me if I'm explaining it wrong, I would love some feedback.

From the state 0 we only have the set {0} since there doesn't exist any ε-transition.
After that we have to input "a" to move to state 1 and here I've got a question. Does it include the 0 also since "a" can either take you to state 1 but also to state 0 since it loops?

Continuing we want to move to state 2 via "a" input. Why does it include the "0"? Is it because you have to consider all the inputs from each set in the state 1? Like, if you input "a" at 0 you loop but you can also go to state 1. From 1 if you input "a" you move forward to state 2. Which gives us the set {0,1,2}.

If this is correct, then the procedure for state 3 should be the same, right?
Also, at the third state {0,1,2,3} he can't just loop "b" since the other states can't "handle" the input so you have to create a new state containing the set {0,3} which can handle the "b" input?

Sorry if this is a bit long, I just want to understand what is going on really.


texts: 3SUM problem solution on the basis of cubic function and a line?

texts:
The 3SUM problem formulation: in a given set of n real numbers find 3 elements that sum to specified value S.

I am trying to understand mathematical solution of the 3SUM problem based on a polynomial of 3 degree. I found some information about 3SUM problem as a special case of geometrical problems. It says:

  There are m points on a plane and it is required to check if some
  3 points are located on on the same straight line.   So, there is a
  straight line function: $y = ax + b$ and a curve: $ y = f(x) = x^3 -
Sx^2 $ Intersection of the above two equations is roots of the
  following equation: $x^3 - Sx^2 - ax - b = 0  $

  So, set of points $(a_1 , f(a_1)), ..., (a_m , f(a_m))$ contains 3
  points $(a_x , f(a_x)), (a_y , f(a_y)), (a_z , f(a_z))$ on the samle
  straight line if and only if $a_x + a_y + a_z = S$

I can't fully percieve the relation between 3SUM problem and the above geometrical problem.
AFAIK, in the equation: $x^3 - Sx^2 - ax - b = 0  $ variable $a$  represents set of points $(a_1 , f(a_1)), ..., (a_m , f(a_m))$ and probably all real numbers in which I search for some 3 numbers that sum to S. So 3 numbers $a_x + a_y + a_z$ sum to S if all of them are on the same line. But what x, y, z represent here? What is $a_z$ or $a_y$? And what is coefficient before $x^3$ equal to? How do I define b?

Can someone clarify relation between 3SUM problem and the above geometric problem?


texts: Are programming languages ultimately procedural?

texts:
I'm studying a declarative programming language (Prolog) and in thinking about how certain things are programmed at a low level, a question came to me:

are programming languages ultimately procedural ?


texts: What are the fundamental principles/algorithms on the process of equation solving?

texts:
I have seen a lot of solvers that are capable of, for example, getting an equation such as x ^ 2 + x = 12 and finding x = [3, -4]. I know some of them are implemented by hardcoding special cases. For example, when finding an equation on the quadratic form, they use a hardcoded bhaskara formula.

What I'm looking for is something different, I want to learn more about the nature of solving equations. That is, I want simple algorithms or systems that generalize the process of solving an equation, in the same principle that lambda calculus encapsules the process of computation.

What are the names I'm looking for?


texts: Efficient way to find the i-th size in a BST

texts:
Given the following definition of binary search tree:

$$\text{size}(t)=\cases{0\qquad\qquad\qquad\qquad\qquad\qquad t=\text{ null}\\
1+\text{size(t.left)+size(t.right)}\qquad\text{otherwise}}$$

for each vertex in the tree t.size contain the size of it's subtree

  Write an algorithm  selection(T,i) that gets a Tree with size at each vertex and return the $i-$th smallest/largest size in the tree

Attempt:

I discovered that the size of a vertex is the number of vertices that there are in the specific root:

e.g:

                              V_1
                             /   \
                           V_2    V_3
                           /      / \
                         V_4     V_5 V_6

The size of $V_4,V_5,V_6$ is: $1+0=1$

The size of $V_2$ is: $1+1=2$

The size of $V_3$ is: $1+1+1=3$

The size of $V_1$ is: $1+3+2=6$

Now to scan all vertices in the tree using preorder or postorder and to find the $i-th$ size, running time $O(|V|)$,

I am looking for something more efficient.


texts: EPI question on multiplying two integers

texts:
The Elements of Programming Interviews book has a question on "computing x*y without arithmetical operators" (question 5.5). The solution is here: https://github.com/epibook/epibook.github.io/blob/master/solutions/cpp/MultiplyShiftAdd.cc

I am confused about the Add() function in the solution. For example, if I want to add a=1110 and b=1, the while loop will execute only once (because temp_b will decrease from 1 to 0). The iteration goes as follows:

ak = 1110 & 1 = 0, bk = 1 & 1 = 1,
carryout = (0 & 1) | 0 | 0 = 0,
sum = sum | (ak ^ bk ^ carryin) = 0 | 1 = 1,
carryin = carryout << 1 = 0,
k = 10,
temp_a = 111,
temp_b = 0

Then we return:

sum | carryin = 1

But the sum of 1110 and 1 should be 1111

EDIT: I realised that the while loop would not stop after the first iteration


texts: All prefixes with same length as their suffix is a regular language

texts:
Suppose $L$ is a regular language over $\Sigma$ and we want to show that $$\frac{1}{2}L = \{x \in \Sigma^* \mid \exists y \in \Sigma^* (xy\in L \wedge |x| = |y|)\}$$ is regular. I thought of taking the set of even length strings over $\Sigma^*$ (given by $(00\cup01\cup10\cup11)^*$) and then interescting with $L$, which would be regular because the intersection of regular languages is regular. Then, the set of prefixes of this language is regular (by a previous exercise), but that's useless because that set of strings isn't actually the set $\frac{1}{2}L$. In particular, we didn't constrain the prefixes to be the ones with equal length suffixes.
Baically, I'm really stuck on how to make a FA that recognizes the length of the strings. Namely, given $x$ how do we add $\epsilon$ transitions to arrive at $xy$ with $|x| = |y|$, which we then pass in $xy$ to the FA for $L$? Thanks in advance, I've been scratching my head on this for a while.


texts: How to prove the regularity of one language given that another is regular?

texts:
Consider the following unary operation on languages:
 min(L) = {x ∈ L | no proper prefix of x is in L}
Prove that regular languages are closed under this operation; that is, prove that if language L is regular, then so is min(L).
(hint: construct a DFA to accept Min(L) based on the DFA accepting L)

After searching online, I found out that I have to:

Let M=⟨Q,Σ,δ,q0,A⟩ be a DFA that accepts L; Q is the set of states, Σ is the input alphabet, δ is the transition function, q0 is the initial state, and A is the set of acceptor states.
To get a DFA that accepts min(L), add a new trap state q∗ and modify δ so that any input to an acceptor state sends M to q∗.

However, I have no idea to construct a DFA for language L where it does not explicitly state the Σ. Can anyone guide me? Any help is appreciated. Thanks!


texts: How can a fully encrypted homomorphic program resist copying?

texts:
Let's say that we have an original homomorphically encrypted program with any possible code inside. What methods can it use to ensure that it is impossible to create an exact copy of it? Are there such ways?

I understand that a person without a key will not see the internal content of a homomorphically encrypted program, I'm interested in whether it is possible to limit the exact copying of this program entirely.


texts:
Following the article's notation, I write $\mathcal{F}$ for the
category of presheaves on a (suitable) category $\mathbb{F}$, $TV$ for the
presheaf of terms, $\delta$ for the context extension, and
$\bullet$ for the product of the $\mathcal{F}$-monoid.

In Abstract Syntax and Variable Binding [Fiore, Plotkin, Turi], the
authors set out to define substitution by structural recursion
(Section 3). I was expecting to see substitution expressed as an
initial algebra of some sort.

Instead, from what I understand, the authors:

 Construct the substitution $\sigma : \delta(TV) \times TV \to TV$ by some universal construction ("Definition of substitution by structural recursion")
 Show that it forms a substitution algebra (Theorem 3.2)
 Show that the categories of substitution algebras and clones are equivalent (Theorem 3.3)
 Show that the categories of clones and monoids in $\mathcal{F}$ are equivalent (Proposition 3.4)
 Show that subtitution is the multiplication of such a monoid (Proposition 3.5)
 Conclude that $\sigma$, the substitution, is defined by structural recursion (Corollary 3.6).

I'm failing to appreciate their motive in moving from substitution
algebras to clones to monoids. Is that a natural thing to do for a
mathematician?

In particular, why not stay focused on substitution algebras and, I
guess, present substitution as the initial one?

Conversely, they claim that Corollary 3.6 gives a definition of
substitution by structural recursion: how is that? It is just said
that "$\sigma$ is the unique homomorphic extension of $V \bullet TV
\cong TV$": how did they derive their example (substitution for the
lambda calculus, very end of Section 3) from this statement?


texts: Is a spanning tree an MST if its weight can't be decreased by adding an edge and removing one?

texts:
My gut says it's true and I have tested it on a few examples. However, I can't prove it. I thought of using contradiction; suppose there exists another tree T' with smaller weight which has m edges not shared with the first tree. We can transform the first tree to second one in m steps by adding one of the m edges which are only in T' and removing one edge off the tree which belongs only to the first tree in each step. The weight of the tree should decrease in at least one of these steps. Take the added edge in that step add it to the first tree and remove an edge and prove that it decreases the weight which contradicts with the weight of the tree cannot be decreased.

I couldn't work out the quirks. Is the statement even true? Why?


texts:
Let $C = shuffle(A, B)$ denote the shuffle $C$ of two languages $A$ and $B$, it consists of
all strings $w$ of the form $w = a_1b_1a_2b_2....a_kb_k$, for $k > 0$, with $a_1a_2 ··· a_k \in A$ and $b_1b_2 ··· b_k \in B$. Show that if A and B are regular then so is $C = shuffle(A, B).$


texts: Names of power-of-two bit operations on bitsets that would not assume any number interpretation

texts:
Three commonly used functions when it comes to bit manipulation are :

is_pow2: Checking that an integer is a power-of-two (only one bit  is set): $00010000 \Rightarrow yes$
floor_pow2: Finds the largest integer power of two not greater than the given value $00010010 \Rightarrow 00010000$ (msb on the left, lsb on the right)
ceil_pow2: Finds the smallest integer power of two not less than the given value $00010010 \Rightarrow 00100000$ (msb on the left, lsb on the right)

However, the concept of a power of two requires to assume a numeric interpretation of sets of bits. But fundamentally the functionality provided by these functions stay valid on bitsets without a numeric interpretation. For example, what is_pow2(x) is really asking is whether popcount(x) == 1. And popcount does not require to define any concept of power of two.

I was wondering if the three functions is_pow2, floor_pow2, ceil_pow2 had commonly accepted names in mathematics, computer science or computer engineering which do not rely on the concept of a power of two.


texts: Analysis of a linear-time algorithm for longest palindromic substring

texts:
Background

$\newcommand\ldotd{\mathinner{..}}$Last month, I heard about a new linear-time algorithm to determine the longest palindromic substring called Jeuring's algorithm. It seemed interesting, therefore I had a try to analyze the algorithm. It's not too difficult to show that it's an $\Theta(n)$-time-algorithm, but I want to observe more closely.

I wrote a C++ implementation, and an essay to prove and analyze the algorithm. It's somewhat long, therefore I will only post the critical part of the code, where you can learn the algorithm by heart, see the succeeding section. You can get all my previous work from github. pldrm.nw is the literate programming source file, which produces the pldrm.cc and pldrm.pdf. pldrm.pdf is the essay I've written.

Problem

Let $A=$ the number of times goto statement is executed in move loop, and $B=$ the number of times move loop is executed where goto statement is NOT executed, $C=$ the number of times a[++j]=min(a[p],l) is executed in move loop. You can see the code in the following section.
I found that $A+B+C=2n$ and $B=\sum_{k=2}^{n+1}[b_k=1]$, where $b_k$ is the length of longest tail palindrome of $s[0\ldotd k]$, and $[P]$ is Iverson bracket. For details, you can read my pdf from github.
I'm looking for somebody to help me analyze the quantity $A,C$. Any help? Thanks!

The critical part of the algorithm

Given that $s[1\ldotd n]$ is the string inputted, and $n$ is the length of $s$, where $s[0]=1,s[n+1]=0$.
We say $l+r$ is the center of substring $s[l\ldotd r]$. For example, $4$ is the center of $s[2\ldotd2]$ or $s[1\ldotd3]$.
$a_k$ is the length of the longest palindrome whose center is $k$, and $a[0\ldotd2n]$ is the array to save $\langle a_k\rangle$.
The algorithm is used to determine $a_k$.
We call some string $A$ is a tail palindrome of the other string $B$ if and only if $A$ is a palindromic tail substring of $B$. For example, $A=aba$ and $B=aaaababa$, where $A$ is palindromic and $A$ is a tail substring of $B$.

Here's the critical part of the code:

<<main loop>>=
j = 1;
l = 1;
a[0] = 1;
a[1] = 0;
for (int k=2; k<=n+1; k++) {
  <<process>>
  advance:
  ;
}
@

Process is made up of an infinite loop, which is used to find the longest tail palindrome of $s[0\ldotd k]$. There are two exits of it. One is in extension subroutine, while the other one is in move loop. The way of exit is goto advance;.

<<process>>=
for (;;) {
  <<check>>
  <<move loop>>
}
@

The check subroutine checks whether a tail palindrome of $s[0\ldotd k-1]$ could be extended to that of $s[0\ldotd k]$. If so, exit from the process loop and advance $k$, otherwise start the move loop.

<<check>>=
if (s[k] == s[k-l-1]) {
  l += 2;
  goto advance;
}
@

Here's the move loop, which looks short and easy. It's used to find a shorter tail palindrome of $s[0\ldotd k-1]$.

<<move loop>>=
a[++j] = l;
for (p=j-1; --l>=0&&l!=a[p]; p--) {
  a[++j] = min(a[p], l);
}
if (l < 0) {
  l = 1;
  goto advance;
}
@


texts: How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)?

texts:
Given

$$
a_1 X_1 + \dots + a_n X_n = b
$$

where $a_i, b \in \Bbb{Z}$.  How do you come up with a clearer picture of the solution set in polynomial time.

Also, what I really want is to do the above, but under the minimization of:

$$
X_1 + \dots + X_n, \ X_i \in \Bbb{N}
$$

All my $X_i$ are bounded with small sets such as $\{0, 2\}$ for small input instances of my certain problem, however I can't very well try $2^n$ or more possibilities, now can I!  That would not be polynomial time.


texts: How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent

texts:
Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form:

To a regular expression equivalent. What I have tried was using arden's rule. However I just cant figure out how to simplify and return the appropriate regular expression corresponding to that NFA.

First I have created the initial equation corresponding to those states:

$1: q3 = q_1 0 + q_1 1$

$2: q1 = q_0 0 + q_1 1$

$3: q0 = q_0 0 + q_0 1 + \epsilon$

Which I have tried to simplify:

$1: q3 = (q_0 0 + q_1 1)0 + (q_0 0 + q_1)1$

$1: q3 = q_0 00 + q_1 100 + q_0 01 + q_1 11$

$1: q3 = q_0(0+1) + q_1(0+1)$

$2: q1 = q_0 00 + q_0 10 + \epsilon 0 + q_0 01 + q_1 11$

$2: q1 = q_0(0+0+1)+ \epsilon 0 + q_1 11$

$3: q0 = q_0 0 + q_0 1 + \epsilon$

$3: q0 = q_0(0+1) + \epsilon$

Here I just lost. Maybe there is a different approach suitable in this context.

Appreciate any help!


texts: Divide sequence of numbers from 1 to n into 2 groups with minimum difference

texts:
Let's say for some $n$ we have the sequence $1, 2, 3, \dots , n$, what we want with this sequence is to divide it in two sets such that each element of the sequence will be in only one set, and the difference in sums of the two sets will be minimum possible.

Example

Let $n = 4$, and $A$ and $B$ are our sets, we can divide the numbers in this set such that the difference in sum between them will be $0$, $A = \{1, 4\}$ and $B = \{2,3\}$

My thinking

I noticed we can divide like this $1$ and $n$ in set $A$, then $2$ and $n-1$ in set $B$, then $3$ and $n-2$ in $A$, etc..

My algorithm gives correct result if $n$ is divisible $4$, but when it is not divisible by $4$ it will return that the difference between the sets is bigger than it actually is, how can we divide the numbers optimally.


texts: How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?

texts:
You are given n integers $a_1, \ldots, a_n$ all between $0$ and $l$. Under each integer $a_i$ you should write an integer $b_i$ between $0$ and $l$ with the requirement that the $b_i$'s form a non-decreasing sequence. Define the deviation of such a sequence to be $\max(|a_1-b_1|, \ldots, |a_n-b_n|)$. Design an algorithm that finds the $b_i$'s with the minimum deviation in runtime $O(n\sqrt[4]{l})$.

I honestly have no clue whatsoever how to even begin to solve this question. It looks like a dynamic programming question to me, but the professor said that this should be solved using a greedy algorithm. It would be much appreciated if someone can point me in the right direction by giving a small hint.


texts: Why are bytes treated like the base unit?

texts:
If bits are the base unit of information, why are bytes treated like the base unit?

For example, usually values are expressed in Mega/Giga/Tera/Exa bytes instead of bits. I am aware that bits are sometimes used (e.g. sometimes for internet speed), but generally to me it seems like bytes are used as if they are the base unit instead of bits.


texts: If a predicate is not computable, what can be said about its negation?

texts:
Doing the following exercise:

Let $\overline{HALT(x,y)}$ be defined as
$\overline {HALT(x,y)} \iff \text{program number y never halts on input x}$
Show that it is not computable.

Just want to make sure I have understood the concept correctly. We had in a theorem that HALT(x,y) is not computable which means that we cannot determine whether program number y eventually halts on input x. I realized that $\overline {HALT(x,y)}$ is the negation of HALT(x,y). Is it true (I cannot find it in my book or on the internet) that if a function is (not) computable, its negation is also (not) computable? A function being computable means there is a program p which computes it, we cannot say there is a program Q that computes its negation. Or can we draw such conclusion?


texts:
From CLRS Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,

$$\begin{align*}
\sum_{k=1}^{n} k &= \sum_{k=1}^{n/2} k + \sum_{k=n/2 + 1}^{n} k\\
&\geq \sum_{k=1}^{n/2} 0 + \sum_{k=n/2 + 1}^{n} (n/2)\\
&= (n/2)^2\\
&= \Omega(n^2)\,\end{align*}$$

I get step 1, that makes sense, but I didn't understand step 2 where they have replaced $k$ with $0$ in one part and $k$ with $n/2$ in the other. Why did they do this?

Thanks!


texts: Intuitive way to understand "Run-Length Encoding"

texts:
Run-Length Encoding is the simple form of lossless data compression in which compression in which runs (execution) of data are stored as a single data value and count rather than as the original run (execution).

Now the definition is there but what's an intuitive way of thinking about this?


texts: Questions about class of problems that can be solved with unlimited computational power, but access to only logarithmically many bits of the input?

texts:
Consider the class $\text{DLOGTIME}^{\text{ALL}}$: the class of problems that can be solved by a machine with unlimited computational power but only access to logarithmically many bits of the input.  Which bits of the input it accesses can depend on the values of bits it has already seen, and it has random access to the input.  For conciseness, let's call this language $\text{X}$.

Does this class have a name?  What is known about it?

Here is what I know so far:

It includes problems that are very undecideable – it includes padded versions of every language whatsoever!
$\text{E}^\text{X} = \text{ALL}$ by a padding argument.
$\text{X}$ does not contain the problem $\text{PARITY}$ (are the number of 1 bits in the input even?).  As such, $\text{X}$ does not contain the regular languages.

Questions:

Is $\text{X}$ contained in $\text{P}/\text{poly}$?
Is $\text{X}$ contained in any other well-known complexity class?
What else is known about $\text{X}$?


texts: What is a lay explanation for universal search?

texts:
I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply haven't been able to find an explanation suitable for a reader without a background in statistics/computer science.

I've been reading this article on Universal Search from Scholarpedia, which seems to cover the topic. I'd appreciate an explanation for what Universal Search (or Levin Search) means.


texts: Equivalence of minimum cost circulation problem and minimum cost max flow problem

texts:
In the following MIT open course, it is claimed that min-cost circulation reduces to min-cost max-flow:

  ...

  The second part of the proof is showing that min-cost circulation
  reduces to min-cost max-flow.

  Consider a network G for which we want to find a min-cost circulation.
  Add a source s and a sink t to the network, without any edges to
  the rest of the network. The maximum flow in this network is 0,
  therefore the min-cost max-flow is actually a min-cost circulation.

In theory, I don't understand how this works. If we add disconnected source and sink nodes, the maximum flow is trivially 0 as claimed. Does that mean the minimum circulation problem has zero flow on every edge of the original network? This seems to violate the lower bound requirement on the edges of min-cost circulation networks.

In practice, I don't know how to implement a min-cost circulation solver using a min-cost max-flow solver such as the one in Boost Graph Library (BGL) here :

#include <boost/graph/cycle_canceling.hpp>
#include <boost/graph/edmonds_karp_max_flow.hpp>

#include "../test/min_cost_max_flow_utils.hpp"

int main() {
    boost::SampleGraph::vertex_descriptor s,t;
    boost::SampleGraph::Graph g;
    boost::SampleGraph::getSampleGraph(g, s, t);

    boost::edmonds_karp_max_flow(g, s, t);
    boost::cycle_canceling(g);

    int cost = boost::find_flow_cost(g);
    assert(cost == 29);
    return 0;
}

The above BGL example solves a small min-cost max-flow problem. I can't figure out how to change the network to include lower bounds of edges as required in the min-circulation problem. Simply adding additional, disconnected dummy source and sink node gives zero flows on all edges (as expected) and solves nothing.

My questions are:

Am I missing something in the above proof?

How should I adapt the BGL min-cost max-flow solver above to solve min-circulation problems?

I'd really appreciate a concrete example with cycle canceling (or another algorithm) in BGL to verify and illustrate the reduction.


texts: Question about set-associative cache mapping

texts:
I found a question:

  Let a two-way set-associative cache of 4 memory blocks, each block containing one word.

  What is the number of misses and hits considering the following sequence of block addresses: 0, 8, 0, 6, 8 ?

  a) 4 misses and 1 hit
  b) 3 misses and 2 hits
  c) 1 miss and 4 hits
  d) 2 misses and 3 hits

Although I understand how set-associative cache mapping works, I don't understand how can you tell if it will be a hit or a miss if you don't know the tags and what is stored on the cache memory.

Can you please point me in the right direction? How should I think about this problem?


texts: Computing the Kolmogorov complexity of a string

texts: What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?


texts: How to understand the formal analysis of quickselect?

texts:
According to various informal analysis, we know that the running time of quickselect is o(n), by assuming thay the partition is always taking half of the array. However, my lecture gives without proof that if we do a formal analysis, we will get the following formula:

$$C_N = 2 N + 2 k ln (N / k) + 2 (N – k) ln (N / (N – k))$$

*$C_n$ is the number of compares if the array has N items.

Does anyone know how this formula is derived?


texts: Get indexes of unique elements in two different arrays in linear time

texts:
I have two array of the same set of elements, say for exemple:
$a_1 = [x_1, x_2, …, x_n]$ and $a_2 = [y_1, y_2, …, y_n]$ so that $i \neq j \Rightarrow x_i \neq x_j$

Is it possible, in linear time, to construct the array $[(x_1, k_1), (x_2, k_2), …, (x_n, k_n)]$ so that $y_{k_i} = x_i$ ?

I found that with dictionnaries, I can get $O(n)$ in average and $O(n^2)$ in worst (hashtable) or $O(n\log n)$ in average and worst (balancing trees), but can't find a way to make it $O(n)$ in worst case.

We can suppose that the $x_i$ objects are integers, since it could represent memory pointers.

I found that it is possible if the set is $[\![1, n]\!]$ (just construct the array directly).

Thanks for your help.


texts: How do bottom up parser evaluate things that need an inherited attribute?

texts:
I learned that Bottom up parsers use only synthesized attributes to evaluate semantics.  Which makes sense considering that it would be very hard to evaluate an inherited attribute in bottom up parsing.
So, can bottom up parser evaluate pretty much anything top down parsers do without using inherited attributes? Is that possible?


texts: Some terminologies in Wirth's book and the satisfying of deterministic algorithm

texts:
I am going through Wirth's Textbook on Compiler design . After proceeding though
some pages ,  I realized I have taken for granted my understanding of some
of the terminologies that have been used . For example ,the following terms :

the examples mentioned in the lines in the screenshot refer to the following set of equations :

Later on while describing the possibility of the conditions of deterministic algorithms being
satisfied it says for an expresion of the following form :

"term_0 | term_1"

the terms must not feature any common starting symbols .And then it says this results in the exclusion of
left recusrsion . If we consider the left recursive production :

A = A "a" | "b"

then the requirement is violated "b" is also a start symbol of "A" .

How is "b" a start symbol of "A" ? Basically from the definitions given I understood start symbol means
the symbol for which an equation is deifined first ?

Why does common start symbol disturb the conditions of deterministic algorithm ?


texts:
Is there a proof for the lower bound of the problem to create a sorted list of sums for a given list of integers with length n.

In this [thread][1] people discuss solving this problem by sorting the list of integers first and then creating the sums. However none of the solutions seems to be faster than $O(n^2 \log n)$, which is the runtime of just creating all sums and then sorting them.

How would you proof that this is the best you can get or is there a better algorithm to solve the problem.


texts: Modify Fibonacci Heap to Have a Linear Chain of Marked/Unmarked Nodes Only

texts:
In CLRS book there is an exercise (19.4-2), the aim of which is to create a linear chain of nodes by a sequence of Fibonacci-Heap operations. I have solved the problem by recursively making a union with a chain of two nodes, inserting a new minimum node and extracting the minimum, after which consolidation takes place and after deleting the node on the shortest path returns a new linear chain. Since there are no DECREASE-KEY or DELETE-NODE operations, no node is being marked.

My question is, is it possible to create a linear chain consisting of marked nodes only. If so, how?

I have tried several strategies. In one case I am getting a linear chain with all but the last node marked and I cannot proceed from there.

Another possibility is to get a chain as follows for $n$ nodes:

From here one can delete all the nodes on the shortest path for each sub-tree starting from the bottom to mark all of the nodes on the longer path. However, I cannot find a way to get this Fibonacci-Heap in the first place (and I am not sure whether it is possible). Any help would be appreciated.


texts: Solving a modular equation programmatically

texts:
Consider that I've a mathematical equation of the form:
$$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$
How can I solve this modular equation by using a program, efficiently? By trial and error, one can infer that the answer is $x=4,15,26,...$. But how can I solve this programmatically?

I can not use a binary search here, as there is no pattern followed by numbers greater than the answer, and vice versa.( Plus, there are infinite solutions).

I can obviously check all values from $0,1,2,...,21$, but that wouldn't be efficient in my use case.

So, for a given equation of the form $$(a+b\times x)mod\text{ }m=0$$, is there any constant or logarithmic algorithm in $m$, that can be used to solve this equation?

P.S: I can't directly solve for $$a+bx=m$$. For example take $$(6+10\times x)mod\text{ }22=0$$
Here, $x=6$, is the correct answer which can't be inferred using the equation mentioned above.


texts: What problems can I reduce Job Shop Scheduling to them

texts:
I want to know which problems are harder than Job Shop Scheduling so I can reduce JSP to them.

Sorry I am new to these problems and looking for a source to know what are problems, what are their hardness variations and more ...


texts: About trap states when converting DFA to regular expression

texts: If we were to have a trap state in a DFA and we are converting it to a regular expression, how exactly would I incorporate that into the regex? Let's say our language only accepts a*, and my DFA has a start state/final state with a a loop, and once I get a b it goes into a trap. Would the regex simply be a* meaning we ignore the b?


texts:
Are there any results generalizing XOR Linked Lists to other types of data structures?

For example, just like an XOR Linked List requires two pointers and can iterate a 1 dimensional list, I can imagine a two dimensional linked list where nodes are arranged on a plane and connected to eachother vertically and horizontally. Such a "Linked Mesh" can probably be iterated using 4 adjacent pointers in both directions and only storing one or two pointers for each node to its neighbor, instead of the full 4.

Are there any such results or similar results?

Is there a name for these type of structures?


texts: Shortest sub-sequence of one string, that's not a sub-sequence of another string

texts:
Given two strings $x$ and $y$ over the alphabet $\{A,C,G,T\}$, I'm trying to determine a shortest string $z$ such that $z$ is a subsequence of $x$ and not a subsequence of $y$.

  Example: a shortest string that is a subsequence of AATGAAC but not a subsequence of ATCGATC is AAG.


texts: Why does this pumping lemma application "prove" that 0*1* is not regular?

texts:
Here is a proof that $0^*1^*$ is not regular, even though it is regular. I'm having a hard time figuring out what is wrong with the proof.

Assume $0^*1^*$ is regular. Let $p$ be the pumping length as defined by the pumping lemma. Let $s = 0^{p-1}11$, then $|s| \ge p$ and $s \in 0^*1^*$. According to the pumping lemma, we can split $s$ into three parts $s = xyz$ such that $|y|>0$, $|xy| \le p$, and $xy^iz \in 0^*1^*$ for $i \ge 0$. Let $x = \varepsilon$, $y = 0^{p-1}1$, and $z = 1$. Clearly, $|xy| \le p$ and $|y|>0$. However, $xy^2z = 0^{p-1}10^{p-1}11$ is not a member of $0^*1^*$. This is a contradiction to the pumping lemma, therefore $0^*1^*$ is not regular.

We know $0^*1^*$ is regular, building a NFA for it is easy. What is wrong with this proof?


texts: Can one build a "mechanical" universal Turing machine?

texts:
This question connects different disciplines so it's awkward to choose a SE site for it, but I'll go with this one because here (I hope) the shared culture will make information transfer easier.
So computers as we know them use electricity and I don't know what other invisible things that I don't understand. I was wondering, is this a matter of efficiency, or of necessity? Can one achieve universal computation with just "moving parts"? Perhaps "Newtonian physics" is some term for this, although I guess it includes gravity which isn't really what I mean. You know, just good old solid pieces of matter moving around.
To get some picture of what I mean, here is a "LEGO Turing machine". I'm afraid that the big gray block on top uses electricity, but could one replace it with a "mechanical" thing, powered perhaps by rotating a piece? I have no idea how such things be designed, and the state transitions for a universal TM have to be fairly complicated, so I have no intuition for whether this is possible or not.


texts: What is this problem? Largest set of contiguous x values for which the same y value can be held

texts:
I'm trying to find a linear solution with a small constant factor but I'm not sure what to search for, or even how to succinctly describe it.  The best I've come up with is:

  Given a set of rectangles on a plane find the set(s) which allow the same y value for some largest contiguous set of x values.  All rectangles are axis aligned, the same width, and do not overlap.

I find this much easier to visualize so below is an example problem instance and solution.

Edit:

We have a linear solution that has a constant factor on the order $y_{max} - y_{min}$ which can be pretty big.  Here is an idea of the algorithm I've been trying to work out since originally posting this.

Rectangles are already sorted by $x$ position.
Maintain an ordered list $I$ of the intervals currently allowing a contiguous line.
Maintain two variables $(i_{min}, i_{max})$ which are the min and max
$y$ value of the current intersection (in the example solution $(5, 5.25)$).
Iterate from $x_0$ to $x_{max}$
At each $x$ position test if any of the current rectangle(s) intersect $(i_{min}, i_{max})$.

1) If yes, add the rectangle to $I$ and update $(i_{min}, i_{max})$.
2) If no, find the longest suffix of $I$ s.t. it allows overlap with current rectangle.
3) If no suffix exists or the current $x$ position has no rectangles skip to the next $x$ position with rectangles and reinitialize $I$, and $(i_{min}, i_{max})$.

In #2 and #3 save the current $I$ if it allows the widest contiguous line so far.


texts: Validity of exponentiation in a polynomial time reduction

texts:
In a very famous paper (in the networking community), Wang & Crowcroft present some $\mathsf{NP}$-completeness results of path computation under several additive/multiplicative constraints. The first problem is the following :

Given a directed graph $G=(V,A)$ and two weight metrics $w_1$ and $w_2$ over the edges, define, for a path $P$, $w_i(P)=\sum_{a\in P}w_i(a)$ ($i=1,2$). Given two nodes $s$ and $t$, the problem is to find a path $P$ from $s$ to $t$ s.t. $w_i(P)\leq W_i$, where the $W_i$ are given positive numbers (example: Delay constraint and cost in a network).

The authors prove that this problem is $\mathsf{NP}$-complete by providing a polynomial reduction from PARTITION.

Then they present the same problem except that the metrics are multiplicative, i.e., $w'_i(P)=\prod_{a\in P}w'_i(a)$. In order to prove the multiplicative version is $\mathsf{NP}$-complete, they provide a "polynomial" reduction from the additive version just by putting $w'_i(a)=e^{w_i(a)}$ and $W'_i=e^{W_i}$.

I am very puzzled by this reduction. Since $W'_i$ and $w'_i(a)$ are part of the input (in binary, I guess), then the $|w'_i(a)|$ and $|W'_i|$ are not polynomial in $|w_i(a)|$ and $|W_i|$. Thus the reduction is not polynomial.

Am I missing something trivial or there is a flaw in the proof?

Paper reference : Zheng Wang, Jon Crowcroft. Quality-of-Service Routing for Supporting Multimedia Applications. IEEE Journal on Selected Areas in Communications 14(7): 1228-1234 (1996).


texts: Will a node with no incoming arc or no out coming arc affect the maximum flow?

texts: So in a maximum flow question, say if we have a node which is not $s$ nor $t$, if it has no incoming arc, can we delete it without affecting the maximum flow? What if it has no output arc? How so?


texts: Converting from m base to n base without arithmetic operations (Where m<n )

texts:
I have been working the last 8 years in try to convert from base n to base m without artihmetical operations.

My hypothesis is that by the same way  that is possible convert bases without division (see the tables bellow.) based in a literal conversion you can create an equivalence table that allow this direct translation.

  00011111  |
       (2)  |

  00011111  | For convert in base 4 you take the follow number of digits.
               x
              2   = 4 | x=2 ( It is eaxctly)

[01][11][11]| You don't need a math operation for this operation because
              The follow symbol '3'(4) -> '11'(2)
   [1][3][3]|

 [0011][111]| You don't need a math operation for this operation because
              The follow symbol '7'(8) -> '111'(2)
      [3][7]|

As it is very know the number of groups that you have to use is:

Log (n) , where ( n can be represented as m^c , and c is and Integer)
  (m)

This operation:

'7'(8) -> '111'(2)   (Symbol(7)->111)

In my case, is a not math operations, because I have an state machine that is able to understand and reflect (bad joke) that symbol 7 means 111 in the default output (or default queue).

As you know when c is not an integer, we have a very complex problem therefore I was creating random table-states based on random rules (it means jumps of states using genetic algorithms) but It has been a real waste of time/energy.

Now I share my Idea, I believe that all bases must be represented as a sub-languages for other bases and they creates a cycle , It I couldn't  demostrate it as a formal theorem. But my heart, my soul and my migth believes that it could be possible.

For example:

(3) 0  1  2  / 10  11  12 20 /
_______
3^1 (grp)  3^2(grp)

(2) 0  1  / 10  11  /
_______
2^1 (grp)  2^2(grp)

(4) 0  1 2 3 / 10 11 12 13 20 21 22 23 30 31 32 33 /
_______
4^1 (grp)  4^2(grp)

Conversion table:
GroupSize = Log(2)^4
Rule: (0/0  1/1 2/10  3/11 )
_______________________________________________________

Do you have any formalism to define a base as sub-language of other base for cases like this?

Post In Edition.


texts: Break an authentication protocol based on a pre-shared symmetric key

texts:
Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa.

$$ \begin{align*}
 A \to B: &\quad \text{“I'm Alice”}, R_A \\
 B \to A: &\quad E(R_A, K) \\
 A \to B: &\quad E(\langle R_A+1, P_A\rangle, K) \\
\end{align*} $$

$R$ is a random nonce.
$K$ is a pre-shared symmetric key.
$P$ is some payload.
$E(m, K)$ means $m$ encrypted with $K$.
$\langle m_1, m_2\rangle$ means $m_1$ assembled with $m_2$ in a way that can be decoded unambiguously.
We assume that the cryptographic algorithms are secure and implemented correctly.

An attacker (Trudy) wants to convince Bob to accept her payload $P_T$ as coming from Alice (in lieu of $P_A$). Can Trudy thus impersonate Alice? How?

This is slightly modified from exercise 9.6 in Information Security: Principles and Practice by Mark Stamp. In the book version, there is no $P_A$, the last message is just $E(R_A+1,K)$, and the requirement is for Trudy to “convince Bob that she is Alice”. Mark Stamp asks us to find two attacks, and the two I found allow Trudy to forge $E(R+1,K)$ but not $E(\langle R, P_T\rangle, K)$.


texts: What is the tightest asymptotic bound for this recurrence?

texts:
$$T(n) = T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + T\left(\frac{n}{8}\right) + n$$

How do you solve this recurrence?


texts: Is substitution done to all occurrences?

texts:
In a CFG, we might have :$A \rightarrow AA$ and $A \rightarrow a$ where $a$ is a terminal and $A$ is a variable.

Then if we apply the first rule,  and then the second , do we get $aa$ or either $aA$ or $Aa$ ?


texts:
I'm trying to solve the problem of transferring data from a pdf file to another file type.  When extracting data from PDF files I am to use the exact coordinates (where each unit is 1/72 of an inch in a pdf file) to the same position in another file type.  Say a text file or a word document etc?

I'm having trouble making the connection between this coordinate system and the file type I'm transferring data to.

Is there a way to make a quasi coordinate system in a text file or word document or a rich text file?  What about an output console.  I thought there might be some conventions used which govern how many pixels a space is in these documents?  For example if I have a space between characters in my pdf which has a difference of 8 x 1/72 of an inch it may just be kerning as opposed to a word space.  I'm not sure how to tell the difference and use that in my destination file.


texts: I have graphs $G_k$ and $H_k$ with $|\mathcal{V}(G_k)|=|\mathcal{V}(H_k)|^{2k}=n^{2k}$ with $k\in\Bbb N$ that pass sanity checks such as no-homomorphism lemma. Are there free and easy to use tools to test graph homomorphism from $G$ to $H$?


texts:
I am working on a special case of the longest path problem. For a cyclic directed graph $G=(V, E)$, where the edge-weights are probability values (i.e., $P(\_) = w(s, q)$ with $s,q \in V$), my aim is to find the least 'probable' path between two vertices.

My initial approach is to generate an graph $G'$ where the weights are the complementary probabilities $1- w(s, q)$ (with strictly positive values), and compute Dijkstra's shortest path on $G'$. Is this reasoning sound? Or am I getting myself into an NP-hard disaster?


texts: Framework or tools to generate theorem prover/solver/reasoner for new logic

texts:
I have new logic which has syntax and semantics in usual natural languages and I have to create theorem prover/solver/reasoner for this logic. Is there framework or tool set that can generate such prover from the formal definition of grammar and semantics? I have heard about Isabelle/HOL, is this right set of tools. Is such generation a common path to proceed. Are the metalogical framework, prover compilers suitable for any kind of new logic?

Of course, I can create parser and encode all the algorithms by myself from scratch but this is not the common practice, I guess?


texts: Why does a simple marking algorithm not work for deciding ETM, the set containing all TMs whose language is the empty set?

texts:
ETM = {|M is a TM and L(M) is the empty set} is not decidable.

This is typically shown by a reduction from HALT. I can kind of comprehend the proof, but intuitvely I still find it very strange that ETM is undecidable.

For example, why wouldn't the following algorithm not work?

1) Mark all states that can be reached starting at the starting state

2) If no final state was marked: return True

3) else: return False

A TM has a finite number of states, so this algorithm should always halt. Why doesn't it decide ETM?


texts: Conditions that imply closure under intersection of context-free languages

texts:
Context-free languages are not closed under intersection.

Suppose $L_1, L_2 \in CF \setminus REG$ (i.e., $L_1,L_2$ are context-free but not regular).

  Are there well-known theorems (and/or whole papers/research topics) that try to shape the sufficient/necessary conditions for $L_1,L_2$ to make $L_1 \cap L_2$ context free?


texts:
I'm trying to prove that $BPP^{BPP}=BPP$.

$BPP\subseteq BPP^{BPP}$ is obvious. I'm struggling with $BPP^{BPP}\subseteq BPP$..

Can anyone help?


texts: Time complexity for two multiplications modulo $p$

texts: The time complexity of computing $MK\bmod P$ is $O((\log n)^2)$.  What is the time complexity of computing $MK^2\bmod P$? Is it $O(2(\log n)^2)$ or $O((\log n)^2)$?


texts: Select a subset of the columns in $2\times n$ matrix, is it easy?

texts:
I want to know if this problem is polynomial-time solvable or not?

The problem is: Given a nonnegative integer-valued matrix of size $2\times n$ and two nonnegative integer numbers $b<n$ and $c$.

The question is: Find a subset of the columns of cardinality at most $b$ such that the sum of each row over the subset of the columns is greater than $c$. Return no if no such subset exists.

I cannot show it is NP-hard.

EDIT:

My attempt to prove hardness: According to the suggestions by Filmus, I tried to reduce PARTITION (an instance is given by the set of non-negative integers $\{a_1,\ldots,a_n\}$) to my problem. I failed of course. The think that I did not understand is how partitioning a set of non-negative integers is related to this problem? I mean in my problem I want to choose a subset of $\{1,\ldots,n\}$ in order to maximize something. I cannot see how this is a partition. I tried many thinks but I cannot write them all here:

I tried to create the matrix with only $a_{2i}$ in the first row and $a_{2i+1}$ in the second row.
I tired to make the first row sorted in increasing order and the second row sorted in the decreasing order.
I tried to divide the $a_i$ into two values $\alpha_i$ and $\beta_i$ such that $a_i=\alpha_i+\beta_i$ and then create the matrix with $\alpha_i$ in the first row and $\beta_i$ in the second row.

Can someone explain to me, intuitively, how can I use PARTITION to show the NP-hardness of my problem? You do not have to give the solution.

My solution to solving the problem:

I tried this solution. Suppose, without lose of generality that the first row of the matrix is sorted in increasing order. (The second row of the matrix does not have to be sorted otherwise the problem is trivial.)

Now, take the last $b$ columns of the matrix.

If the sum over the first row is less than $c$ than we are done. No solution exists.
Else, the sum of the first row over the last $b$ columns is greater than $c$, then see the sum of the second row.

If the sum of the second row over the last $b$ columns is greater than $c$ than we are done. Return the last $b$ columns.
Else, the sum of the first row over the $b$ columns is greater than $c$ but the sum of the second row over the $b$ columns is less than $c$. Well, here we have a problem.


texts: Is it possible to mapping reduce either of these languages to the other?

texts:
I have the following two languages, which are languages of TM descriptions:

$$INFINITE = \{ \langle M \rangle | \mbox{M is a TM and L(M) is infinite} \}$$

$$A_{ALL} = \{ \langle M \rangle | \mbox{M is a TM and } L(M) = \Sigma^* \}$$

Neither of these languages are decidable, recognizable, or co-recognizable.

However, I believe they're in $\Pi_2$, since a TM belongs to $INFINITE$ iff for every $x$, there is a string $y$ and computation history $H$ where $y$ has length greater than $x$ and $H$ is a history that shows that $M$ accepts $y$.
And a TM belongs to $A_{ALL}$ iff for every $w$, there is a computation history $H$ that shows that $M$ accepts $w$. (I'm not sure if this reasoning is correct or not, though).

I have been wondering for a while whether either of these languages are mapping reducible to one another. I don't see a quick way to prove that the languages are not reducible to one another, but I similarly can't see a simple reduction in either direction.

Are either of these languages reducible to the other? If so, how?


texts: Amortized analysis of base Fibonacci counter

texts:
We just started learning the potential method this week and I'm having a bit of trouble on this problem regarding Fibonacci numbers; specifically I'm having some difficulty thinking of a good potential function.

Suppose instead of powers of two, we represent integers as the sum of Fibonacci numbers. In other words, instead of an array of bits, we keep an array of fits, where the $i$th least significant
fit indicates whether the sum includes the $i$th Fibonacci number $F_i$. For example, the fitstring 101110 represents the number F6 + F4 + F3 + F2 = 8 + 3 + 2 + 1 = 14.

a. Describe an algorithm for an increment operation.

b. Show that a sequence of $n$ operations is amortized $O(n)$ using the potential method.

c. Do the same thing above, but now add a decrement operation.

This is what I started out with:

The general rule is to never let two consecutive Fibonacci numbers exist in the counter at the same time. In other words, no two 1's can occur consecutively. This is because of the definition of Fibonnaci numbers, i.e. a number such as 011 can be replaced by 100.

In general, when incrementing, change the least significant bit that's a 0 to 1 (this is one of the two "1" representations that are the first two bits in the counter). Starting from the most significant bit, if some positions $i$ and $i-1$ have 1's, then change them to 0's and change position $i+1$ to a 1. Keep recursing until there are no more consecutive 1's.

Now we will use the potential method to show that the amortized cost of $n$ consecutive increment operations is $O(n)$.

We will define our potential method as follow: (this is one part I'm having trouble with)

I then made the following observation:
Suppose the $i-th$ operation makes $x_i$ Fibonnaci conversions (changing consecutive 1's to 0's and changing the next significant bit to a 1). Then the actual cost is $1 + 3x_i$.

Any help is appreciated! Thanks!


texts: Can Expectation-Maximization algorithm with batch update diverge?

texts:
I am using EM to uncover a continuous hidden variable $z$ (E-step), then maximizing the model prediction (M-step) with parameters $\theta$. The complete data are $[x,z]$.

I can formulate the E-step as follows

$$p(t|x,\theta^{old}) = \mathop{\arg\,\max}\limits_z \sum log(p(t|x,z,\theta^{old}))$$

since I am looking for the most probable value of $z$ according to my current model parameters $\theta$.

Then I am looking for matching $\theta$ to the newly obtained $z$ by M-step

$$\theta^{new} = \mathop{\arg\,\max}\limits_{\theta} \sum log(p(t|x,z,\theta))$$

batch update

Now about the $x$. I have 3 batches of the $x=\{x_{1},x_{2},x_{3}\}$, such that E-step produces 3 batches of complete data $[x,z]=\{[x_{1}, z_{1}],[x_{2},z_{2}],[x_{3},z_{3}]\}$.

The E-step receives 3 different batches in 3 consecutive iterations. The M-step updates on every $[x,z]$. In other words, the M-step is the same, while the E-step iterates over 3 different data, with the model parameters $\theta$ being constantly updated.

Problem

The algorithm converges to the optimum (or quite close), and then diverges. The log-likelihood of the data being generated by the model is increasing (until the optimum) and then decreases.

Question

Can batch update cause a stable algorithm to diverge ?

In other words, can the batch update cause the E-M algorithm to diverge (literary decreasing the log-likelihood) ?

If so, please update me with some literature.


texts:
I'm working on a problem related to Latin squares, and I want a method for what essentially boils down to the decision problem:

Input: A finite, simple graph G.
Output: YES if G has a non-trivial automorphism, NO otherwise.

Hence...

Question: Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?

We could use Nauty or Bliss (and possibly some other packages) to compute the whole automorphism group, but I don't need it;  all I need to determine is whether or not it's trivial.

It's possible this decision problem is theoretically equivalent in complexity to "compute the whole automorphism group" in some way.  I'm not sure.

For my purpose, "efficient" basically means "faster in practice than computing the whole automorphism group", but I'm also interested in the theory behind it.


texts: Uniform sampling over non-standard simplex

texts:
Uniform sampling over a $n$-dimensional standard simplex is described here: Uniform sampling from a simplex

I want to sample one point from a non-standard simplex with vertices at:

$s_{i}\vec{e_{i}}$, where $\vec{e_{i}}$ is the $i^{th}$ vector in the standard basis, and $s_{i} \ge 0$.
the origin is : $\vec{0}$

How to do that? It seems to be no longer a special case of the Dirichlet distribution.

Hit-and-run sampling would need a lot of cycle to diffuse throughout the simplex. When I only need one point, the other points are wasted.

Currently, $n \approx 15$


texts: Iteration vs. recursion: what do these terms really mean?

texts:
Most of us know the typical answer to this question: if a function calls itself, it's recursion, if it's a loop, it's iteration. We also know that recursion can be simulated using iteration (by manually unrolling the call stack) and iteration can be turned into recursion.

Yet there's something about this that keeps bugging me. Suppose we have a recursive algorithm that we unroll, so it does not use our favourite language's function call operator on itself anymore. Has this really become an iterative algorithm though? Would this mean in a language that has no concept of functions (most assembly languages go here) we cannot have a recursive algorithm? Graph travelsals and some numerical algorithms are often recursive in nature: we start a computation for some input, discover we can't finish it without doing the same computation on some other input, so we put it aside, start working on something else and then later come back and finish the job. To me, "iterativizing" these algorithms still leave the algorithms themselves recursive, just making the implementation iterative.

Just like if we're trying to compute some numerical sequence that has a nice iterative algorithm (think sum of first $n$ numbers and similar), putting tailcalls where the loop would restart doesn't really feel like we've made the algorithm itself recursive.

To me recursive/iterative has more to do with whether we start at the root or the leaves of a computational dependency graph (in which a problem instance has an edge leading to another if the former is dependent on the result of the latter).

Could anyone shed some light on the theoretic background of this matter please? What do these terms really mean? It would be greatly appreciated.


texts: Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph

texts:
I have been scratching my head to find good counter examples to the following problem:

  Suppose we are given a directed graph G=(V,E) in which every edge has
  a distinct positive edge weight. A directed graph is acyclic if it has
  no directed cycle. Suppose that we want to compute the maximum-weight
  acyclic subgraph of G (where the weight of a subgraph is the sum of
  its edges' weights). Assume that G is weakly connected, meaning that
  there is no cut with no edges crossing it in either direction.

  Here is an analog of Prim's algorithm for directed graphs:
  Start from
  an arbitrary vertex s, initialize S={s} and F=∅.
  While
  S≠V, find the maximum-weight edge (u,v) with one endpoint in S and one endpoint in V−S. Add this edge to F, and add the appropriate endpoint to S.

  Here is an analog of Kruskal's algorithm. Sort the edges from highest
  to lowest weight. Initialize F=∅. Scan through the edges; at each
  iteration, add the current edge i to F if and only if it does
  not create a directed cycle.

Both algorithm fail.
There should be a 4 vertices graph with 2 cycles that demonstrate this.

So far I played with different weights for this:

A<----B
^⟍    ^
|  ⟍  |
|    ➘|
C<--- D

However I am not yet able to prove that both algorithms fail.
I would love any suggestioin


texts: Amortized time of insertion into an Array list

texts:
According to Amortized time cost of insertion into an Array list,

  A dynamically resizing array list will resize when the number of elements reaches a power of two. So, after n elements inserted, we've resized at sizes 1, 2, 4, ... , n.

Can anyone kindly explain me the logic of this? If we consider the n(number of elements)=7 then we resize array at sizes 1,2,4 but according to above statement "1,2,4....7".


texts: How to represent a 0-valid boolean formula?

texts:
I read in these two papers http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf and http://people.csail.mit.edu/madhu/papers/noneed/fullbook.ps that if we have a boolean formula that is $0-valid$ then (of course) SAT problem is in $\mathcal{P}$ but finding a solution with maximum true literals is $\mathcal{NP}-$hard.

N.B. As defined in the previous papers, a $0-valid$ boolean formula $f$ is a boolean formula $f: \{0, 1\}^n\rightarrow\{0, 1\}$ that satisfies $f(0, \dotsc, 0)=1$.

My question is:

Can I represent a general $0-valid$ boolean formula on the variables $x=\left(x_1, \dotsc, x_n\right)$ by the following one:

$f(x)=\bigwedge\limits_{i=1}^{L}\bigvee\limits_{i\in\mathcal{S}_l}\neg\;x_i$?

Where $L$ is the number of clauses and $\mathcal{S}_l\;\forall\;l\in\{1,\dotsc, L\}$ is a subset of $\{1, \dotsc, n\}$.


texts: Dijkstra's algorithm - additional properties

texts:
Say we let $R$ denote the set of currently chosen vertices in Dijkstra's algorithm, $d$ be the currently stored path-length estimates, and $s$ be the source. The standard property that we know is true is that for all $r\in R$, $d(r)$ is the correct shortest path length from $s$ to $r$.
I was just wondering if the following additional properties would be true:

For all $r\in R$, the shortest path from $s$ to $r$ lies completely within $R$.
For all $u\not\in R$, $d(u)$ is the length of the shortest path from $s$ to $u$ which passes through only vertices in $R$ (except $u$ itself, of course).


texts:
Trying to understand the concept of NP-completeness, I came across this pearl on Wikipedia:

  From NP-complete:

  A decision problem L is NP-complete if it is in the set of NP problems
  and also in the set of NP-hard problems.

  From NP-hard:

  A problem H is NP-hard if and only if there is an NP-complete problem
  L that is polynomial time Turing-reducible to H [...].

So it appears that the definition of NP-completeness depends on the definition of NP-hardness, and vice versa.

What is going on here? How can I untangle these concepts?


texts: Help Finding Loop Invariant From For Loop

texts:
I have created the algorithm below...

        String A = v[0];
        int val = 1;

        for (int i = 1; i < v.length; i++) {
            if (val == 0) {
                A = v[i];
                val++;
            } else if (v[i].equals(A))
                val++;
            else
                val--;
        }

The goal of the algorithm is to find the item that occurs in more than half the array.

Let v = {"one", "two", "one", "three", "one", "two", "two", "one", "one"}

The string "one" occurs 5 out of 9 times.  So, at the end of the loop, the String A will be equal to "one".

I'm lost as to how to derive a loop invariant from this.  Could someone provide me with some direction?


texts: Difference between assignment, binding, and substitution?

texts: I am trying to understand the difference of assignment, binding, and substitution. I know the three things are related, but to me it's not exactly clear what word refers to what. Example, illustration, and citations from computer science wiki/articles/textbooks are welcome.


texts: How to express modalities in rule bases, knowledge bases or expert systems?

texts:
Knowledge bases and expert systems are usually production rules systems and as such they lack expressive means for expressing modalities like "agent believes in statement", "agent has duty to perform action", "agent has permission to perform action". Modalities are usualy written as modal operators (diamond and square boxes) or as special kind of implications. https://ts.data61.csiro.au/publications/nictaabstracts/5627.pdf is good example how to introduce modalities in defeasible logic without Kripke/relational/possible world semantics/machinery.

Introduction of modalities introduces both new symbols in language and new inference rules in language (like permission follows from duty), https://en.wikipedia.org/wiki/Modal_logic contains list of good examples of rules that are brought with introduction of modal operators.

So - my question is - how to introduce modalities in expert systems / production rule systems which have no dedicated operators or implications for modalities?

My proposal is to treat modalities as predicates and introduce special kind of metarules that for each type of modal predicate generate relevant modal predicates. E.g. which for duty-predicate generates permissions-predicate. There is book about such approach http://www.springer.com/us/book/9783319225562

Is my proposal about modalities as special kind of predicates sound, are there alternatives?

Specifically, I am trying to introduce modalities http://opencog.org/, this system support meta-rules and higher-order rules, so my approach maybe is valid and academically acceptable?


texts: Are regular expressions a*a and aa* equivalent?

texts: Let $\Sigma = \{a, b\}$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $\Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is correct, but I am not sure.


texts: Clear definitions of various terms related to top down parsers and classification of the same

texts:
I am trying to clearly define various terms related to top down parser "so that I can relate them and come up with clear classification". Now this efforts might seem unnecessary as the terms I am talking are pretty basics, but I am trying this all for sake of 100% clarity.

The dragon book defines predictive parsing as follows:

  A special case of recursive descent parsing, where no backtracking is required. Predictive parsing chooses the correct A-production by looking ahead at the input a fixed number of symbols, typically we may look only at one (that is, the next input symbol).

It defines $LL(k)$ grammars as follows:

  The class of grammars for which we can construct predictive parsers looking
  $k$ symbols ahead in the input is sometimes called the $LL(k)$ class.

Now I have following doubts:

Is the definition of $LL(k)$ parsers same as that of $LL(k)$ class of grammars above?
Is above definition of "predictive parsing" correct? Are the two definitions of predictive parsing and LL(k) parsing same? and hence the two concepts are also same?
If answer to above (Q2) is NO, then in what other (than $LL(k)$) way, we can implement predictive parsers?
Is the above definition of predictive parsers correct? It says "a special case of recursive descent parsing, ...". Cant we implement predictive parsers with non recursive descent approach?
Similarly, cant we implement $LL(k)$ parser with non recursive descent approach (which I know we can)?
Question 4 and 5 asks for non recursive descent approach for predictive and $LL(k)$ parsers, which are essentially non backtracking. Can we implement backtracking parser with non recursive descent approach (without lookahead) (pink box below)?
Is "bruteforce parsing" same as "recursive descent parsing without lookahead"? I have just heard of "bruteforce parsing", how we define it?
Is below classification looks correct?

(Sorry for so many questions, but I believe they make sense together.)


texts: Complexity of keeping track of $K$ smallest integers in a stream

texts:
I need to analyze the time complexity of an online algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers. The algorithm is

Suppose the $i$th number in the stream is $S_i$.
Keep a max heap of size $K$.
If the heap contains fewer than $K$ elements, add $S_i$ to the heap.
Otherwise: if $S_i$ is smaller than the maximum element in the heap (i.e., the root of the heap), replace the root of the heap with $S_i$ and apply Max-Heapify to the heap; if $S_i$ is greater than or equal to the max element, do nothing.

The problem now is to find the expected number of times the Max Heapify operation will be called, when the stream of integers is of length $R$ and each element of the stream is (iid) uniformly distributed on $[1,N]$.

If the stream were guaranteed to contain only distinct elements, then the answer is easy:

$$E[X] = E[X_1] + E[X_2] + \dots + E[X_R],$$

where $X_i$ is the random indicator variable for occurrence of the Max Heapify operation at the $i$th number in the stream.  Now

$$E[X_i] = \Pr[\text{$S_i$ is ranked $\le K$ among first $i$ elements}] = \min(K/i, 1).$$

Hence,

$$E[X] = K + K/(K+1) + \cdots + K/R.$$

That case is relatively easy.  But how do we handle the case where the elements are iid uniformly distributed?

[This was actually a Google interview question.]


texts: Calculate boolean matrix multiplication (BMM) using transitive closure

texts:
Let us say I am given an algorithm that calculates the transitive closure of a given graph $G = \{ V, E \}$.
How can I use this algorithm in order to perform the Boolean Matrix Multiplication of two matrices $X$ and $Y$?

I know that in order to calculate the transitive closure of a matrix $I$ need to compute $I^{(V-1)}$. But what else?