In complexity, why do we find upper bounds, not lower bounds?

Lower bounds are of great interest and an active topic of research. However, we tend to be interested in lower bounds for problems and upper bounds for algorithms.

An upper bound for an algorithm is a performance guarantee: the algorithm will not use more than such-and-such an amount of memory or processing steps when run on an input of a particular size. On the other hand, lower bounds for algorithms aren't especially interesting, since most algorithms can be modified to be fast on certain instances and knowing that an algorithm might terminate very quickly isn't often a useful guarantee.

Conversely, any algorithm is an upper bound for the problem it solves. Lower bounds for problems, on the other hand, tell you whether it's worthwhile looking for a faster algorithm than the one you already have. Examples of lower bounds you'll probably be familiar with are completeness results (especially NP-completeness) and the fact that comparison-based sorting takes time  $\Omega(n\log n)$.


Is it possible to give a guarantee about the accuracy of the local time?

No.  No guarantee is possible.  The network latency could have arbitrarily high variance, in which case NTP might be arbitrarily inaccurate.


How to find out if a piecewise function is partially computable?

Page 3 of the book says: "partial function on a set S is a simply function whose domain is a subset of S."

The difference between $H_3(x)$ and $H_4(x)$ are the sets of $B$ and $C$ that you are going to make. for example if you give $B$ such that for all $x$ the other wise don't happen, then $H_3(x)$ will be a total function and we know every total functions are partial functions since $S \subseteq S$.

between $f_1(x)$ and $f_2(x)$ the one is partial computable which gives output for some $x$s in its domain.


How can I write this simple function in mathematical notation?

While you are free to use whatever notation you want, as long as you explain it, it seems that the simplest solution here would be

  $$ score(answer) = \sum_{i=0}^3 POINTS\_TABLE[answer[i]] $$

This should be self-explanatory in most circumstances.


What is the order of the Pancake graph in Given example & what are the properties of Pancake graph?

Based on the example I infer the following structure.

The pancake graph seems to be defined with flipping pancakes in mind. For order $n$ we take all $n!$ permutations of the numbers $1,\dots,n$ as vertices of the graph. The vertices represent orderings of the pancakes, with the topmost pancake listed first, and the other pancakes are listed from top to bottom. The edges represent flips. Take any first $k>1$ numbers in a vertex, and reverse that prefix. An edges is added between those to vertices.
Thus $i_1, \dots, i_k, i_{k+1}, \dots, i_n$ flips to $\overleftarrow{i_k, \dots, i_1}, i_{k+1}, \dots, i_n$.

With $n=3$ there are obviously $3! =6$ vertices. $123, 132, 213, 231, 312, 321$. Each node has degree 2 (i.e., has two neighbours) as I can flip topmost 2 pancakes or all 3 of them. From $123$ I thus have edges to $213$ and $321$. The other edges follow the same rule.

Your example figure has missing edges. All vertices should have three neighbours for $n=4$. So $1324$ should also be connected to $4231$ flipping all the pancakes.

The above diagram have dimension 4.

PS. The pancake graph is important in the context of "sorting by reversal", for instance giving bounds on the number of steps to sort any permutation into the identity permutation. This bound is of course the diameter of the pancake graph. The field has a famous paper by Papadimitrou and Gates (of Microsoft fame).


What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization?

While I suspect that the notion of "bottleneck" has been introduced in an earlier lesson, it's all in the document you link.

Page 8:

  Edmonds and Karp’s first rule is essentially a greedy algorithm:

    Choose the augmenting path with largest bottleneck value.

Page 11:

  For any flow network $G$ and any vertices $u$ and $v$, let bottleneck
  $G(u,v)$ denote the maximum, over all paths $\pi$ in $G$ from $u$ to $v$,
  of the minimum-capacity edge along $\pi$.

This sentence is a bit hard to parse. Unfolded:

Let $P_G(u,v)$ be the set of all $u$-$v$-paths in $G$, and $E(\pi)$ the set of edges that comprise a path $\pi$ in $G$. Then,

$\qquad\displaystyle G(u,v) = \max_{\pi \in P_G(u,v)} \quad \min_{e \in E(\pi)} c(e)$.

Note that $\min_{e \in E(\pi)} c(e)$ is the bottleneck (capacity) of $\pi$.

So Edmongs-Karp picks the $s$-$t$-path with the largest bottleneck (in the residual network), which means it picks the path it can send the most flow over (while maintaining conservation of flows).


It's not correct. As you said, you cannot prove $f$ is polynomial-time computable.

However, you can reduce from a particular NP-complete language, for example, 3SAT. Now $f$ is polynomial-time computable as you can easily write a verifier for 3SAT.


What is the main difference between binary decision tree and binary decision diagram(BDD)?

One is a tree; one is not.  A BDD is a directed acyclic graph (dag), but not necessarily a tree.  This allows a BDD to be more compact, in some cases.

That's the only essential difference.  Of course, they have different properties (that follow from this difference in their definition).


Let us prove that for $m \geq 1$,
$$
T(n,m) = \max(1, 2\lfloor \tfrac{m-1}{(n-1)!} \rfloor - 1).
$$
(This is the same as your formula.)

If $m \leq 2(n-1)!$ then by definition $T(n,m) = 1$, and indeed $\lfloor \tfrac{m-1}{(n-1)!} \rfloor \leq 1$, showing that our formula also gives the value $1$. If $m > 2(n-1)!$, then
$$
T(n,m) = \min_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n-1,a) + T(n-1,b) + T(n-ab).
$$
Since $ab \leq (n-1)!$ also $a,b \leq (n-1)!$, and so $T(n-1,a) = T(n-1,b) = 1$. Therefore
$$
T(n,m) = 2 + \min_{\substack{a,b \geq 1 \\ ab \leq (n-1)!}} T(n,m-ab) = 2 + \min_{1 \leq c \leq (n-1)!} T(n,m-c).
$$
We can prove inductively that $T(n,m)$ is monotone nondecreasing, and so
$$
T(n,m) = 2 + T(n,m-(n-1)!).
$$
From here it's not too hard to prove the formula by induction.


The shunting-yard algorithm was introduced in Dijkstra's article Making a Translator for ALGOL-60 (APIC Bulletin no7, 1961; see this PDF, from p.22; also published in Annual Review in Automatic Programming, 7:3–11, 1963 and available from Science Direct if your institution has a subscription).  Pages 7–9 of the article (pp.28–30 of the PDF) explain how the algorithm works and argue its correctness. It's not a formal proof but it looks like it contains everything you should need to produce one.


Algorithm to replicate human noising of names by creating a categorical distribution given a character, with higher probabilities on similar chars

I will assume, based on the way you presented the problem, that you only care about errors where single characters are replaced with other single characters—as opposed to merging two adjacent characters into a similar-looking single character, splitting a single character into two similar-looking adjacent characters, etc.

One option would be to build a table of confusion likelihood by using an existing OCR algorithm on an MNIST-style dataset of supervised character images. This does not eliminate the lookup table of probabilities, but it avoids having to construct the table by hand.

As I'm guessing you already know, each entry in this type of dataset is an image together with a label for which character that image supposedly represents. A typical neural network trained for this dataset can output, for any image, a score for each possible character that represents the algorithm's confidence that the image represents that character.

Given an image and the OCR algorithm's score of each possible output character, what you want to do is look at the score of each of the wrong outputs, i.e. the scores assigned to characters other than the one listed on the image's label. An image of a lowercase letter L is likely to have a high score not only for lowercase L but also for uppercase letter I, the digit 1, etc. You can average this information over all the images in the dataset [*] to form a score for each character pair $(a, b)$ of "probability of guessing character $b$ when it was actually supposed to be character $a$".

The dataset and OCR algorithm you choose will obviously affect your results. You will probably get different results using a dataset with handwritten letters in plain white on a black background than using a dataset of Street View house numbers (besides the fact that the house numbers only contain digits).

[*] If you are using an ML model that was trained on the same dataset you are using for building the table, you might want to only use the test dataset for building this table rather than also including the training dataset. Even though you would only be using the scores from the wrong outputs here, you want to avoid any possibility of things getting skewed somehow by overfitting.


Reason to learn propositional & predicate logic

I tend to like Unification and anything related to it. If you don't know propositional & predicate logic, then you are skipping the basics of logic. If you have an interest in anything listed, then it would be like having an interest in math and skipping addition and multiplication. Logic is not just for AI.

As a practical answer, remember the Intel floating point problem and how you never see them anymore? Thanks to the use of theorem provers they are a thing of the past. Remember the Microsoft blue screen of death. Thanks to SAT solvers, model checking and other logic based solution, they are an endangered species.


Lazy lists with call-by-value reduction strategy

Have a look at Wadler et al's How to add laziness to a strict language without even being odd. It presents a number of techniques (for Standard ML) and provides a good survey of the literature of the time.

The most naive way is to delay the evaluation of term $t$ by making it, using a term such as $\text{delay }t=\lambda ().t$, and to force the evaluation of such a term by applying it, using a term such as $\text{force }t=t~()$.  For less naive/more systematic approaches, integrated into programming languages, read the paper.


How many different languages over the unary alphabet {a} are recognized by 2-state DFAs?

There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that $Q = \{q_0,q_1\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here is one of them.

Case 1: $\delta(q_0,a) = q_0$. In this case we don't care about $\delta(q_1,a)$, since $q_1$ is unreachable. This case gives the two languages $\emptyset$ and $a^*$, depending on whether $q_0$ is a final state or not.

Case 2: $\delta(q_0,a) = q_1$. Since $F = \emptyset$ and $F = \{q_0,q_1\}$ will give the languages $\emptyset$ and $a^*$, respectively, it suffices to consider $F = \{q_0\}$ and $F = \{q_1\}$. Together, there are 4 machines to consider:

$\delta(q_1,a) = q_1$, $F = \{q_0\}$: the language is $\epsilon$.
$\delta(q_1,a) = q_1$, $F = \{q_1\}$: the language is $a^+$.
$\delta(q_1,a) = q_0$, $F = \{q_0\}$: the language is $(aa)^*$.
$\delta(q_1,a) = q_0$, $F = \{q_1\}$: the language is $a(aa)^*$.

These are the six different languages produced by unary two-state DFAs.


In fortran a dummy argument is what other languages
refer to as a formal argument. So the dummy arguments
are the list of arguments in the function (or subroutine) definition.

The actual arguments are the list of arguments in the calling
list, at the point in the source code where a function is called (ie used).


Proof of value discovery in complete graphs

If I understand correctly, a rough approach could be as follows.

Each processor $p_i$ can read $s_{i+1\ {\sf mod}\ n}$ and write its content to $r_i$.

Then each processor $p_i$ can read the wanted value by reading $r_{i-1\ {\sf mod}\ n}$.

The main issue of this naive algorithm is that some synchronization is needed between the two steps: $p_i$ must not read $r_{i-1\ {\sf mod}\ n}$ too soon, before it is written by $p_{i-1\ {\sf mod}\ n}$.


Create an optimal to express all natural number as an arithmetic expression using the alphabet $\Sigma=\{(,),1,+,\times\}$

You can't prove that your algorithm is correct because it isn't. First counter example is n = 46. If we don't bother writing 2 = 1+1 to make it more readable, your algorithm gives
46 = 2 * (1 + 2 * (1 + 2 * (1 + 2 * 2)))

which uses 13 1's.
A better solution is
46 = 1 + ((1 + 2) * ((1 + 2) * (1 + 2 * 2))

which uses only 12 1's.
The difference is bigger for n = 235 (difference 2), n = 649 (difference 3), n = 1,081 (difference = 4), n = 7,849 (difference = 5), n = 33,793 (difference = 6), n = 221,617 (difference = 8).


Semi-streaming algorithm for $s$-$t$ connectivity

You cannot do it in a single pass. Consider the set of all graphs of the following form: the vertices are $\{s,t\} \cup A \cup B$, where $|A|=|B|=n/2-1$. The only allowed edges are between $s$ and $A$, between $A$ and $B$, and between $B$ and $t$.
Suppose that the algorithm is first presented with the $(A,B)$ edges, and then with the $(s,A),(B,t)$ edges. After reading the $(A,B)$ edges, it must "remember" all of them, since there could be only one $(s,A)$ edge and only one $(B,t)$ edge, in which case the answer depends on whether the corresponding vertices in $A$ and $B$ are connected. Since there are $2^{(n/2-1)^2}$ choices for the $(A,B)$ edges, the algorithm must have a memory of at least $(n/2-1)^2$ bits (since after reading the $(A,B)$ edges, it could be in any of $2^{(n/2-1)^2}$ possible states).


one for loop wraps 2 indexof method, what is the time efficiency?

Yes, you are correct. But time complexity we measure only in big-O notation.

So the code above has time complexity $\mathcal O(n^2)$

The space complexity depends on indexof's space complexity. Assuming it was done with a for loop and a simple comparison, the space complexity would be $\mathcal O(log(n))$ - as the  storing the array length $n$ required $log(n)$ bits, and therefore keeping in memory the index i will take at most that much space.


Confusion about Definition of DPDA and $\epsilon$-move

The deterministic concept in pushdown automata means that next move of automata is determined uniquely.

This concept contains two points.
First, there are no multiple choices in reading an alphabet from the input. For example, you should not have both of following rules is your transition rule

$$\delta(q,a,\alpha)=(p,\beta), \delta(q,\epsilon, \alpha)=(p',\gamma),$$

because you either can choose the first rule (that is $\delta(q,a,\alpha)=(p,\beta)$ ) read the $a$ then go to next state, or you can choose the second one (that is $\delta(q,\epsilon, \alpha)=(p',\gamma)$ ) do some other job before reading $a$ by $\epsilon$-transition. In the other words your choice in reading $a$ is not unique.

The second point of the definition is that you should exactly know what to do when you are reading an alphabet. Pay attention that the definition says $$\forall q\in Q, a\in \Sigma, x\in \Gamma,$$ which means there should be no ambiguity when you read an alphabet. For example, in above state diagram, one of the undefined rules is $\delta(q_3,0,x)$, where $x\in \Gamma$. Of course, this undefined rule is not important in our intuition that the PDA works correctly, but if we want to satisfy the definition of DPDA, then we should not let machine crash in the middle of reading an input. In the other words, the DPDA should read all characters of its input, then stop either in final state or non-final state.

I hope the above explanations help you in understanding Deterministic pushdown automata.

Now let's take a look at your first question. You've asked is it possible to stop at two states with the same string? The answer is no.  I want to draw your attention to this part of definition again that says $\forall q\in Q, a\in \Sigma, x\in \Gamma.$ You missed the second point in the concept of determinism in the definition, that is you should define the rule $\delta(q_2,\epsilon,\$)$ for your DPDA. If we define $\delta(q_2,\epsilon,\$)=(\epsilon,q_4)$ and assume $q_4$ be the only final state, then the problem you arose will be solved.

To answer your second question, the definition allows $\delta(q,\epsilon,\epsilon)$ mostly because of the first transition rule. You will find some different definition for DPDA in some other books which handle the first transition rule in some other ways. For example, some people agree that at the beginning we already have $\$$ on the stack.

your statement about $q_4$ is ok.


Simple, I don't know if you want the full answer but here is my proof:

We know that
"A language is CF iff a PDA recognized it", and you know that this proof has two directions, I won't prove it here either.
We can answer your question if we proof: "Any PDA has an equivalent TM".

IDEA:

Let state a TM M and a PDA P.

We know that any operation in P has the following format:
a, b -> c, where a is the item you have at the input, b is at the top of the stack and c the symbol I want to put at the top of the stack.
We can simulate all the possible operations of P on M and the stack on the tape.

How? P will be simulated on two tapes: one for reading the input and the other for simulating the stack ( we still can simulate on a single-tape TM, since any k-tape TM can be turned on a single one tape TM.) by adding elements to the tape and erasing them as we need. The blank symbol will now be allowed as part of the input symbols $\Sigma$ (so that we can "use" the pop instruction of a PDA).

(I won't go through this but if you want me to, I can rewrite it later).

PROOF:

We know by definition that P has the formal description:

"P is a 6-tuple(Q, $\Sigma ,\Gamma,\delta, qo, F$) where:

Q is a set of states,

$\Sigma$ is a finite set called the input set,

$\Gamma$ is a finite set called the stack set,

$\delta$ is a finite subset of $Q \times  (\Sigma \cup\{\varepsilon\})  \times \Gamma \times Q \times \Gamma^* $, the transition relation.

q0 E Q  is the start state,

F $\subseteq$ Q is the set of accepting states.

"

Great, now we'll make a transition algorithm that any TM can be turned into an AP, simply put:

Given an TM M, we'll create the formal transition to make an equivalent PDA:

1st step: We add the state "idle" on M, which is simply move to the left, do nothing, move to the right, do something.

2nd step:
For every transition of P (a, b -> c), we'll create an equivalent in M $\delta$.

3rd step: The accept state will only happen if we erase the initial symbol of $\Sigma$ and the reject state if the input ends.

I think you'll get the idea, sorry for my english mistakes, if you want to make improvements, you are free to do so.


What you have (after generating the keys):

$$ \gcd(p, q) = 1 $$
$$ N = pq $$
and a number $e$ and it's inverse $d$, modulo $\phi(N)$. That is:
$$ ed \equiv 1 \pmod{\phi(N)}$$

Encryption:
$$ c \equiv m^e \pmod{N}$$
Decryption:
$$ m^\prime \equiv c^d \pmod{N} $$
$$ m^\prime \equiv (m^e)^d \equiv m^{ed} \pmod{N} $$

We don't yet if $m^\prime \equiv m$.

Well... you can use Euler's Theorem:
$$ a^{\phi(N)} \equiv 1 \pmod{N}, \text{ if } \gcd(a,N) = 1. $$

Write $ed = 1 + k~\phi(N)$:
$$ m^\prime \equiv m^{1+k\phi(N)} \pmod{N}$$
$$ m^\prime \equiv m\cdot m^{k\phi(N)} \pmod{N}$$
$$ m^\prime \equiv m\cdot \underbrace{m^{k\phi(N)}}_{1} \pmod{N}$$

So $m^\prime \equiv m \pmod{N}$.


I'll start with your last question (in the comments); namely "Why doesn't x = y satisfy the initial problem".

The answer is in the quantifiers. Read from left to right. It starts with "there exists" X. So pick an X in your head. Say X = 5. We can not pick Y here because it doesn't have a value yet and we MUST pick a value for X NOW. Now proceed to read the next quantifier which reads "for all Y". Oops. We can't say for all Y because we already set Y = X.

Actually if you are going to look for a solution that satisfies the original formula, it should be of the form "X=(some positive integer)", with Y not involved at all, as it is a bound variable (as opposed to being a free variable which we can choose).

However, the formula says "there is a (single, and specific) positive integer X which all integers are less than or equal to it" which is clearly false because given any positive integer X, X+1 is a positive integer which is not less than nor equal to it (which is what the negated formula says!).


Existence of a function between two functions $f$ and $g$ where $f \in o(g)$

Yes.
For example, let $h=\sqrt{fg}$, assuming $f$ and $g$ are positive.
If not, we can let $h(x)=\max(\sqrt{|f(x)g(x)|}, g(x)/(|x|+1))$. The term, $g(x)/(|x|+1)$ makes sure that $h(x)$ will stay positive eventually.

Exercise. For each two functions $f$ and $g$, where $f \in \omega(g)$, there exists a function $h$ where $f \in \omega(h)$ and $h \in \omega(g)$.


Winning strategy of Nim game when picking from multiple piles is allowed

The answer assumes that you have to take the same amount of stones from each pile that you choose. Otherwise the first player always wins as long as the piles are not all empty.

The rule "xor = 0" doesn't work. In particular, there is a winning position with xor = 0 (easy exercise; be creative).

In order to analyze the game, you can compute which positions are winning and which are losing recursively (surely you have been shown how to do that in your course). Then you can look at which positions are winning and which are losing, and try to guess a rule; you will then need to prove that your rule works.

In this particular case, however, the analysis will be quite difficult. The case of two piles is known as Wythoff's game, and is already pretty non-trivial to analyze.


Find hamilton cycle in a directed graph reduced to sat problem

Just add the constraint that $x_{1j}=x_{nj}$ for all $j$, and make a special exception to constraint 2 so that you omit constraint 2 in the case where $i=1$ and $k=n$.

Everything works fine for a directed graph.  You just need to interpret constraint 5 appropriately.


The NL algorithm for $s$-$t$ connectivity proceeds as follows. Start at $s$. For $n-1$ steps, guess a neighbor of the current node, and accept if that neighbor is $t$. The memory requires is two vertices (the current one and the next one), and a counter that counts the length of the current walk.

If you want to check that there is a simple $s$-$t$ path of length at least $n/2$, you need some way to ensure that in the process, vertices don't repeat. It's not so clear how to do that without storing all vertices visited so far, which cannot be done in logspace.


D.W.'s advice to consider some small examples is excellent.  Two great examples to start with are an isolated vertex and a single edge!  Once you can how the construction transforms vertices and edges, you know what happens to the building blocks.

Also, some familiarity with the basics of these constructions helps.  In particular, any time you see "Let the vertex set of the new graph be $V\times S\,$" for some set $S$, you should think: "Take a copy of $V$ for every element of $S$, and label each copy with the element it's associated with."  So, here, the vertex set of $H$ is two copies of $G$'s vertex set: one labelled $0$ and one labelled $1$.  Now, look at the edges.  The first set of edges says, "For every vertex $v\in G$, add an edge from copy $0$ to copy $1$." The second set says, "For every edge $(x,y)\in G$, add an edge from copy $1$ of $x$ to copy $0$ of $y$."


What is the difference between a collection of Turing Machines and a family of Circuits?

What you describe is essentially Turing machines with advice, the advice for length $i$ being simply the description of $T_i$. It is a classic result that the two models are equivalent in the case of poly-time TMs and poly-sized circuits, that is, both produce the same class $\mathsf{P}/\mathrm{poly}$. If the description length of $T_i$ is allowed to be arbitrary, there is also no computational power to be gained since you can then express all Boolean functions for each length (just as with circuits).


How best to statistically verify random numbers?

You can't.  Randomness is a property of the source, not a property of the values you get from that source.  In other words, randomness is a statement about the probability distribution, not about some specific values sampled from that distribution; from a finite sample, you can't give a definite answer to your question.

Or, to quote Dilbert:

What you can do is perform some kind of statistical test, with the properties that (a) if it is truly random, it'll probably be accepted, (b) if it is not truly random, it might be accepted or might be rejected (no guarantees).  In other words, if the statistical test rejects it, then odds are it wasn't random.  However, if the statistical test doesn't reject it, you can't conclude anything -- it might be random, or it just be a good enough mimic to fool that one statistical test.  Such statistical tests are often sufficient that they can reject many obviously-bad generators.

If that sounds like the kind of thing you're looking for, look up the DIEHARD test suite and related tools.

See also How can it be detected that a number generator is not really random?.


There is an implicit (trivial) reduction, from each instance of the restricted version to itself, really just relabelling it as an instance of the unrestricted problem.

To give an example that I think is more illuminating than Partition and Multiprocessor Scheduling, we can look at Vertex Cover and Hitting Set:

  Vertex Cover
  Input: A graph $G=(V,E)$, a positive integer $k$.
  Question: Is there a set $V'\subset V$ of size at most $k$ such that for every $uv \in E$ either $u\in V'$ or $v\in V'$ or both?

  Hitting Set
  Input: A hypergraph $H=(X,E)$, a positive integer $k$.
  Question: Is there a subset $X'\subseteq X$ of size at most $k$ such that for every $e \in E$ there exists an $x \in X'$ such that $x \in e$?

So we can easily see that Vertex Cover is just Hitting Set where the size of the edges is exactly two. As Vertex Cover is NP-hard (indeed, complete), Hitting Set must also be NP-hard. As Hitting Set is also in NP, it is therefore NP-complete.

So we have a "reduction" from Vertex Cover to Hitting Set, but it's just the identity mapping. The graph remains unchanged (as does $k$), we just call it a hypergraph, and call the edges hyperedges.

To think about it from the other end, if we have a problem $\Pi$ where a restricted subproblem $\Pi'$ is already NP-hard, and we had a PTIME algorithm for $\Pi$, then we could use it to solve all the instances of $\Pi'$ in polynomial time and hence everything in NP would have a polynomial time algorithm. Thus $\Pi$ must be NP-hard (and if $\Pi \in$ NP, NP-complete).


Can you generate random linear programming problems?

Sure, of course you can create random linear programming problems.  Why not?

Yes, in general, you can usually verify the solution to a linear programming problem faster than you can find the solution.  Verifying the solution just involves plugging into the equations and checking that all equations hold.  Finding the solution requires a bit more work (e.g., the simplex method, interior point method, ellipsoid method, something else).

However, as you may know, linear programming problems can be solved in polynomial time, and solutions can be verified in polynomial time.  Therefore, the difference between "time to solve" and "time to verify" is not as huge as for (say) NP-complete problems.

The best way to check that a linear programming problem is solvable is to solve it.  If you want a slight improvement, you can simply test whether the constraints admit any feasible solution.  The way you test feasibility is by omitting the objective function (or replacing it with a trivial objective function) and giving it to a LP solver; the solver will then tell you whether the linear program has a feasible solution or not.  If it has a feasible solution, then it is solvable; if it doesn't have any feasible solution, it isn't solvable.  In practice, testing for feasibility might be somewhat faster than solving it, for many problems.  However, there are no guarantees.  Based on theoretical work, we know that the worst-case running time to test for feasibility is approximately the same as the worst-case running time to find the optimal solution.

I know of no perfect way to test how difficult they will be to solve, other than solving it.  In practice, though, linear programming solvers are so efficient that a problem of the sort you list (with half a dozen variables and a dozen or so constraints) will be solved almost instantaneously, no matter what values you use -- so there is no point in trying to figure out how difficult it will be to solve.


Is order of matrix multiplication affecting numerical accuracy of the result?

Yes, there are differences in accuracy since with machine numbers the usual properties of arithmetics don't hold.

Machine numbers are defined as
$$ F(\beta,t,m,M)= \{ 0 \} \cup \{ x \in \mathbb{R} : x = sign(x)\beta^{p} \sum_{i=1}^{t}d_i\beta^{-i},\ 0 \leq d_i \lt \beta\ ,\ d_1\ne 0\ , -m \le p \le M  \} $$ and represent the subset of $\mathbb{R}$ that your machine is able to represent.

All other numbers must be approximated with a number in this subset (usually by truncating the numbers or rounding them).

Let's assume we are in $F(10,2,m,M)$ meaning we are working in base 10 with two digits.

Let $x=0.11*10^1$, $y=0.31*10^{1}$ and $z=0.25*10^{1}$.

The associative property of multiplication doesn't hold:

$(x*y)*z = 0.34*10^1 * z = 0.85*10^1$

and

$x*(y*z) = x * (0.78 * 10^1)  = 0.86*10^1$

other properties that don't hold are:

the associative property of the addition
distributive properties
$x(y/x)$ isn't always equals to $x$
if $xy=yz$ then isn't always true that $x=z$


Embedding trees of diameter four is NP-hard

It is reducible from Independent Set in cubic graphs.

Given a cubic graph $G(V,E)$, construct a bipartite graph $\mathcal{B}(V\dot{\cup}E,\mathcal{E})$, where $$\mathcal{B}(\mathcal{E})=\{(u,e)|u\in V\ \mathrm{is\ incident\ to}\ e\in E\}$$

Create a new vertex $r$ (the root), connect it to all $V$-vertices in $\mathcal{B}$.

Now, if the IS instance asks for an independent set of size $k$, we create $T$ of diameter $4$ as follows:

Make a new vertex $r_T$ as root of $T$. This vertex would have $k$ children. Each of these $k$ children would have $3$ leaves attached to it.

Our reduction then outputs the instance $\mathcal{B},T$ of $\mathrm{TREE\ EMBEDDING}$ problem.

Note that $k>10^9$, otherwise the vertex cover can be decided in polynomial time. So, if there exists an embedding, $r_T$ must be mapped to $r$.

Since all the leaves are pairwise distinct. The image set of $k$ children of $r_T$ is the independent set.


Why do we need/use operator precedence for Arithmetic operators?

As you note, there is no need for operator precedence. There are a number of other conventions that have been used in various contexts. A few programming languages have implemented the left-to-right convention you mention in the question, and a larger number have avoided the problem entirely by using Polish notation or its reverse.

The purpose of operator precedence conventions is to reduce the number of parentheses that are required to unambiguously communicate ideas that occur in practical mathematical usage. The most important rules—that multiplication has a higher precedence than addition, and exponentiation has a higher precedence than multiplication—exist primarily for the convenience of writing polynomials. Without these rules, polynomial expressions would require far more parentheses. Polynomials are so central to mathematical practice that they bleed into the notation, in operator precedence and elsewhere.

Rules for operator precedence beyond the basic arithmetic and relational ($=$, $\leq$, etc.) operators are domain-specific, and authors of papers occasionally have to specify the convention they are using in their notation section. Again, the purpose of having such rules is to improve communication in situations where specifying a convention that the reader has to remember is better than writing parentheses everywhere.

When precedence rules are standardized across an entire mathematical field, it is often because the rules have a clear analogy to arithmetic or relational operators on numbers. For example, concatenation has a higher precedence than union in regular expressions because the regular languages form a semiring, just like all your favorite number systems, and regular expressions are polynomial expressions in this semiring.


You have your quantifiers wrong. The ~ should be on the outermost level. That is:

~(forall x y z, {P x y z} + ~{P x y z})

i.e. to prove it's undecidable, you assert that there's no function which decides every instance. There may be functions which decide particular instances, which your type would rule out.

If you add LEM to MLTT, you can still have a perfectly good logic system, but provability in this logic no longer implies decidability.

Moreover, even the type I've listed above isn't sufficient: just because a problem isnt' expressible in MLTT or COC or any other non-Turing-complete logic, doesn't mean that it's undecidable.

A better approach would be model Turing Machines or (even better) a Turing Complete Lambda Calculus in your language, and assert that there are no functions in this model that always halt and answer your problem. This way, you're not trying to use your logic to reason about decidability within that logic, but an external model.

If you want an easier way, you could provide a function that takes as a parameter a function of type forall x y z . {P x y z} + ~{P x y z}, and returns a decision procedure deciding a commonly undecidable problem. (My favorite is Post's Correspondence, simulating a 2-counter machine is also an easy one). This reduces the trusted base of your proof: now the reader only needs to believe that PCP or 2CM is undecidable in order to see that your problem is.


Efficent deterministic algorithm to sort n numbers with many duplicates ( distinct integers $O(\log n)$)

How much time does it take to make $\Theta(n)$ queries in a Red-Black Tree with size $O(\log n)$ ?
A detailed solution follows:

Let $T$ be a new empty self-balancing search tree storing pairs of integers, where the order property is w.r.t. the first element of each pair. For each element $A[i]$ of the original array, query $T$ for a node which first element is $A[i]$. If there is no such node, insert a new node $(A[i], 1)$; otherwise, update the node $(A[i], m)$ with $(A[i], m+1)$.
After you are done with all the elements in A, clear $A$ and visit $T$ in-order. For each node $(x, m)$ of $T$, append $m$ copies of $x$ to $A$. Correctness is trivial, and to prove the complexity bound it is sufficient to observe that at any given time the size of $T$ is $O(\log n)$.


Why do they say `A, B, C, ... implies M` instead of `A∧B∧ C∧ ... implies M`?

It's a distinction between language and metalanguage.

$A, B \vdash M$ says: if I have both $A$ and $B$ amongst my hypotheses, then I can deduce $M$.
$A \wedge B \vdash M$ says: if I have $A \wedge B$ amongst my hypotheses, then I can deduce $M$.
The fact that the two are equivalent comes from the definition of the operator $\wedge$.

I could define a new operator $?$ with these deduction rules (using the sequent calculus formulation):
$$
  \frac{A \vdash M}{A ? B \vdash M} \qquad
  \frac{B \vdash M}{A ? B \vdash M} \qquad
  \frac{\vdash A, M \quad \vdash B,M}{\vdash A?B,M}
$$

This new operator has the same rules as $\wedge$ (in the sequent calculus), so I could substitute $?$ and $\wedge$ in a true judgement and still get a true judgement, and vice versa. Nonetheless, they are syntactically speaking two different propositions.

It takes a while to internalize the difference between the language and the metalanguage, especially in the beginning when you only study a logic which models our everyday reasoning. There are logics such as intuitionistic logic and linear logic which diverge further, and while these logics (especially linear logic) are more advanced, they are in some ways easier to handle because there is a clearer separation between the logic and the meta-logic.

I'll briefly discuss “and” in linear logic, to illustrate this point. To put it in a nutshell, in everyday logic, if you have a hypothesis, you can use it at multiple points in a proof. In linear logic, a hypothesis can only be used once, unless it's marked as reusable. Linear logic can thus model processes that aren't proofs as you think of them, but more physical processes, such as “if I have a cake before eating it, then I have no cake after eating it”. Linear logic has two conjunction operators. Both say: if I have a process that produces an $A$, and I have a process that produces a $B$, then I have a process that produces an $A$ “and” a $B$. They differ in how the processes are combined:

Multiplicative conjunction puts the two processes next to each other: given $\vdash \Gamma, A$ and $\vdash \Delta, B$ (a process that produces an $A$ and some more stuff, and a process that produces an $B$ and some more stuff), I can combine them to make $A \otimes B$ and the combined output of the two processes: $\vdash \Gamma, \Delta, A \otimes B$. For example, if I make a plate of spaghetti and an apple pie, I can eat a plate of spaghetti and an apple pie.
Additive conjunction runs the two processes together: given $\vdash \Gamma, A$ and $\vdash \Gamma, B$ (I can run the process and produce $\Gamma$ plus either $A$ or $B$), I can run that same process and produce both: $\vdash \Gamma, A \& B$. For example, if I can spend \$10 to get a plate of spaghetti or I can spend \$10 to get an apple pie, then \$10 gets me the choice of spaghetti or pie (but it doesn't get me $A \otimes B$, where I have both spaghetti and pie).


If you need four bit changes to change from A to B, then you can make two bit changes from A to some A' followed by two more bit changes from A' to B. If you receive A' then you don't know whether it is a double bit error coming from A, or a double bit error coming from B. Therefore, you cannot fix double bit errors.

Since four bit errors are needed to go from one valid code to another, you can detect double bit errors.

You also have the choice of either fixing single bit errors and detecting double bit errors at the same time (assuming that there will be no triple bit errors), or detecting triple bit errors. You cannot both fix single bit errors and detect triple bit errors, since I can get the same result by changing a single bit in A and changing three bits in B.


How are image files, sounds, data, etc. compiled/linked in to a single file?

A file is just a file. Any given sequence of bytes can be interpreted as instructions for the CPU, pixels of a graphics file or anything else. And a file can contain sequences of bytes that should be interpreted as instructions and sequences of bytes that should be interpreted as graphics. If the executable part has been written correctly, it will never try to interpret the graphics part of the file as CPU instructions; when it needs to refer to the graphics, it knows where they are in the file (and, hence, the memory image) and starts reading from the appropriate address. In principal, the operating system doesn't even need to know it's doing this.


The setup places $aa\$$ on the stack and puts the machine in state $x$. We then have this sequence of moves on input $aa$:

Consume the first $a$ and pop the stack. We're then still in state $x$ with stack contents $a\$$. No other move is possible.
Consume the next $a$ and pop the stack. We're then still in state $x$ with stack contents $\$$. No other move is possible.
Seeing a $\$$ on the stack, the only possible move is to pop the $\$$ and pass to state $y$.
In state $y$ with no further input, there are no possible moves, so the machine halts, in a non-accepting state.

Notice that there's no nondeterminism here: perhaps you were mistaken in your first bullet point: indeed there is a $\$$ in the stack at move (1), but it's not on the top of the stack.

The deeper question is exactly what model of a PDA is being used here: some people allow multiple accept states and say that the PDA accepts a string if it is in an accept state when the input has been completely consumed, others require that the stack be empty when the input has been consumed; some require a single accept state, some don't. All these models are equivalent, but you need to look closely at the definition you are using.


This question illustrates a lack of understanding of fundamentals. What does moving mean!?
The RAM stores data in transistors. Do you want a little robot to pick up the specific transistors you want out of the RAM chip and deliver them to the CPU? I hope it is obvious why that is not possible.
Instead, an electronic circuit (which those transistors are part of) looks at whether those transistors are on or off. This causes an electrical signal to be sent to the CPU which updates some of its own transistors according to the electrical signal.
The question is akin to: "Whenever I need my friend's phone number, I copy it from my brain into my phone. Why can't my brain send the original data instead of making a copy?"


You're confusing a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS).  Euclidean TSP has a PTAS, but it is not an FPTAS because the polynomial increases in degree as 1 / ε decreases.  Only an FPTAS is disallowed for strongly NP-hard problems, assuming P $\neq$ NP.


Which theoretical parallel model is closest to CUDA?

To the best of my knowledge, it may be the Queuing Shared Memory (QSM) model, even though hierarchical parallelism of threads is not taken into account. However, accesses to local memory and global memory (different bandwidth), and bulk synchrony (in which threads can work asynchronously beetween barrier synchronizations) are considered.


Detecting a cycle in an undirected graph and printing the vertices if there is a cycle, printing no cycle otherwise

You've basically got it!

The usual way to record the cycle is to mark the predecessor or parent of each node: that is, the node from which it was first visited. Then you can follow the trail of parents to print out the cycle.


Proving that L is not regular using closure properties

Let $ L_1 = \{\ ab^jc^j\ |\ j \geq 0\ \} $ and $ L_2 = \{\ a^ib^jc^k\ |\ i, j, k \geq 0 \ and\ i \neq 1\ \} $. Then

$$
L = L_1 \cup L_2.
$$

If we take
$$ \begin{align}
L\ \cap\ ab^*c^* &= (L_1\cup L_2) \cap ab^*c^* \\
 &= (L_1\cap ab^*c^*)\ \cup\ (L_2 \cap ab^*c^*)\\
\end{align}
$$

Since $L_1\cap ab^*c^* = L_1$ and  $L_2 \cap ab^*c^* = \emptyset$, we have

$$
L\ \cap ab^*c^* = L_1
$$

Now, $ab^*c^*$ is regular, and $L_1$ is not regular (can be shown using the Pumping Lemma). If $L$ was regular, by the closure properties, $L_1$ would be to, which is a contradiction. Hence, $L$ is not regular.


An example where the algorithm of Hopcroft and Karp performs poorly?

I was able to construct a simple example where the algorithm taken literally is easy to trick. The case goes as follows. Given a bipartite graph consisting of a union of simple paths of odd lengths $P_1, P_3, P_5, \dots, P_{2r-1}$ for some $r \in \mathbb{N}$. Assuming $P_i = v_{i,0}, v_{i,1} \dots v_{i,i}$ for $i = 2k-1; k \in [r]$. The shortest augmenting path in the first iteration has length one (namely any edge in the graph is such a path). Consider the following scenario of the algorithm.

In the first iteration, the algorithm chooses $\left\lfloor \frac{i}{2} \right\rfloor$ edges from each path $P_i$, namely the edges $v_{i, 2}, v_{i, 4}, \dots v_{i, i-1}$ as a maximal set of shortest augmenting paths. The set is maximal, since any other edge share an endpoint with an edge in the set. However, the matching resulting from these edges admits an augmenting path in each path $P_i$ of the length $i$. Since all paths have distinct lengths, the algorithm as given in the paper from Hopcroft and Karp augment exactly one path in each phase (in the pahse $j$ it will not look for paths longer than $2j-1$ since an augmenting path of this length exists). In total we need $\Omega(r)$ phases which is $\Omega(\sqrt n)$ with simple math. This bound is tight to the proven bound.

I considered this case trivial, since all augmenting paths are vertex disjoint and instead of looking for maximal set of vertex-disjoint shortest augmenting paths in each phase, we can look for a maximal set of vertex-disjoint augmenting paths with monoton-increasing lengths of the paths. I mean with that, that in each phase, after we run the BFS, we do not stop when a maximal set of vertex disjoint shortest augmenting paths are found, but we look further for (second-shortest) augmenting paths that are vertex-disjoint from what we already found and so on. In this case we would have considered all augmenting paths in the given graph in the previous example in one step.

On the other hand, it is not directly clear how to implement this kind of rounds in linear or almost-linear time from the given implementation of the algorithm in the paper of Hopcroft and Karp.

I was able to go further and construct examples with a bit more complicated structures and the same number of rounds, where we add edges arbitrarily between the middles of these given simple paths or parallel copies of subpaths. Even though, these edges might change the sequence of the algorithm, since they can be chosen at the first round of the algorithm, it is not hard to see that the total number of rounds does not change critically.

On the other hand, dense graphs seem to need less rounds in general. This can also be seen "intuitively" from results proben by Hegerfeld and Kratsch in this paper, which gives more insight about the number of needed rounds.


Parallel shortest path in directed acyclic graphs

In complexity theory, the notion of P-complete (wiki) denotes the problems that are (widely believed) difficult to parallelize effectively. (Note: I am not good at this area. Please correct me if I am wrong.)

One typical P-complete problem is

  Circuit Value Problem (CVP): Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate.

The "shortest path in DAG" problem is similar to CVP. I think it is not hard for you to find a reduction in the literature with, for example, the paper A Compendium of Problems Complete for P as a starting point.

A positive side: Of course you can layer the nodes in DAG and parallel the computation layer by layer to some extent.


Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?

We can associate a language to a Turing machine in several ways.
If the Turing machine halts on all inputs, then the language accepted by the Turing machine consists of all words which cause the Turing machine to halt in an accepting state. The class $\mathsf{R}$ consists of all languages which are accepted by some Turing machine.
For an arbitrary Turing machine, the language recognized by the Turing machine consists of all words that cause the Turing machine to halt (in any state). The class $\mathsf{RE}$ consists of all languages which are recognized by some Turing machine.
If $L \in \mathsf{coRE} \setminus \mathsf{R}$, then in particular $L \notin \mathsf{R}$, and so no Turing machine accepts $L$. If $L$ were recognized by some Turing machine then $L \in \mathsf{RE}$. However, this is impossible, since then $L \in \mathsf{RE} \cap \mathsf{coRE} = \mathsf{R}$.


I need help in this regural expression exercises

In order to solve this exercise, we need to come up for regular expressions for two classes of words:

Words of the form $x00$, where $x \neq \epsilon$ and the only occurrence of $00$ is at the end.
Words of the form $x01$, where $x \neq \epsilon$ and the only occurrence of $01$ is at the end.

Let us start with the first class. For starters, $x$ must end with $1$ or $2$. So such words are of one of the forms $y100$ or $y200$, where $y$ doesn't contain $00$. Presumably you already know how to describe all words not containing $00$ using a regular expression.

For the second class, the only constraints on $x$ are that it is non-empty and doesn't contain $01$. If you don't like the "non-empty" constraint, you can use the following case distinction:

If $x = y0$ or $x = y2$, then the only constraint on $y$ is that it doesn't contain $01$.
If $x = y1$, then $y$ cannot end with $0$. It could be empty. If it ends with $2$, then $x$ is of the form $z21$. If it ends with $1$, then we're again in the same situation: the preceding symbol (if any) cannot be $0$. Continuing in this way, we see that either $x \in 1^+$ or $x$ is of the form $y2z$, where $y$ doesn't contain $01$ and $z = 1^n$ for some $n \geq 1$.

I'll let you figure out how to describe strings $y$ avoiding $01$ – this is very similar to the case of avoiding $00$.


Can there be a context free language that is not recognizable by a PEG?

I see two flaws in this proof sketch, one related to CFLs vs CFGs, and another related to nested quantifiers and running time as a function of multiple parameters.

Any time you have a high-level proof strategy that seems to lead to surprising results, it is a good idea to check it carefully by expanding each step to obtain a detailed proof.  Expand each claim with a precise statement, by applying the definition or the exact theorem in the literature, and verify carefully that they match up.  This is particularly important when dealing with lower bounds, as they tend to introduce nested quantifiers that can lead your intuition astray when thinking only at a high level.

Flaw #1: CFLs vs CFGs

The proof seems to conflate context-free languages (CFLs) with context-free grammars (CFGs).  However, there can be multiple CFGs that all generate the same CFL.  At best, your proof strategy shows that there exists a CFG $G$ that can't be parsed by a PEG parser.  But that's not surprising; we already know that PEG parsers can only parse CFGs that are in the PEG format.  We cannot  conclude anything about the corresponding CFL $L(G)$; for all we know, there might exist some other grammar $G'$ that is a PEG grammar and that yields the same language, i.e., $L(G)=L(G')$.  Your proof doesn't rule that out, so it does not prove that the CFL it constructs can't be parsed by a PEG parser.

A concrete example of this is given at https://en.wikipedia.org/wiki/Parsing_expression_grammar#Expressive_power, which shows a simple CFG that cannot be parsed by a PEG parser, but where there exists another CFG for the same language that can be parsed by a PEG parser.

Flaw #2: Multiple parameters

It's important to expand out the statement of what is meant by these lower bounds.  The lower bound on matrix multiplication means that, for each matrix multiplication algorithm, there exists an infinite family $(A_1,B_1),(A_2,B_2),\cdots$ of matrices such that $A_n,B_n$ are $n\times n$ matrices, and multiplying $A_n \times B_n$ using this algorithm takes $\Omega(n^2)$ time.

Lee's reduction describes how to construct a matrix multiplication algorithm from any context-free parser.  If we now apply Lee's reduction to the matrix multiplication algorithm obtained from a PEG parser, we obtain an infinite family $(G_1,w_1),(G_2,w_2),\cdots$ of CFGs and inputs such that parsing them takes a long time.  You'll need to dive into the details of Lee's reduction to determine the sizes of the $G_n,w_n$.  Based on a quick look, it looks to me like the size of $G_n$ is $\Theta(n^2)$ and the size of $w_n$ is $\Theta(n^{1/3})$, but I'm not sure whether that's correct; you'd need to figure that out.

Next, you'd need to figure out the running time of a PEG parser, as a function of both the size $g$ of the grammar and the size $n$ of the input string.  Standard references state the running time of a packrat parser for a PEG grammar as $O(n)$, but they don't describe the dependence on $g$; is it $O(gn)$? $O(g^2n)$? something else?  You'd need to figure that out, and then apply it to the family above, to determine what the asymptotic running time of this parser is on the family $L_n,w_n$, and thus what the running time of this matrix multiplication algorithm is on the family $A_n,B_n$, to determine whether it contradicts the $\Omega(n^2)$ lower bound.

For instance, if the running time of a PEG parser is $O(gn)$, then Lee's reduction yields a matrix multiplication algorithm that takes $O(n^{2.333\ldots})$ time on the family $A_n,B_n$, which does not contradict the known lower bound.

Notice how Lee's result does not provide a single context-free grammar or context-free language where parsing is slow; it provides an infinite family of pairs of languages and inputs (which was not considered in your proof strategy).  Also note the importance of getting the nested quantifiers right, and of capturing how the running time of a parser depends on both the size of the input and on the size of the grammar (which was not considered in your proof strategy).  Hopefully this highlights how a strategy that sounds good can run into difficulties when one tries to apply it in detail; and one must check those details before assuming the strategy will work out.


How are CPU architecture and word size related?

It's simple - 32 bit word size, or 32 bit architecture, mean exactly what the person using the expression means. No more, no less. You can't draw any conclusions from it.

For example, there's an Intel 32 bit architecture that can address 64 GB of physical RAM, and no Intel 64 bit architecture that can address anything near 2^64 bytes of physical or virtual memory, while 32 bit PowerPC supported 2^53 bytes of virtual memory.

64 bit POWER has 32 bit instructions. 32 bit Intel has instructions from 8 bit to over 100 bit.

32 bit ARM is what it is, and 64 bit ARM is what it is. Some with 32 and 64 bit x86, except they are different. And so on. Don't make any assumptions, they will all be somewhere between wrong and not quite right.

If you want to pass an exam, learn the answers that the exam expects (sad but true).


Min max solution to the random assignment problem

Yes, there is an efficient algorithm to find an assignment that minimizes the largest cost.  Suppose we want to check whether there is an assignment with largest cost $t$.  To do that, delete all edges with cost larger than $t$, ignore the costs, and check whether the graph has a bipartite matching using the Hopcroft-Karp algorithm; if it does, there is a valid assignment.  Now use binary search over $t$ until you find the minimum $t$ such that a valid assignment exists.  Thus, the problem can be solved $O(|E| \sqrt{|V|} \lg |E|)$ time.


Are interrupts needed for a computer system to work?

No, they're not needed for a computer to work.  For instance, you can use polling to interact with devices, instead of interrupts, and you can use cooperative multitasking for scheduling multiple processes, rather than preemptive multitasking.

(Thank you, @Paul A. Clayton!)


Shifted Big Os. How to say O((n+c)!) = O(n!)?

No, $(n+1)!$ is not $O(n!)$.  There is no constant factor $c_0$ so that $(n+1)!$ is at most $c_0 \times n!$.
You can say that $(n+1)!$ is in $O(n! \times \text{poly}(n))$.  Here $\text{poly}(n)$ represents the class of functions that grow polynomially fast in $n$; so in other words, this statement says that there is a polynomial $p(n)$ so that $(n+1)!$ is in $O(n! \times p(n))$.  Indeed, it is also true that $(n+c)!$ is in $O(n! \times \text{poly}(n))$.  This may be enough for your purposes.
Sometimes people may define new notation for this kind of case.  For instance, if we are dealing with functions that grow exponentially fast, and we don't care about a factor of $n$ (which grows much more slowly than any exponential function), we might define $f(n) = O^*(g(n))$ if $f(n)$ is in $O(g(n) \times \text{poly}(n))$.  Then it is true that $(n+c)!$ is in $O^*(n!)$.


This is a classical problem that I have previously seen framed as a puzzle rather than a CS question (with some fixed $n$ and fixed number of beakers), though I don't remember any source for it.

You can solve it as follows:
Number your bottles from $0$ to $n-1$, and label your beakers from $1$ to $\lfloor\log_2(n-1)\rfloor+1$ (the number of bits needed to represent numbers $0$ to $n-1$ in binary).

Now for every bottle, do the following: let $x$ be the label of the bottle. For every $i$ such that there is an $1$ at the $i$'th position in the binary representation of $x$, put a bit of that bottle's compound in beaker $i$.

Now after 10 days, the beakers which explode will exactly spell out the number of the explosive bottle in binary.


Using dynamic programming to maximize work done

This seems to be exercise 9 from Kleinberg's Algorithm Design, chapter six. I'll report how i tried to solve it.

Let's define $OPT(i)$ as the maximum amount of work from day $1$ to day $i$, with $i \leq n$

For every $i$, there can be a reboot in any previous day $1\leq j < i$. If it was on day $j$, than you processed $\sum_{k=j+1}^i \min\left\{s_{k-j}, x_k\right\}$ terabytes. Furthermore, on day $j$ you cannot process anything. Than you can define the following recurrence relation:
$$
OPT(i) = \displaystyle\max_{1\leq j < i} \left\{\displaystyle\sum_{k=j+1}^i \min\left\{s_{k-j}, x_k\right\} + OPT(j-1)\right\}
$$

The algorithm can be implemented in a bottom-up fashion, with $O(n^3)$ running time:

let OPT[0...n] be a new array of n+1 elements
OPT[0] = 0, OPT[1] = min(s[1], x[1])
for i = 2 to n
  m = -infinity
  for j = 1 to i-1
    l = 0
    for k = j+1 to i do l = l + min(s[k-j], x[k])
    l = l + OPT[j-1]
    if l > m then m = l
  OPT[i] = m
return OPT[n]

There is also a $O(n^2)$ solution based on a matrix of subproblems. Define $OPT(i, j)$ as the maximum from day $i$ to $n$ with last reboot done $j$ days before, more exactly on $i-j$ day. For every day $i$ you have to consider these alternatives:

you have a reboot. So on day $i$ you cannot process anything: $OPT(i,j) = OPT(i+1, 1)$
go on with processing: $OPT(i,j) = \min\left\{s_j, x_i\right\} + OPT(i+1, j+1)$

Because it's of no use reboot on last day, you have $OPT(n,j) = \min\left\{s_j, x_n\right\}$.

This last approach is taken from Mangat Rai's work, a user that shared a collection of solutions to Kleinberg's book problems, although the first one i reported is also very close to what you can find there. I suggest you to do a web search for it (no official site as far as i know).


Speaking of "randomness" in computing terms, to what sense can any extant digital processor make "random" results?

Everything you can do in a high-level language can be done in assembly. After all, the high-level language is compiled to machine code.

What you seem to be describing is pseudorandom numbers, which are numbers generated by a computer using an algorithm, and look (computationally) random. It is also possible to generate "somewhat random" numbers by harvesting (say) thermal heat, or other "random" phenomena. The result won't quite be a sequence of i.i.d. fair coin tosses, but if you run it through an extractor it will look (computationally) pretty similar, and be theoretically unpredictable (since it's based on actual physical randomness).


The grammar as given in your assignment is an abbreviation for the following expanded grammar:
$$P=\left \{
\begin{align}
\begin{aligned}
S &\to \epsilon, \\
S &\to L_a R_a, \\
S &\to L_b R_b, \\ \\
L_a &\to a, \\
L_a &\to L_a a W_a, \\
L_a &\to L_a b W_b, \\ \\
L_b &\to b, \\
L_b &\to L_b a W_a, \\
L_b &\to L_b b W_b, \\
\end{aligned}\qquad\begin{aligned}
W_a a &\to a W_a, \\
W_a b &\to b W_a, \\
W_b a &\to a W_b, \\
W_b b &\to b W_b, \\[8pt]
W_a R_a &\to R_a a, \\
W_a R_b &\to R_b a, \\
W_b R_a &\to R_a b, \\
W_b R_b &\to R_b b, \\[8pt]
R_a &\to  a\\
R_b &\to  b\\
\end{aligned}\end{align}\right \}$$
So, yes, $x$ and $y$ need to be replaced consistently when you expand the shorthand notation. (And it's probably clear why the shorthand was used.)
Intuitively, what's happening here is that $S$ creates a left marker ($L_x$) and a right marker ($R_x$) which will eventually resolve to the same character. The left marker then expands to a sequence of $xW_x$ pairs, where $W_x$ is a "walker". The $W_x$s all walk to the right; when they finally hit the right marker, they deposit their payload after the right marker. This has the effect of creating two copies of the same string.
In an abbreviated form (combining derivation steps) you get something like this:
$$S\to L_aR_a\Rightarrow L_a b W_b a W_a R_a \Rightarrow L_a b a R_a b a \Rightarrow a b a a b a$$
Filling in the complete derivation would be a useful exercise. (Indeed, it's the exercise you've been asked to do.)


Towers of Hanoi Algorithm "Using Auxiliary" Peg

In mathematics, the literal meaning of a phrase is of little importance. What is important is that both author and reader know what a phrase means, and this can come about in two ways. Either the phrase is well-known, or the phrase is defined in the article. In your case, the phrase "move $n$ pegs from $A$ to $B$ using $C$" means "call the function Hanoi with parameters $n,A,B,C$" - no more, no less. The author could have chosen a completely different phrase, for example "jump from $A$ to $B$ doing $n$ flips above the midpoint $C$", as long as they make it clear that it means "call the function Hanoi with parameters $n,A,B,C$".

Another point that you raise is that when $n=1$, you can move the disc directly from $A$ to $B$, without involving $C$ at all, which you feel contradicts the phrase "using $C$", since $C$ isn't actually used. However, in mathematics such phrases are usually inclusive rather than exclusive — it is not obligatory to actually use $C$. This highlights the fact that mathematical terms often differ in meaning from their common use. For example, when mathematicians say "$p$ or $q$", they are also allowing the possibility "both $p$ and $q$", although common knowledge precludes it.


Can we use exponential function in a reduction?

For the sake of notation, I'm going to assume you're trying to produce a polynomial time reduction $f$, which that maps instances $x$ of some problem $L_1$ to instances $f(x)$ of some other problem $L_2$.  Instances of $L_i$ have parameter $p_i$ ($i\in\{1,2\}$).  Since the reduction has to run in polynomial time, it has to output at most a polynomial number of bits, say $|x|^q$ for some constant $q$. In particular, the representation of $p_2$ can't be more than $|x|^q$ bits long.

So, suppose the value of the parameter is $k$ in some instance $x$ with parameter $p_1=k$. Whether or not $f(x)$ can have parameter $p_2=2^k$ depends entirely on what the parameters are and how big $p_1$ can be.

If $p_1$ is a number represented in unary, we have $p_1\leq |x|$; if it's a number represented in binary or some higher base, then $p_1 = O(2^{|x|})$. If $p_1$ is the size of some object described in $x$, then its size will depend on what kind of object it is (e.g., if $p_1$ is the size of some set of a graph's the vertices, $p_1\leq |x|$; if it's the number of pairs of vertices with some property, $p_1\leq |x|^2$, and so on).

And, now, what's $p_2$? If it's a number in unary, then $2^k$ is a string of length $2^k$, so we need $2^k\leq |x|^q$, i.e., $k=O(\log |x|)$. If it's a number in binary, then $2^k$ is just a $1$ followed by $k$ zeroes, so we can write this in our output as long as $k=O(|x|^q)$. If it's the size of some structure then, again, it depends on how that structure is represented. For example, if you need to add $2^k$ vertices, you need all those vertices to be stored in at most $|x|^q$ characters, so $k$ had better not be any bigger than about $\log n$.


How is a communication protocol a mechanism?

The view of Alice is what Alice gets to see; it is a probability distribution that depends on the inputs of both players $x,y$. It is a distribution over triples $(x,\tau,r_A)$, where $x$ is Alice's input, $\tau$ is the transcript of the protocol, and $r_A$ is Alice's private randomness. This probability distribution depends both on $x$ and on Bob's input $y$.

Here is how to generate this probability distribution, given a protocol $P$ and the inputs $x,y$ of both players. Generate the shared randomness $r$ according to its distribution, and Alice's private randomness $r_A$ according to its distribution. Run $P$, obtaining a transcript $\tau$. Output $(x,\tau,r_A)$.


Show that { xy ∣ |x| = |y|, x ≠ y } is context-free

Claim: $L$ is context-free.

Proof Idea: There has to be at least one difference between the first and second half; we give a grammar that makes sure to generate one and leaves the rest arbitrary.

Proof: For sake of simplicity, assume a binary alphabet $\Sigma = \{a,b\}$. The proof readily extends to other sizes. Consider the grammar $G$:

$\qquad\begin{align}
  S &\to AB \mid BA \\
  A &\to a \mid aAa \mid aAb \mid bAa \mid bAb \\
  B &\to b \mid aBa \mid aBb \mid bBa \mid bBb
\end{align}$

It is quite clear that it generates

$\qquad \mathcal{L}(G) = \{ \underbrace{w_1}_k x \underbrace{w_2v_1}_{k+l}y\underbrace{v_2}_l \mid |w_1|=|w_2|=k, |v_1|=|v_2|=l, x\neq y \} \subseteq \Sigma^*;$

the suspicious may perform a nested induction over $k$ and $l$ with case distinction over pairs $(x,y)$. Now, $w_2$ and $v_1$ commute (intuitively speaking, $w_2$ and $v_1$ can exchange symbols because both contain symbols chosen independently from the rest of the word). Therefore, $x$ and $y$ have the same position (in their respective half), which implies $\mathcal{L}(G) = L$ because $G$ imposes no other restrictions on its language.

The interested reader may enjoy two follow-up problems:

Exercise 1: Come up with a PDA for $L$!

Exercise 2: What about $\{xyz \mid |x|=|y|=|z|, x\neq y \lor y \neq z \lor x \neq z\}$?


What is the earliest use of "trees" in computer science?

Wikipedia says that the first use of tree in mathematics was by Cayley in 1857.

Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than, say, the first Australian to use "tree".


Shortest path including all nodes in a subset

The purpose of the BFS in the transposed graph is to eliminate edges that are part of shortest paths to some vertex, but not to $t$. These "useless" edges could otherwise lead to false positives in the traceback phase that builds $c(\cdot)$.
Consider the digraph with $E=\{st,su\}$ and $U=\{u\}$. The unique shortest path is the single edge $st$, so the answer is NO, but unless you know that the $su$ edge should be ignored (by making use of the transposed graph), the traceback phase will process it (on either its first or second iteration) and assign $c(s)=1$, resulting in YES being reported.
(Alternatively, you could augment the traceback phase by "marking" $t$ and any edge into a marked vertex, and considering only values of $c(\cdot)$ for marked vertices. This is fairly similar to just performing a backwards BFS from $t$, and probably a little more efficient in practice.)


Calculate number of error-correcting code check bits

Consider a binary code $C$ of length $n$ (each codeword consists of $n$ bits), containing $2^m$ codewords, and allowing all single-bit errors to be corrected.
Let $x \in C$, and let $B_x$ denote all words at distance at most $1$ from $x$, that is $x$ itself, as well as any word obtained by flipping a single coordinate. Any word in $B_x$ could result from a transmission of $x$ followed by at most one error. Since $C$ allows all single-bit errors to be corrected, for any $y \in B_x$, the only codeword within distance $1$ from $y$ must be $B_x$. In other words, the balls $B_x$ are disjoint.
Since there are $2^m$ balls $B_x$, each one contains $n+1$ words, the balls are disjoint, and there are $2^n$ possible words, we deduce that $(n+1)2^m \leq 2^n$. This is the so-called sphere-packing bound or Hamming bound.


Understanding the fundamentals of building an in-Memory Distributed Graph

You should look at the Cloud Computing area - there is a lot of research about graphs representation and processing there.

For example, this paper.


How can languages that are E-complete have sub-exponential size circuits?

What you're missing is that it might be hard to construct the circuits. In order for your algorithm to simulate the circuit, it needs to know the circuit, but since the circuit depends on $n$, you can't hard-code it — you'll need to hardcode an infinite number of circuits.

To give a simpler example, consider the following language:
$$
\{ x : \text{The $|x|$th Turing machine halts on the empty input} \}.
$$
This is an uncomputable language which has constant size circuits.

What could not be the case is that some language in $\mathsf{E}$ has uniform subexponential circuits, for a suitable notion of uniformity (given $n$, you need to be able to construct the circuit in time subexponential in $2^n$). Your argument would work then, since the algorithm would be able to construct the circuit in subexponential time.


Computing every possible sum of integers taken from different sets


If the grammar includes $M \to \alpha N \beta$ and $\beta$ is nullable then anything which could follow $M$ could also follow $N$. In other words,

$FOLLOW(M) \subset FOLLOW(N)$

So we need to add everything in $FOLLOW(M)$ to $FOLLOW(N)$. It does  not oblige us to alter $M$'s follow set.

If there is also $M \to \gamma K \theta$ with $\theta$ nullable, then similarly we have

$FOLLOW(M) \subset FOLLOW(K)$

so we also have to add everything in $FOLLOW(M)$ to $FOLLOW(K)$. That implies that the FOLLOW sets for $N$ and $K$ are not disjoint, but it really says nothing interesting about $M$'s FOLLOW set.


The main reason is that context-free grammars, once introduced, were quickly adapted to provide a theoretical basis for program language compilation.  For this usage, the goal is to parse as quickly as possible using as little storage as possible.  For that the best approach is to scan the input source once from 'left-to-right' [we interpret the source as a sequence of characters all on a single line], and be done with the parse exactly when done scanning the source.  Two derivation patterns naturally fit into this protocol: leftmost-first derivations performed top-down in forward order, and rightmost-first derivations performed bottom-up in reverse order.


What is the asymptotic runtime of this nested loop?

The result is correct, but your reasoning is not. You can't mix big-oh with ellipses. It happens to work here because of extra conditions that happen to be true but that you haven't checked.

Why summing big-ohs just doesn't work

Fundamentally, you are abusing notation. For example, it doesn't make much sense to write $O(1)$, $O(2)$, $O(3)$, etc. as if they were different things — after all, they all mean “bounded function”.

The definition of big-oh depends on some values that differ from one $O(…)$ to the next. When you write $O(1) + \ldots + O(n)$, the constants could be different in each term of the sum, and if they are, you can't say anything about the sum. $f(n) = O(g(n))$ means that there exists some threshold $N$ and some factor $C$ such that if $n \ge N$ then $f(n) \le C g(n)$. When you have a variable number of big-ohs like $O(f_1) + \ldots + O(f_n)$, each term of the sum has its own threshold and factor. Your reasoning assumes that the threshold and factor are the same, and it's true that in this example you can pick them to be the same, but it isn't true in general.

The first hurdle is what $O(1) + \ldots + O(n)$ actually means. This is a sum whose general term is $O(k)$: $O(1) + \ldots + O(n) = \sum_{k=1}^n O(k)$. The general term of the sum could depend on both $k$ (the index into the sum) and $n$ (the number of terms)! Big-oh is defined in terms of a variable, it describes what happens when that variable approaches infinity. If you consider the general term as a function of $k$, then $O(k)$ means that there exists some threshold $K_n$ and some factor $D_n$ such that if $k \ge K_n$ then $f_k(n) \le D_n k$. If you consider the general term as a function of $n$, then $O(k)$ means that the function is bounded for any given $k$, i.e. that there exists a bound $B$ such that $\forall n, f_k(n) \le B_k$.

To illustrate how the sum can get big under the first interpretation, consider the function
$$ f'_k(n) = 2^n k $$
For any given $n$, $f'_k(n) \le D_n k$ where $D_n = 2^n$ so $f'_k(n) = O(k)$ as a function of $k$. Yet the sum is
$$ \sum_{k=1}^n f'_k(n) = f'_1(n) + \ldots + f'_n(n) = 2^n \cdot 1 + 2^n \cdot 2 \ldots + 2^n \cdot n = 2^n \cdot (1 + 2 + \ldots + n) = 2^n \frac{n(n+1)}{2}$$
which is not $O(n^2).

To illustrate how the sum can get big under the second interpretation, consider the function
$$ f''_k(n) = k^2 $$
The general term $f''_k(n)$ is constant with respect to $n$, so it is $O(k)$ as $n$ goes to infinity (since $k$ is fixed, this is the same as writing $O(1)$). Yet the sum is
$$ \sum_{k=1}^n f''_k(n) = f''_1(n) + \ldots + f''_n(n) =
   1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6} $$
which is not $O(n^2)$.

What actually works

Here, you have a special case which does make sense. It's not any sum of big-ohs — it's the same function every time:
$$ f(1) + f(2) + \ldots + f(n) = \sum_{k=1}^n f(k) $$
where $f(k) = O(k)$. Now we have a function of a single variable, which makes the analysis simpler. By the definition of big-oh, there is a threshold $N$ and a factor $C$ such that for all $k \ge N$, $f(k) \le C k$. Therefore, if $n \ge N$, then
$$ \sum_{k=1}^n f(k) = \sum_{k=1}^{N-1} f(k) + \sum_{k=N}^n f(k)
   \le \sum_{k=1}^{N-1} f(k) + \sum_{k=N}^n C k
   \le \sum_{k=1}^{N-1} f(k) + C \frac{n(n+1) - N(N-1)}{2} $$
This last term is of the form $C n^2 + B n + A$, so it is $O(n^2)$ and thus $\sum_{k=1}^n f(k) = O(n^2)$.

If $f$ is monotonically increasing (which is often but not always the case for complexity bounds), then there is an easier way to prove this:
$$ \sum_{k=1}^n f(k) \le \sum_{k=1}^n f(n) = n f(n) $$
and since $f(n) = O(n)$, the sum is $O(n \cdot n) = O(n^2)$.

Note that we are taking the sum of the values of a function which is $O(n)$. This is crucially different from summing functions, each of which is $O(n)$.

Application to a loop

Consider a loop

for i = 1 to n do
    /*do something*/

If the running time of /*do something*/ does not depend on $n$, then we are in the case that works. For example, take your nested loop:

for i = 1 to n do
    for j = 1 to i do
        statement

Assuming that statement runs in constant time, the run time of the inner loop is $j$ which is $O(j)$. The run time of the outer loop is thus $O(n^2)$. Of course, you don't need to remark that $j = O(j)$ to see this — you could directly remark that $j \le n$ and therefore statement is executed at most $n$ times per run of the inner loop and thus at most $n^2$ times per run of the outer loop.

The general way to analyze the complexity of loops is by summing the complexity of the iterations. You cannot sum big-ohs, you need to write an actual mathematical expression. If the final desired result is a big-oh approximation, then you don't need to write an exact computation: it is enough to find an upper bound for each term and then calculate an upper bound for the sum of the upper bounds.


Lambda Calculus inductive substitution definition

"If one deletes $(\mathrm{d})$ and allows bound variables to be substituted..."

The problem here is that substitution of a bound variable makes little sense, since one substitutes a variable (let's forget for a moment it should be free) with a term, which may very well be an abstraction or application, but not a variable.

Let me illustrate this by example. What if we are trying to substitute a bound variable with a term, which is not a variable? Like this:
$$[(y\; y)\ / \ x]\ \lambda x. x.$$
What should we do?

Produce $\lambda (y\; y). (y\; y)$? It is not a well-formed term, so the answer is no.
Another choice would be to leave the binding instance intact and make $\lambda x. (y\; y)$ a result. Let's not take into account if it makes sense, at least it is syntactically correct. This variant causes us major troubles too: it will mess up scopes and render $\beta$-reduction useless. And our end goal is to define $\beta$-reduction via substitution.

  $(\mathrm{g})$ prevents a bound variable from changing to a free one. It does this by first substituting a bound variable.

It does not use substitution, it uses renaming, which is a different notion.

  "...is $(\mathrm{g})$ strong enough to handle it without messing up everything?"

$(\mathrm{g})$ does not tell us anything about substitution of bound variables, since it has the condition $x \in \mathrm{FV}(P)$


Recurrence which cannot be analyzed by master theorem

Suppose for simplicity that $n$ is a power of 2. Construct the tree corresponding to the recursion – each vertex is labelled by the current value of $n$, has three children, one of which is a leaf. We assume for now that the tree continues forever. Associate with each edge a weight, which is $1$, $a$, or $1$, depending on which term it corresponds to. The weight of a vertex is the product of all weights in the path from the root to the vertex.

Consider the generating series $$P(x) = \frac{1}{1-x-ax^2} = \sum_{m=0}^\infty (x+ax^2)^m.$$
The coefficient of $x^k$ in $P(x)$ is the total weight of vertices whose label is $n/2^k$. Therefore $\tilde T(n) = n^2 P(1/4)$, where the tilde denotes that there is no base case and the recursion continues forever (we will discuss this later on). Thus $\tilde T(n) = \omega(n^2)$ iff the power series $P(x)$ diverges at $x = 1/4$. This happens if $1/4 + a/4^2 \geq 1$, that is, if $a \geq 12$.

There is a slight problem with this argument, namely the tree doesn't continue forever. However, it is easy to see that all leaves are at depth $\Theta(\log n)$, or more accurately, at depths between $\log_4 n$ and $\log_2 n$ (assuming a base case $T(1) = 1$). This shows that
$$
\sum_{m=0}^{\log_4 n} \left(\frac{1}{4}+\frac{a}{16}\right)^m \leq T(n) \leq
\sum_{m=0}^{\log_2 n} \left(\frac{1}{4}+\frac{a}{16}\right)^m.
$$
When $a < 12$, the preceding argument already shows that $T(n) = \Theta(n^2)$. When $a = 12$, these bounds show that $T(n) = \Theta(n^2 \log n)$. When $a > 12$ these bounds are not enough to determine the asymptotics, though definitely $T(n) = \omega(n^2)$.

The Akra–Bazzi method is a general form of this argument. To solve your recursion, you first have to find the value of $p$ such that $(1/2)^p + a(1/4)^p = 1$. Given that, the Akra–Bazzi theorem tells you that
$$
T(n) = \Theta(n^p) \cdot \left(1 + \int_1^n \frac{u^2 \, du}{u^{p+1}}\right) = \begin{cases} \Theta(n^2) & p < 2, \\ \Theta(n^2\log n) & p = 2, \\ \Theta(n^p) & p > 2. \end{cases}
$$
(I leave the case analysis needed to prove the formula on the right-hand side to you. It is very instructive.)
The critical point is when $p = 2$, and this happens when $1/4 + a/16 = 1$, that is, when $a = 12$, and so in this case $T(n) = \Theta(n^2 \log n)$. When $a < 12$ we have $p < 2$, and so in this case $T(n) = \Theta(n^2)$. These results agree with the calculations above. Finally, when $a > 12$ we have $p > 2$, and so in this case $T(n) = \Theta(n^p)$, the estimate which was too difficult for our crude method above.


It's a synthetic notation for complexity classes of oracle machines. Let $\mathcal{A}$ be a class and $L$ be a language. We define:

$$
\mathcal{A}^L
$$

to be the complexity class of the languages decidable by a machine in class $\mathcal{A}$ with access to an oracle for $L$.

If $\mathcal{A}$ and $\mathcal{B}$ are classes, we define:

$$
\mathcal{A}^\mathcal{B} = \bigcup_{L \in \mathcal{B}} \mathcal{A}^L
$$

Therefore, $\mathcal{P}^\mathcal{P}$ is the class of languages decidable in polynomial time by a machine with an oracle for any language of $\mathcal{P}$, and $\mathcal{P}^\mathcal{NP}$ is the class of languages decidable in polynomial time by a machine with an oracle for any language of $\mathcal{NP}$.


Reduction PSPACE language to DSPACE(O(1))

The only languages in $PSPACE$ that can be reduced by the above constraint are languages in $LOG-SPACE$.

Assuming it's a Karp reduction:

A language in $DSPACE(O(1))$ is in $DTIME(O(n))$ (the number of configurations is linear). [Thanks to Yuval's comment]

Clearly, everything you can solve in $DSPACE(O(1))$ you can solve in $DSPACE(O(logn))$; So, you might as well leave a bit flag indicating whether to accept the string or not when you reduce the language by solving it in the transducer directly.

Thus, the reduction function will decide the language and since you are constrained to $LOGSPACE$ reduction you can decide only languages in $LOGSPACE$.


two languages reducible to each other can belong to RE and recursive?

Reductions are translations between computational problems.  Reductions are used to define the concept of NP-hardness but that doesn't mean that every use of reductions has something to do with NP – analogously, you can translate between English and French but that doesn't mean that every piece of translation has something to do with French.  In this case, there's no reason to assume that we're in the context of P vs NP: the question is in the context of computability theory (what functions can we compute?) not complexity theory (how much resources are required?).

For your question at the end, remember that every decidable language is semi-decidable.

I've no idea what the answer to the multi-choice question is, since it's so badly worded.  Choosing "C", for example, would mean asserting that the statement "both" is false but "both" isn't a statement with a truth value.


How to count the biggest size of the problem during some time period?

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.


Time complexity of a triple nested loop with squared indices

For one of the loops, you've a complexity of $O(\sqrt n)$. You're nesting the loops three times, so you'll get the complexity of $O(\sqrt n^3)$, which is $O(n^{3/2})$.

If you want to be more precise, then for your original question, the complexity will be:

$O(\sqrt n)$ for the first loop
$O(\sqrt n - 1)$ for the second loop, which is the same as $O(\sqrt n)$, since the time complexity of 1 is constant.
$O(\sqrt n - 2)$ for the third loop, which is the same as $O(\sqrt n)$, since the time complexity of 2 is constant.

Therefore, the total complexity is still $O(\sqrt n^3) = O(n^{3/2})$.

EDIT/ADD:

You're pretty much correct, just make one more step to simplify the expression, remembering that $\log(n^2) = 2 \times \log(n)$.  There are three loops:

The first on is, correctly, $O(\log n)$.
The second one is just like in the first problem, so you get $O(\sqrt n)$.
The third one is on the square of $n$, therefore you get $O(\log(n^2))$, which is the same as $O(2\log(n))$, which is the same as $O(\log(n))$.

Combining the three, it's pretty much like a multiplication, you will get: $O(\log(n) \times \sqrt n \times \log(n))$, which is $O(\log(n)^2 \times \sqrt n)$.


Is there a model of computation, that tries to be realistic?

As D.W. mentions in the comments, the model you are looking for is the RAM machine. In fact, there are several different models, and I recommend the following recent paper of Fürer's for a good overview.

In contrast to what you describe, the correct ring is $\mathbb{Z}_{2^n}$, where $n$ is the width of registers – up to 512 bits in future Intel processors. The exact value of $n$ doesn't matter at all as long as it's constant, since in computational complexity we are always interested in time and space complexity up to a multiplicative constant. Therefore, to make matters interesting, the RAM models described above let $n$ depend on the input size.

Regarding finitude of memory, this is captured, to some extent, by space constraints – polynomial space (or linear/quasilinear space) for algorithms working on normal data, logarithmic space (or polylogarithmic space) for algorithms working on big data; there are also streaming models for even less space. Restricting the space altogether would be destructive since then all deterministic algorithms would terminate in constant time – to make sense of asymptotics, we must allow space to grow with input size.


Do the images need to be the same/similar resolution as the camera I'll be using, for best results?
Technically yes, for best results, you should use as close as possible images that you train them on to predict, for example, HD camera and webcam images are quite different, but in real life, it is not usually possible, as it is costly. You don't need the same resolution images, but if you resize from 30 x 30 x 3 to 256 x 256 x 3  or 1024 x 768 x 3 it to 256 x 256 x 3 makes a difference in how the image looks after transformation, but  You can use different resolution images, but you need to resize them, using letterbox (padded image while preserving aspect ratio), or crop, or even in some cases just resizing without preserving aspect ratio gives good results.
It depends on a case by case.
Does the images all need to be the same resolution? Can I use a single image and just digitally zoom out on the image to give the illusion of different distances?
No, you don't have to have them in the same resolution. You can always resize images.
If the object is small in the image it could be possible, but remember it's better to have more unique data for generalization of the network. But for augmentation usually one of the augmentation techniques is zooming in (center crop and resize), and you could use zoom out as well.  There are other various techniques rotation, HSV transformations, shear, and many more you can use for augmentation.


The cost of a branch misprediction depends on the depth and width of the pipeline and not the amount of code guarded by a condition. A processor keeps fetching and decoding down the wrong path until the branch is resolved and the correct target determined. In a two-wide processor with five stage before branch resolution (a "moderate performance design", say two instruction fetch stages, a decode stage, a register read stage, and an execute stage with a branch resolving at the end of the execution stage), a mispredicted branch could lose up to nine instruction execution opportunities:

br+w1       IF IF ID RR EX
w2+w3          IF IF ID RR EX
w4+w5             IF IF ID RR EX
w6+w7                IF IF ID RR EX
w8+w9                   IF IF ID RR EX
c1+c2                      IF IF ID RR EX

In most real code, two consecutive instructions would not always be able to execute in parallel, so the actual lost performance would be lower. (If the branch was the second instruction of a pair, only 8 instruction execution opportunities would be lost.)

In a fully predicated ISA, the predicated form could also have one less instruction (a branch instruction might include a comparison that would have to be provided as a separate instruction to provide a predicate but often normal instruction results provide a predicate).

Another consideration is that predication avoids fetch redirection. Some implementations have had a one cycle taken branch fetch penalty; for a two-wide processor, this would allow two predicated instructions to execute "for free".

(Out-of-order execution complicates the tradeoffs in providing and using predication. Predication turns an instruction with two dynamic sources into one with three dynamic sources, so the scheduler has to monitor the availability of an additional source (the predicate). In addition, predication converts a control hazard (which can often be bypassed using prediction) into a data hazard (if the predicate is not available, the instruction will not execute and its dependencies cannot execute). In theory, predicates can be predicted just as branch direction is predicted with the prediction only used if the data hazard is expected to introduce excessive slow-down, but this requires both a confidence estimate for the prediction and an estimate of the costs for using and not using the prediction when the prediction is right and when it is wrong.)

Furthermore, not all branches are equally predictable. Some branches approach fifty percent predictability. It is even possible to always mispredict (e.g., with two-bit counters initially at weakly wrong for the first encounter and a branch that alternates between taken and not-taken), though this is a rare occurrence.

Predication of nested conditions can also exponentially increase the number of executed instructions. Branch prediction would choose one path for a switch statement; complete predication would follow all the paths.

Another factor is that processing extra instructions can be relatively inexpensive if the processor has otherwise idle resources. E.g., if one path is stalled waiting for the result of a long latency instruction (or cannot fully utilize available execution width), (predicated) instructions from the other path may be able to execute "for free" (power and other costs would still apply).

Predication also makes more sense with vector/SIMD operations where per-element predication can facilitate the use vector operations that would otherwise need to be executed in a scalar fashion. (Even without predication, one can use bitwise SIMD operations to select operands, choosing between the true operand and the identity value for the operation.)


In simple words: ack is the way of the receiver to tell you "i got data until some num now send me from this num",now if a packet is lost it means the reciver will not get its data.

If i understood your question right then we can see the acks in the 12th and 13th packets are identical,the reason is because not data was sent between them to the reciver

Now why the window size is bigger?its simply because the receiver reads the data in a certain speed and the buffer now has more space in it

So th reason they have same acks its because no data was sent to the receiver
And the reason why the window size is bigger is because the receiver reads from the buffer


How does a recurrent connection in a neural network work?

When a recurrent network is calculated you can imagine the network is 'unrolled' out through time.

When visualized this way, you can see activation and loss can be calculated using the same method as a typical network.

So to clarify using the example you provided. Yes, the input to node #5 is the output from node #1, node #2, and the previous time steps node #4.

It is important to note; Typically the input and output to RNN's are expected to be time dependent. That is, for each time step t there is input t and output t. This makes RNN especially good at things like evaluating sequences. Although it is possible to keep the input and output equal throughout time.


The formal version of your statement is known as the invariance theorem, which states (informally) that any two definitions of Kolmogorov complexity differ by at most a constant. This issue is covered on any textbook or lecture notes on Kolmogorov complexity.


There is a standard for this, ANSI/IEEE Std 91a-1991. The second version is what that standard gives for the "distinctive shape symbol" (5.1-11). So if you want to know what one is "correct", it's arguably that.

The other version is not the standard, but it's extremely common and everyone knows what you mean by it. But it's not distinct.


Implementing Tarjan's strongly connected components algorithm in a language without exceptions or undefined behavior

There will always be situations where we can see there is a complex invariant but the compiler cannot derive it.  Type systems are sound but not complete: not all invariants can be expressed in the type system.  So this isn't something specific to Tarjan's algorithm; it is a general fact of life when working in a type system -- sometimes the compiler will insert type checks that the programmer can tell won't be necessary, and similarly, as a programmer you might need to insert type checks that you can tell won't be necessary.


Reconstructing Graphs from Degree Distribution

If the degree distribution is given as a list of degree, then you can do the following, given $n$ nodes with degrees $d_1, ... ,d_n$:

Create a complete graph $K_n$ on $n$-vertices. For each vertex $v_i$ in $K_n$, split it into $d_i$ copies. Split here means, create a number of copies with edges to every vertex $v_i$ has an edge to, but no edges to other copies of $v_i$. If $d_i = 0$ then simply remove the vertex. In the new graph, call these vertices $v_{ij}$ for $1 \leq j \leq d_i$.

Once you are done, you have a very dense graph on $N = d_1 + ... + d_n$ vertices; call this graph $H$. Pick your favorite algorithm for maximum matching (since the graph is so dense, you should probably use one of the fast matrix-multiplication based algorithms) and run it on $H$. This will return a matching $M$. If the matching is not perfect (i.e. if it does not cover every vertexes) then your degree distribution was impossible; so return no.

If you have a perfect matching $M$, then remove all edges not in $M$ from $H$, and then for every $1 \leq i \leq n$ merge the $d_i$ many vertices $v_{i1}, ... , v_{id_i}$ into one vertex $u_i$. Merging two vertices means combining them into one, such that the resulting vertex has edges to every vertex at least one of the original had an edge to. Call the resulting graph $G$; it has the desired degree distribution.

The resulting runtime is $O(N^\omega)$ where $\omega$ is the constant for the fastest matrix-multiplication algorithm (which at the time of writing is about $2.373$). In terms of number of vertices in the resulting graph, in the worst case of degree distribution being dense, we have $O(n^{2\omega})$.


Why does the operating system switch an active process to different cores?

Multitasking works like this: allow user process to execute for a little, then switch back to OS scheduler to be able to execute something else.

In multicore architectures, every core has equal opportuninty to acquire the process.

If you want to force your process execution on the selected core, this selection must be stored somewhere. There’s usually no reason to do that.


Strictly speaking, your statement is invalid because $\ldots$ is not part of the syntax of first-order logic. However, your statement is an abbreviation of a statement in first-order logic. For example, when $n = 3$, your statement is an abbreviation of the bona fide statement
$$ \forall x, \exists y_1, y_2 (x \neq y_1) \land (x \neq y_2). $$
As long as you understand this difference, you can use the statement. Your statement is stated in the metalanguage, and it corresponds to a bona fide statement of the language.

Here is a similar example. The following defines a number, for every integer $n \geq 1$:
$$
\overbrace{11\cdots 1}^{\text{$n$ times}}
$$
For example, when $n = 5$, this number is $11111$. While the notation above, which belongs to the metalanguage, is not in itself a valid number, for every specific $n$ it satisfies a valid number. You can think of it as a pattern, a number scheme (in your case, a statement scheme), or a function that takes $n$ and outputs a number (in your case, a statement).

That said, your statement (for every $n > 1$) states that there are at least two different objects in the universe. So while it is a valid statement, it doesn't state what you intended it to.


here, you are multiplying the depth of the "parent" array, instead of the nested array.
sum+=(depth)* productSum(array[i],depth+1)

try this
 sum+=(depth+1)* productSum(array[i],depth+1)

multiply it by depth+1


Longest path in a strongly connected component

You won't be able to find any efficient algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$.
Consider an instance of Hamiltonian path: given a graph $H=(V,E)$ on $n$ vertices decide whether it contains a simple path of length $n-1$. This is a well-known $\mathsf{NP}$-hard problem.
Construct $G$ from $H$ by adding two vertices $x$ and $y$, the edges $(x,y)$ and $(y,x)$, and all the edges $(y,v)$ and $(v,y)$ for $v \in V$. Notice that the only strongly connected component of $G$ is $G$ itself.
There is a simple path of length $n+1$ in $G$  if and only if there is a path of length $n-1$ in $H$.
Indeed, if $P = \langle v_1, v_2, \dots, v_n \rangle$ is a path of length $n-1$ in $H$, then $\langle x, y, v_1, v_2, \dots, v_n \rangle$ is a path of length $n+1$ in $G$.
Conversely, if $P$ is a path of length $n+1$ in $G$, $P$ must have $x$ as one if its endpoints (as otherwise $x$ would have one in-neighbor and one out-neighbor in $P$, but the only in/out neighbor of $x$ is $y$, contradicting the hypothesis that $P$ is simple). Then $P$ is of the form $\langle x, y, v_1, v_2, \dots, v_n \rangle$ and $\langle v_1, v_2, \dots, v_n \rangle$ is a path of length $n-1$ in $H$.