Proving that it's decidable whether a TM ever moves on the blank input I'm trying to understand how to prove a language is decidable, semi-decidable, co-semi-decidable, or none of the above.

I've got the problem: $$A_{\mathrm{right}} = \{ \left<  M\right>  | M \text{ never moves on blank input} \}$$

and I have to prove what it is. I know that it is decidable, because if given an input where there is a blank, then it will enter a halt and will loop there forever and not move, thus it is rejected. Everything else can be accepted. I just don't know how to go about proving this with quantifiers.

Any help would be greatly appreciated.

In order to understand what $M$ does on a blank input, one needs only examine its transition function $\delta$. As mentioned in the question, assume the starting state is $q_0$, then there are two options: either $\delta(q_0,\text{blank})$ moves the head (and then we can reject) or it doesn't move the head, which brings us to two other options: either it remains in state $q_0$ (then we can accept, right?) or it moves to another state, say $q_1$.

But, with $q_1$ the same reasoning applies, and as Raphael suggested, we can't go on with this logic forever since the number of states is bounded by $|Q|$. So after $|Q|$ "steps" of the above reasoning we will have a conclusive answer to the question of whether the head moves or not, and we can accept or reject accordingly. Since we were successful at constructing a decider, this question (and hence the induced language $Aright$) is decidable.


Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting? I have seen a remark saying "we usually say that a turing machine accepts/rejects a string, while it decides a language" Is this correct?

As I have also seen places where we mention a Turing machine "accepting a language"

See comment on OP's answer here, then the answer by Jan Hudec : What is the difference between a TM accepting and deciding a language?

I have also seen the definition of total/decider to mean, the Turing machine halts on all inputs. Is this all inputs in the language the Turing Machine is defined over?

A Turing machine cannot accept a language.

A Turing Machine will either accept or reject a string or loop forever. We know it accepts the string because it will halt in an accepting state. It is said to reject a string, of it halts in a rejecting state.

A TM recognises a language, if it halts and accepts all strings in that language and no others.

A Turing machine decides a language if it halts and accepts on all strings in that language, and halts and rejects for any string not in that language.

A total Turing machine or a decider is a machine that always halts regardless of the input. If a TM decides a language, then it is decider by definition or a total Turing Machine.

Edit:

To answer some of the questions in the OPs comments:

A language does not define a Turing Machine. The TM defines the language; this language is set of all inputs that the TM halts and accepts on.
All finite languages are decidable which means that there is a corresponding Turing machine which is a decider


Paxos: Instances, Rounds, Phases In the paper, Paxos Made Simple, Lamport describes a round of Paxos as two phases: a $prepare$ phase, and an $accept$ phase. An instance of Paxos can have multiple rounds. Can a round have multiple proposers make proposals, or is it strictly one proposal per round?

In addition, I found a number of sources which indicate there are three phases in Paxos: an $accept$ phase, $propose$ phase and a $learning$ phase, in which a distinguished learner informs all other participants of the chosen value. For example: http://pdos.csail.mit.edu/6.824-2007/labs/lab-8.html

Which is true?

If we do require three phases, in which a distinguished learner informs all other participants of the chosen value, does Paxos then guarantee that all nodes agree on the chosen value? What about the minority of acceptors that did not accept the value? Does the distinguished learner inform them too?

Q1: Lamport describes a round of Paxos as two phases: a prepare phase, and an accept phase. An instance of Paxos can have multiple rounds. Can a round have multiple proposers make proposals, or is it strictly one proposal per round?

I don't think Lamport uses the term "round" to organize the two phases, at least it is not the case in the "Paxos Made Simple" paper. Actually, the word "round" only occurs once in that paper and it is used to refer to the communication round.

The term "round" is used in James Aspnes' lecture notes to refer to

  the collection of all messages labeled with some particular proposal $n$.

It is important to distinguish between the definition of "round" here and the "communication round". In this sense, a round is dedicated to a single proposal (and belongs to a single proposer), because different proposals have globally unique timestamps.

Q2: I found a number of sources which indicate there are three phases in Paxos. Which is true?

As explained in James Aspnes' lecture notes,

  Note that acceptance is a purely local phenomenon; additional messages are needed to detect which if any proposals have been accepted by a majority of acceptors. Typically this involves a fourth round, where acceptors send accepted(n, v) to all learners.

In the "Paxos Made Simple" paper, Lamport mentions the "learning" phase in Section 2.3 (see Page 6). Notice that it is a fourth phase in Aspnes' lecture note.

Q3: If we do require three phases, in which a distinguished learner informs all other participants of the chosen value, does Paxos then guarantee that all nodes agree on the chosen value? What about the minority of acceptors that did not accept the value? Does the distinguished learner inform them too?

In the classic formalization of Paxos, there are three roles which are proposers, acceptors, and learners. Learners are required to learn the chosen value. So the "learning" algorithm in Section 2.3 is (there are other variants):

  We can have the acceptors respond with their acceptances to a distinguished learner, which in turn informs the other learners when a value has been chosen.

In this approach, all acceptors send every proposal they have accepted to the distinguished learner. The distinguished learner (locally) regards a value to be chosen only when it is accepted by a majority of acceptors. Then, the chosen value is propagated to other learners.


Bytes--Measured or Counted I hope the Computer Science section is the appropriate place to ask this question. I’m working on profiling some data sets and I am a bit tripped up on something, I was hoping I could get some assistance.

Part of my project is to determine whether some of my data is an integer and whether is a continuous or discrete quantity.

I understand that in a simple sense Discrete data is counted and Continuous data is measured. I also know Discrete Data can only take on certain values while Continuous Data can take on any values.

It seems that the size of a computer file (in bytes) could take on either of these descriptions because bytes are based on bits and are based on a power of 2 (which would make it discrete). However at the same time a file size could be Continuous because it could be of any size.

If anyone could help me out it would be greatly appreciated! Also if you are aware if I misunderstood something please let me know!

A file size is measured in bits, you cannot have a portion of a bit, only a whole bit, it is a discrete quantity. Something is continuous if it can can have any possible value in a range, bounded or not. Something can be discrete and at the same time infinite.

The best way to think about discrete or continuous is if for any two values you can find a value between them then it is continuous, otherwise it is discrete.


Model Counting for Sum of Conjunctive Formulas Problem:
Let $X=\{x_1, ..., x_N \}$ be a set of binary variables. Each variable can be assigned to either $0$ or $1$ so there are $2^N$ possible assignments.
Input: We are given a positive integer $C$ and a set of binary functions $F=\{f_1,...,f_M\}$ where each function is defined as a simple conjunction of some subset of $X$. That is, each $f_i \in F$ is defined as $f_i(X) := \prod_{x \in X'}x$ for some $X' \subseteq X$.
Output: The number of assignments to variables in $X$ such that $\sum_{i=1}^M f_i(X) = C$.
Question:
Do you know of a polynomial-time algorithm that solves this problem for a bounded value of $C$?
Any ideas or pointers to references would also be greatly appreciated.
It is OK if the complexity is bounded with respect to e.g. some constant $D$ which could be the maximum size of $X'$, that is, the maximum number of variables in the product of any function $f_i \in F$.
Observations:
When $|X'|=1$, that is, when each function $f_i \in F$ can only have one variable, then the problem can be reduced to the counting version of the subset sum problem and can be solved in $\mathcal{O}(N\cdot C)$ time using an modified version of a dynamic programming algorithm for solving subset sum.

When $C = 0$ and each $f_i$ depends on two inputs, your problem is equivalent to #2-MONOTONE-SAT, which is #P-complete, see for example this question on cstheory.


Linear programming vs integer linear programming Given $A,b$, let $Ax \le b$ be an instance of linear programming on the variables $x=(x_1,\dots,x_n)$.  Assume that the constraints $0 \le x_i$ and $x_i \le 1$ are included in $A,b$.
Suppose that there is a feasible solution $x \in \mathbb{R}^n$ to the linear programming problem where $x_1 = 1$.  Also, suppose there exists a solution to the corresponding integer linear program, i.e., there exists $x' \in \{0,1\}^n$ such that $Ax' \le b$.  Are we guaranteed that there exists a solution with $x'_1=1$, i.e., there exists $x' \in \{0,1\}^n$ such that $Ax' \le b$ and $x'_1=1$?
To put it another way: if we solve the linear program associated with a zero-or-one ILP instance, and find that one of the variables gets assigned to 1 in some solution to the linear program, does it follow that there exists a solution to the ILP instance where we set that variable to 1?
I am skeptical but could not find either a proof or a counterexample.

The program $x_1 + 2x_2 = 2$ has the integer solution $(0,1)$ and the fractional solution $(1,1/2)$ but not an integer solution of the form $(1,\cdot)$.


How to simplify sum of products boolean expression? I started with this sum of products:

abc’d’ + abc’d + ab’cd’ + a’b’cd’ + a’bc’d + a’bcd + ab’c’d + a’b’c’d

I have been able to simplify to this:

b'c'd + abc' + a'bc + b'cd'

I can't seem to find a way to simplify it anymore. I have tried reading and watching a ton of tutorials but nothing is clicking.

Some things I have tried is finding the common values among the or expressions such c' or b'.

combining c'

c'(b'd + ab) + b'cd' + a'bc

combining b'

b'(c'd + cd') + abc' + a'bc

I get stuck with the simplification of combining b' or c'.

Can anyone provide any guidance as to what I am doing wrong or missing?

From a Karnaugh map you can get a one group of 4s and three group of 2s. So you can reduce sum of 4 term in which three will have 3 literals and one with 2 literals. By doing it use K-map you will use few 1s for more than one terms so if you don't want to use a K-map just use idempotent rule($x = x + x$) and then simplify.


Calculating execution time for recursive algorithm How would I calculate the execution time, T(n), for this algorithm?

int search(int a[], int l, int r, int x) {
    int m = (l+r)>>1;
    if (l > r) return -1; // not found
    if (a[m] == x) return m;
    if (a[m] > x) return search(a, l, m-1, x);
    return search(a, m+1, r, x);
}

I'm assuming that the one if statement is not supposed to be on the same line as the comment... if that is intentional it does change things up somewhat :)

int search(int a[], int l, int r, int x) {
1.    int m = (l+r)>>1;
2.    if (l > r) return -1; // not found
3.    if (a[m] == x) return m;
4.    if (a[m] > x) return search(a, l, m-1, x);
5.    return search(a, m+1, r, x);
}

I am also assuming T(n) means you are looking for the worst-case scenario (eg. the number you are searching for was the last one you checked, or was not found at all). The most straight forward way of solving these is to simply trace it through line by line, keeping track of the values of the variables in a table, until you notice a pattern emerge. Now, note that finding a pattern by itself never proves that the pattern you found is actually correct, but it will give you a good place to start, and will frequently (but not always) even yield the correct solution to the problem.

So, that being said, here's the gist of how I traced through it, minus a table with variable values like r/2, r/4, etc.

m is being set to halfway between l and r in line 1 (I suppose doing it with a bitshift is more efficient...)
The worst case would definitely involve running the search again. However, you can tell that this time either r is going to be halfway closer to l (line 4) or l is going to be halfway to r (line 5)
m is being set to halfway between l and r again, and so on, until m cannot be cut in half anymore (this will occur in line 2 where l > r)

m keeps getting cut in half again and again until it cannot get cut in half. This pattern implies that maybe (probably) T(n) = O(log2 n). If you need to prove its correctness you would need to do a more formal direct proof than a trace. You could use Master's Theorem to prove its correctness as well.

If you are going to be doing a lot of these or if you need to prove the correctness of these it may be worth your time to look up how Master Theorem works, as getting your mind around that will make these a lot easier.


I'm quite confused about the convergence of pix2pix cGAN, how can we tell whether my model is well trained? Usually we will see decreasing loss for regular CNN model, but for GAN, it seems to be not that simple. How can we tell whether my model is well trained?

Create a test set, by taking a subset of the training set (make sure to not train on this test set!). Then evaluate the model against the given labels in the test set.
Also, this trick is very useful generally, since it works for any supervised machine learning model.


For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar? Apparently, ReDos attacks exploit characteristics of some (otherwise useful) regular expressions ... essentially causing an explosion of possible paths through the graph defined by the NFA.

Is it possible to avoid such problems by writing an equivalent 'non-evil' regex?  If not (thus, the grammar can't be handled in practical space/time by an NFA), what parsing approaches would be better?  Why?

It depends upon whether you've got a regular expression or a regexp: regexps are evil, but regular expressions are a thing of beauty and will never turn evil on you.

By regexp, I mean a modern regular expression: i.e., a regular expression with additional modern features such as backreferences -- e.g., a Perl-compatible regular expression.  This is more powerful than a classical regular expression from a formal languages / automata theory textbook, as classical regular expressions don't allow backreferences, lookahead, lookbehind, and so on.

For a classical regular expression, if you have a good implementation for the matcher, then no regular expression is too evil.  In particular, a standard algorithm for matching is to convert the regular expression to a NFA and then executing the NFA on an input string.  For this algorithm, the worst-case running time to test a $n$-character string is $O(n)$, when the regular expression is fixed.  This means that the running time can't explode too rapidly.  There is no string that will cause an exponential increase in running time.  Thus, if you're using a matcher that uses this algorithm, no classical regular expression will be evil.

This does depend on the implementation of the regular expression matcher.  If you have a naive or poor implementation of the matcher, then matching could take exponential time; there are certainly algorithms with that property.  But the best answer to that is probably not to change the regular expression; it's probably better to pick a better matcher, if you are concerned about denial-of-service attacks.

In comparison, some modern regexps are unavoidably evil.  If you have a modern regexp, then matching can require exponential time.  In particular, regexps with backreferences can recognize NP-hard languages.  Consequently, under plausible assumptions, there exists a class of evil regexps where testing for a match takes exponential time.  Thus, some modern regexps are unavoidably evil: there is no feasible way to find an equivalent regexp that won't cause exponential blowup in running time to match.

(Such an equivalent might exist and might even be findable in theory, but under plausible assumptions, finding the equivalent regexp will take exponential time, which isn't feasible in practice.  If you had a systematic procedure to find the equivalent regexp in polynomial time, then you could solve the NP-hard problem in polynomial time, proving that P = NP.  It doesn't do much good for there to exist an equivalent regexp if there's no way actually find it within your lifetime.)

Background and sources:

Which languages do Perl-compatible regular expressions recognize? and Expressiveness of modern regular expressions provide references to justify that modern regexps can recognize NP-hard languages.
How to simulate backreferences, lookaheads, and lookbehinds in finite state automata? and When a regexp is not a Regular Expression? can be helpful to understand the difference between regular expressions and regexps.
This article from Russ Cox has a nice explanation of two different ways of building a regular expression matcher, and explains why the running time if you use the proper algorithm is linear in the length of the input string (when the regular expression is held fixed and its length is treated as a constant).  In particular, the NFA-based algorithm -- also known as the Thompson algorithm -- has linear worst-case running time.  It also shows how some popular languages have regexp implementations that can go exponential on some regexps, and it discusses which aspects of modern regexps can introduce exponential running times.
In this post I assume P != NP.  More to the point, when I refer to "plausible assumptions", I am referring to the exponential time hypothesis.


Pumping lemma problem I need some help with the following question:

One of the languages

$$L_1 = \{a^pb^{q+r}c^sd^{q+t}e^{p+r} \mid p, q, r, s \ge 0\ , s > t\}$$
$$L_2 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\}$$

is context-free and the other is not. Build a context-free grammar for the one that is. For the other one provide a proof that it is not regular, or that it is not context-free.

How do I approach this problem ? I think that L2 is context-free because no comparisions are made. L1 is not context-free.

Thanks in advance

You are actually wrong. I'll give you a hint for the grammar of $L_1$. Rewrite it as $a^p b^r b^q c^{s-t} c^t d^t d^q e^r e^p$. Although I have no idea how the case $s = 0, q = 0$ (thus $q+t < 0$) is supposed to work.

For $L_2$ there is an implicit comparison $r \leq q+r$. Take $p = q = 0$ so that the string is $b^rc^sd^re^s$. You should be able to apply the lemma here easily.


Calculating eigenvalue gap of a torus graph Consider a two-dimensional grid with wrap-around edges (a doughnut-shaped graph). I need to calculate the second-largest eigenvalue of the adjacency matrix. Is there a faster way of computing it for such a special graph than a general method such as the "eigs" function in MATLAB?

Suppose that the torus is $n\times n$. Let $\omega = e^{2\pi i/n}$ be a primitive $n$th root of unity, and let $v_{\alpha,\beta}$ be the $n\times n$ vector given by $v_{\alpha,\beta}(i,j) = \omega^{i\alpha+j\beta}$. Using $A$ for the adjacency matrix of the torus (indexed by pairs $(i,j) \in \mathbb{Z}_n$),
$$
\begin{align*}
(Av_{\alpha,\beta})(i,j) &= v_{\alpha,\beta}(i+1,j) + v_{\alpha,\beta}(i-1,j) + v_{\alpha,\beta}(i,j+1) + v_{\alpha,\beta}(i,j-1) \\ &= v_{\alpha,\beta}(i,j) (\omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta}).
\end{align*}
$$
In other words, $v_{\alpha,\beta}$ is an eigenvector with eigenvalue $\omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta}$. It is not hard to check that the $n^2$ vectors $v_{\alpha,\beta}$ are linearly independent, and so they form a basis of eigenvectors for $A$. The eigenvalues are
$$
\lambda_{\alpha,\beta} = \omega^\alpha + \omega^{-\alpha} + \omega^\beta + \omega^{-\beta} = 2\left(\cos \frac{\alpha2\pi}{n} + \cos \frac{\beta2\pi}{n}\right).
$$
For $\alpha \in \{0,\ldots,n-1\}$, the function $\cos \frac{\alpha2\pi}{n}$ reaches its maximum $1$ at $\alpha = 0$, and otherwise its second largest value is attained at $\alpha=1$ and $\alpha=n-1$. Therefore the second-largest eigenvalue is $2 + 2\cos \frac{2\pi}{n}$. More generally, for a $d$-dimensional grid, the second-largest eigenvalue is $2(d-1) + 2\cos \frac{2\pi}{n}$, and the eigenvalue gap is $2-2\cos \frac{2\pi}{n} = \Theta(\frac{1}{n^2})$.

More generally, the $n\times n$ torus is the cartesian product of the $n$-cycle with itself. It is well-known that if $G$ has eigenvalues $\lambda_i$ and $H$ has eigenvalues $\mu_j$ then the eigenvalues of the cartesian product of $G$ and $H$ are $\lambda_i + \mu_j$ (the proof follows the computation above, replacing $\omega^{i\alpha}$ with an arbitrary eigenvector of $G$, and $\omega^{j\beta}$ with an arbitrary eigenvector of $H$). It follows that the eigenvalue gap of the product is the minimum between the eigenvalue gaps of $G$ and $H$.


Count points enclosed by several planes in 3D space I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points.
Those plane can make regions, some of them closed, and others not, the task is to count the number of points in each region.

I just need some ideas about how to solve, or if there is an algorithm for that.

A plane divides the 3D space in two regions.  A good method to discern is to apply the plane equation to the point and see if it yields negative or positive result:

$$Ax + By + Cz + D = 0$$

is the equation of a plane in 3D. So if you put the point coordinates you'll get a positive, zero or negative number. (If zero, the point belongs to the plane and so, it's neither in either side of the plane.)

The question asks to count the points that belong to each of the delimited regions for each plane.  Well, you have n planes each dividing the space in two halves (so you have $2^n$ regions at most, except in case you have paralell planes, but this procedure is applicable also in that case ---you'll get regions not accounted for as no point can lie in them), just consider each point and apply it to each plane.  Then construct a number X, making bit $i$ (for plane $i$) of X a 1 in case applying plane to it gives a positive number and 0 in case applying it gives a negative one (in case it returns 0 you have to decide what side to count it ---what value you select for bit $i$--- for (if any) as this is a point that belongs to the plane) then with that number as a key for region X, increment counter of region X selected, so in one pass over all points you'll get all counters actualized with how many points belong to each region.  Each key X, so constructed, identifies each of the possible regions you have divided the space into, so you must cope with $2^n$ regions (and counters) for $n$ planes.


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

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

Your approach doesn't work.  Presumably, you want to define the probability of a path to be the product of the probabilities on its edges.  It sounds like you want to define the weight $w(e)$ on an edge $e$ to be $w(e)=1-p(e)$ (one minus its probability). However, doesn't work.  It doesn't do what you want: you want $w(e)+w(e')$ to correspond to $p(e) \times p(e')$, but it doesn't.

Instead, you should be taking logarithms.  In particular, you should define the weight on edge $e$ by $w(e) = -\log p(e)$.  Now addition of weights corresponds to multiplication of probabilities:

$$w(e) + w(e') = -(\log p(e) + \log p(e')) = - \log(p(e) \times p(e')),$$

as desired.  At this point all of the weights in $G'$ will be non-negative (do you see why?), so you can use Dijkstra's algorithm to find the shortest path in $G'$, and that will correspond to the path in $G$ with highest probability.  As you can see, this is not a longest-path problem at all; it is just a straightforward shortest-paths problem.

The trick of taking logs to turn multiplication into addition is a standard one, including in many applications of graphs, so this is worth knowing.


Converting along regular expression to NFA I have the following regular expression for the set of all strings such that each block of five consecutive symbols contains exactly two 0's (consider the alphabet to be {0, 1}):

(0+1+ϵ)4+(11100+ϵ)r(0011100r)*(00111+ϵ)

r=11+(110+ϵ)s(0110s)*(011+ϵ)

s=(0+10)*(1+ϵ)

How should I convert this into an NFA? Please explain the steps behind it as well!

What you need is the Berry-Sethi algorithm, constructing the Glushkov's automaton.
However, for your problem, I'd consider constructing directly a DFA with $10 = \begin{pmatrix}5\\2\end{pmatrix}$ states corresponding to words of size 5 containing exactly two zeros, and a sink state (and maybe some other states for the begining of the reading).
The Glushkov's automaton on your regular expression will be very big.


Why does the Θ-class survive adding a constant only for positive, monotonic, and non-decreasing functions? I know that for positive monotonically non-decreasing functions, f(n) and g(n),

f(n) = O(g(n) + c) entails
f (n) = O(g(n))

Why is this always true only for positive monotonically non-decreasing functions? $\Theta$

If there exists one, give a counter-example that shows that the above Big O rule is not necessarily true for functions that are not monotonically non-decreasing.

I'm really confused why the rule specifies only positive, monotonic, non-decreasing functions. Thanks for your help!

Let $f(n) = 1-1/n$ and $g(n) = 1/n$, so we've violated the condition that $g$ is non-decreasing. However, it's not hard to show that $f(n) \in O(g(n)+2)$ but we also have $f(n)\notin O(g(n)$, invalidating the inference.


Given matrix, count paths visiting each number exactly once We are given matrix of size at most $21$ by $21$, each number of the matrix is either $-1$, which means empty element, or integer between $1$ and $21$. Each integer may occure several more times in the matrix.

We want to count paths that start in some cell, then moving in one of the four directions (up, down, left, right) visit all $21$ number exactly once.

It is impossible to move on cells marked as $-1$.

For example:

1,  2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, -1, 21
-1,-1,-1,-1,-1,-1,-1,-1,-1, -1, -1, -1, -1, -1, -1, -1, 18, 19, 20
We can start in the upper-left cell, move right until 17 then down, right again, and up on the end.
The second path is the same as the first path but reversed (starting from 21).

My idea is to use dynamic programming with three states $i, j$, coordinates of the current point, and bitmask of the visited cells. However this is pretty slow for numbers up to 21. Is there any way to speed up this calculation.

Link from the task that appeared on the contest: mendo.club/Task.do?id=647

If I understand well, you are looking for an Hamiltonian path which is basically NP-complete. With your DP idea, there is $2^{21} = 2M$ possible bitmasks and there is no way to order them. So I am not sure to understand how it works.

In fact you can start building a graph and get rid of any direction/"-1 cells" consideration. In your example you would get a simple chain from 1 to 21.

Then, in the very general case you may have to explore all possible paths (using DFS for instance). But in this kind of problem you can look for some tricks. The point is to select the 20 edges of the path:

Any vertex having only one edge is either start/end (NB a reversed valid path is valid like in your example) and its edge is selected
A vertex having 2 edges have these edges selected (unless it is start or end)
A vertex having 2 edges selected, have all the other edges removed.


Does CSL contain an empty string or not? Is empty string accepted by LBA or not? I am confused and got contradictory statements from various sources. It is mentioned in Page no 292, Chapter 11 A Hierarchy of Formal Languages & LBA, Peter Linz -An Introduction To Finite Automata, 5th Edition that "A language L is said to be CSL if there exists context-sensitive grammar G such that $L = L(G)$ or $L = L(G) \cup \{\varepsilon\}$." So the Language contains empty string & grammar as per Peter Linz.
In another version, I found that the production $S\to\varepsilon$ is also allowed in CSL, provided that 'S' does not appear on the right-hand side of any productions. However, several other sources like this youtube lecture (https://www.youtube.com/watch?v=i3c_2c2KFpY) explain that CSL does not contain a null string. Here in this given link (https://gyires.inf.unideb.hu/GyBITT/14/ch06s04.html)  it is written that LBA accepts null string generated from a CSL.
In the book, "Theory of Computer Science: Automata, Languages and Computation" by Mishra K.L.P , third edition, Publisher-PhI, on page 299, subsection 9.8.1 that "The set of strings accepted by nondeterministic LBA is the set of strings generated by CSG, excluding null strings".
This is too much for making a complete confusion.
Example:
L=$\{a^nb^nc^n| n\geq 0 \}$, whether this is CSL or Not? This language contains empty string too!
Please help me to get the right knowledge.

Welcome to CS.SE!
I only know of the latter definition, i.e. the one allowing $S \to \varepsilon$ but disallowing $S$ in the right sides of productions.
Ultimately this is done to have a nice definition in the sense that the class of context-sensitive languages forms a proper superset of the class of context-free languages.
Definitions excluding the empty string to be in context-sensitive languages are a little bit less nice, in that sense.
As you found out, definitions may vary between sources and are often chosen in order to state some property or result in a particularly nice manner.
This is common in mathematics and another example would be the question of including 0 in the natural numbers $\mathbb N$ or not.
The thing is that usually these little changes do not really matter in the end; they do not fundamentally change the mathematical nature of the thing defined, and this is also the case with the small differences between the definitions for context-sensitive languages you encountered.


List of intro TCS books for those who don't know much about TCS If you have to recommend books for someone who wants to learn more about TCS at the introductory level such as automata theory, algorithmics, complexity theory, etc, what book(s) would you recommend for those who are interested and want to learn more about TCS, but not had any exposure to it?

If you would like to have a general introduction without getting to deep into the technical details, I suggest David Harel's Algorithmics: The Spirit of Computing. After that, this is my favorite list:

Michael Sipser's Introduction to the Theory of Computation: the best introduction to automata theory, computability and complexity.
Algorithms by  S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: the most intuitive introduction to algorithms with stronger focus on intuition than technical proofs.
Jon Bentley's Programming Pearls: this is not a textbook on algorithms, but it demonstrates beautifully how to use algorithm design techniques to solve real problems that irritated real programmers. :-) This might be a good start if you have some pre-knowledge on programming.


Collisions in independent hashing Let $H$ be a $s$-wise independent family of hash functions from $\{1,\ldots,M\}$ to $\{1,\ldots,N\}$. It is easy to bound one collision, but are there good bounds for muliple collision ?

You can upper-bound your probability using a union bound.  In particular,

$$\Pr[\exists x \in S . \phi(x)] \le \sum_{x \in S} \Pr[\phi(x)].$$

Using a union bound we obtain ${M^s \choose 2}$ terms in the sum, and each term is upper-bounded by $1/N^s$, so we find that your probability is at most

$${M^s \choose 2}/N^s.$$

If $M < \sqrt{N}$, then this probability will be at most $1/2$.  If $M \gg \sqrt{N}$, then this probability is close to $1$.

(Qualitatively, this upper bound is fairly close to tight for a wide range of settings of $M,N$.  I am not going to prove this fact, but you can take my word on it.  So there's not much hope for a significantly better bound using some other proof technique.)

In short: as Yuval Filmus says, unless $M$ is very small, your event is actually pretty likely.

No, something stronger than $s$-independence will not help.  Even if you assume that $h$ is generated uniformly at random from the set of all hash functions with the right signature (something that is not actually implementable), you don't get a much better bound.

The only plausible approach I can see is to choose a hash function $h$ that does not have any collisions at all: e.g., choose $h$ from a family of injections, or use a perfect hash.  Each of these has serious shortcomings: the former requires $M<N$, and the latter typically requires you to know in advance the full set of values that you will ever compute $h$ on.


Is it possible to prevent arithmetic errors with a dependent type system? In a functional programming language I have functions like
$$f\colon Int \times Int \times \cdots \times Int \to Int$$ which do some computation. However for certain arguments $(x_0, \dots, x_n)$ the function will cause arithmetic errors like Integer overflows, Integer underflow or even Division by zero. I do not want to handle those special cases within the function. Instead I would like to throw a type error at compile-time if someone calls the function with a undefined input.

So, my question is: Is possible to prevent arithmetic errors with a dependent type system?

And if so, does Adga, Idris or any other dependent type language support this?

In theory, you can do anything of this sort with dependent types! Typically you would define your own (dependent) type, say

b_int = {z : Z | MIN_INT <= z <= MAX_INT}

Depending on the "flavor" of your dependent types, you might need a bunch of functions for going from b_int to Z and vice-versa (for well-defined values).

and then your function f would have to be of type:

 f : b_int * ... * b_int -> b_int

Now the tricky part. First you have to specify all the arithmetic operators, say b_add : b_int * b_int -> b_int in terms of the "ordinary" add function add. Ah except this isn't quite right. b_add MAX_INT 1 shouldn't be allowed! So you would have to give it a stricter specification, along the lines of

 b_add : { (n, m) : b_int * b_int | MIN_INT <= n + m <= MAX_INT } -> b_int

Then you want to prove something along the lines of:

b_add_correct : forall n m, n + m = b_add(n,m)

where the pair (n,m) needs to be in the domain of definition of b_add. Here, again, there may be a lot of pain if you need to translate to and from the Z type of unbounded integers, depending on how explicit the sub-types are.

Similarly for division:

b_div : { (n, m) | MIN_INT <= n / m <= MAX_INT, m =/= 0 }

So, if your program only uses the bounded operations, then there should be no way of writing a type correct program that has overflow or NaN operations.

However, I hope to convince you as well that there may be a significant amount of pain if there are no natural inclusions of types into sub-types, b_nat -> Z and if proofs of the inequalities have to be carried around explicitly.

One example is if the coercion box : Z -> b_nat explicitly carries the proof of inequality, i.e. box actually has the type:

 box : (x : Z) -> (p : x <= MAX_INT) -> b_nat

(I'm omitting the lower bound for simplicity). Then the correctness for b_add might be something more like:

 b_add_correct : forall n m : Z, (p : n <= MAX_INT) ->
                                 (q : m <= MAX_INT) ->
                                 (r : n + m <= MAX_INT) ->
    n + m = unbox (b_add (box n p) (box m q) r)

Whew! It gets even worse if just applying a bop operation requires explicitly building a proof that some bound holds (for example if you know $n < m$, then you might want to use the fact that $m - n \neq 0$ to do division). That can make your program look quite messy, and be hard to write, since your proof obligations and program writing become inextricably linked.


Why is a regular language called 'regular'? I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata.

He defines a regular language as anything that can be described by a finite automata. But I could not find where he explains why a regular language is called "regular?"  What is the origin of the term "regular" in this context?

NOTE: I am a novice so please try to explain in simple terms!

As Kaveh says in a comment, Kleene bestowed the name way back when he kicked off automata theory and formal languages. I believe the term was arbitrary, though it has been many years since I read his original paper.

Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such as geometric or other analogies or metaphors, and sometimes arbitrarily. Just look at "group", "ring", "space", "sheaf", "atlas", "manifold", "field" and so on.

In fact, the term "regular" for finite-state languages, while still prevalent in automata theory, is not used very much in its algebraic cousin, finite semigroup theory or abstract algebra in general. Why? Because the term was already taken for a semigroup that is close to a group in a specific technical sense, so you couldn't match up a regular language in Kleene's sense with a corresponding regular semigroup. Third, Kleene defined another kind of event called "definite", which was much studied for a while, but has turned out to be not particularly fruitful. Today, finite sets of language play the role of definite events as the basis for regular events.

The preferred term in algebra is "rational" for both Kleene's class of languages and the more general semigroups and monoids. That usage also reflects an important analogy between the term "rational" in algebra as the solution of a linear equation with integer coefficients and the concept of rational power series in automata and formal language theory.

Additional information.  Kleene's original paper of 1951, entitled "Representation of events in nerve nets and finite automata" may be found here. On p. 46 it settles the arbitrariness of the term "regular" with this statement:

  We shall presently describe a class of events which we will call "regular events".  (We would welcome any suggestions as to a more descriptive term.)

Apparently, nobody came up with a more descriptive term. ;-)

As is often the case with seminal papers which lead to the intensive development of whole new areas, the terminology and concepts are almost unrecognizable in today's terms. First, the paper was about models of neurons, hence the use of "events" instead of "languages" or "sets". The term "events" persisted well into the 60's and 70's, even after the importance of Kleene's concepts for automata and formal languages vastly outweighed any value for neuroscience.

Second, there are some mathematical differences, such as defining what came to be called "Kleene Closure" as a binary operation, equivalent to $a^*b$, instead of the simpler unary operation $a^*$ or $a^+$ that we use today. Kleene's motivation was to avoid the empty string (or event with duration zero in his terms). That was a remarkably prescient intuition since subsequent theory has shown how crucial the choice is to include or exclude the empty string from definitions in many contexts. Third, Kleene defined a concept called "definite events" and developed regular events from them, but nowadays we use finite sets for the purpose. Definite events were studied for a while, but have turned out to be far less important than regular events/sets/languages.

Anyway, a complete reading of this paper is probably not worth anyone's time today, except for historical purposes. I just skimmed it for the crucial definitions and ideas, and that was fun.


Turing machine with "move to origin" instead of "move left" You have a Turing machine which has its memory tape unbounded on the
  right side which means that there is a left most cell and the head cannot move left beyond it since the tape is finished. Unfortunately, you also find that on execution of a head move left instruction, rather than moving to the adjacent left cell, the head moves all the way back to the initial left most cell of the tape. Now figure out whether you can still use this TM effectively. The Turing machine with left initialize is similar to an ordinary Turing machine, but the transition function has the form

  $$\delta  \colon Q × Γ → Q × Γ × \{R, \mathit{INIT}\}.$$

  If $\delta(q, a) = (r, b, \mathit{INIT})$, when the machine is in state $q$ reading an $a$, the machines head
  jumps to the left-hand end of the tape after it writes $b$ on the tape and enters state $r$. Show
  that you can program this TM such that it simulates a standard TM.

I can't figure out how to simulate this as standard TM. One thought I have is to copy the content of the tape which is afterwards the left move to the starting point of the tape before making a left move. Any further help would be appreciated.

When you want to move one position to the left, execute the following algorithm:

Mark the current position as special.
Move to the origin.
Translate the tape one cell to the right, while keeping the special marker in place.
Move to the origin.
Scan until reaching the special marker.
If you move to the right, don't forget to erase the special marker.

(This simulates a Turing machine with a single two-sided tape.)


Using Queues for a Stack and Stacks for a Queue I was asked a question on how to use a pair of Queues to create a Stack and how to use a pair of Stacks to create a Queue. Any thoughts on how I would do this? Right now I don't even know where to start.

To answer the question in the comment above-

Two queues to implement a stack(Assume Queue A is filled with elements in LIFO order and Queue B is empty):

PUSH: Empty Queue A into Queue B. LIFO order will be persisted in Queue B. Now insert the new element into Queue A. Now empty Queue B into Queue A.

POP: Dequeue from Queue A


Round robin tournament scheduling using divide and conquer I want to scheduling $n$ teams using divide and conquer method for $n \in \mathbb{N}$.My approach is that if $n$ is even divide it to to group $\frac{n}{2}$ and  $\frac{n}{2}$ but if $n$ is odd, add auxiliary team and scheduling $n+1$ team at the end we remove the last team and in table every match between $n+1$ team and others will mark as rest. but for some $n$ like 6 there will be a little problem. we should first schedule table for 3 team, 3 is odd so we should schedule for 4. for scheduling 4 teams we need schedule for 2 team and that's the base case so we have:

\begin{array}{c|ccc}
 & \text{Day 1} & \text{Day 2} & \text{Day 3} \\
\hline
1 & 2 &  &  \\
2 & 1 &  &  \\
3 & 4 &  & \\
4 & 3 &  &
\end{array}

now we should conquer the result. upper side of table didn't play with down site of table so we should schedule their matches, and remove team 4. then we have

\begin{array}{c|ccc}
 & \text{Day 1} & \text{Day 2} & \text{Day 3} \\
\hline
1 & 2 & 3 & - \\
2 & 1 & - & 3 \\
3 & - & 1 & 2\\
\end{array}

now we have table for 3 teams it's time to schedule 6 teams so we create table like this

\begin{array}{c|cccccc}
 & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\
\hline
1 & 2 & 3 & - & & & \\
2 & 1 & - & 3 & & & \\
3 & - & 1 & 2 & & & \\
4 & 5 & 6 & - & & & \\
5 & 4 & - & 6 & & & \\
6 & - & 4 & 5\\
\end{array}

for conquer step we should schedule match for upper side of table with down side so then

\begin{array}{c|cccccc}
 & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\
\hline
1 & 2 & 3 & - & 4 & 5 & 6\\
2 & 1 & - & 3 & 5 & 6  & 4 \\
3 & - & 1 & 2 & 6 & 4 & 5 \\
4 & 5 & 6 & - &1 &2 &3 \\
5 & 4 & - & 6 &2 & 3& 1\\
6 & - & 4 & 5 & 3 & 1 & 2\\
\end{array}

but it's not best answer and we can reschedule rest matches such that tournament end in 5 days for $n = 6$. how can I modify conquer step?

The recursive approach is not necessarily the simplest one here. There is a simple direct construction I am quoting from here. Suppose first that you are trying to schedule $n$ teams, where $n$ is odd. In total there are $n(n-1)/2$ matches to schedule, and in each round at most $(n-1)/2$ matches can take place, so there should be $n$ rounds in total. All computations below are modulo $n$. In round $r$, team $x$ plays against team $r-x$, except for team $r/2$, which stays out. Here is an example for $n=5$:

Round 0: 1–4, 2–3, 0 sits out
Round 1: 0–1, 2–4, 3 sits out
Round 2: 0–2, 3–4, 1 sits out
Round 3: 0–3, 1–2, 4 sits out
Round 4: 0–4, 1–3, 2 sits out

It's easy to prove the correctness of this schedule. Indeed, teams $x$ and $y$ meet in round $x+y$ and in no other round.

If $n$ is even then there are $n(n-1)/2$ matches to schedule, and each round at most $n/2$ can take place, so there should be $n-1$ rounds. Indeed, we take the schedule for $n-1$, and pair up the team sitting out with the extra team. For example, for $n=6$:

Round 0: 1–4, 2–3, 0–5
Round 1: 0–1, 2–4, 3–5
Round 2: 0–2, 3–4, 1–5
Round 3: 0–3, 1–2, 4–5
Round 4: 0–4, 1–3, 2–5

It's again not hard to prove the correctness of the schedule. If $x,y \neq n-1$ then they meet in round $x+y$, while $x$ and $n-1$ meet in round $2x$ (where all computations are modulo $n-1$).


Is an expression in normal form if terminates on normal order but not applicative? Just wondering if something like this...

(λx. y)((λx. (x x))(λx. (x x)))

Would be considered to be in normal form since it terminates with y if done by normal order but does not terminate if done by applicative order

The expression $(\lambda x.y \  (\lambda x.(x \  \ x) \  \lambda x.(x \ \  x)))$
is not in normal form because it can be further reduced using the β-rule.

Also, as you noted, Applicative Order is not a normalising reduction strategy. For the expression $(\lambda x.y \  (\lambda x.(x \  \ x) \  \lambda x.(x \ \  x)))$ it fails to find the normal form. This is because $(\lambda x.(x \  \ x) \  \lambda x.(x \ \  x))$ is a non-terminating argument, it has no normal form, then it will loop forever.

On the other side, Normal Order is a normalising reduction strategy because it will always find the normal form, if it exists of course. In fact this a practical consequence of the second Church-Rosser theorem. For the expression $(\lambda x.y \  (\lambda x.(x \  \ x) \  \lambda x.(x \ \  x)))$ it finds the normal form. In this case, since $\lambda x. y$ is a constant function, it will ignore its (non-terminating) argument.


Christofides algorithm (by hand) I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:

[![enter image description here][1]][1]

Calculate minimum spanning tree T:

[![enter image description here][2]][2]

Calculate the set of vertices O with odd degree in T

Same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O

(as all were odd, this should give us the original graph)
[![enter image description here][1]][1]

Construct a minimum-weight perfect matching M in this subgraph

(I am not sure if I did this right)
[![enter image description here][3]][3]

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

[![enter image description here][4]][4]

This is definitely not right.

What went wrong?

In fact, you have been correct all along. However, you have not finished Christofides algorithm yet.

The next step is "Calculate Euler tour".
In the last picture, you have obtained a multigraph all of whose vertices have even degrees. So it must have an Eulerian path. For example, let us select the Eulerian path A -> F -> A -> C -> B -> D -> E -> D -> A.

The last step is "Remove repeated vertices, giving the algorithm's output".
Removing the second A and the second D on that above path, we obtain a wanted output, A -> F -> C -> B -> D -> E -> A. Done.

Please note it is not very meaningful to apply Christofides algorithm on the given graph.

"The Christofides algorithm is an algorithm for finding approximate solutions to the travelling salesman problem, on instances where the distances form a metric space (they are symmetric and obey the triangle inequality". The given distances do not obey the triangle inequality, since d(B,D) + d(D, E) = 1 + 4 < 6 = d(B,E). Moreover, the (direct) distance between A and B is not given, raising doubt whether this is a travelling salesman problem at all.


Size of framebuffer lookup table If the frame buffer has 8 bits per pixel and 8 bits are allocated for  each of the R, G, B components, what would be the size of the
      lookup table?
      a) 24 bytes
      b) 1024 bytes
      c) 768 bytes
      d) 256 bytes

I read about Framebuffer and what I understood is

"It stores the color values (in case of color frame buffer) in indexed form. So if we have $8-bit$ color, then possible colors are  $2^8$*So frame buffer would store color values for each pixel on screen and it's size would depend on screen resolution. Corresponding actual color values (or codes) would be stored in lookup table"

So, Lookup table would have
$2^8 = 256$ entries, which is $256$ bytes, since each entry is of 8-bits = 1 byte.

But that is not the correct answer to above question. So, can anyone tell, where am I going wrong ?

Also, question says frame buffer has 8-bit per pixel and 8-bits are allocated for each RGB , This means for each pixel, frame buffer has $8,8,8,8$ bits allocated ?

Assuming that by framebuffer they really mean palette table, then the table consists of 256 entries, each encoding an RGB color ("true color"). An RGB color takes 24 bits (3 bytes), 8 bits per color component, so in total we need 256$\times$3=768 bytes. That said, it may be easier to access the table if each color takes up an entire dword (32 bits, 4 bytes): for example, indexing could be for free in certain processors. In that case the table would take up 256$\times$4=1024 bytes. However, given the data at your disposal, the best guess would be 768 bytes.

Palette tables are most celebrated for their use in the popular GIF format. GIF uses a color palette consisting of 256 colors (in its most popular version), one possibly being reserved for "transparent", and the colors themselves are stored separately, usually as "true color" 24-bit values. The color table indeed uses 3 bytes per color, for a total of 768 bytes.


Is Goedel's 1st theorem not algorithmically derivable? First let me explain what I mean by algorithmically derivable.
An algorithm must be able to come up with the proof without prior knowledge of the proof, in the same way mathematicians and computer scientists are able to create new proofs without prior knowledge of the proofs.

Our proof deriver enumerates all possible axiomatic systems, and with each system enumerates all possible proofs.
It checks each proof to see if it proves Goedel's 1st theorem.
This algorithm will necessarily derive all finite proofs eventually.

Goedel's 1st theorem states no sufficiently powerful axiomatic system can be complete and consistent at the same time.
The deriver is complete, since it will eventually be able to prove all true statements and disprove all false statements.
This means the deriver is inconsistent, so it cannot know whether a set of axioms used to prove Goedel's 1st are consistent.

Therefore, an algorithmic deriver is unable to derive the proof for Goedel's 1st theorem.

Does this proof succeed in showing Goedel's 1st theorem is not algorithmically derivable?

Your reasoning is incorrect.

It is true that your hypothetical "proof deriver" cannot derive all true statements. No proof derivation system can, and indeed, it is not even possible to express the set of true statements in arithmetic, which is a consequence of Tarski's theorem on truth, itself a consequence of Gödel's theorem.

However, your algorithm does enumerate all provable statements, including the incompleteness theorem itself.

In fact, here's a much simpler algorithm:

Print a formal proof of the incompleteness theorem.
Halt.

So you need a much subtler argument to prove that computers can't do what humans can do in terms of proofs. Certainly you would need a better notion of what "prior knowledge" of a proof means. Indeed, many people today believe that there are no tasks which are fundamentally impossible for computers but possible for humans, and I know of no unassailable argument for that position.


Transitive closure of a directed graph (reachability) algorithm intuition/explanation Consider $n\times n$ matrix $T$ which represents transitive closure of a directed graph. That means $T_{uv}=1$ if and only if there exist a directed path between vertices $u$ and $v$. Initially, $T$ is a identity matrix (every vertex has a self-loop). Now consider following function:
function insertEdge(u, v):
  for x from 1 to n:
    if T[x][u] == 1 and T[x][v] == 0:
      for y from 1 to n:
        T[x][y] = max(T[x][y], T[v][y])

This function adds a directed edge from $u$ to $v$, while maintaining the transitive closure of the matrix $T$. However, I have no idea how and why this algorithm works. So I'll be glad for any intuition or explanation of this algorithm.

What the algorithm is doing is updating all $T[x][y]$.
Assume that $T$ is transitive and that a new edge $(u,v)$ is added. Which pairs $(x,y)$ would need updating? Well, those pairs for which adding $(u,v)$ creates a new path from $x$ to $y$.
Assume that we are in a case that doesn't enter the IF. If it is because $T[x][u]\neq 1$ then there was no path to go from $x$ to $u$. So adding $(u,v)$ will not help getting from $x$ to $y$.
If $T[x][u]=1$ and $T[x][v]=1$, then the new edge $(u,v)$ doesn't really change anything in terms of being able to get from $x$ to $y$.
So, the cases excluded by the IF are cases that don't need updating anyway.
Assume now that you are in a case that does enter the IF. So, $T[x][u]=1$ and $T[x][v]=0$.
If $T[x][y]=1$ we already were able to get from $x$ to $y$ before adding $(u,v)$. The maximum returns $1$. So, the value of $T[x][y]$ is not changed and still is $1$ after the loop exits.
Assume that $T[x][y]=0$. If we consider a $y$ such that $T[v][y]=1$, then that means that we can go from $x$ to $y$ by going from $x$ to $u$, from $u$ to $v$ using the newly added edge, and from $v$ to $y$. Precisely in this case the maximum will also result in $1$. To $T[x][y]$ gets updated to $1$.
Now, if the inned loop lands in a $y$ such that $T[x][y]=0$ and $T[v][y]=0$, that means that we originally were not able to get from $x$ to $y$ by paths not using the edge $(u,v)$. Any path that uses the newly added edge $(u,v)$ would have to go from $x$ to $u$, then $u$ to $v$ and finally some path from $v$ to $y$. This last part of the path can be assumed consisting entirely of edges different from $(u,v)$ by taking the portion starting from the last time that the supposed path leaves $v$. But the assumption $T[v][y]=0$ means that this path doesn't exist. So, there is no way to go from $x$ to $y$, and in fact the maximum in the code results in $0$ in this case.
So, that covers all the cases.


Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL I want to prove that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a Context Free Language.
so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free Languages but have not been successful yet.
Any guidance and explanation would be greatly appreciated.

Suppose that $w$ is in the language. We can write $w$ as a concatenation of runs:
$$
w = a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_m} b^{j_m},
$$
where all indices other than possibly $i_1,j_m$ are strictly positive.
A word of this form belongs to $(a^nb^n)^m$ if all indices are equal. Since $w$ is in the language, there must exist two indices which are different. There are several cases to consider:

$w = \epsilon$.
$i_1 = 0$ and $w \neq \epsilon$. In other words, $w$ starts with $b$.
$j_m = 0$ and $w \neq \epsilon$. In other words, $w$ ends with $a$.
$i_s \neq i_t$ for some $s < t$. The word is thus of the general form
$$ (a+b)^*ba^xb^+(a^+b^+)^*a^yb(a+b)^*, $$
where $x \neq y$.
$j_s \neq j_t$ for some $s < t$. This is similar to the preceding case.
$i_s \neq j_t$ for some $s \leq t$. The word is thus of the general form
$$ (a+b)^*ba^x(b^+a^+)^*b^ya(a+b)^*, $$
where $x \neq y$.
$j_s \neq i_t$ for some $s < t$. This is similar to the preceding case.

Starting with a context-free grammar for $\{a^xb^y : x \neq y \}$ (a standard exercise – separate into cases $x<y$ and $x>y$), you can create a grammar covering all the cases above.


Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication? One is required to find power (positive integer) of matrix of real numbers. There are lots of efficient matrix multiplication algorithms (e.g. some parallel algorithms are Cannon's, DNS) but are there algorithms that are intended exactly for finding power of matrix and that are more efficient than sequential execution of matrix multiplication? I am particularly interested in parallel algorithms.

If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate:

Stage 1: Calculate $M^2$

Stage 2: Calculate $M^3 = M^2 * M$ and $M^4 = M^2 * M^2$

Stage 3: Calculate $M^7 = M^4 * M^3$ and $M^8 = M^4 * M^4$

Stage 4: Calculate $M^{15} = M^8 * M^7$

This is one multiplication more than calculating $M^5$ in three multiplications and raising $M^5$ to the third power in another two multiplications, but should be faster if you have two processors. For arbitrary high powers, you will need more processors.

If you use a brute force algorithm for the multiplication, multiplying row by column, you may save some time by calculating one row of a product, then immediately using that row for the next product. This would help in the calculation of $M^3$ where we can start calculating $M^3$ as soon as the first row of $M^2$ has been calculated; it wouldn't be that helpful with $M^4$ since we need both rows and columns of $M^2$. For large powers, you could probably arrange which powers to calculate.

And after posting this it becomes obvious that you can use multiple processors very easily: You start by calculating the first row of $M^2 = M * M$. When you have that row, you have all the information you need to calculate the first row of $M^3 = M^2 * M$, so you calculate the second row of $M^2$ and the first row of $M^3$ in parallel. Then you can calculate the third row of $M^2$, the second row of $M^3$, and the first row of $M^4$ in parallel and so on.

This will do a lot more operations than necessary (for example, 14 matrix multiplications for $M^{15}$ instead of the minimal 5 or the 6 of the four-stage method). If the power is not large compared to the number of processors this will still be faster. But calculating $M^{1000}$ with four processors using this method will be inefficient; doing this in an optimal way would be an interesting problem.

Combining approaches: Using four processors for example, you can calculate AB, ABC, ABCD and ABCDE almost in parallel by calculating each product one row at a time. This allows calculate all four of $M^2$ to $M^5$ using four processors in about the same time as one product with one processor.

Given these four results and the original M, you can calculate four of the matrices $M^6$ to $M^{25}$ in the same time again, provided the matrices are at most five powers apart from each other. So each power up to $M^{25}$ can be calculated in about twice the time of a single processor matrix product.

With these matrices calculated, all matrices up to $M^{108}$ and some more up to $M^{125}$ can be calculated in three times the time of a single matrix product if four processors are available. With k processors this should go up to at least the power $k (k+1)^2$.


How is $A.in$ an inherited attributed in $2nd$ production in $(1) S \rightarrow A_1A_2\{ A_1.in := 1; A_2.in := 2 \}(2) A\rightarrow a\{print(A.in)\}$ Below is an excerpt from the Red Dragon book.

$$(1) \quad S \rightarrow A_1 \quad A_2 \quad\{ A_1.in : = 1;\quad A_2.in : = 2 ;\}$$
$$(2) \quad A  \rightarrow a \quad \{ print(A.in) \}$$
We find that the inherited attribute $A.in$ in the second production is not defined when an attempt is made to print its value during a depth-first traversal of the parse tree for the input string $aa$.

Now the authors define inherited attributes as:
An inherited attribute is one whose value at a node in a parse tree is defined in terms of attributes at the parent and/or siblings of that node.
But in the above excerpt, $A.in$ for the nodes $A$ of the parse is not defined in terms of attributes at the parent or siblings. But rather it is sort of based on itself.

But in the above excerpt, $A.in$ for the nodes $A$ of the parse is not defined in terms of attributes at the parent of siblings.

Yes, it is. The parent of $A\to a$ is $S \to A_1 A_2$. $S$ has two children, both of which are instances of $A$. And the rule for  $S \to A_1 A_2$ assigns values to the inherited attributes of both children.
That's precisely what an inherited attribute is. Inherited attributes (which are inherited from the parents in the parse tree) can be used in the synthesized rules for those non-terminals, which is what is happening in the rule for $A$.


Is the optimal order of graph vertices s.t. minimizes edges to later vertices a well-known problem? I'm a little unfamiliar with graph theory, and I found an interesting problem in my work that I do not know if its already well-known or can be easily mapped to another one. If I were to express the problem more formally:

Given a directed unweighted graph $\langle V,E \rangle$, find a total order between vertices $v_1 < v_2 < \dots < v_n$ such that minimizes $\vert F \vert$, where $F = \{ \langle v_i,v_j \rangle \ \vert\ v_i < v_j , \langle v_i,v_j \rangle \in E \}$. That is find a total order between vertices such that it minimizes the number of edges that go "forward" in the order.

Lets suppose a simple directed graph:

The list of edges would be $[ a \rightarrow b $, $b \rightarrow c$, $a \rightarrow c ]$.

A bad order would be  $b < a < c$, because, for example, $c$ comes after $b$ in the order and we have the edge $b \rightarrow c $. Therefore, $F = \{ \langle b,c \rangle , \langle a,c \rangle \}$, $\vert F\vert = 2$.

A good order would be $c < b < a$, because $b < a$ and $c < b$. This gives $F = \emptyset$ and therefore the optimum: $\vert F\vert = 0$.

I have graphs that are dense, with some strongly connected components, and when trying to solve it using a SMT solver it works really bad with non-trivial instances. My intuition says that it's like a pigeonhole problem. So, my questions are:

Is this a well-known problem in the graph-theory community?
Can be easily mapped to any other problem?
If so, there is any good algorithm to solve it?
Can a good heuristic be computed easily?

Many thanks in advance :)

Your problem can be mapped to problem of finding minimal set of edges $F$ such that $G\backslash F$ is a DAG (each solution for your problem is a solution for this problem and vice versa). This problem is known as minimum feedback arc set problem and is one of Karp's 21 NP-complete problems


How to prove that the time complexity of this algorithm is O($\sqrt{N}$)? int n;
  cin >> n;
  int sum = 0;
  for (int i = 1; sum <= n; i++) {
      sum += i;
  }

If I assumed that $N = 100$, the loop will run $13$ steps, which is almost the square root of $N$, if $N = 10000$, the loop will run $141$ steps, which is almost the square root of $N$, but I don't know how to prove that, I only know it by intuition

The loop iterates $k$ times, where $k$ is minimal such that $\sum_{i=1}^k i>n$.  We know that $\sum_{i=1}^k i = \tfrac12k(k+1)$, so you just need to solve for $k$.


What if p and q are not distinct in RSA Crypto System? What could go wrong? In RSA Crypto System we choose p and q such that they are distinct primes. Calculate n=pq and phi=(p-1)(q-1). Then e is chosen for public key (n,e) s.t. gcd(e,phi)=1

The security of RSA relies on the fact that the best known way to compute $\phi(n)$ is to prime factorize $n$. For $n=pq$, where $p$ and $q$ are large, distinct primes, this is very hard. If instead $n=p^2$, then one could quickly find $p$ by calculating a square root. Then one could calculate $\phi(p^2)=p^2-p$ and break the encryption completely.


Calculating the number of assignments satisfying a general propositional formula I know, for a disjunctive clause of the form $x_1 \vee ... \vee x_i$, the number of assignments satisfying it is simply $2^i - 1$, but what about for a general formula? Is the number of satisfying assignments be calculated polynomially?

In Papadimitriou's Computational Complexity (p. 301), when explaining an approximation algorithm for $k$-MAXGSAT where the input is, over $n$ variables, $\Phi = \{\phi_1, ..., \phi_n\}$ with $\phi_i$ being any general formula involving at most $k$ variables, it is stated that

  ... Each expression $\phi_i \in \Phi$ involves $k$ Boolean variables. Out of the $2^k$ truth assignments, we can easily calculate the number $t_i$ of truth assignments that satisfy $\phi_i$. ...

But I don't find it obvious how one can compute it easily, as even with Tseitin's method, the transformed result of $\phi_i$ wouldn't necessarily be a single disjunctive clause. Where did I go wrong?

As I have mentioned in the comments, being able to determine the number of truth assignments of a generic formula in polynomial time would imply not only $\textbf{P} = \textbf{NP}$ but actually the much, much stronger $\textbf{#P} = \textbf{P}$ (see Yuval Filmus' answer).

What Papadimitriou really means in this context is that the number of truth assignments of each $\phi_i$ depends on the value of only $k$ variables, with $k$ being constant with respect to $n$. Thus, determining the number of truth assignments can be done in constant time (relative to $n$, not to $k$; for a more precise runtime bound, see again Yuval Filmus' answer).

For reference, here is the earlier paragraph from the text (emphasis mine):

  In this problem we are given a set of Boolean expressions $\Phi = \{ \phi_1 , ... , \phi_m \}$ in $n$ variables, where each [...] is a general Boolean expression involving at most $k$ of the $n$ Boolean variables, where $k > 0$ is a fixed constant [...]


How to make smart contracts work in a small network? Suppose we have a small computer network, there are 30 random people who have provided their computers to perform any computational tasks on them. Let's call these 30 computers nodes. We can access any of these 30 nodes arbitrarily, but by the condition of the problem, we do not know whether the node is honest. That is, we can not guarantee that the node will execute exactly the f (x) that we send to it, or that the node will certainly give us the correct answer.

Also, we have, by condition, A and B that want to conclude a smart contract with each other. A smart contract is a code (usually a small one, 15-25 lines long), whose body will certainly execute when a certain condition is set in the code.

In our case, the smart contract says that if event E1 occurs, B will pay A from its account, and if event E2 occurs, then A will pay B (how exactly will the payment in details not be discussed, it will occur within this network, using conventional cryptocurrency algorithms in the classic blockchain, for example).

The problem is that neither A nor B can guarantee if they entrust the execution of the smart contract code to a random node from our network that it will be executed correctly. One node can execute the received code in reverse or not execute at all. So which cryptographic algorithm A and B can use to ensure (statistically) the correct execution of the concluded smart contract? As already mentioned, they can use the services of any of the 30 nodes as you like.

I thought about dividing the smart contract into small parts and dividing them one by one into each of the 30 nodes, but how would this help if some dishonest nodes still execute their code incorrectly? We can easily find a dishonest node and exclude it, but a smart contract must be executed correctly the first time - that is, certainly, and not after the selection of honest nodes. When one of the nodes behaves incorrectly, the entire smart contract will already be executed incorrectly.

One approach is to use a system like Ethereum, Truebit, or their successors.  In Ethereum, every node checks that the smart contract was executed correctly.  In Truebit, there is a sophisticated way to assign the contract to untrusted nodes and check that they executed it correctly.

Another approach is to use trusted hardware, like SGX.

There are probably other options as well.

I suggest reading up on those systems.  There's lots written on them.


What does feedforward inversion mean in the context of convolution and catastrophic codes? i'm reading the article of J. L. Massey and M. K. Sain, "Inverses of Linear Sequential Circuits" (Date of Publication -
April 1968) (here) and i cannot understand - what is "feedforward inversion"?

They give a short description of circles in convolution codes and a little bit description about catastrophic codes (codes that makes an infinite amount of errors on decoding if there was a couple of errors in channel).

Can anyone explain the term "feedforward inversion", and what do they mean by delay in that regard?

P.S. i'm interested in this theme because i want to understand the proof of Theorem 1 in that article, no more.

The paper deals with sequential encoding and decoding of codes. Maybe you have heard of "block codes": these codes take a message $M\in \{0,1\}^k$, perform some computation, and then output a code-word $c_M \in \{0,1\}^n$.(1). A main drawback of encoding systems for such codes is that need to know the entire message $M$ in order to output $c_M$.
This is not the case in convolution code.
Sequential circuits
Convolution codes are usually designed so that there is a very simple and sequential encoding algorithm. By "sequential" I mean that the system reads $M$ bit by bit, and immediately(2) outputs some part of $c_M$. Say, if the rate is $k/n=1/2$, then for every bit of $M$ given as an input to the encoder, the encoding system outputs the next $2$ bits of the codeword (even without knowing the rest of $M$). After the entire input $M$ is fed into the encoder, we will get the entire codeword $c_M$.
This sequential nature of encoding is what the paper means by "feed-forward": you always input the next part of the data, and that's enough for the system to proceed and give output, as a function on the current state of the encoder. This is/was crucial in memoryless implementations (those can't hold the past bits of the message $M$), or implementations that could not wait to have the entire $M$ due to the large delay incurred (those don't know the future bits of the message $M$).
Thus, a "feedforward inverse" is simply a sequential decoding algorithm. ("inverse" is the algorithm that inverses the code, that is, the decoding system).
Delay
The delay $L$ is explained in the first paragraph of the paper:   (below, not a precise quote)

An inverse with delay $L$, for a sequential circuit with $k$ inputs and $n$ outputs [= a decoder for the encoder], is a sequential circuit with $n$ inputs and $k$ outputs, that cascaded with the encoder, yields an overall sequential circuit with delay $L$.

That is, take the encoder, and connect the decoder immediately to the output of the encoder. Now start feeding the input into the encoder. $L$ is the amount of "clocks" until you see the same bit at the output of the decoder.

(1) The alphabet needs not be binary, this is just for simplicity.
(2) Or after a fixed number of clocks.


Describe a data structure to track visitors Given $n$ cities, describe a data structure which supports the following functions:
Init$(n)$ - initializes the data structure in $O(1)$
Visit$(j,i)$ - adds "citizen from city $j$ would like to visit city $i$" in $O(1)$
Favorite($k$) - prints the $k$ most favorite cities in descending order in $O(k)$ (ignore ambiguity such as 2 cities with same amount)

I can't find how to do the last one in $O(k)$, hints would be appreciated.

The idea is to keep a sorted list of non-empty "buckets". Each bucket $v$ is associated to a certain number $n_v$ of people that wish to visit some city and contains all the cities $c$ that wish to be visited by exactly $n_v$ people.
By keeping a suitable set of pointers cities can be moved from one bucket to the next in constant time. To perform a Favorite($k$) operation it suffices to look at the "last" buckets in the sorted list.

The data structure consists of:

A doubly-linked list $L$. Each node $v$ of $L$ is associated to an integer $\eta_v$ and to a (pointer) to an inner list $\ell_v$ of cities $c$ such that exactly $\eta_v > 0$ people want to visit $c$. The integers $\eta_v$ are appear in increasing order when traversing $L$.

An array $N$ of $n$ elements. The $i$-th element $n_i$ of $N$, if initialized, is the number of people that want to visit the $i$-th city.

An array $P^L$ of $n$ elements. The $i$-th element $p^L_i$ of $P^L$, if initialized, is a pointer to the node $v$ of $L$ such that $\eta_v = n_i$.

An array $P^\ell$ of $n$ elements. The $i$-th element $p^\ell_i$ of $P^\ell$, if initialized, is a pointer to the node containing the $i$-th city in the list $\ell_v$, where $v$ is the node of $L$ pointed by $p^L_i$.

Init$(n)$:

Create an empty list $L$. Allocate (but do not inizialize) the arrays $N$, $P^L$, and $P^\ell$ in $O(1)$ time.

Visit$(\cdot,i)$:

If $n_i$ is initialized, delete (in constant time) the node pointed by $p^\ell_i$ from the list $\ell_v$ where $v$ is the node of $L$ pointed by $p^L_i$. If $\ell_v$ is empty, delete $v$ from $L$.  Increment $n_i$.

Otherwise, if $n_i$ is not initialized, set $\eta_i=1$.

Find the node $v'$ of $L$ such that such that $\eta_{v'}=n_i$, if it exists. Notice that $v'$ can only be the node of $L$ following (the possibly just deleted) node $p^L_i$ in $L$.

If $v'$ did not exists, then create it (in constant time).

Add city $i$ to a new node $z$ of $\ell_{v'}$.

Make $p^L_i$ point to $v'$.

Make $p^\ell_i$ point to $z$.

Favorite$(k)$:

Let $v$ be last node of $L$.
While $k>0$ and $v$ exists:

Let $x$ be a pointer to the first node of $\ell_v$
While $k > 0$ and $x$ exists:

Return the city stored in $x$.
Set $x$ to the vertex following $x$ in $\ell_v$ (possibly none).
Decrement $k$

Set $v$ to the vertex preceding $v$ in $L$ (possibly none).


How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight? The theorem states that

$$
H(P)\leq\mathrm{MinACL}(P)<H(P)+1
$$

where, $\mathrm{MinACL}$ means the minimum average code word length of a given information source, i.e. the average code word length of any Huffman coding and $H$ means the entropy of the probability distribution $P$.

Now, the problem is how to show that for any $\epsilon>0$, there is a probability distribution $P$ s.t. $\mathrm{MinACL}(P) - H(P)\geq1-\epsilon$?

(I was given a hint that I can start with a source s.t. $H(P)=\mathrm{MinACL}(P)$ and try to change the probabilities in order to skew the code.}

Em…… I seem to have figured out how to construct a probability distribution to achieve $\mathrm{MinACL}$ as close to $H(P)+1$ as possible. Suppose, for the information source $(S,P)$ with $|S| = 2^l + 1$, $p_0 = 1 - \epsilon$, $p_i = \epsilon/2^l,1\leq i\leq2^l$, a valid Huffman tree could be constructed as follows: First build a full binary tree with $s_i,1\leq i\leq2^l$, as leaves and then make $s_0$ sibling of the root of this binary tree, and child of the Huffman tree root node. This scheme can be justified easily given $\epsilon\in(0,0.5)$. Then, $H(P) = -(1-\epsilon)\log(1-\epsilon)-(\epsilon/2^l)\log(\epsilon/2^l)$ and $\mathrm{MinACL}(P) = (l+1)\cdot\epsilon+1\cdot(1-\epsilon)$.

$$
\lim_{\epsilon\to0}\mathrm{MinACL}(P)-H(P) = 1
$$

(I haven't calculated the limit, but the graph below if of much evidence:
)


Decisional problems vs Optimization problems : NP-COMPLETE vs NP-HARD I'm studying some of computation theory and i encounter a big question mark. I have an optimization problem and i have to proof that is NP-HARD. I know that my problem can be reduced to another np-complete problem so my problem is np-hard. But my question is: why some algorithms are np-hard for the combinatorial version and the same problem transformed in a decision problem are np-complete?

I mean, if i have an optimization problem, is this np-hard because the decision problem can be reduced in a np-complete problem?

NP-hardness is a category that applies to both decision problems and optimization problems. In contrast, NP-completeness is a category that applies only to decision problems.

Here are the relevant definitions:

A decision problem is in NP if it is accepted by some polynomial time nondeterministic Turing machine.
A decision problem is NP-hard if all problems in NP can be reduced to it in polynomial time.
A decision problem is NP-complete if it is both in NP and NP-hard.
An optimization problem "max $f(x)$ subject to $x \in X$" is NP-hard if the decision problem "given $x$ and $y$, does there exist $x \in X$ such that $f(x) \geq y$?" is NP-hard.
An optimization problem "min $f(x)$ subject to $x \in X$" is NP-hard if the decision problem "given $x$ and $y$, does there exist $x \in X$ such that $f(x) \leq y$?" is NP-hard.

The decision problems used to define NP-hardness for optimization problems are known as decision versions of the optimization problems.

One could extend the definition of NP to optimization problems in various ways. For example, we could say that "max $f(x)$ subject to $x \in X$" is in NP if its decision version is in NP. This would also allow us to define NP-completeness for optimization problems. But for some reasons these definitions are not standard.

Let me also mention FNP, an extension of NP to functions.


All strings in which every substring 000 appears after every 1 I found this given problem as follows:
Write a regular expression where all strings in which every substring 000 appears after every 1.
Now, I also found the answer from Illinois university study material which is available online. The given answer is as follows:
(1+01+001)*0*
However, I think this is not the correct answer as the RE can generate the given strings as 1, 10, 1010010 and so many. So the RE is not properly justified to the given problem.
Please, help me to get the correct information. Thanks for your kind consideration.

The formulation

every substring 000 appears after every 1

is extremely ambiguous. However, given the proposed solution, here is how we are supposed to interpret it. Let $w$ and $x = x_0 \ldots x_{m-1}$ be words. We say that $x$ occurs in $w$ at position $i$ if $$w_i w_{i+1} \ldots w_{i+m-1} = x_0 x_1 \ldots x_{m-1}.$$
The language in question consists of all words $w$ such that if $1$ occurs in $w$ at position $i$ and $000$ occurs in $w$ at position $j$, then $i < j$. This means that after the first time that $000$ occurs, the word consists only of $0$s. Therefore we can break words in the language into two parts: the first part doesn't contain $000$ at all, and the second part, which is optional, contains $000$ followed by any number of $0$s.


Should we not reuse constants in tableaux proofs? I am trying to understand the proof of the following using tableaux:
$$
\exists x\forall y.r(x,y) \to \forall x \exists y . r(x,y)
$$

This is how it works out:
$$
(1) \space \exists x \forall y .r(x,y)
\\
(2) \space \lnot(\forall x \exists y . r(x,y))
\\
|
\\
(3) \space \forall y.r(a,y)
\\
(4) \space \lnot \exists y.r(b,y)
\\
(5) \space r(a,a)
\\
(6) \space r(a,b)
\\
(7) \lnot r(b,a)
\\
(8) \lnot r(b,b)
$$

I understand that (4) is derived from (2). However, shouldn't that be
$$
\lnot \exists y.r(a,y)
$$
reusing the constant a which was introduced by (3)? This is because we are expanding the quantifier:
$$
\lnot(\forall ...)
$$

Can anyone explain?

On the contrary, you never want to reuse constants. Each time you witness an existential quantifier, you should use a different constant. For example, consider the following two sentences:

Some integer is even.
Some integer is odd.

You wouldn't want to instantiate them with the same variable.


What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$? For language $L$, we have $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$?

It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $L\in\mathcal{O}(\lg(n))$ or $L\in\mathcal{O}(\mathrm{polylog}(n))$?

Define
$$A := \bigcap_{\varepsilon > 0} O(n^\varepsilon) = \bigcap_{i \in \mathbb{N}} O(n^\frac{1}{i}).$$
This complexity class is analogous to
$$B := \bigcap_{i \in \mathbb{N}} \Omega(n^i),$$
the class of super-polynomial functions, in the sense that if $f$ is strictly increasing, $f \in A \Leftrightarrow f^{-1} \in B$. There isn't a "nice" description of $B$ so you wouldn't expect a "nice" description of $A$.

Note that $e^\sqrt[i]{n} \in B$ so $\log^i n \in A$.


How can context switch affect the modification of a variable? float myTotalAmount=0;
void update(float amt){
    myTotalAmount+= amt;
}

Task A called update(10);

Calculated myTotalAmount+= amt;

Didn't store the value for myTotalAmount; -------X

Task B called update(5);

Can we say X didn't happen due to context switch? or is Task B able to call update method because context switch happened due to some reason before the X?

Overall I am trying to understand race condition.

A context switch is simply the operating system pausing the execution of one process and starting another. As such, context switches are required for any concurrency problem since, if there are no context switches, there's only one process executing so there is no concurrency.

In your example, the race condition occurs because what the function update really does is:

Read the value of myTotalAmount from memory;
Add amt to this value;
Store the result back in the memory.

Context switches at bad times can cause a race if the processes don't protect against that.  Let's say that myTotalAmount currently has value zero.

Process B reads the value of myTotalAmount, which is zero.
Process B calculates the new value 0+5=5.
Context switch.
Process A reads the value of myTotalAmount, which is still zero.
Process A calculates the new value 0+10=10.
Process A writes the value 10 to myTotalAmount.
Context switch.
Process B writes the value 5 to myTotalAmount.

(Note that ordering the steps 13456728 would give the same result.)


What is the explicit definition about the computablity of non-deterministic Turing machine? Given a finite alphabet $\Sigma$. We define the set of all words of finite length to be $\Sigma^{*}$.

A partial function can become a total function with trivial modifications, thus we just consider about the total function.

Is the following definition correct?

We say a function $f \colon \Sigma^{*} \rightarrow \Sigma^{*}$ is computable by a NDTM $M$, if $M$ halts on every input $x \in \Sigma^{*}$ and The run of $M$ on $x$ halts with $f(x)$ written on its tape.

My questions:

1-What is the usefulness of $q_{accept}$ and $q_{reject}$ here？What kind of inputs dose the $M$ accept (reject)?

2-Is the output of the $M$ are the same on input $x$? (the NDTM may choose different transition functions)

3-Do we need require that all branches halt for $M(x)=1$?

Finally, how can we use this definition to solve a function problem or a search problem?

One should not confuse function problems like FNP and FP with the different types of functions computable by deterministic, non-deterministic, alternating, probabilistic, or ... Turing machines.

Instead of starting by looking at functions $f:\Sigma^* \to \Sigma^*$, it is easier to start by looking at functions $f:\Sigma^* \to \mathcal{P}(\Sigma^*)$. A function $f:X\to\mathcal{P}(Y)$ is equivalent with to a subset $R\subset X\times Y$ of the cartesian product of $X$ and $Y$, i.e. to a binary relation.

Since we can assume that the decision problem is already defined, using the decision problem for $R$ gives one reasonable definition for the computable functions (of this form). However, that definition would force the different Turing machines to compute each output-bit separately and independently, which is a small speed penalty. One can allow the different machines to produce the output in a way more suitable to their capabilities, to avoid that penalty.

The more annoying problem is that the form of output is different from the form of input. One could combine that with a stupid translation function $g:S\to \Sigma^*$ for $S\subset \mathcal{P}(\Sigma^*)$ to bring the output into the same form as the input. But if the output was produced in a way more suitable to the different capabilities of the Turing machines, such a stupid translation function might need to be more powerful than desired. Even accepting the small speed penalty would not allow to avoid that problem, since the functions computable by the different Turing machines are often not closed under composition. That problem might be partly solved by using monads (and accepting $\mathcal{P}(\Sigma^*)$ as the form of output), but then the fact that functions computable by deterministic or alternating Turing machines were actually closed under composition gets hidden.


Proof that (A ∪ B)∘C = A∘C ∪ B∘C where A, B and C are languages How can I prove this identity of languages?

My aproach is the following:

Let A, B and C to be languages, and let x to be an arbitrary string.

(A ∪ B) ⇒ x ∈ A ∨ x ∈ B

How do you proceed?

Just keep going. You've written what it means for $x$ to be in $A\cup B$. Now write out what it means for a string $y$ to be in $(A\cup B)\circ C$.  Do the same kind of thing on the right-hand side and relate the two statements you get.


What does every root is at the same level mean My textbook says a "complete binary tree" is a "full binary tree" where every root is at the same level.

My conceptual understanding:

All this time, I was led by my textbook to believe a root is the "top-most vertex" in which all the other vertex are led away from it. So basically I am led to believe there can be only one root in a tree.

Questions:

What does "where every root is at the same level" even mean?

Isn't a root suppose to be at level 0 all the time?

It basically is a typo, every leaf at same level may be the correct words


Can a Turing machine compute the outcome of any machine that is less powerful than a Turing machine? It is known that a Turing machine cannot predict the outcome of another Turing machine. Given a machine $M$ less powerful than any Turing machine (i.e. able to decide less languages, i.e. a subset of langauges, than any Turing machine), does there exist a Turing machine $T$ which can always compute $M$ such that $T(M, x) = M(x)$?

Pick any model of computation, say a class of Arbitrary Automata $\mathcal{A}$, so that $F_{\mathcal{A}} \subseteq \mathrm{RE}$, i.e. this model is sub-Turing-complete.

Since TMs are an admissible numbering and $\mathcal{A}$ is a numbering of some set of (semi-)computable functions, for every $A \in \mathcal{A}$ there is a Turing machine $f(A)$ with $F_A = F_{f(A)}$ -- and we know that this compiler $f$ is computable.

By the existence of a universal Turing machine $U$, we get that $U(\langle f(A) \rangle, x) = A(x)$ for all $x$. Applying the s-m-n theorem gives us a TM $T$ with $T(\langle A \rangle, x) = U(\langle f(A) \rangle, x) = A(x)$.


Union of two finite automata? How do you union of two finite automata as well as establish the transition table for it. I'm unsure of how to properly union the two finite automata. I believe the transition table would look something like this:

state |  a  |  b  |  a,b

x1|  x2 |  x3 |
x2|     |     |  x3
x3|     |     |  x3
y1|  y2 |  y3 |
y2|     |     |  y3
y3|     |     |  y3

I'm to sure how to properly develop the FA for these two diagrams. I would appreciate any links or advice on how to go about this.

Hint from "Introduction to the Theory of Computation" by Michael Sipser (bible of theory of computation):
"We construct $M$ from $M_1$ and $M_2$ (the two original DFAs). To keep track of both simulation with finite memory you need to remember the state that each machine would be in if it had read up to this point in the input. Therefore you need to remember a pair of states...."
Initial states:
The start state will be a state constructed from the two original start states, i.e
$(x_1,y_1)$
Transitions:
What happens with input $a$?
Let's examine the two original automata:
$x_1$ can transition to $x_2$
$y_1$ can transition to $y_3$
Due to these facts we make the transition $\delta((x_1,y_1),a) = (x_2,y_3)$.
Final/Accepting states:
Any state pair $(x_i,y_j)$ where $x_i$ was an accepting state in automata 1, or $y_j$ was an accepting state in automata 2, i.e any state where $x_2$ or $y_2$ is mentioned.
One consequence is that the state we created a transition to i.e $(x_2,y_3)$, will be an accepting state.


Check constraint under some condition in linear programming I would like to minimize linear pseudo-boolean function

$$\mathrm{obj} = \sum_i c_i \mathrm{sel}_i$$

subject to $$\sum_i c_i sel_i \geq \mathrm{Value} \qquad\qquad(1)$$ where

$c_1,\dots c_5, \mathrm{Value}$ are some constants;

$\mathrm{sel}_1,\dots,\mathrm{sel}_5$ are sort of selector variables, $ 0 \leq \mathrm{sel}_i \leq 1$

Everything is pretty straightforward, but I need to check constraint (1) if and only if some of $\mathrm{sel}_i = 1$. In the other words, if $\mathrm{obj} = 0$, that is OK with me, but if some or all of $\mathrm{sel}_i$ are picked up, I need to check $\mathrm{obj} \geq \mathrm{Value}$. Currently I'm using SAT to solve similar problem, but I prefer to study something else. Maybe I need consider different framework for this task? Any directions will be very useful. Thanks in advance.

This can be solved by case-splitting, depending upon whether any of the $sel_i$ are 1 or not, and then solving each case separately.  Each case can then be handled using integer linear programming, so you might like to read about ILP solvers.

There are only two cases.  We'll optimize for each, separately.  The two cases are:

Case 1: No selector is $=1$. In this case, $sel_i < 1$ for all $i$, and the linear inequality can be skipped.  So the problem is to minimize the objective function subject to the requirement that $sel_i < 1$ for all $i$.

You could solve this using an integer linear programming solver, but actually that's shooting a fly with a cannon.  Since each $sel_i$ is required to be an integer in the range $0 \le sel_i \le 1$, this means you know that $sel_i = 0$ for all $i$.  So, this case really covers only one possible assignment to the selectors: the all-zeros assignment.  You can simply evaluate the value of the objective function at $sel_i=0$; in particular, this means that the objective function takes on the value $0$.  So the value $0$ is always attainable.
Case 2: At least one selector is $=1$. In this case, there exists at least one index $i$ such that $sel_i = 1$ for all $i$, and the linear inequality cannot be skipped.  So now we have some kind of knapsack-like problem: we are looking for a sum of a subset of the $c_i$'s that is as small as possible, subject to the requirement that it be greater than $Value$.

This could be handled with integer linear programming.  Each $sel_i$ is an integer unknown, and you have linear inequalities and want to minimize a linear objective function.  Adding the extra constraint $sel_1 + sel_2 + \dots + sel_5 \ge 1$ will ensure that at least one of the selectors is $=1$, as needed for this case.  This means that you could just feed the problem to an ILP solver and see what solution it gives you.

You might be able to find better algorithms, by borrowing techniques used for the subset sum problem or knapsack problem.  In fact, it looks like this is a kind of reverse knapsack.  If we just negate the constants, then we're looking for a subset of the negated constants whose sum is as large as possible, subject to the constraint that it be $\le Value$.  That sounds like a knapsack problem; each negated constant is the weight and value of some object, and $Value$ represents the capacity of the knapsack.  The one twist is that now your objects might have negative weight/value.

Since we're in the special case where weight = value, this is in fact an instance of a subset sum kind of problem.  The decision version of youur problem is: given $\alpha$, we want to know whether there is any subset of the constants whose value is in the range $[\alpha,Value]$.  If we can solve the decision version, then we can serve your optimization problem by using binary search over $\alpha$.


Boolean expression logic law confusion I've been trying to attempt a particular question that I need to translate truth table into boolean expression but I'm completely stuck on one point now.

First, I worked it out by using Sums of product by getting X first.

(I did this by taking the inputs with X = 1)

A'B'C'D' + A'B'C'D + A'B'CD + A'BC'D' + A'BCD' + A'BCD +AB'C'D + AB'CD + ABC'D' + ABC'D

= A'B'C'(D'+D) + A'CD(B'+B) + A'BC(D+D') + AB'D(C'+C) + ABC'(D'+D) (Distributive Law)

= A'B'C' + A'CD + A'BC + AB'D + ABC' (Double Complement Law)

[Currently I'm stuck here and don't know how to proceed]

If you want to obtain a minimal DNF in this way, it is generally a good idea to follow the Quine-McCluskey algorithm (https://en.wikipedia.org/wiki/Quine-McCluskey_algorithm). Otherwise, it is easy to get stuck when you use distributivity to combine each term with just one of several possible partners (if you look at your kmap, this would correspond to arranging the $1$ into pairs in such a way that none of them combine into larger blocks).

One other problem with your computation is that you lost the term $A'BC'D'$ when forming pairs (the reason why you still ended up with five pairs os that $A'BCD$ is covered twice).


How to count the biggest size of the problem during some time period? We assume that time of solving the problem $=f(n)$$\mu$s.
Now we have to calculate how big problem we can calculate for each time periods.

So there are:
$\lg n,
\sqrt{n},
n,
n\lg n,
n^2,
n^3,
2^n,
n!$,

How to calculate size of the biggest problem during those times periods?:
1s,
1min,
1h,
1 day,
1 month ,
1 year,
100 years

I completely don't know how to start.

Freeman,

the answer is somewhat easy and you can do it with a simple calculator. I will assume that $\mu s$ represents a microsecond, i.e., 0.000001 second.

Let's take for example the calculus for $n^2$. You need to answer which value of $n$ makes $0.000001 f(n^2) = time\_limit$. Thus, we have:

$0.000001 f(n^2) = 1 ~~~~~~~~\rightarrow n = 1000 ~~~~~~~~\text{(1 second)}$
$0.000001 f(n^2) = 60 ~~~~~~\rightarrow n = 7,745.97~\text{(1 minute)}$
$0.000001 f(n^2) = 3600 ~~\rightarrow n = 60,000 ~~~~\text{(1 hour)}$
$0.000001 f(n^2) = 72000 \rightarrow n = 268,328 ~~\text{(1 day)}$

You need to compute that for all combinations of time limit and growth factor.
Try writing a simple computer program to compute such numbers and plot all of them like the figure below. Hope you go well on your studies :)

P.S.: This figure was retrieved from here.