Showing that a language satisfies the pumping lemma I am wanting to show that this language fails to show that it is not context-free. So, in essence, it satisfies the pumping lemma

If L = {ambncndn | m,n >= 1 }

Should I have n be the constant of the pumping lemma? Is z=ambncndn and |z|= m+3n>n ?

By the pumping lemma, there exist u,v,w,x,y such that z=uvwxy, |vwx| <=n, |vx|>=1 . I'm just a little thrown off by the two different letters for the exponents, can I treat m and as another n?

Assume that pumping lemma is satisfied for $L$. Let $N$ be the pumping length.

Now take $z = ab^Nc^Nd^N \in L$. $|z| = 3N+1$ and hence this string can be pumped.

For this string, every choice of $u,v,w,x$ and $y$ that satisfies the conditions of pumping lemma will have a choice of $i \in \mathbb{N}$ such that $uv^iwx^iy \not\in L$. This is a contradiction. Hence $L$ is not context-free.


Why is casting float to double applicable? This is indeed a Computer Science Question.
As far as I am concerned casting down (up) does not require any mathematical operation. It is just shrinking down (leveraging) the significant bits.

e.g

Long: 0x00000000ffffffff casts down to
Int:  0xffffffff

However, this does not work with the representation of double and float:

Double:  b = 0xa000 0001 1000 0001 should cast down to

Float:   c = 0x1000 1001

which is not the same, even if the double is in the boundaries of float.

So how is Casting from any type to another defined?

This is really not a computer science question...

First, you failed to distinguish between "casting" and "conversion". In many computer languages, "casting" is an explicit instruction to convert a value from some type to another type. For example in C,

double d = 3.7;
float f = d; // Automatic conversion, no casting

double d = 3.7;
float f = (float) d; // Casting as requested by programmer
double e = (float) d; // Casting to float, followed by conversion to double

So what you were really talking about was value conversion, not casting. (Being precise in what you write is arguably part of computer science).

The effect of any conversion is defined by the computer language in question. "Shrinking down (leveraging) the significant bits" is something that doesn't make any sense at all. Bits don't have a size, you can't shrink them. And the word "leveraging" doesn't mean what you think it means. I assume you meant "removing the significant bits".

But that's not how value conversion is defined. In C and C++, it is defined in terms of values. A conversion between scalar types results in the exact same value if the old value can be represented in the new type. If the value cannot be represented, then there are rules for conversions between integer types; in some cases the value is modified according to rules in the language, sometimes the value is modified according to implementation defined rules (and "implementation defined" has a very specific meaning in C and C++ that you need to learn), or it is undefined behaviour.

Converting non-integral floating point values to integer values first rounds the value towards zero, and then other rules apply. Conversion between floating-point values will produce the original value if possible, rounds according to rounding rules in the language if that is not possible, with additional rules if the value is too large to represent.

Do you notice how nothing at all here is talking about bits?

Swift distinguishes between conversions that cannot fail and conversion that can fail. Conversions that can fail produce an optional value. Which is a totally different thing. For example, you cannot convert UInt to Int, only to an optional Int. You cannot convert Int64 to Int32, only to an optional Int32. But you can convert Int32 to Int64, because it is a conversion that cannot fail.


Why is Brent's Cycle Detection method faster at finding a Linked List cycle than Floyd's Cycle Detection method? I understand in Floyd’s cycle, you are finding a cycle in a linked list by moving two counters- one by a factor of 2, other by a factor of 1. In Brent’s you are basically doing the same but the one factor moves by multiplying 2 instead by merely adding 2. Is there any math explanation behind why Brent’s is faster than Floyd’s?

The performance of cycle-finding algorithms depends on two parameters $m,n$. Here $n$ is the length of the cycle, and $m$ is the initial position of the cycle. For example, consider the sequence
$$ 2, 3, 5, 6, 5, 6, 5, 6, \ldots $$
Here the cycle is $5,6$ and so $n = 2$. The first index of the cycle (assuming $x_1 = 2$ and so on) is $m = 3$.

We assume that the sequence is generated by repeatedly applying some function $f$. We measure the complexity of cycle-finding algorithms by the number of applications of $f$.

According to Brent's paper, the complexity of Floyd's algorithm is between $3\max(m,n)$ and $3(m+n)$, and that of Brent's is at most $2\max(m,n) + n$, which is always better than $3\max(m,n)$.

A perhaps more meaningful comparison is what happens in the average case. In this case we assume that $f$ is a random function on a universe of size $N$ (the starting point doesn't matter in this case). Knuth showed that the expected running time of Floyd's algorithm is roughly $3.0924\sqrt{N}$, whereas Brent's algorithm runs in expected time roughly $1.9828\sqrt{N}$, as worked out in Brent's paper.

For more details, take a look at Brent's paper and the references therein.


How to write Context Free Grammar with numerical restrictions I am supposed to write a Context free grammar that generates the language:

$\qquad L(G) = \{0^{3n}1^{2n}0^{m}1^{m} : n \ge 1, m \ge 1\}$

I have the rules:

$$S \rightarrow 000S$$
$$S \rightarrow S11T$$
$$T \rightarrow 0T$$
$$T \rightarrow T1$$

This looks correct in terms of the structure of the grammar but I am not sure how to denote how to tell the grammar to terminate at the correct time given the conditions $n \geq 1$ and $m \geq 1$.

First off, your grammar isn't quite right, since there's no way to eliminate $S$; every production with $S$ on the LHS produces a string including $S$, so your grammar generates no (finite) strings at all.

To capture the "greater than or equal to 1" requirement, you should have a rule that produces the smallest permissible string; to handle the $m$ case, this would mean you need a production yielding $00011$. To handle the $n$ case, on the other hand, you'd need a production yielding $01$. Together, this implies that $0001101$ is the smallest string in your language. With the base cases out of the way, you can add other productions to build on this base case.

For your case, you have have a context-free language which is the concatenation of two other context-free languages. If you can make a grammar for the two constituent languages, it's easy to make a grammar for your language:

$$S \rightarrow S_1S_2$$

Grammars for the other are easy, too, and you had the right idea:

$$S_1 \rightarrow 00011 \mid 000S_111$$

and

$$S_2 \rightarrow 01 \mid 0S_21$$


What is the difference between designing an algorithm that solves a problem and creating a TM that decides a language? Question: What is the difference between designing an algorithm that solves a problem and creating a Turing machine that decides a language?
A turing machine "decides" the language if it "accepts" the language and enters a rejecting state for any input not in the language.
Don't really know what the difference is

Depending on the problem, there might not be any difference.
If the problem's goal is to answer a yes/no question, then there is no difference; accepting the input is equivalent to answering yes, and rejecting is equivalent to answering no.
However, if the goal of your problem is to output something else (e.g., output a number), then it is not identical to deciding a language.  There are still ways to formulate a corresponding language, but the correspondence is not quite as direct.
To learn more, see https://en.wikipedia.org/wiki/Decision_problem, https://en.wikipedia.org/wiki/Function_problem, https://en.wikipedia.org/wiki/Optimization_problem, https://en.wikipedia.org/wiki/Formal_language.


How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3)

I was told it takes:

$$2(n-2) + 1 =  2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

  The worst case occurs if the first list empties when there is
  exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers
  requires 2 comparisons before going into the big list. After this, we only need 1 more
  comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the $2(n-2)$ came from... What does:

  The worst case occurs if the first list empties when there is
  exactly 1 item in each of the other two.

even mean?

When it says "prior to this", its not clear to me what exactly happened before hand...

What does the "big list" referring to? How did we even get a "big list"?

Btw, I am not looking for an asymptotic answer.

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left[ (c-1)(n-(c-1)) + \sum^{c-2}_{i=1} i\right]$$

The extra term for merging is not entirely clear to me.

First of all, we have to distinguish between two different questions. The first is about analyzing the specific (generalized) merging algorithm used in merge sort. The second is about analyzing the problem.

Merge sort merging

The paragraph you quote attempts to analyze the merge sort merging algorithm. It only gives a lower bound on the number of comparisons, though presumably it is easy to show that it is also an upper bound. In order to give a lower bound of $C$ on the number of comparisons, it is enough to describe a situation in which the algorithm uses $C$ comparisons. Such a situation is the "worst case [instance]" that the paragraph is talking about.

The merging algorithm starts with three lists of length $n/3$, and constructs a "big list" of length $3$. The algorithm works by comparing the smallest elements in all remaining lists, and moving the smallest one to the top of the big list. As the algorithm progresses, eventually lists will empty — all their elements have been moved to the big list.

The paragraph suggests to consider the situation in which the first list empties when the other two have exactly one element remaining, which it claims is a "bad case", indeed the "worst case"; for the sake of the lower bound, we don't care whether this is actually true. You have to argue that the situation can actually happen, and carefully count all comparisons done by the merging algorithm. The merging algorithm the paragraph considers always compares the bottom elements of all remaining lists, requiring $\ell-1$ comparisons if $\ell$ non-empty lists remain. In this case, as long as all lists are non-empty, we need two comparisons per element.

At the situation considered there are only two elements left, so $n-2$ elements have been processed with two comparisons per element, leading to $2(n-2)$ comparisons. The final two elements require one more comparison. It is not too hard to check that this is indeed the worst case: this situation maximized the number of times that an element requires two comparisons to process.

The more general case with $c$ lists is very similar. Again the worst case is when the first list empties when all other lists have exactly one element. Up to now there have been $(c-1)(n-c+1)$ comparisons. The next element will require $c-2$ comparisons only (since there are only $c-1$ non-empty lists), the element after that $c-3$, and so on. This gives the formula you state.

General question

A different question one can ask is: given $c$ sorted lists of length $n/c$, how many comparisons are needed to determine the sorted order of all of them merged. There are two variants of this question:

What is the minimal $C$ such that there is an algorithm which outputs the correct order and never uses more than $C$ comparisons; the algorithm is only allowed to access the lists by comparing two elements. This is the so-called decision-tree model.
What is the minimal running time of an algorithm merging the lists.

These questions are rather different. The first question is much easier to answer, and I will only comment on it. However, the minimal $C$ doesn't necessarily correspond to an efficient algorithm, since determining which comparison to do next could be difficult.

The classical lower bound on sorting extends to this situation. Given $c$ sorted lists of length $n/c$, the number of possible ways they fit together to one big list is $\frac{n!}{(n/c)!^c} = \Theta\big(\frac{c^n}{n^{(c-1)/2}}\big)$, and we obtain a lower bound of $(\log_2 c)n - O_c(\log n)$. Fredman's classical result shows that there is a corresponding algorithm in the decision-tree model using at most $(2+\log_2 c)n$ comparisons (for large enough $n$, depending on $c$), which is better than the merge sort merging procedure for $c \geq 5$. The correct answer is probably $(\log_2 c)n \pm o_c(n)$. Indeed, using heaps you can merge $c$ lists with $O((\log c)n)$ comparisons efficiently, as described for example in answers to the following question.


Addition errors in IEEE754 floating point representation So in class, we were talking about the idea of floating point precision in IEEE754 format, and how, when some numbers are added, precision is lost. My professor then gave the following example of a large absolute error between what we think the answer might be, and what the answer actually is when our program (written in Java) actually compiles it:

$0.4 \times10^{30} + 1.1 \times10^{30}$

Compiling this in Java, i get $1.5000001 \times 10^{30}$

My question is, why does this happen? Printing out the IEEE754 format of the two numbers, I get:

$\space\space\space0[11100010]10111100010010010101011=+1.10111100010010010101011\times2^{99}$
$+0[11100001]01000011000111100001000=+1.01000011000111100001000\times2^{98}$

So, I suppose when you add these, you end up loosing precision, but exactly how? Moreover, how can I even tell, before adding, that the addition of two numbers will make them loose precision? Or is the only way to just plus into a program and see what happens? None of this was really covered in class unfortunately.

Printing out the IEEE754 format of the two numbers, I get:

  $\space\space\space0[11100010]10111100010010010101011=+1.10111100010010010101011\times2^{99}$
  $+0[11100001]01000011000111100001000=+1.01000011000111100001000\times2^{98}$

Compare the exact values:

$$
1.1011110001001001010101011000111111010110011111001110000010110110100111 \times 2^{99} \\
1.0100001100011110000011111010111001101101011100100001011111001010101 \times 2^{98}
$$

Observe that both of the numbers are already rounded to represent them in IEEE 754, and it happens that both of them have rounded up.

Also note that since the values have different exponents, they've been rounded at different places.

Now add the rounded values:

  1.10111100010010010101011 ×299
+ 0.101000011000111100001000×299
 -------------------------------
 10.01011101110110000101111 x299
 11  1         1111

There's overflow, so the answer will have exponent $2^{100}$ and we have to round. Again, we're rounding up, to $1.00101110111011000011000\times2^{100}$.

  So, I suppose when you add these, you end up loosing precision, but exactly how?

You will nearly always lose precision when adding two floating point numbers. If they're both positive and have the same exponent, the output will have a larger exponent and you lose some bits from the end. If they have different exponents, the smaller one will lose bits from the end. And if they have opposite signs and the same exponent, the output has a smaller exponent and you lose precision because you need bits beyond the end which were lost earlier. Essentially the only cases where you don't lose precision are when you add a number to itself, or when the input numbers and the result can all be represented exactly in the width of the type.


Can anybody suggest some algorithms for computing the edit distance other than Wagner–Fischer algorithm? I'm currently working with finding edit distance between two string of unequal length. But I'm sorry to say that I've got only one algorithm using Dynamic programming to find out edit distance. But I'm dealing with some cryptographic measure with edit distance where algorithm with dynamic programming is not suitable. Please have a look at the algorithm. If we want to do this computation homomorphically, circuit-based computation is needed here which will time consuming one. Usually homomorphic computation works well where there is more additions than multiplications.

This is why, I'm looking for another algorithm rather than the above one.

The fastest known exact algorithm is due to Masek and Paterson, and runs in time $O(n^2/\log n)$ for two strings of length $n$. Bačkurs and Indyk show that an $O(n^{2-\epsilon})$ algorithm would refute a (somewhat) widely believed conjecture, SETH, and Abboud et al. gave stronger results in this direction.


Why is it O(1) (and not, say, O(2))? 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?

"$O(1)$" is used because it is simple, clear and unambiguous. "$O(C)$" would be a poor choice of notation because in any given context, $C$ might have a specific meaning, such as the number of clauses in a CNF formula, the number of components in a graph.


Does there exist a subset of substrings for reconstructing another string? I am looking for a high performance algorithm to check whether I can reconstruct a given string using a given set of substrings. More details:

Let's say our strings are over the alphabet $\Sigma$.

Inputs:

A string $S \in \Sigma^*$
A finite set of strings $A = \{a_1, a_2, ..., a_n\} \subset \Sigma^*$.

Output:

Whether $\exists m: \exists b_1, b_2, \ldots, b_m \in A: b_1+b_2+\cdots+b_m = S$

where $+$ is string concatenation.

For example, if $S={}$"$abcd$" and $A = \{$"$ab$"$,$"$cd$"$,$"$ac$"$\}$, the answer is True.
For the purposes of this question, assume that strings in $A$ can be reused multiple times if necessary.

If reusing strings in $A$ is allowed you can solve it with dynamic programming: First, store strings in $A$ in a prefix tree (just a reversed suffix tree link), and recursively detrmine if $S[i:end]$ can be constructed from $A$: Let $\ell$ be the length of the string, and wlog assume $S$ is appended by $\$$ and $A\gets A\cup \{\$\}$. Moroever, let $m[i]\in\{0,1\}$ indicate if $S[i:\ell]$ can be constructed by elements in $A$. Initialize $m[i]\gets \infty$ for $i=0,\dots, \ell-1$ and $m[\ell]=1$ (because $S[\ell]=\$$).
Now, suppose $f(i)$ is the function that recursively computes $m[i]$ if it hasn't been computed already. When $f(i)$ is called, start at the root of the suffix tree of $A$, and traverse $S[i], S[i+1], \dots$ on the suffix tree until index $j$ , such that the corresponding node is in $A$, and recursively call $f(j)$. If returns $1$, set $m[i]=1$ and return $1$. Otherwise, repeat the process with traversal of $S[j+1], S[j+2], \dots$ until another member in $A$, or a leaf is reached. If there was no success, set $m[i]=0$ and return $0$. To decide the problem, call $f(1)$. The worst case complexity is the complexity is $\ell d$, with $d$ being depth of the suffix tree (longest sequence in $A$), plus the cost of construction of the prefix tree.

The worst-case scenario in many cases will be avoided because the recursive call search stops as soon as one solution is found. So in practice, the $\ell d$ part might be much less. The construction of the suffix tree can be expensive depending on $A$. But if $A$ is used for several strings $S$, the cost is amortized. If $A$ is really big and $S$ is short, it might be better to just sort elements of $A$ and do a binary search instead of traversal.


Amdahl's law of processors (infinite processors to test limits of speedup) My processor noted that an infinite number of processors will allow me to test how much speedup I can achieve.

I am not exactly sure how this applies.

For instance, let's say I have a program that takes $1000$ seconds to execute and is broken into 4 phases(A, B, C, D). If two of the phases are $50%$ parallelizable and the other $2$ are not parallelizable at all, how can I apply the concept that I have infinite available processors to figure out how much maximum speed up I can achieve?

I attached numbers to my example, but a generic one would be just as helpful.

If I am to strictly just apply Amdahl's law, I'd say the answer is just $1/(1-0.5) = 2$ times faster.

Don't think of it as "you've been given infinity processors." Think of it as "you can have as many processors as you want, but of course after a certain point more professors won't help, so find out how fast you can make it run with the optimum number of processors."


Pumping Lemma. Why is there a word w in L for infinite languages with n≤|w|≤2n The following comment on an other question says that if we have an infinite language L that satisfies the pumping lemma for regular languages then we have a word with n≤|w|≤2n which is in L. (n is the constant in the pumping lemma)

https://cs.stackexchange.com/a/55606/99669

Why is this the case? The lower limit can be explained by the constant of the regular pumping lemma, because in infinite languages there exists a word in L which is longer than n.

But how comes there is an upper limit? The pumping lemma does not say anthing about a upper limit for the words we choose.

Suppose that $L$ is an infinite language which satisfies the pumping lemma with constant $n$. Let $w \in L$ be a word of minimal length in $L \cap \Sigma^{\geq n}$ (i.e., among the words in $L$ of length at least $n$, choose a word of minimal length). Since $L$ satisfies the pumping lemma, we can write $w = xyz$ in such a way that $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. In particular, $xz \in L$. Since $|xz| < |xyz|$, we must have $|xz| < n$, and so $|w| = |xz| + |y| < n + |xy| \leq 2n$.


one-to-many matching in bipartite graphs? Consider having two sets $L$ (left) and $R$ (right).
$R$ nodes have a capacity limit.
Each edge $e$ has a cost $w(e)$.

I want to map each of the $L$ vertices to one node from $R$  (one-to-many matching), with minimum total edge-costs.

Each vertex in $L$ must be mapped to one vertex in $R$ (but each node in $R$ can be assigned to multiple $L$-nodes).

Examples: Consider the capacity of $R$ nodes is $2$.

1) This is NOT correct, since one node from $L$ has not assigned to a node in $R$.

2) This is NOT correct, since the capacity of a node in $R$ is violated.

3) This IS correct. All $L$ nodes are assigned to a node in $R$, and the capacity of $R$ nodes is not violated.

Any idea how can I solve this?

This problem is called the B-matching problem. Where you are given a function $b:V \rightarrow \mathbb{N}$ that assign a capacity to each vertex and a function $u:E \mapsto \mathbb{N}$ that assigns a weight to each edge.

The problem is solvable in polynomial time. An easy solution is to reduce the problem to minimum weight maximum matching. Create $b(v)$ copies of each vertex  $v$ and connect each of them to all neighbors of the original vertex v. We get a polynomial time reduction, since for $b(v) \geq \mathrm{deg}(v)$ we can set $b(v) := \mathrm{deg}(v)$ since we can not match $v$ with more vertices than its neighborhood anyway and that each of its neighbors is matched with at most one vertex in your special case.


Reducing vertex cover to minimal vertex cover What is a quick and a elegant way to reduce vertex cover to minimal vertex cover?

Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? since minimal vertex cover is essentially $min{f(x)|x\in VertexCover(G)}$

Graph is basic if it matters, no weights, and it is undirected

thank you for helping

Search for Bellare and Goldwasser "The Complexity of Decision vs. Search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119, or Bellare's class note on the matter.


Collection of real world non computable programming tasks I'm quite new to computability theory and would be interested in some examples of realistic programming tasks you could encounter when working as a C++ programmer that are not computable.

Are there some inputs that make my program crash?
Can this object be freed (from memory) or can it be needed later?
I'm building an editor and want to detect the programming language automatically. Given two languages described by CFGs, is there some input code for which I won't be able to guess the language (because it's valid in both languages)?
Do these two programs do the same thing?

Suppose that you have a property of programs so that:

It only depends on what the program does, not how it's written. So for example "It computes the factorial" or "It loops forever" work, but neither"It's written using a for loop" nor "It uses 5 variables" do.
There is some program that has the property
There is some program that doesn't have the property

Then Rice's theorem tells you that you can't have a (meta-)program that looks at source code and tells you if the program it describes has the property.

(My first and last examples are instances of that theorem)


Matching with One-sided Preferences I'm dealing with a slight variation on a classic matching problem on sets $A$ and $B$), where:

Set $A$ has an incomplete set of preferences (not all of $B$ is included)
Set $B$ has no preferences whatsoever.

I want to find an $A$-optimal matching (e.g, for any $(a_1 \rightarrow b_1), (a_2 \rightarrow b_2)$, then either $b_2$ is lower than $b_1$ or does not appear in $a_1$'s preferences, and likewise for $a_2$) between $A$ and $B$, respecting $A$'s preference lists, and where ties between members of $A$ are broken randomly. I've been trying to apply the Gale Shapely algorithm to this problem, with random preferences for B, but it appears to have degenerate cases where the above criterion is violated.

A pre-rolled solution to this problem seems to be somewhat elusive, potentially because it's so obvious. There's a related SO question, Stable marriage problem with only one side having preferences, which states the no-preference issue, but the answers only cover how to check for a perfect matching, which does not necessarily guarantee the optimality of the result with respect to $A$'s preferences. Is there an algorithm that produces an $A$-optimal matching?

We can suppose without loss of generality that the elements of $A$ have complete sets of preferences (if an element of $A$ is indifferent to some elements of $B$, we put them at the bottom of the element's preference list).

Our goal would be to match elements of $A$ and elements of $B$ such that the resulting matching is stable in the following sense. For any two elements $a_1,a_2 \in A$, either $a_1$ prefers its current match to that of $a_2$, or $a_2$ prefers its current match to that of $a_1$.

Here are two different algorithms for solving the problem. The first uses a greedy approach. Order the elements of $A$ arbitrarily: $A = a_1,\ldots,a_n$. Let $a_1$ choose its top pick, let $a_2$ choose the top available pick, and so on. This results in a stable matching since if $i < j$ then $a_i$ prefers its current match to that of $a_j$.

A different approach, more similar to the Gale-Shapley algorithm, is iterative. Start with an arbitrary matching $f$. If there is a pair $a_1,a_2$ in which $a_1$ prefers $f(a_2)$ over $f(a_1)$ and $a_2$ prefers $f(a_1)$ over $f(a_2)$, then switch $f(a_1)$ and $f(a_2)$. This decreases the objective function $\Phi$ which is the sum over $i$ of the index of $f(a_i)$ in $a_i$'s preference list. Since $n \leq \Phi \leq n^2$ and $\Phi$ is an integer, we deduce that this algorithm terminates in $O(n^2)$ rounds.


How would a neural network deal with an arbitrary length output? I've been looking into Recurrent Neural Networks, but I don't understand what the architecture of a neural network would look like when the output length is not necessarily fixed.

It seems like most networks I've read descriptions of require the output length to be equal to the input length or at least a fixed size. But how would you do something like convert a word to the string of corresponding phonemes?

The string of phonemes might be longer or shorter than the original word. I know you could sequence in the input characters using 8 input nodes (bitcode of the character) in a recurrent network, provided there's a loop in the network, but is this a common pattern for the output stream as well? Can you let the network provide provide something like a 'stop codon'?

I suppose a lot of practical networks, like those that do speech synthesis should have an output that is not fixed in length. How do people deal with that?

You just add more neurons. You're right that it's often not useful (if you only get 5 bits of information in, it's hard to put 10 bits of information out), but if you want to (e.g. because your output format is less dense), go ahead.

As a trivial example, if you wanted to create an ANN to convert characters to graphemes (as represented on an 8x8 grid of on/off pixels) you could have 26 input neurons and 64 output neurons. Connect each input neuron to the output neurons which would be turned on if that character is being displayed; then the output neurons' function is just logical OR.

The standard learning algorithms like gradient descent should work fine no matter the size of the output layer.

EDIT: I guess your question is: "how do you handle unknown input and output lengths?" Any Turing machine can be simulated by a recurrent neural network, so you will never run into a "halting problem" (if I understand what you mean by that phrase).

It's very rare that you can't bound the size of the output as a function of the input size. So you just have some metalearning procedure which generates the network for you on the fly.

One common idea is that of "template" models. I'm not familiar with text-to-speech, but I guess you would make an assumption like "no phoneme spans more than 6 characters". So you build your network with 6 inputs, and just repeat it for as long as the word is. You need some rule like "each network gives the pronunciation of the middle two characters" to handle overlaps, as well as some special handling for the beginning and end of words too.


Interactive programming language minimizing reevaluations I'm looking for any programming language, DSL, library or pattern for live scripting but minimizing the expressions reevaluation.

Topological sorting provides non-revaluation of expressions.

Memoization provides a simple way of not re-evaluating but is a waste of memory.

A form of topological ordering can be achieved by maintaining (in each language object) a version number for each dependency but it does not seem to be easily composable/scriptable.

Which available tools would be the most suitable?

Thank you!

(I think the closest I've found might be https://www.shinoe.org/cameleon)

The specific CS topic resolving the question is:
Incremental computing
A detailed article explaining a related DSL is:
IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs


Run Length Encoding Compression With Nested Level I am studying about some compression methods, and I'm very interested in RLE Algorithms. But are there any Nested-Level RLE methods, such as:

ABABABCABABABC --> 3(AB)C3AB(C) --> 2(3(AB)C) ?

It's easily to decompress it by using some techniques like stack, but what is the most efficient way to compress it, any formal algorithms or how to evaluate that?

Yes.  The Sequitur algorithm could be viewed as doing more or less what you've asked for.

For instance, Sequitur would encode abababcabababc to the grammar

S → WW
T → ab
U → TT
V → UT
W → Vc

You can think of this as having your form. V is basically an encoding of 3(ab).  W is basically an encoding of 3(ab)c.  WW is basically an encoding of 2(W).  So, the final grammar is equivalent to 2(3(ab)c) -- it is just a different way to write it.  Sequitur writes the output as a context-free grammar, instead of using your notation, but its grammar is equivalent to the answer you were hoping for.

Here is the sequence of steps that Sequitur would use to reach that result.

First, we have the grammar

S → abababcabababc

The first digram encountered is ab, so it replaces that with a non-terminal:

S → TTTTcTTTc
T → ab

Then this becomes

S → UTcUTc
T → ab
U → TT

and then to

S → VcVc
T → ab
U → TT
V → UT

and then to

S → WW
T → ab
U → TT
V → UT
W → Vc


How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form? I am trying to find the frame check sequence in cyclic redundancy check(CRC). Given that the generator polynomial is $\ g(x)= (x+1)(x^3 + x^2 + 1)$. Let's say the data sequence is $\ 10110001$.

In this case, $\ g(x) = x^4+x^3+x+x^3+x^2+1 $ after multiplying. But how do I handle 2 $\ x^3 $ terms? Is it okay to convert it into binary without worrying about it? For example, $\ 1 1111$ and continue with the division?

When computing CRC, we are working over the field of two elements. In this field, 2=0. Therefore
$$
(x+1)(x^3+x^2+1) = x^4+x^2+x+1.
$$


Are subsets of $PSPACE$ closed under common operations By "subsets of $PSPACE$" I am referring to classes like $SPACE(n^k)$ for some constant $k$ (e.g. $k = 42$).

Under the union, intersection, and concatenation operations, such subset is apparently closed.

For the Kleene star and polynomial-time reduction, I am not so sure. Here's what I have tried:

To show that $PSPACE$ is closed under Kleene star, assume that some $L \in PSPACE$. To decide whether some input $w \in L^*$, we can non-deterministically split the $w$ into $i$ chunks ($1 \leq i \leq n$, and $i$ is chosen non-deterministically), and check if each chunk is in $L$. If that check can be done in $O(n^k)$ space, this whole procedure can be done in $NSPACE(n^k) \subset SPACE(n^{2k}) \subset PSPACE$ (the first inclusion is by Savitch's theorem). In a similar manner, I tried to show that a subset like $SPACE(n^k)$ is NOT closed because $2k > k$.
To show that $PSPACE$ is closed under polynomial time reduction, suppose some $L_2 \in PSPACE$ and some $L_1 \leq_p L_2$. Since the reduction is in polynomial time, it uses at most polynomial space, so $L_1 \in PSPACE$. I tried to show that something like $SPACE(n^k)$ is NOT closed under polynomial time reduction by saying that the reduction might runs in $O(n^j)$ time and $j > k$, then the whole process will use at most $O(n^j)$ space, which is no longer in $SPACE(n^k)$.

My doubts:

For the Kleene star closure proof, we can't guarantee that deciding $L^*$ will necessarily use $O(n^{2k})$ space, since we don't have $NSPACE(n^k) = SPACE(n^{2k})$.
For the polynomial time reduction closure proof, such a $O(n^j)$ space reduction exists, but it might not actually uses more than $O(n^k)$ space.

I can't really convince myself one way or the other, so any help is appreciated.

$SPACE(n^k)$ is closed under Kleene star. Just enumerating all possible partition (which can be done in linear space, or at most quadratic or $nlogn$ space), then decide each partition using the $n^k$-space machine.

This class is not closed under poly-time reduction. Prove by padding technique. This part would be found here at CS.SE or CSTheory.SE


Can you have three consecutive black nodes in red-black search tree? Suppose I am making a red-black search tree, and in my right subtree, I have a black node, then a red node, and it has two black children, the black children further black childrens. As such a lemma has been made that red-black trees with $n$ internal nodes have height at most $2\log(n+1)$, would this proof still hold for such a black tree?

In fact, a red-black tree can have all black nodes. In that case the tree is completely balanced and has the required bound.


Regular Expression to Context-Free Grammar Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?

I assume you want to get a grammar that generates the same language as the given regular expression.

You can achieve that by the following steps:

Translate the regular expression into an NFA.
Translate the NFA into a (right-)regular grammar.

Both translations are standard and covered in basic textbooks on formal languages and automata. Note that any regular grammar is also context-free.


What does the actual parameter A[i] refer to in this example of call by value-result? From Programming Languages: Principles and Paradigms, by Maurizio Gabbrielli, Simone Martini

void fiefoo (valueresult int x, valueresult int y) {
x = x+1;
y = 1;
}
...
int i = 1;
int[] A = new int[5];
A[1]=4;
fiefoo(i,A[i]);

  we are to execute fiefoo with parameters passed by value-result. On
  termination, we will have A[1] with value 1 and i with value
  2, while the rest of the array A has not been touched.

Why is it A[1] instead of A[2] whose value is 1?

My thought is that when returning from the function fiefoo, x's value 2 is assigned to i, so A[i] is evaluated to be A[2], and y's value 1 is assigned to A[i].

My thought is according to what the book says

  It should be clear that, as in call by value, the following questions
  about evaluation order in call by return must be answered. If
  there is more than one result parameter, in which order (for example,
  from left to right) should the corresponding “backward assignment”
  from the actual to formal be performed?

  Finally, when is the actual parameter’s l-value determined? It is
  reasonable to determine it both when the function is called and when
  it terminates. We can construct an example which gives different
  results if the l-value of the actual is determined at call time or
  when the procedure terminates.

Thanks.

This example is to get readers to think about the consequences of how A[i] is resolved in a call by value-result setting- should it be before or after the function call to fiefoo?

The example assumes that A[i] is resolved before the call, and hence i and A[1] are assigned values 1 and 2 respectively. It has the nice property that fiefoo can only modify those variables.

On the other hand, you can imagine a programming language designer who chooses to resolve the value of A[i] after fiefoo returns, but there's two possible outcomes depending on the order in which the value-results are assigned: 1) A[old i] = y, i = x; and 2) i = x, A[updated i]. Case #2 being what you proposed.

When the designer is faced with these design decisions, she would likely opt to resolve before the call to fiefoo to avoid the possible ambiguity associated with resolving after the call to fiefoo.


How to represent bottom element (integer domains) in SMT formula I'm doing some work with static analysis and need to represent local variables as SMT formulas.  In general this is fairly straight forward, depending on the domain of the static analysis.  However, my question lies when needing to represent impossible or infeasible values, e.g., divide by zero paths from the static analysis under an integer domain.  This is often referred to as the bottom element, ⊥.
I'm struggling to develop a formula which can represent these "impossible"  (integer) values.  Is there a way to do this?
I've been thinking along the lines as an impossible inequality, but I've been unsuccessful thus far.  Similarly, I've thought about attempting to represent using divide by zero within an SMT formula, such as the following Z3/SMT formula:
(declare-const a Int)
(assert (= (/ a 0.0) 1.0))
(assert (= (/ a 0.0) 2.0))
(check-sat)

However, given the application, I'm not sure this is going to be helpful.
Application: I'm using this to compare results between two different static analyses between different domains.
tl;dr:
How to represent infeasible, bottom integer elements as SMT formula?
Edit
I didn't try this enough, maybe the question is more along the lines of "is there a more eloquent way to model a bottom value besides the following?":
(declare-const a Int)
(assert (and (>= a 0) (< a 0)))
(check-sat)

The above will yield unsat, as expected.  And since I'm trying to compare results of different static analyses, I can formulate questions about locals as such (is a top value equal to a bottom value):
(declare-const a Int)
(declare-const b Int)
(assert (= (and (>= a 0) (< a 0))
           (or (>= b 0) (< b 0))))

(check-sat)

This will also yield unsat.

First, you need to figure out the semantics of your language: does divide-by-zero cause the program to abort/halt/throw an exception, or does execution proceed and the divide-by-zero returns a NaN?
If it causes the program to halt, then you should not try to represent $\bot$ values.  Instead, treat division as a conditional statement, that first tests whether the divisor is zero, and if so, aborts/halts/etc.
If it returns a NaN, then one approach is to introduce an extra boolean variable associated with each program variable.  This boolean indicates whether the corresponding program variable holds a NaN.  You should be able to work out the appropriate constraints to ensure these boolean variables receive the appropriate values.


Mathmatical way to represent an image kernel? How to represent the calculation in this image mathematically?

For example: With the discrete convolution
$(f * g)[n]\ \stackrel{\mathrm{}}{=}\ \sum_{m=-\infty}^\infty f[m]\, g[n - m]$
and Fourier transform.

Applying the filter corresponds to two-dimensional convolution:
$$
(f \ast g)(x,y) = \sum_{i=-\infty}^\infty \sum_{j=-\infty}^\infty f(i,j) g(x-i,y-j).
$$
In our case, $f$ is the filter, $g$ is the image, and $f \ast g$ is the filtered image. Since the support of $f$ (the number of non-zero entries) is finite, the sums in question are finite, and the convolution is well-defined. More explicitly, we have $f(0,0) = 5$, $f(-1,0) = f(1,0) = f(0,-1) = f(0,1) = -1$, and $f(i,j) = 0$ otherwise.

Edit 1: Here is another way of viewing it. This time, $f$ is the image and $g$ is the filter, defined by $g(0,0) = 5$, $g(-1,0) = g(1,0) = g(0,-1) = g(0,1) = -1$, and $g(i,j) = 0$. The same formula for filtering, $f \ast g$, works before, since $f \ast g = g \ast f$. In other words, the filtered image $h$ is given by the formula
$$ h(x,y) = \sum_{i=-\infty}^\infty \sum_{j=-\infty}^\infty g(i,j) f(x-i,y-j). $$

Edit 2: We can rewrite the convolution as a product of generating functions. Suppose the original image is given by
$$ F = \sum_x \sum_y f(x,y) X^x Y^y. $$
The filter $G$ in your case is given by
$$ G = 5 - X - X^{-1} - Y - Y^{-1}. $$
Filtering the image corresponds to the multiplication $H = FG$, and the filtered image $h$ can be extracted as
$$ H = \sum_x \sum_y h(x,y) X^x Y^y. $$

Edit 3: Going back to the notation of Edit 1, in terms of the two-dimensional Fourier transform, we have
$$ \hat{h} = \hat{f} \hat{g}, $$
where the multiplication on the right is pointwise. So filtering corresponds to multiplying each Fourier coefficient by some fixed amount, which depends on the filter.

Edit 4: In this particular case, the relation between the original image $f$ and the filtered image $h$ is
$$ h(x,y) = 5f(x,y) - f(x-1,y) - f(x+1,y) - f(x,y-1) - f(x,y+1). $$

Edit 5: The image you posted handles the boundary issue by extending the first and last rows and columns past the boundary. For example, $f(x,-1) = f(x,0)$, $f(-1,y) = f(0,y)$ and $f(-1,-1) = f(0,0)$.


SVMs - Fat (Margin) Boundary: Why is $\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$? I am trying to understand SVMs in depth watching lectures from MIT.
The professor to reduces the classification problem into an optimization problem. To do that, he first defines the decision and margin boundaries as following:

Note that $\frac1{||\theta||}$ is the distance between the margin boundaries and the decision boundary ($\gamma_i$ is just the signed distance, but we don't care for this question).
We then proceeds to note that our goal is:

To maximize $\frac1{||\theta||}$
while minimizing the Hinge Loss

Now, it is apparent that these two terms will co-exist in the objective function we are trying to form $(1)$.
The Objective Function
$$\text{minimize } J(\theta,\theta_0) = \frac1n \sum_1^n \text{HingeLoss}(\theta,\theta_0) + \frac{\lambda}{2} ||\theta||^2 \quad (1) $$
Given the fact that he wants to create a minimization problem he describes the maximization of the distance to be equal to the minimization of it's inverse squared divided by 2, i.e:
$$\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$$
This does not make sense, as far as I can understand. In my mind this is the correct way of doing it:
$$\max\frac1{||\theta||}=\min||\theta||$$
Why did he insert a square and a division into the equation?

Minimizing $\|\theta\|$ is equivalent to minimizing $\|\theta\|^2/2$, in the sense that the minimum is achieved for the same value of $\theta$.  Since our goal is primarily to find $\theta$, this substitution is not unreasonable.
Why was the substitution done?  I don't know.  Perhaps because it makes the resulting optimization easier; or just because it seemed simpler.  Note that while $\|\theta\|$ might look "simpler", in some sense it is an uglier function, as it involves a square root, which can be messy to deal with.  The way to figure out would be to understand the basic derivation using $\|\theta\|^2/2$, and then try replacing with $\|\theta\|$ and see if the same logic goes through or if there is a barrier.


Algorithm for fewest moves in 1's, 10's, 100's, etc I'm building a math application (not homework) and I want to build a component that allows players to drag-and-drop 1's, 10's, 100's, etc to complete problems and a bonus reward if they do it in the fewest moves possible--How can I calculate this? e.g.

50 + X = 96

where X is a randomly generated integer and the player is modifying X during play. So, the player needs to make X=46, but starts at 121. For example,

if X is initially 121, and player needs to get to 46

player thinks, "cool, i'll just subtract 75"

remove 7x 10's, remove 5x 1's - 12 moves

but it turns out, there's a faster way to do it:

remove 1x 100's, add 2x 10's, add 5x 1's - 8 moves

Is there an existing algorithm for this? It would be helpful to calculate this for anything up to 10,000 where I can calculate the minimum number of moves required.

You can construct a graph with vertices $0,1,2,3,4,\dots,10000$, two vertices are adjacent if you can construct a number with a single operation from another one. A single operation is either adding or subtracting $1,10,100,1000,\dots$. For example,$N(46) = \{45, 47, 36, 56, 146, 1046,\dots\}$. Then the minimum number of operations required to construct a number $x$ is the shortest path from $x$ to 0. Since graph is undirected, you can run a single one to all algorithm (Dijkstra,BFS) and obtain all distances from 0 to any other vertex. Also the graph is pretty sparse, hence Dijsktra with heap will nail it. An implementation might no need to construct the whole graph, since neighborhoods are small and easily computable on the fly.

EDIT:
if you take Dijkstra code from Geeks, you can construct graph as

for(int v1 = 0; v1 < V; ++v1)
   for(int v2 = v1+1; v2 < V; ++v2)
      if(v2 - v1 == 1 || v2 - v1 == 10 || v2 - v1 == 100)
         g.addEdge(v1,v2,1);
 g.shortestPath(46); // gives 8 to 121


Is the time complexity of the Fibonacci sequence O(fib(n))? I started watching SICP lectures and am totally new to computer science.
SICP. LEC 1B: Procedures and Processes; Substitution Model
I don't know why the time complexity of the Fibonacci sequence is O(Fib(n)).
So, I googled about it,
he says

There's a thing that grows exactly at Fibonacci numbers. It's a horrible thing. You wouldn't want to do it. The reason why the time has to grow that way is because we're presuming in the model-- the substitution model that I gave you, which I'm not doing formally here, I sort of now spit it out in a simple way-- but presuming that everything is done sequentially. That every one of these nodes in this tree has to be examined. And so since the number of nodes in this tree grows exponentially because I add a proportion of the existing nodes to the nodes I already have to add one, then I know I've got an exponential explosion here.

Can anybody please explain what he's saying?

$\DeclareMathOperator{\fib}{fib}$If you choose to calculate $\fib(n)$ by using the naive recursion
formula, then you need $\Theta (\fib(n))$ additions, and since the
numbers involved grow to $c\cdot n$ bits for a not very large constant
$c$, it will take $\Theta(n \cdot \fib(n))$ operations.  (I may be wrong
here because most of the numbers involved may be much smaller than $c
\cdot n$ bits).
If you are reasonably clever and calculate
$$\fib(0), \fib(1), \fib(2), \dots, \fib(n),$$
then you have $n$ additions of $c \cdot n$ bit numbers, which takes
$\Theta(n^2))$ operations.
You can use matrix exponentiation to calculate $\fib(n)$ faster for
large $n$, I'd estimate something like $M(n)$ where $M(n)$ is the time
for an $n$-bit multiplication.
Most important is that for maybe $n = 100$ or $n = 200$, your computer
has not a chance to calculate $\fib(n)$ using the naive recursive
algorithm within your lifetime, while the simple method of calculating
consecutive values will find the same result within microseconds on a
newish smartphone.


How do solve assignment of one interval to another? Is there an efficient algorithm for the following problem?

Input:  Set of holes and pegs.  Each hole/peg is an interval $[\ell,u]$ with integer endpoints.

Question:  Can all the holes be filled using the pegs given, satisfying the following conditions?

Each peg is assigned to at most one hole.
No hole is assigned more than one peg.
If peg $p$ is assigned to hole $h$, then the interval $p$ must be contained in the interval $h$.

Here's a picture to help clarify:

My algorithm: For each hole, check if any peg can be assigned to this hole.

Issues: Unfortunately, this doesn't work.  See Scenario 3 in the picture above: my algorithm assigns the same peg ($[1,2]$) to multiple holes ($[1,2]$ and $[1,3]$), which is not legal.

My second attempt: I tried to construct an algorithm that marks a peg as unavailable it is used.

Let available_pegs = all input pegs
For each hole, check if any peg from available_pegs can be assigned to this hole.
If a peg is found, remove it from available_pegs and assign it to that hole.

Issues:  Unfortunately, this doesn't work either. It can fail in Scenario 2: if I assigned peg $[1,2]$ to hole $[1,3]$, peg $[1,2]$ will be marked unavailable and now there is now way to fill the hole $[1,2]$.  Thus in this example the algorithm would say that there are not enough pegs to assign to all the holes, which is wrong.

This is an instance of bipartite matching (i.e., the assignment problem with no costs).  It can be solved by standard methods, such as network flow algorithms (e.g., Ford-Fulkerson), the Hopcroft-Karp algorithm, or using linear programming.  See also https://cs.stackexchange.com/a/61264/755.

In particular, you can build a bipartite graph, with one "left vertex" per peg, and one "right vertex" per hole, and an edge from peg $p$ to hole $h$ if the interval $p$ is contained in the interval $h$.  Compute the maximum cardinality matching for this bipartite graph.  If this matching covers every hole, then  the answer to your problem is "yes", otherwise the answer is "no".


what will be space complexity for snippet for(i=1 to n) int x=10;? The space complexity of the code snippet given below:
int *a = malloc(n * sizeof(int));
int sum=0;
for (i = 0; i < n; i++)
{
    scanf("%d", &a[i]);
    for (j = 0; j < n; j++)
    {
        int x = a[i];
        sum = sum + x;
    }
}
free(a);

This is question of a test.
I answered it $O(n)$, considering space only for array and constant space for rest of the code.
But in the answer they given $O(n^2)$ and there explanation is "The array is of size $n$ and the inner most loop we are declaring a variable $x$ every time the loop is executed, this loop is executed $O(n^2)$ time hence overall space complexity is $O(n^2)$."
Now my doubt is what should be space complexity of
for (i = 1; i <= n; i++)
    int x = 10;

What i thought is that it should be $O(1)$ because in each iteration variable $x$ gets destroyed.

You are right. Are they saying if we run that loop n times then n different variables having name x will be created? This doesn't happen. Moreover, it is good practice to avoid unnecessary global variables. To check this yourself, you can try printing the logical address of x using this:-
for(i=0;i<10;i++)
   {
       int x=1;
       printf("%d\n",&x);
   }

The same logical address gets printed every time. So yes, the total space used by this is not dependent on n. It is O(1).
By the way, You could have thought that x gets destroyed only once at the end of last iteration and meanwhile all the values a[i] would be getting overwritten on the same x in each iteration. Even this is not what happens. x gets destroyed after each iteration and the space is made available for use by other parts.


Finding the number of distinct strings in regular expression Given the regular expression $(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )(1 + \varepsilon + 0 )$, how many distinct strings are in the language? How do you determine this from looking at the regular expression? Do I have to generate a table of all possible combinations or is there a more straightforward way?

In your example, think of the result as having filled four slots: _ _ _ _, each of which can take one or three substrings, namely 0, 1, or the empty string. Ignoring the empty strings, it's clear that there are sixteen possible results: 0000, 0001, 0010, ... , 1111.

With the empty strings, though, since we could make 10 by $(\epsilon)(\epsilon)(1)(0)$, or by $(\epsilon)(1)(\epsilon)(0)$, or four other arrangements. What now? Well, if we realize that the six possibilities we just had all correspond to the string 10, we've got it: we'll have all strings over $\{0,1\}$ of length zero, one, two, three, and four, namely

$\epsilon$ (1 of them)

$0, 1$ (2 of these)

$00, 01, 10, 11$ (4)

$000, 001, 010, \dots, 111$ (8)

$0000, 0001, 0010, \dots 1111$ (16)

For a total of $1+2+4+8+16=31 = 2^5-1$. This is a particularly nice example; in general it'll be far more complicated, like, say the the expression $(1  + 01)1(1(0+\epsilon) + (101(10+101)))$. Sad to say, there's no simple rule governing all cases.

By the way, welcome to the site!


How can an LBA check legality of TM transitions without extra memory? In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A_$_{\text{TM}}$.

The reduction is proposed in the following manner:
we receive a TM $M$ and a word $w$, and build an LBA $B$ that accepts if is fed an accepting computation history of $M$ on $w$.

At page 224, it describes how $B$ checks that the configuration $C_{i+1}$ is legal for M on $w$ at the step $i+1$, and states "then $B$ verifies that the updating was done properly by zig-zagging between corresponding positions of $C_i$ and $C_{i+1}$. To keep track of the current positions while zig-zagging, $B$ marks the current position with dots on the tape."

How can we know that $B$ does not need additional memory to check for legality of configuration change from $i$ to $i+1$? $B$ is an LBA, that says it has only the memory it got with initialisation and cannot go beyond it on the tape, so if it needs additional memory it has a problem.

B is given the complete computation history as input. All it does on that input, according to the description, is moving around, reading, marking, and unmarking things. Moving around and reading obviously don't need extra space, and marking/unmarking can be done in-place as well. (For each letter of M's alphabet B's alphabet can contain a marked copy, so that marking just means replacing the unmarked symbol with the marked one.) Thus, all is well.


How to treat ϵ-productions in table-driven predictive parsing? Here:
https://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html
in chapter Driver Procedure, it's shown how table-drive predictive parsing works.

The predict table however can involve $\epsilon$-productions (which leads to including a production in the symbols of $FOLLOW(w)$, where $w$ is a non-terminal/row, in addition to $FIRST(w)$) and I cannot find how these should be treated. I.e. how should the parser decide whether it predicts for an $\epsilon$-production or non- $\epsilon$-production. I.e. e.g. how should the end of the string be handled by the Driver.

Case example:

Such production involving the $\epsilon$ could be e.g.

$$A \rightarrow \text{B | c | $\epsilon$}$$ where c is a terminal and B is a non-terminal.

The remaining input could be "". So how should the driver decide to match with the $\epsilon$ and not e.g. something that the non-terminal $B$ leads to.

A guess would be that it tries all of the symbols between the $|$s but fails in other than the $\epsilon$.

It will predict $A\rightarrow B$ if the look-ahead is in $FIRST(B)$, it will predict $A\rightarrow c$ if the look-ahead is $c$, it will predict $A\rightarrow\epsilon$ is the look-ahead is in $FOLLOW(A)$.

If the prediction is ambiguous, the construction of the tables should either have failed or used another way to resolve the conflict (for instance you could get a generator which allow ambiguity in the productions and resolve them using precedence -- using associativity to solve conflicts in a predictive parser is harder).


What practical/efficient algorithms exist for minimum weighted set cover problem (MIN-WSCP)? For TSP there are well known heuristic and approximation solutions which run in low-polynomial time, like Christofides / 2-OPT and so on.

I need a practical, fast algorithm, ideally sub-quadratic complexity, to solve the minimum weighted set cover problem (which is NP hard). It solves subproblems in a genetic algorithm so needs to be fast rather than optimal. Are there any standard algorithms used to solve this?

One possibility is to use the standard greedy algorithm.  It can be adapted to weighted set cover by counting the total weight of previously uncovered elements that will be covered by adding a particular set, instead of counting the number of such elements.  This is standard and covered in standard textbooks and resources.  Another option is to use linear programming or integer linear programming.  A little research on set cover approximation algorithms will find much more that is written on the subject.  In the future, I suggest doing more research before asking here.


Is that true that A is decidable if A$\le_m$A complement? A is decidable if A$\le_m$A complement

Can i think that it is true because decidable is close under complement, so if A complement is decidable, so is A

If co-$A$ is decidable then so is $A$, as you mention in your question.

However the mere fact that $A \le_m$ co-$A$ does not imply the dependability of $A$. See this answer.


4 Neurons to Decide 10 Digits I am trying to solve this algorithm exercises (http://neuralnetworksanddeeplearning.com/chap1.html#exercise_513527) in Michael Nielson's online book: Neural Networks and Deep Learning (http://neuralnetworksanddeeplearning.com/chap1.html#complete_zero).

In another word, he says that there is a way to use four neurons to decide 10 digits on top of of the last hidden layer (which consists of 10 neurons and decides 10 digits separately with a high correct rate).

However I couldn't figure out the way. Do you have any idea about this? I look forward to your idea. Any help is appreciated.

You could use 4 neurons to produce a 4-bit output, which then represents the digit in binary.  A digit in the range 0-9 can be expressed in binary as a 4-bit number.

However, classification accuracy might potentially be worse than the standard method of 10 output neurons with a softmax layer.


Matrix Multiplication Algorithms for Non-Square Matrices I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such algorithms except for a couple of extremely general pieces of pseudocode that I found on Wikipedia and MIT OCW.

If anyone could pass on some links to papers that discuss these algorithms in greater detail, I would greatly appreciate it! Thanks!

There is an algorithm due to Coppersmith (later improved by him) that can multiply an $N \times N^\alpha$ matrix by an $N^\alpha \times N$ matrix in time $\tilde{O}(N^2)$ for some $\alpha > 0$. The state of the art in this regard is a paper by Le Gall achieving a better $\alpha$, though his algorithm is much more complicated than Coppersmith's. Both algorithms are probably impractical. Ryan Williams (Appendix C) explains how to implement Coppersmith's algorithm, which a priori is non-uniform, in the context of a circuit lower bound; later it was shown that Coppersmith's algorithm can be replaced by other ingredients.


Asymptotic growth rate of $f(n)$ and $f(n+1)$ Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be a continuous positive function, where $f(n)$ is integer for each integer $n$. Prove or disprove whether the following always holds:

$\qquad f(n+1) = \Theta(f(n))$

Imagine any continuous, monotonically non-decreasing function $f$ such that $f(n) = n!$ for all non-negative integers $n$. Then $f(n+1) = (n+1)! = (n+1)n! = (n+1)f(n)$. Since there is no constant $c$ such that $n+1<c$, it follows that it is not true that $f(n+1) = \Theta(f(n))$. QED.


Find the central point in a metric-space point set, in less than $O(n^2)$? I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I define as the point with the minimum sum of distances to all other points. The metric computation is slow, so needs to be avoided where possible.

The obvious way to find this point uses $n^2$ metric distance calculations, as it simply (a) calculates for each point the sum of distances to all other points and then (b) takes the minimum point.

Is there a way to do this in less than $O(n^2)$ distance comparisons? (Probably making use of the triangle inequality in some way, which should hold with my metric.)

A good approximation might suffice if an exact method doesn't exist.

No.  You can't do better than $\Theta(n^2)$ in the worst case.

Consider an arrangement of points where every pair of points are at distance $1$ from each other.  (This is a possible configuration.)  Then you can't do better than to examine every edge.  In particular, if there is any edge you have not examined, then an adversary could choose the length of that edge to be either $0.9$, $1.0$, or $1.1$; all of those choices are consistent with all of the other observations you've made and with the requirements of a metric (e.g., with the triangle inequality), so all three are possible; but they require different outputs.  Thus, if your algorithm doesn't examine that edge and then outputs something, an adversary can always choose a length for the unexamined edge that will make your algorithm's output wrong.

However, if you know that all the points live in $\mathbb{R}^d$ (even though you are not given their coordinates), then the problem can be solved by  measuring $O((d+1)n)$ distances, assuming no degeneracies (no subset of $d+1$ points are co-planar).

In particular, pick $d+1$ points randomly.  These will be anchor points.  Given their pairwise distances, you can compute coordinates for them that are consistent with their pairwise distances.  Now, for every other point $P$, compute the distance from $P$ to each of the anchor points.  Using triangulation and these distances, you can compute the location of $P$ relative to the anchor points and thus the coordinates for $P$.  Do this for every non-anchor point $P$.  Now you have coordinates for every point, and you can use those coordinates to find the central point without asking the oracle to give you any more pairwise distances.  I don't know whether this last step can be done faster than $O(n^2)$ time, but it can be done without measuring any more pairwise distances.


Doubt regarding Cantor's diagonalization argument So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider.

I understand the overall argument but have a problem regarding one caveat mentioned in my book.

My book says that some real numbers like 2.000... and 1.999... have different decimal representations but are actually the same real numbers. Suppose we have a bijection $ f: N \rightarrow R$ where $N$ and $R$ are the sets of natural and real numbers respectively. Now, suppose $f(1) = 1.999...$ and no $x \in N$ exists such that $f(x) = 2.000...$. In such a scenario it is possible that the diagonalization argument ends up constructing the real number $2.000...$ which is already in our list since $1.999...$ and $2.000...$ are the same real numbers. To get around this problem, we never select 0 or 9 when constructing our number.

I don't understand two things. First, why do $1.999...$ and $2.000...$ represent the same real number? Second, how never selecting 0 or 9 solves the problem this poses?

There are several issues with your question but perhaps I can clarify some issues.

First off you assume $f(1) = 1.999...$ and also that no $x \in \mathbb{N}$ exists such that $f(x) = 2$ but that's a contradiction in terms because $1.999... = 2$ and thus $f(1) = 2$.

Why does $1.999... = 2$? Well there's an easy answer but not fulfilling answer and a more complicated answer that I find satisfactory. The easy answer is that $1 = \sum_{i=1}^{\infty}9*10^{-i}$ (the general form $(N - 1)*N^{-i}$ holds for all $N$) and $0.99...$ is definitionally $\sum_{i=1}^{\infty}9*10^{-i}$

A more satisfactory answer comes from understanding the representation of real numbers as you would in an analysis class and understanding when we define two real numbers to be equal. There are many different representations and I'll get details wrong here if I try and give you a precise example but the basic idea of most representations is to represent a real number as a sequence (sometimes its not a sequence but generally) of finite (generally rational) approximations. So $[1/1, 1/1, ...]$ is a real number representing 1.0 and $A = [9/10, 99/100, 999/1000, ...]$ is another that as we shale see is equivlent. Notice that the terms in that are the finite sums of $\sum_{i=1}^{\infty}9*10^{-i}$. We define the summation to be the sequence of its finite summations. If the sum converges then this defines a valid real number. Why does $[2/1, 2/1, ...] = [19/10, 199/100, ...]$? Because for any $\epsilon > 0$ I choose you can find an $N$ such that the difference of the $N$th elements of each sequences is within $[-\epsilon, \epsilon]$ or in a nutshell, the approximations become arbitrarily close. Take this paragraph with a grain of salt though, I'm being handy wavy and imprecise.

The traditional proof of cantor's argument that there are more reals than naturals uses the decimal expansions of the real numbers. As we've seen a real number can have more than one decimal expansion. So when converting a bijection from the naturals to the reals into a list of decimal expansions we need to choose a canonical choice. The axiom of choice just lets us do this for free but it sounds like your book tried to do something different. It isn't clear to me what your book did exactly from your description. Here's a potential way but it relies on further knowledge of reals and decimal expansions.

Take for granted that only the rationals with terminating decimal expansions (e.g. not 1/7 or 1/3 but 1/2 = 0.5 and 1/8 = 0.125 etc.. are valid) have two representations. Then its clear that every real number has exactly one non-terminating representation. So for our decimal expansions if we restrict ourselves to the non-terminating expansions we have no ambiguity.


Euclid's Algorithm Time Complexity I have a question about the Euclid's Algorithm for finding greatest common divisors.

gcd(p,q) where p > q and q is a n-bit integer.

I'm trying to follow a time complexity analysis on the algorithm (input is n-bits as above)

gcd(p,q)
    if (p == q)
       return q
    if (p < q)
       gcd(q,p)
    while (q != 0)
       temp = p % q
       p = q
       q = temp
    return p

I already understand that the sum of the two numbers, u + v where u and v stand for initial values of p and q , reduces by a factor of at least 1/2.

Now let m be the number of iterations for this algorithm.
We want to find the smallest integer m such that (1/2)^m(u + v) <= 1

Here is my question.
I get that sum of the two numbers at each iteration is upper-bounded by (1/2)^m(p + q). But I don't really see why the max m is reached when this quantity is <= 1.

The answer is O(n) for n-bits q, but this is where I'm getting stuck.

Please help!!

Here is the idea of the proof. Throughout, we assume that $p \geq q$.

Let $p^{(t)},q^{(t)}$ be the values of $p,q$ after $t$ iterations, so that $p^{(0)}=p$ and $q^{(0)}=q$.

Let $F_m$ be the $m$th Fibonacci number, which satisfies $F_m = \Theta(\varphi^m)$, where $\varphi = \frac{1+\sqrt{5}}{2} > 1$. Suppose that $p \leq F_m$. If $q \leq F_{m-1}$ then $p^{(1)} = q \leq F_{m-1}$. If $q \geq F_{m-1}$ then $q^{(1)} = p \bmod q \leq F_{m-2}$, and so $p^{(2)} = q^{(1)} \leq F_{m-2}$.

This argument shows that if $p \leq F_m$ then after at most (roughly) $m$ steps, the algorithm will terminate (since we cannot have $p \leq F_0 = 0$). Since $F_m$ grows exponentially, it's not hard to check that $p \leq F_{O(n)}$, where $n$ is now the length of $p$ in bits. Therefore the algorithm terminates in $O(n)$ steps.

If you want a bound depending on $\min(p,q)$ rather than on $\max(p,q)$, simply notice that $p^{(1)} = q$, and run the above analysis on $p^{(1)}$.


Two definitions of Safe Edge I ran into an interview two days ago and came across one strange definition of safe edge.
We are given an undirected weighted Graph $G = (V,E)$ with all distinct edge weights. Assume that the graph is connected.

Safe Edge Definition: if an edge $e \in E$ is not contained in any cycle, we called it a safe edge

Following is a theorem based on the above definition.

Theorem: All the safe edges must be in Minimum Spanning Tree (MST).

Please compare the definition of a "safe edge" on this interview with the classical definition of safe edge at all courses like here: MAIN SAFE EDGE THEOREM.

They are two different definitions.
The interview definition calls a safe edge one that is not part of any cycle and therefore cannot be removed from $G$ without disconnecting it, thus changing the resulting MST.
Notice that this definition depends solely on the chosen edge and on $G$. Notice also that it does not depend on the edge weights in any way.
The definition in the notes defines a safe edge $e$ as one that can safely be added to a subgraph $A$ of $G$ so that $A + e$ is a partial MST of $G$.
In this case $A$ is probably thought to already be a partial MST of $G$, since otherwise no edge would be safe, although this is not formally required.
Notice that this definition depends on the particular choice of $A$ and on the edge weights of $G$.
As an example, let $G$ be a cycle on $n$ nodes, where the $n$ edges have weights $1, \dots, n$. None of these edges is safe according to the interview definition.
If $A$ is the empty graph then all edges except for the one of weight $n$ are safe w.r.t. the definition in the notes.
If $A$ is the subgraph containing the edge of weight $n$ then no edge is safe w.r.t. the definition in the notes.


Can the following conditions hold all together? Let $L_1, L_2$ be languages.

Can the following conditions hold:

$L_1,L_2\notin RE$.
$L_1\cap L_2\in R$
$L_1\cup L_2\in R$
$\overline{L}_1, \overline{L}_2 \in RE / R$

I believe the above cannot hold at the same time. I thought since $L_1\cap L_2\in R$ and $L_1\cup L_2\in R$ then $\overline{L}_1\cup \overline{L}_2\in R$ and $\overline{L}_1\cap \overline{L}_2\in R$. Then I know that $L_2 \ L_1 = L_2 \cap \overline{L_1}$. And now I want to somehow use condition 4 to reach a contradiction, but I don't see how...

Or perhaps I'm wrong and they can hold together?

Conditions $2,3,4$ imply $L_1 \in RE$, contradicting $1$.

Here's how to semi-decide $L_1$. Take a candidate $x$.
If $x \in L_1 \cap L_2$ (decidable by $2$), accept.
If $x \notin L_1 \cup L_2$ (decidable by $3$), diverge (we know $x \notin L_1$ for sure).

We now know that
$$x \in (L_1\setminus L_2) \cup (L_2\setminus L_1) \qquad (*)$$

Exploiting $4$, we run semi-deciders for $\overline{L_1}, \overline{L_2}$ on $x$ in parallel. By $(*)$, (exactly) one of these must eventually halt.

If the former halts, we infer $x \notin L_1$, so we diverge.
If the second one halts, we infer $x \notin L_2$, and by $(*)$ we obtain $x\in L_1$, so we accept.


What Good Is Kolmogorov Complexity Since It Is Relative? Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a constant that depends on the choice of that pair. They can't disagree too much because one can always switch over to emulating the other. However, this amount of maximum disagreement can be arbitrarily large.

Given that, of what use is Kolmogorov complexity? I suppose if you have a sequence of bitstrings, then you can talk about the asymptotic growth of the complexity of these bitstrings, and you will know that this is independent of choice of UTM.

But I thought that Kolmogorov was supposed to be meaningful for individual finite strings. But every bitstring can be produced by an arbitrarily small program: imagine a language that functions just like Java but where an empty file produces the bitstring under consideration.

Doesn't this relativity make Kolmogorov complexity basically pointless? I must be mistaken, right?

The relativity is up to an additive constant. Suppose that you express Kolmogorov complexity relative to your favourite universal Turing machine $U$, but I do it relative to my favourite UTM $V$. If the shortest program for $V$ that outputs a string $x$ is $M$, then the shortest program for your machine $U$ can't be any longer than the one that simulates $V$ running $M$, and that has length $|M|+k$, where $k$ is the size of the simulator.

So, yes, you could pick a UTM that has a very efficient coding for some finite set of strings. However, that would increase the length of the coding of at least that the same number of other strings, and we're typically interested in the asymptotic behaviour of infinite families of strings, rather than individual strings.


does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence? let S be the set of all programs that take a natural number as input and return another natural as output. let M be the set of all programs that take a natural number as input and return true or false. In both cases for a program to be in S or M it must halt.

Consider programs P in S, I will say the integer n is "in" P if there is some integer m such that P(m)=n

Consider a program P in M, I will say the integer n is "in" P if P(n)=true

Consider 2 programs P1 in S and P2 in M. I will say P1 and P2 are equivalent if for each integer n in P1, n is also in P2 and for each integer n in P2, n is also in P1.

I believe I have managed to prove the following:
There doesn't exist a program P such that P takes as input a program in S and returns an equivalent program in M.

However what I'd actually like to know is if for each program in S there is an equivalent program in M.

I figure this question can be answered in one of two ways. An explicit function in S could be given such that it has no equivalent function in M (this would require a proof that there is no equivalent function in M). Or it must be proven that for each program in S there is an equivalent program in M.

If there is another way to resolve this question other than one of the two ways I mentioned above I'd be interested to hear it. Also if you feel that simply proving there is no function P such that P takes inputs from S and returns equivalent programs in M is sufficient, please give an argument as to why this is.

I have chosen not to include the proof I mentioned above as its not strictly essential to the question however you think it would be relavent let me know and I can include it.

If any clarifications need to be made let me know.

Also please note that I might have gotten the tags wrong, I'm fairly new to the CS stack exchange, if I should change them let me know.

Thanks

Let us denote by $L_S(P)$ the set of numbers in $P$ for $P \in S$, and similarly by $L_M(P)$ the set of numbers in $P$ for $P \in M$.

Consider the following program $P \in S$. It interprets as input as a pair of integers $(x,y)$, runs the $x$'th Turing machine on the empty input for $y$ steps, returns $x$ if the machine halts, and returns some fixed $C$ if $x$ doesn't halt, where $C$ is the index of a halting Turing machine. Thus $L_S(P)$ is the set of indices of Turing machines which halt on the empty input. It is well-known that this language cannot be computed by an $M$-program, that is, $L_S(P) \neq L_M(Q)$ for all $Q \in M$.

More generally, a non-empty language is of the form $L_S(P)$ iff it is r.e., whereas a language is of the form $L_M(Q)$ iff it is recursive.


Depth of a leaf in a prefix tree (Huffman Coding) So, regarding Huffman Coding we know that the optimal way of "storing" it is using a full binary tree (where all nodes have either 0 or 2 children). All leaves are the symbols $i$ of the alphabet we want to encode (all $i$ have a frequency of appearance$f_i$) and if we consider the freq. $f_i$ of each leaf (freq. of that character) then the freq. of a node is the sum of the frequencies of its children, therefore the root has $f_i = 100$ or $f_i = 1$.

Visual example (taken from Introduction to Algorithms) because I'm not really good at explaining this stuff:

Now I want to prove that the depth of a leaf (a character) in this prefix tree is $O(\log_{2}{(1/f_I))}$, where $f_i$ is the freq. of the character $i$.

I've tried by induction, where the base case would be for $\log_{2}{(1/1) = 0 }$ and indeed the depth of the root is 0. But I don't know how to proceed.

I've been thinking about how in a complete binary tree the depth of a leaf is $\log_{2}{n}$ with n being the number of nodes in that level (I'm not 100% sure about this) and how de depth of a character i in the prefix tree = length of the binary code (for example depth of d is 3 and its coding is 111) but I can't see how I could use those two things (if they are even useful).

What do you think about it? I don't know how to approach it :(

Btw thanks for your time and have a nice day!

Consider a symbol $\sigma$ whose frequency is $f$. During the course of Huffman's algorithm, $\sigma$ is matched with other nodes, and the depth of $\sigma$ is the number of times this happens.

At the first time that $\sigma$ is matched, it is either the symbol with smallest frequency or with second smallest frequency. In the former case, it is merged into a new symbol whose frequency is at least $2f$. In the latter case, after $\sigma$ is merged with the symbol of smallest frequency, all symbols have frequency at least $f$, and so the next time that it is merged, the merged symbol will have frequency at least $2f$.

Summarizing, it takes at most two mergings to double the frequency of a symbol. If its original frequency is $f$, then this shows that the depth of $f$ is at most $2\lceil \log_2(1/f) \rceil = O(\log(1/f))$.


eliminate left recursion of below grammar Please look at this grammar:
$$ →  \  |  \   \ | \  \\
 →  \ | \   \  | \   \\
 →  \  | \ d$$
I eliminated B from the grammar and it converted to:
$$ S → SAAS \ | SAd \ | \ Ab | \ b \\
A → SAS \ | \ Sd \ | \ a \ | ASS \ | dS $$
But I can't eliminate loop recursion between A and S.Was it a good solution I removed the B at first?
How can I solve that?
any help is much appreciated.

$$ → YX \ | \ Y \\
Y → Ab \ | \  b \\
X → ABX \ | \  AB \\
A → SB \ | \  BS \ | \ a \\
 →  \  | \ d$$

At first I say which rules have a left recursion, considering that the middle tree which is A(the one that A node is the root) has not called itself in its children from the beginning of the left of each child so there is no left recursion in tree which A is root.Similarly the right tree(the one that B node is the root) in its children has not called itself from the beginning of the left of each child, so they do not need to remove the left recursion, so They they have the previous rule (the fourth and fifth lines of my answer A→SB|BS|a,→|d ).
So our problem is the tree with the S root.
I come and look at the children of the S root, there is only one child who starts with S from the beginning of the left of child, so I just have to correct one left recursion to right recursion,
Now I know that there are two children left of the tree with S root, since I only have a left recursion which I want to convert to the right recursion, So I have to put those two children on the left side of this conversion to the right! (For example, if we have two of these conversions we have to pack each of two children(with no recursion) with those two conversions.)
So I write the second line of my answer (Y→Ab|b) and then I write the third line of my answer (X→ABX|AB), which is actually the left-to-right conversion, The first line that these two children connect to each other,
and the last two lines are the two trees in the middle and right.


Average Case Running Time of Quicksort Algorithm From this website, it states that the average case of Quicksort algorithm is

  T(n) = T(n/9) + T(9n/10) + θ(n)

Im a bit confused. Is it supposed to be ?

  T(n) = T(n/10) + T(9n/10) + θ(n)

The average case running time of quicksort satisfies the recurrence
$$
T(n) = \frac{1}{n} \sum_{i=1}^n [T(i-1) + T(n-i)] + \Theta(n),
$$
with base case $T(0) = \Theta(1)$.

In view of solving this recurrence, let us replace $\Theta(n)$ with $n+1$ and $\Theta(1)$ with $2$ (the reason for these specific choices will become apparent below). Changing the order of summation, we get
$$
T(n) = \frac{2}{n} \sum_{i=0}^{n-1} T(i) + n + 1,
$$
and so
$$
nT(n) = 2\sum_{i=0}^{n-1} T(i) + n(n+1).
$$
This implies that
$$
(n+1)T(n+1) - nT(n) = 2T(n) + 2(n+1),
$$
and so
$$
T(n+1) = \frac{n+2}{n+1} T(n) + 2.
$$
Unrolling this gives
$$
\begin{align*}
T(n) &= 2 + \frac{n+1}{n} T(n-1) = 2 + \frac{n+1}{n} 2 + \frac{n+1}{n-1} T(n-2) = \cdots \\ &=
2\left[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2}\right] + \frac{n+1}{1} T(0) \\ &=
2\left[1 + \frac{n+1}{n} + \frac{n+1}{n-1} + \cdots + \frac{n+1}{2} + \frac{n+1}{1} \right] \\ &=
2(n+1) \left[\frac{1}{n+1} + \cdots + \frac{1}{1} \right] \\ &=
2(n+1) H_{n+1} \\ &= \Theta(n\log n).
\end{align*}
$$

A different way of analyzing the running time of quicksort in the average case computes the average number of comparisons. Due to linearity of expectation, it suffices to calculate the probability that two elements are compared. You can see both methods worked out in Section 3.4 of lecture notes from CMU.


Omega-Language to Büchi automaton I'm currently preparing a presentation about LTL and a book says that the language $L = (a(a \cup b))^\omega$ cannot be described by any LTL (or FO) formula which is understandable but how does the corresponding Büchi automaton $\mathcal{A}$ look like with $L(\mathcal{A}) = L$?

Intuitively, the language is exactly the set of words that have $a$ in all the odd places. Thus, the corresponding NBW (in fact, $DBW$) has three states, $q,s,r$, where $q$ is initial, $s$ is accepting, and $r$ is a rejecting sink. The transitions are $\delta(q,a)=s, \delta(q,b)=r$, and $\delta(s,a)=\delta(s,b)=q$.


Asymptotic runtime of recursive algorithm uisng subsitution method I need to solve this question using the substitution method:
$T(n) = 3T(n/2)+2n$ if  $n>1$ otherwise,  $T(n) = 1$
Note: $$\sum_{i=0}^k x^i = \frac{x^{k+1}-1}{x-1}$$
$$a^{\log_b n} = n^{\log_b a}$$

I made some attempts at it but I haven't been able to recognize the pattern. It looks to me that it will be  $\mathcal{O}(n \log n)$ but I'm having a hard time proving it.

The substitution method: Substitute the right-hand side of the equation into any recursive instances that appear on the right-hand side:
$$T(n) = c + T(n-1)$$
$$T(n) = c + [c + T((n-1)-1)] = c + [c + T(n-2)]$$
$$T(n) = c + [c + [c + T(n-3)]]$$
$$...$$
$$T(n) = c+c+...+c + T(0)$$
$$T(n) = nc + T(0)$$
So $T(n) \in  \mathcal{O}(n)$

Here is an argument by substitution:
$$\begin{aligned}
T(n) &= 3T(n/2)+2n \\&= 3(3T(n/4)+n)+2n \\&= 3(3(3(T(n/8)+n/2)+n)+2n \\&= \cdots \\&= 3^kT(n/2^k)+\sum_{i=0}^{k-1}{2n\left(\frac{3}{2}\right)^i} \\&= 3^kT(n/2^k)+2n\frac{\left(\frac{3}{2}\right)^k-1}{\left(\frac{3}{2}\right)-1} \\&= 3^kT(n/2^k)+4n\left(\frac{3}{2}\right)^k-4n
\end{aligned}$$
Here, we stop to expand terms when $n/2^k=1$, or equivalently, when $k=log_2n$. Using that knowledge and the identity that you wrote in your question, we get that:
$$\begin{aligned}
T(n) &= 3^{log_2n}T(1)+4n\left(\frac{3}{2}\right)^{log_2n}-4n \\&= n^{log_2{3}}+4n\cdot n^{log_2\frac{3}{2}}-4n \\&= \cdots \\&= 5n^{log_2{3}}-4n \\&\in\mathcal{O}(n^{log_2{3}})
\end{aligned}$$
So as you can see, the fact that you have a factor 3 outside and a factor 2 inside makes your runtime polynomial in $n$.


Showing that deciding whether a given TM accepts a word of length 5 is undecidable I'm having trouble grasping this the concept of reductions. I found the solution and it looks like this:

Assume that $M_5$ is a Turing Machine that can decide if a given Turing Machine $M$
accepts any string of length $5$, i.e., $L(M)$ contains a string of length $5$. The above figure shows how we can use this to construct a Turing Machine that can solve the Halting
problem.

The output $M′$ of our translator behaves as follows:

$M′$ erases its own input and replaces it with the string w.
It them simulates $M$ on $w$.
If $M$ halts on $w$, then it goes into a final state (accepts its input).
It is clear that if $M$ halts on $w$, $M′$ accepts all its inputs. So it accepts a string of length 5 as well.
If $M$ does not halt on $w$, $M′$ does not accept any string at all. So it does not accept any
string of length 5 either.
So $L(M′)$ includes a string of length $5$ if and only of $M$ accepts $w$. So by running $M_5$ on $M′$, we can decide if $M$ halts on $w$ or not. But we know that this is not possible since the halting problem is undecidable. Hence $M_5$ does not exist and the given problem is undecidable.

What I am confused about is: "if $M$ halts on $w$, $M′$ accepts all its inputs" and "If $M$ does not halt on $w$, $M′$ does not accept any string at all". Can someone clarify why this is the case? I've been trying to work out the logic for so long. If any of you guys could help this would be great!

Source

Suppose that $M$ halts on input $w$ and consider the behaviour of $M'$ when it is given input $w'\!$. $M'$ first deletes its input $w'$ and replaces it with $w$, which means that the behaviour of $M'$ doesn't depend on what input it actually receives. Then, $M'$ simulates $M$ on input $w$. So, if $M$ halts on $w$, $M'$ halts for every input, becaues $M'$ ignores its input and just pretends to be $M$ running with input $w$. Likewise, if $M$ does not halt on $w$, $M'$ doesn't halt for any input.


Formal definition of the Dynamic Array - what is the Dynamic Array I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points.

Dynamic Array, according to the Wikipedia's article, is a Data Structure. Article states, that:

  Dynamic array (also called as growable array, resizable array, dynamic
  table, or array list) is a random access, variable-size list data
  structure that allows elements to be added or removed.

This/above definition, surprisingly coincides with the definition of the Dynamic Array provided in the Data Structures and Algorithms Made Easy book (Chapter 3.5), by Narasimha Karumanchi.

However!,

We know, that the Data Structure, by its formal definition, is a specialized implementation of the Abstract Data Type (ADT), but I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic Array.

For instance, we have several Data Structures, in Java, which implement List interface (and interface constitutes an ADT, in this case, as similarly to the concept of ADT, it declares the abstract behavioural characteristic of What must be done, and - says nothing about How), and Dynamic Array is defined (as shown above) as a Data Structure implementing a concept of the Array with the functionality of adding and removing elements in/from it. Many resources (including books provided) define the model of the Dynamic Array as implementations of List - namely ArrayList and LinkedList in the case of Java.

So,

if the Dynamic Array is a Data Structure, then what is the ADT
implemented by that Data Structure?
Maybe Dynamic Array suits more the concept of ADT where the implementations of it are provided in a different ways (example in Java is classes implementing List)?
What is the formal definition of Dynamic Array? is it ADT? is it Data Structure? as I find the definitions in the books/articles, quite contradictory and they oppose each other.

I, personally, think of defining it as a special type of Array Abstract Data Type, in which, structure is not a fixed-sized. I'd call it a special type of Array ADT, which makes it also ADT. Because, it's obvious, that if the Data Structures implementing the Dynamic Array (as said in the provided resources) are very concrete classes like LinkedList and ArrayList then the Dynamic Array itself is no longer a Data Structure, but rather it's some special kind of Array ADT.

What is the Dynamic Array? how it should be correctly and formally defined? Maybe it's just a concept of non-fixed-sized array, which is a conceptual model and has nothing to do with any ADT or DS?

I'm not sure what you mean by this:

  I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic Array.

There are many examples of dynamic arrays in mainstream programming languages:

Python: list
C++: std::vector
Java: ArrayList
Rust: Vec
OCaml (Batteries included): BatDynArray
Javascript: array (when dense)
and many others...

To answer your question about whether or not dynamic arrays are data structures or ADTs: why not both? Clearly, there is a well-known implementation technique known as a "dynamic array" which is characterized by random-access arrays and exponential resizing. So in this sense, there is an agreed upon notion of a "dynamic array data structure". But also, in many of the examples I gave above, the library interface exposes functionality for explicit resizing (e.g. trimming to size). This suggests that dynamic arrays could be considered as an ADT, because the library interface includes details of performance semantics. And presumably, the "dynamic array data structure" is not the only possible implementation of the "dynamic array ADT".


Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$? From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity.

Can it be said then that every algorithm has a complexity of  $O(\infty)$ since infinite complexity is the worst ever possible?
By the same token, can it be said that every algorithm is $\Omega(1)$ since the absolute lowest complexity an algorithm can be is a constant?

To be clear, Big O and Big Omega are classes of functions. So if I have for example $\Omega(1)$, that's a set of a whole bunch of functions.

An algorithm's complexity is a function giving how many steps the algorithm takes on each input. This function may be in a class like $\Omega(1)$, or not.

$\Omega(1)$ is the class of functions $f(x)$ that are greater than some constant $c$ as $x$ goes to infinity. According to the technical definition, the function $f(x) = 0$ is not $\Omega(1)$, so an algorithm that never takes any steps (for instance) would not have complexity $\Omega(1)$. But virtually all algorithms would have complexity in $\Omega(1)$. (For example algorithms that always take at least one step.)

Since $\infty$ is not a number, $O(\infty)$ is not defined under any definition I've seen. It does not seem to be interesting to make this definition (
"all functions which are either finite or undefined"? but that is just all functions). So intuitively the answer to your question is yes, infinity is an upper bound on all algorithms' running times, but technically it's somewhat meaningless.

As a sidenote, we could extend little-o to include a domain of infinity by saying $f(x)$ is $o(\infty)$ if $f(x)$ is finite (i.e. well-defined) for all $x$. Under a definition like that, an algorithm that does not halt on some inputs would not have complexity $o(\infty)$. But every algorithm that does halt on all inputs would.

Edit/PS as pointed out by Yuval, we can give a slightly better answer for $O(\infty)$. Let's restrict attention to algorithms that halt on all inputs. Then we can define a function that grows like the maximum number of steps taken by any algorithm that halts. Call it $B(n)$. Then every algorithm's running time will be $O(B(n))$.

To define the function, let's take Yuval's suggestion and let $B(n) = $ the maximum number of steps taken by any halting TM of up to $n$ states on an input of up to $n$ bits. Now given any algorithm, it will be encoded as a Turing Machine, so it will have a certain number of states; say $N$ of them. Then the running time of the algorithm on inputs of size $m \geq N$ is at most $B(m)$. We can see this because $B(m)$ takes the maximum over all Turing Machines up to a certain size, including this one, so $B(m)$ will be at least as big as this TM's runtime.

See also: http://en.wikipedia.org/wiki/Busy_beaver


Shortest hamiltonian path for different dimension points The shortest Hamiltonian path (solution) for a set of points in $\mathbb{R}^k$ (in Euclidean space) changes subject to $k$.

For example if for $k=1$, the shortest Hamiltonian path will be the sorted set of points, which can be achieved in $O(n\log n)$.

My question is what happens when $k$ increases - does the solution become more and more complex or is it the same for all values of $k$ larger than $1$?

Your problem is a variant of Euclidean TSP in which you are looking for a path instead of a cycle. You can (essentially) reduce your problem to the usual Euclidean TSP by adding a point at infinity.

Here is a quick summary of what is known about Euclidean TSP, paraphrasing a survey of Czumaj from the Encylopedia of Algorithms:

For every fixed $k$, there is a randomized PTAS due to Arora and Mitchell. The running time has been improved by Rao and Smith, and by Bartal and Gottlieb (in the real RAM model).
Trevisan showed that there is no PTAS when $k = \log n$ (unless P=NP).
Euclidean TSP with an unbounded number of dimensions is known to be NP-hard. The same isn't known for fixed $k$!