Where/how did a $\log(n)$ factor disappear from well-known algorithms?

You're not wrong, you're just using a different cost model.

Typically there are two:

  Uniform cost model - assigns a constant cost to every machine operation regardless of size of numbers.
  Logarithmic cost model - assigns a cost proportional to the number of bits involved for each machine operation.

Under uniform cost, a binary search takes constant operations to find the next index to search at, we get a recurrence relations like so:
$$\begin{align}
T(1) & = O(1)\\[0.5em]
T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + O(1)\\[0.5em]
& = \Theta(\log n)
\end{align}$$

Under logarithmic cost, we can assume it takes $f(n)$ operations to find the next midpoint and we get a recurrence like so:
$$\begin{align}
T(1) & = O(1)\\[0.5em]
T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + f(n)\\[0.5em]
\end{align}$$
For binary search, typically $f(n)$ will be no more than computing $\lfloor \frac{l + r}{2} \rfloor$ which would take $\log_2 n$ operations for the addition, and to divide by $2$ we could do a bit shift taking $\log_2 n$ operations (see here). Which brings us to:
$$\begin{align}
T(n) & = T\left( \left\lfloor \frac{n}{2} \right\rfloor \right) + \Theta(\log n)\\[0.5em]
& = \Theta(\log^2 n)
\end{align}$$
These logarithmic costs are just for addition and shifting though. If you were to do other $n$-bit operations then $f(n)$ could change. For example, $n$-bit multiplication and exponentiation could be larger than $\Omega(n)$ and you would have to adjust you complexity accordingly under logarithmic cost.


Your solution doesn't quite make sense for many reasons:

The reduction should take $\langle M \rangle$ as input, and using an oracle to $Q$, decide whether $\langle M \rangle \in I$.
The reduction should be deterministic (so step 3 is invalid).
The function of the arbitrary word $u$ is not explained; indeed, steps 1 and 2 seem useless.
You don't explain what $M_1,M_2$ are in step 4 (are you trying to reduce from $Q$ to $I$?).
You don't explain how to implement step 4.

Also, you are missing a proof that your reduction works. Without a proof, your solution is wrong even if it could be completed to a correct solution.

One solution goes along the following lines (I'm assuming $L(M)$ consists of all inputs on which $M$ halts; I also say that $n \in L(M)$ is accepted by $M$):

Given $M$, let $M'$ be the machine that on input $n$, simulates $M$ on $n$, and then (if $M$ halted) tries to find an $m > n$ accepted by $M$ (if there is no such $M$, it never halts); you can implement this using the technique of dovetailing.
Give $M$ and $M'$ to the $Q$ oracle, and return its answer.

The idea is that $L(M)$ is infinite iff $L(M) = L(M')$. I'll leave you the details.


Operator precedence in propositional logic

If you look at formal definitions of the syntax of propositional logic, you will find that

$\qquad p \land \lnot q \to r$

is not a proper sentence; parentheses are needed to avoid exactly the ambiguity you mention.

Operator precedences can be used for implicit parenthesisation. You seem to be asking if there are agreed-upon operator precedences in logic.

I don't think formal logics contains this concept; formal grammars just do not lend themselves to model precedences (or any ambiguity) very well. In practice (by which I mean both blackboard writing and implemented logic parsers), we do use precedences; usual conventions include

$\lnot$,
$\land$,
$\lor$,
$\implies$,
$\iff$

in decreasing order of precedence. Using these, your example is equivalent to

$\qquad (p \land (\lnot q)) \to r$.

David's warning is apt, though: if you want to be clear, don't rely on implicit precedences. Typesetting can help -- you can e.g. group terms with spacings -- but in case of doubt, just put the parentheses. In a larger body of work, you can also state your convention once and safe symbols afterwards, provided you stick to your own rules.


Can a NP problem be reduced to another NP problem?

Suppose I have a problem $A$, which is in NP. Suppose there is another problem $B$ in NP, can I reduce $A$ to $B$?

Maybe, maybe not. It depends on what $A$ and $B$ are. I suggest you revise the concept of NP-completeness and bear in mind that every problem in P is also in NP. These will help you understand the situation better and I think you'll be able to answer your question yourself, then.

  If it is possible, can this reduction be done in polynomial time?

Not necessarily. I think when you've figured out part 1, you'll probably be able to figure this one out, too.

  Is it even meaningful (having any importance, in terms of complexity analysis) if we have a non-polynomial time reduction?

If we don't restrict the power of reductions, they're not interesting.  Let $A$ be any problem at all and let $B$ also be any problem, except for $\emptyset$ and $\Sigma^*$.  We can define a reduction from $A$ to $B$ as follows.  Choose any string $y\in B$ and any string $n\notin B$ (think: "yes" and "no").  Now define the function
$$f(x)=\begin{cases}y&\text{if }x\in A\\ n&\text{if }x\notin A\,.\end{cases}$$
This is a reduction from $A$ to $B$. It's as hard to compute as $A$ is, which could be in P, NP, quadruply exponential nondeterministic space, uncomputable, or anything else; it's independent of the complexity of $B$. Can you see why we need $B\neq\emptyset$ and $B\neq \Sigma^*$?

So unrestricted reductions aren't really of any interest. However, there are situations in which we consider reductions other than polynomial-time ones. For example, when we study computability (e.g., the undecidability of the halting problem), we usually allow any computable reduction.1 In other contexts, we use reductions that are weaker than polynomial time. There is a perfectly good concept of P-complete problems but, as a consequence of the things I wrote above (can you see why?), it's boring to consider polynomial-time reductions between problems in P. So, typically, we use logspace reductions, there.  In fact, we can consider NP-completeness with respect to logspace reductions and, as far as anybody knows, that gives exactly the same class of NP-complete problems. Sometimes, even weaker notions of reductions are used.  There are probably also contexts in which it makes sense to use resource-bounded reductions (i.e., not just any computable function) that are more generous than polynomial-time. Maybe if you were studying problems of such high complexity that, say, an exponential-time reduction would still be cheap compared to solving the actual problem.

1. Actually, thinking about it, most of the reductions you'll see in an undergraduate computability course probably can be done in polynomial time, but that's unnecessary detail if all you're trying to work out is "Computable? Yes or no."


If the edges don't satisfy the triangle inequality then the problem becomes harder. In your case the non-edges have infinite weight (since you want never to use them), so you can't expect Christofides' algorithm to be useful as such.


Algorithm for finding best match between two database rows

Assuming we're talking about a relational database, a straightforward query would be to do a theta-join on two copies of the food relation, renamed $a$ and $b$, with the condition
$$
\theta = (a.isvegan)\land\neg(a.buyorsell=b.buyorsell)\land(a.amount=b.amount)
$$
Without knowing the internal workings of the DB engine, your question about the "right" algorithm to use is impossible to answer. For instance, does the engine use, say, merge join or hash join to answer the query; is the table sorted by some attribute, do you have indexes to help you, if so how are they implemented?


Is it possible to solve maximum weight independent set in linear time for a cycle?

This can be done in polynomial time by dynamic programming. Let the cycle be $x_1\dots x_\ell x_1$ and let $I$ be a maximum-weight independent set.

First, observe that either $x_1\in I$ or $x_1\notin I$.  In the first case, $I$ is the union of $\{x\}$ and a maximum-weight independent set in the path $x_3\dots x_{\ell-1}$ and, in the second case, $I$ is a max-weight ind-set in the path $x_2\dots x_\ell$.

So it suffices to be able to find a max-weight ind-set in a path $y_1\dots y_k$.  But we can do this by the same trick: either the set is $y_1$ plus a max-weight ind-set in $y_3\dots y_k$ or it's a max-weight ind-set in $y_2\dots y_k$.


I suspect this paper has typos (see e.g., line 2 of Algorithm 1).  If so, you're going to have to guess from context what they might have meant.
It's possible that they might have meant to write
$$fd_i = \frac{\sqrt{\frac{\sum_j (x_j - \bar{x})^2}{n}}}{\bar{x}}$$
In other words: the ratio between the standard deviation and the mean of that attribute.
Who knows; this is just a guess.  You might try contacting the authors.


Is the chalk really needed in the "chalk and string labyrinth" analogy for depth-first search?

First of all keep in mind that this is just an analogy meant to convey the intuition behind the DFS algorithm on graphs.
Now graphs can be directed, which would correspond to having a labyrinth with junctions/rooms and one-way pathways between them.
Then it is possible for you to be in some room $r_0$ and to travel to some other room $r_1 \neq r_0$ as a part of your labyrinth exploration.
Maybe all paths from $r_1$ lead to a dead end, so you backtrack to $r_0$. From there you continue to explore until you reach a third room $r_2 \not\in \{r_0, r_1\}$.
The problem arises if $r_2$ has a pathway to $r_1$: without any record that you already visited $r_1$, you'd visit it again.
To stick with your analogy, you don't need strings if the floor plan of your labyrinth can be represented as a tree (rather than a general graph). Indeed, if you have a tree and some (arbitrary) order among the edges from a vertex to their children (as it is usually the case in actual implementations), you can implement a DFS without keeping any information other than the current and previous vertices of the search (i.e., an edge of the tree).


I cannot find a way to make the specification coincide with what your solutions say, but I can get very close to that (personally, I think that your solutions contain a small mistake).

The first part should be $a*((n+1)^2-h.n)$ (and not $a*((n+1)^2+h.n)$), as per the definition of $g$ in terms of $h$.

The second part, $b*(4*g.n-7*h.n)$, comes from the definitions of $h$ and $f$: $b*h.(n+1)=b*(f.n+g.n)=b*((3*g.n-7*h.n)+g.n)=b*(4*g.n-7*h.n)$.

Finally, $c*((n+1)^2+2*n+3$ is just a (uselessly convoluted) way of writing $c*(n+2)^2$.


User recognition through keystroke pattern

Keystroke dynamics is indeed a form of biometric recognition that has been studied for a long time. It was already known in the telegraph era: skilled operators could recognize each other's “fist”, similar to recognizing someone's handwriting.

As far as I know, this is not precise enough to authenticate someone. A 2005 study by Araújo et al. results in a 96.34% success rate (3.66% false acceptance) in a controlled experiment, for an imposter, for typing the same user-chosen string 10 times (see §IV.B). The false acceptance rate for a hard-to-type password is likely to be worse. It can be used as a second authentication factor, but as an authentication factor, it's pretty weak.

These days, a lot of authentication is performed remotely, with the typing device under control of the unauthenticated user, who may be the attacker. This means that keystroke dynamics is not reliable in this setting.

Keystroke dynamic is sometimes used, not as a primary authentication factor, but to raise alerts when an account might have been compromised. On its own, it has poor signal, since a user with unusual typing patterns may be wounded, tired, using an unfamiliar keyboard, etc. It can be useful in combination with other factors however.


D has polynomial verifyer, the certificate for any word $w \in D$ is at most O(|log w|) space. Prove $D \in P$

Suppose language $D \in NP$ and for every input $w \in D$, the certificate $y_w$ is of logarithmic length; $|y_w| = O(\log|w|)$, and a polynomial verifier $V(w,y)$ exists for $D$.

We can also say: a constant $c$ exists s.t for any $w \in D$ whose certificate is $y_w$, $|y_w| \leq c \log |w|$

Consider the following algorithm $A$:

Given input $x$, for every possible certificate $y_i$ of length at most $c \log |x|$, run $V(x,y_i)$

$\bullet$ If $V(x,y_i) = 1$, then $x$ has a provable witness and $x \in D$

$\bullet$ If $V(x,y_i) = 0$, continue to the next certificate. If all certificates are exhausted, then no $y_x$ exists, and $x \notin D$.

$A$ checks at most $2^{c \log |x|}$ certificates, and $2^{c \log |x|} = |x|^c$. $V$ verifies each certificate at polynomial time (say $|x|^k$), so in total $A$ runs in $O(|x|^{k+c})$ which is polynomial in $|x|$

We get that $D$ can be decided in polynomial time $\Rightarrow D \in P$


Where can I find information on Data Structures used in common software?

Off the top of my head:

Every modern operating system uses balanced binary search trees to implement the virtual memory map of a process. Windows uses splay trees, Linux and OS X use red-black trees, and Solaris uses AVL trees. They do this because the operating system needs to store the virtual memory map in order (by virtual address), to allow for fast insertion and removal, and to look for unused regions where it could allocate space.

Many modern 3D games (e.g. anything which uses a recent version of Unreal Engine) use octrees to determine what objects are visible to the camera. They do this because it's quite efficient to calculate what nodes overlap with a camera's view frustum.

Many (if not most) routers use radix trees to implement routing tables. They do this because it is often the prefix of a network address (i.e. the most significant bits) which is important, not the whole key. Moreover, lookup takes time which only depends on the size of the address, not the number of routing table entries, which makes predicting timing easier.

Hash tables are, of course, used everywhere. Antivirus software uses it to perform lookups in its database of known malware, word processors use it to perform spelling checks, etc.

Graph data structures are used by spreadsheets to implement evaluation. Think of each occupied cell as a node, and draw an arc between to cells if the value of one directly depends on the value of the other. When an entry changes in a cell, the graph is traversed to determine which cells need updating based on that change.


Are shift and goto moves for all LR parsers ( LR(0), SLR(1),CLR(1),LALR(1) ) same?

Every reduce action corresponds to a production; the action "undoes" the production by replacing its right-hand side with the non-terminal which produced it.

That can only happen in one way; the parsing automaton does not invent or suppress non-terminals. So it doesn't matter which algorithm was used to create the automaton; the actions will be the same.

The automata may have different numbers of states, so the state sequence may differ. But not the actions performed on state transitions.

To put it another way:

If a grammar has an *LR automaton, the grammar is unambiguous, which by definition means that there is only one rightmost derivation. A rightmost derivation, written backwards from sentence to start symbol, can be represented as a series of shifts and reduces. Any LR grammar which recognises a sentence in this grammar must produce the same rightmost derivation, so it must perform the sane sequence of shifts and reduces.


Is the isometric path cover problem NP-complete?

This question is mentioned in a recent (2017) paper, Strong geodetic problem in networks:
computational complexity and solution for
Apollonian networks by Paul Manuel, Sandi Klavžar, Antony Xavier,
Andrew Arokiaraj, and Elizabeth Thomas. On page 8, they state:

  To our knowledge, the complexity status of the isometric path problem is
  not known.


Is Artificial intelligence simply taking decisions on the basis of values produced by a machine learning model

Artificial Intelligence is a very broad area of Computer Science which is intertwined with many other fields, and someone might argue that its definition is the discipline that develops rationally acting systems.

When it comes to Machine Learning, the generally accepted definition is programming computers to perform a specific task without specific instructions about the problem.

Being that broad of a field, AI comprises Machine Learning problems, but the difference between the two areas relies on how you devise your system:

if you make use of problem-specific knowledge in your algorithm: you're outside the ML field;
if you formulate your problem in a general-enough manner and use a generic algorithm: most likely you're inside the ML field.

I'm sure you have already seen this image from Nvidia a million times already, but it's intuitive to understand what's the relationship between AI and ML: the latter is part of the former.


pda: transformation between acceptance by empty stack and final states

If I am understanding this correctly, you want to transform a PDA with final state acceptance into one that accepts by empty stack.

First point is, like you mention, when entering an "old" final state to go into a special state where the stack is emptied.

Second point is that we do not want to reach an empty stack at another moment during the computation. Note in that case the old automaton does not accept, but the new one accidentally does! The solution is (indeed) to add a new bottom symbol that can not be removed except at the special state. In that way accidental accepts are avoided. (And this what I understand is the extra part of the construction.)


I don't know precisely how Bob works, but let's talk about clause learning.
Suppose you have a set of variable assignments, $A$, say $x_1 = 0$, $x_2 = 1$, $x_3 = 0$. This is a single clause in disjunctive normal form:
$$A = \neg x_1 \wedge x_2 \wedge \neg x_3$$
The negation of this set of assignments is a single clause in conjunctive normal form:
$$\neg A = x_1 \vee \neg x_2 \vee x_3$$
So if you have a set of variable assignments that you know you never want to see in any solution, you can add its negation to a SAT problem in CNF and it remains a SAT problem in CNF.
With conflict-directed clause learning, you add clauses which correspond to "dead ends" in the search. Suppose you try some assignments and find that this is not a valid SAT solution. This means that you have identified a CNF clause which is unsatisfiable (i.e. a "conflict"). So if you can find an appropriate subset of assignments that inevitably leads to the dead end, and add its negation as a new clause, this has the effect of directing the search so that it will not get stuck in that dead end any more, while also not changing the solution set.
For model counting, you find a solution to the SAT problem, add its negation as a new clause, and then go try to find a solution to the augmented problem.
It would be big news indeed if adding the negation of a known solution to a SAT problem meant that the solution that you explicitly negated is still a solution. I suspect Bob has a bug.


What do f(x) and g(x) represent in Big O notation?

Summary: $f$ and $g$ are typically functions, and $f$ is typically the runtime and $g$ is typically the asymptotic complexity of $f$. But if any of this is unclear from the description, I think it is best to either find another explanation, or to forget about application domains and intuitions for a second and go back to the definitions.

They're both functions. The fact that they are named "f" and "g" is probably due to the usual naming convention of functions, just like "x", "y" and "z" are usual names given to variables.

In this context, $f(x)$ is often the runtime of the algorithm under question, while $g(x)$ is used to denote the asymptotic complexity of $f(x)$; so $f(x) \in O(g(n))$ (or, $f(x) = O(g(n))$). But, convention or not, what $f$ and $g$ are, and they're relation to each other (if any), should be clear and unambiguous from the explanation. Not something that the reader has to guess based on what it usually means. (And the reader should have the mathematical maturity that is necessary to understand the concept.)

Personally, when I am confused about terms and names that are being used, I like to try to forget everything that the terms and names are ultimately used to represent. In computer programming, big-o is often used to describe algorithms. But big-o notation itself abstracts such things away; it is only about functions and their relation to each other. Forget about "runtime", "complexity" or anything else that has to do with the intended application of the notation.

Here is an example:

  Let $f$ and $g$ be two functions defined on some subset of the real numbers. One writes

  $f(x) = O(g(x))$ as $x \to \infty$,

  if and only if there is a positive constant $M$ such that for all sufficiently large values of $x$, $f(x)$ is at most $M$ multiplied by the absolute value of $g(x)$. That is, $f(x) = O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that

  $|f(x)| \leq M \cdot |g(x)|$ for all $x \geq x_0$.

We see that $f$ and $g$ are functions. Together with all the variables used, and the relations between them, what $f(x) = O(g(x))$ means is as clear as you might reasonably expect from a Wikipedia article on a mathematical topic. We don't have to consider what this notation is supposed to be used for, and neither what those functions are even supposed to represent/model. Now, going back to the application domain of algorithm analysis; can we use this notation to describe algorithms? Yes, since runtimes of algorithms are just functions on real numbers. Then what does it mean when $f(x) = O(g(x))$, in the context of algorithm analysis? If $f(x)$ is the runtime of the algorithm, then this notation means that $f(x)$ (a runtime) does not grow more quickly than a multiple of $g(x)$, for sufficiently large $x$. That's all from reading from the definition, and interpreting $f(x)$ as a runtime.

Pitfalls of convention

Sometimes, conventions can be misleading. In fact, we've seen a "violation" of a usual mathematical convention in this post.

$f(x) = O(g(n))$

Here, the $=$ sign is used. At least for us non-mathematicians, we are used to this sign denoting a sort of equality between two things. This usually means that the two things are of the same type, e.g. they are both real numbers, and that they are equal in some sense. In particular, $=$ is often an equivalence relation. But this is not the case of this particular use of the $=$ sign. First of all, $f(x) = O(g(n))$ does not mean that $f(x)$ and $g(x)$ are equal: the closest "normal" relation to this is "$f(x)$ is less than or equal to $g(x)$", which obviously has nothing to do with equality (except as a special case). Secondly, $f(x)$ and $O(g(x))$ are not even of the same type: $f(x)$ is a function, while $O(g(x))$ is a class of functions. (An alternative notation to $f(x) = O(g(x))$ is $f(x) \in O(g(x))$, which I used in the beginning. It is arguably more "honest".)


Longest common subsequence with at most one swap

Swapping two non-overlapping subsequences is same as swapping two non-overlapping substrings of one of the input strings.

A simple algorithm would be to guess the start and end points of the substrings that we want to swap, let them be (s1,t1) and (s2,t2), and run LCS using this swapped string. There are O(m^2*n^2) such guesses and each one takes O(m*n).


I want to pursue a career in computer programming. Where do I start?

You are already making iOS Apps, so you most likely already know at least 1 programming language. You don't need a degree in computer science to be a programmer. You (usually) need a degree in computer science to be a computer scientist.

You should continue programming, as it's the only way you'll get better. If you want to put it on your resume you need to be extremely fluent in at least 1 language and show that you're fluent (you're off to a great start with those iOS apps).

Employers don't look for a CS degree, although it is nice. Most jobs require a bachelors degree, but not in computer science per se.

Putting personal projects on your resume along with an explanation of your ability to write code should be good enough. And trust me, they will be testing your abilities as a programmer from the second you get a callback.

During the first interview, you will most likely be asked to write code on paper with a developer at the company. If you pass that, they might ask you to complete a lengthy exercise to demonstrate your proficiency.

So in my opinion: Keep doing what you're doing. If you want to land a job as a programmer master at least 1 language.


Dijkstra’s in a graph with negation of edges

The answer is FALSE.

Contradicting example: (starting from S)

Running Dijkstra on the following graph will not find the longest path from S to D (S->A->B->C->D). Due to removing node C from the queue too soon (before the relaxation of node B), hence prev(D) = E.

Please follow the correctness argument of Dijkstra's algorithm, which relies heavily on the edge weights being positive.

In addition, longest path problem is computationally hard. (NP-Hard).


DFA which visit a specific state at least once

You can add the "have seen $r$" information as follows.

Based on the old DFA $A = (Q, \Sigma, \delta, q_0,F)$ construct a new one $A' = (Q', \Sigma, \delta', q'_0,F')$. State set of $A'$ equals $Q'=Q\times \{0,1\}$, which adds a bit to the original states.

In each step you mave along just like the original automaton, except when entering state $r$ when we set the bit to $1$.

Initial state $(q_0,0)$: initial, not seen $r$. Final states $F' = F \times\{1\}$: final and seen $r$.


How to find all topological sortings of a special DAG in O(N^2)

First, the problem is about counting, not finding, all the topological sorts (though it is still hard for general DAGs). Second, the constraint that the graph is a tree makes this problem much simpler.

Consider a node $n$ with $k$ children $n_1,\ldots,n_k$. Suppose the subtrees rooted by $n_1,\ldots,n_k$ are respectively $T_1,\ldots,T_k$, the sizes of $T_1,\ldots,T_k$ are respectively $s_1,\ldots,s_k$, and the numbers of topological sorts of the members in $T_1,\ldots,T_k$ are respectively $c_1,\ldots,c_k$, then the number of topological sorts of the members in the tree rooted by $n$ is

$$\frac{(n_1+\cdots+n_k)!}{n_1!n_2!\cdots n_k!}c_1c_2\cdots c_k.$$

Using the formula above, you can compute the number of topological sorts of the members in each subtree from bottom to top. This results in an $O(N^2)$ algorithm.


Which inductive schemes can encode the following Agda definition?

No scheme that I know of directly encodes that type. Sometimes it's called a "nested" inductive definition. The complication here is that Maybe and List are type constructors which are external to the signature, and we have to formalize strict positivity for external type operators in general, if we want to allow such definitions.

In other words, the consistency of A depends on the definition on Maybe and List. Some external type operators are not positive, as in:

data Neg (A : Set) : Set where
  neg : (A -> Bool) -> Neg A

data B : Set where
  b : Neg B -> B

Agda does look into all the external definitions and tries to determine the variance of type parameters. While I don't know a reference for a direct formal specification of this, an easy way to reformulate nested definitions as non-nested is to include the external type operators into a mutual inductive signature. For example:

data A : Set
data ListA : Set
data MaybeListA : Set

data A where
  a : MaybeListA -> A

data ListA where
  nil : ListA
  cons : A -> ListA -> ListA

data MaybeListA where
  nothing : MaybeListA
  just : ListA -> MaybeListA

This is an ordinary mutual inductive type, which is covered (modulo cosmetic details) by Dybjer's inductive families.


Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too?

Éva Tardos gave a function which can be computed by a polynomial size general circuit but requires an exponential size monotone circuit. The circuit computes a good enough approximation to the Lovász theta function of the input graph.

Razborov gave an $n^{\Omega(\log n)}$ lower bound monotone circuits computing the bipartite perfect matching function, for which polynomial size general circuits exist.


Do all programming languages adhere to the IEEE 754-2008 standard?

For example, C and C++ don’t adhere to it. They don’t define the details of floating point arithmetic. An implementation may adhere to that standard, and there is a standard way to inform the user about it.

I used one compiler with ieee compliant 32 and 64 bit floating point, and totally non-compliant 128 bit fp with roughly 105 bit mantissa.


Proving the equivalence of two definitions of NFA acceptance

Just a hint:

First, generalize the problem: show that, for any $q\in Q$ and any word $w$, $q \in\hat\delta(S,w)$ if and only if $\exists r_0,...,r_{|w|}\in Q$ such that $r_0\in S$, $r_{|w|}=q$, and $r_{i+1}\in\delta(r_i, w_{i+1})$.
Second, show this statement by induction on the length $|w|$ of $w$. This is trivial for the base case, and should be easy for the inductive case, just apply the induction hypothesis and the definition of $\hat\delta$.
Finally, show that your equivalence follows from the general statement: apply it for any $q\in F$.


Let $A$ be your array, let $B$ a circular subarray of $A$ that maximizes $\sum_{b \in B} b$, and let $C$ be the subarray that contains all elements of $A$ that are not in $B$. Notice that $C$ is also a circular subarray.

You have $\sum_{a \in A} a = \sum_{b \in B} b + \sum_{c\in C} c$, which implies that $\sum_{c \in C} c = \sum_{a \in A} a - \sum_{b \in B} b $. Since $\sum_{a \in A} a $ is a constant (w.r.t. $B$) and $B$ maximizes $\sum_{b \in B} b$, $C$ minimizes $\sum_{c \in C} c$.

Moreover, at least one of $B$ and $C$ is not only circular but also contiguous and can therefore be found in $O(n)$ time.


k-nearest neighbors (Euclidean distance): How to process multiple attributes?


Advantage of using generating functions in analyzing an algorithm

Generating functions can be used to solve recurrence relations more complicated than linear recurrence relations with constant coefficients. As an example, let us consider quicksort (credit: lecture notes of Rezaul A. Chowdhury). Let us denote by $t_n$ the average number of comparisons performed by quicksort when the pivot is chosen at random. We have $t_0 = 0$ and for $n \geq 1$,
$$
t_n = n-1 + \frac{1}{n} \sum_{k=1}^n (t_{k-1} + t_{n-k}) = n-1 + \frac{2}{n} \sum_{k=0}^{n-1} t_k.
$$
Some work shows that the generating function $T(z)$ of the $t_n$ is
$$
T(z) = \sum_{n=0}^\infty t_n z^n = \frac{2\log \frac{1}{1-z} - 2z}{(1-z)^2}.
$$
From this it is not hard to extract the formula
$$
t_n = 2(n+1)H_n - 4n.
$$

In this particular case, there are more direct ways to calculate $t_n$. However, in more sophisticated situations, such tricks might not work. Furthermore, generating functions lead to mechanical manipulations - in fact, a software package can probably convert the recurrence for $t_n$ to the generating function, and hence to the exact expression. In this sense, generating functions generalize linear recurrence relations with constant coefficients by providing a large class of recurrences whose asymptotics can be ascertained.


Determining Number of States in a Turing Machine

I am afraid you cannot tell the number of states from an informal description. There may be states needed to handle trivial details or limit cases that are not obvious from that description. So the answer is usually: as many states as needed to actually implement the behavior described informally.

Better precision may be required when analyzing some complexity issues, though even then it may be up to some constant.

For simpler problems, people may give a detailed description of the TM where you can count the states. This may also happen when you study techniques for combining 2 TMs in some way. Then you may want a formula that gives you (a bound for) the number of states of the combination from the number of states of the 2 initial TM (and possibly some other parameters of the twp TM)

But describing TM in details is like programming in machine language: very tedious and highly prone to errors and bugs of all kinds. And usually you do not have a testing environent.

If there is a methodology, it is probably in combining TM that can perform some specific tasks. It is like library functions in programming languages, which implement specific algorithms that you combine to solve a problem.

So the informal description may also, to some extent, be understood as a high-level language that does not yet have a compiler. So you do not really know what machine code you will get. But do not take this last sentence too seriously.


Linear codes : why has the parity check matrix dimensions $(n-k)*k$?

You can have as many rows in $H$ as you like, but they will be linearly dependent after you reach $n-k$ independent rows.  You can apply the rank-nullity theorem.  If you like, think of the rank of $H$ as the number of pivots you get, when you row reduce.  It is the same number you get when you column reduce.  Now for $H$ is a $s\times n$-matrix with kernel of dimension $k$.  That means by the rank-nullity theorem that $\mathrm{rank}~H+k=n$.  So $\mathrm{rank}~H=n-k$ but rank is just the number of pivots (either from row or column reducing).  Said another way, $s\geq n-k$ and if $s>n-k$ then after row reducing you get just $n-k$ nonzero rows.  So the most compact $H$ is $(n-k)\times k$.

Usually one thinks of generator and parity check matrices as having been row/column reduced with 0 rows serving no purpose so omitted.  That forces your dimensions. But yes in principal you could repeat yourself, it just wouldn't help or be what anyone expects.  But no, you can't choose just 2 that will make for a larger kernel in general.


Shortest past including an edge from a given set

Create two copies of your graph. The first copy represents not having taken a good road, and the second copy represents having taken a good road. You transfer between the copies by taking a good road. The weighting scheme you describe will result in minimizing the number of broken roads. Details left to you.


What is the difference between transmission delay, queuing delay, and processing delay?

There's some similarity.  In the end, they all get bundled up into one big "delay" factor, but the size of the delays depends on different factors so it makes sense to break them apart.

Transmission delay is a delay based on how long it takes to send the signal down the transmission line.  This includes costs like the time it takes for an EM signal (or other signal) to propagate from one side to the other.  It also includes costs like training signals that are often put on the front of a packet to help the receiver synchronize clocks.  The important factor to transmission delays is that the packet is in motion.  Once the transmission period starts, bits have to keep appearing on the wire one after another, without unexpected delays.
Queuing delay is a delay based on how long the packet has to sit around in the router.  Quite often the wire is busy, so we can't transmit a packet immediately.  In these cases, the packet sits, ready to go, in a queue.  These delays are almost entirely defined by the amount of traffic on the network (often queuing delay is the only traffic dependent part of the puzzle!).  The more traffic there is, the more likely a packet finds itself stuck behind another packet in the queue, just sitting in memory, waiting.
Processing delay is the delay based on how long it takes the router to figure out where to send the packet.  Once it figures it out, it will queue the packet for transmission.  These costs are predominantly based on the complexity of the protocol.  The router must decode enough of the packet to figure out which queue to put the packet in.  Sometimes that's easy, sometimes it's not.  Typically the lower level layers of the stack have simpler protocols.  If a switch doesn't already know which physical port to send a packet to, it will typically send it to all ports, queuing the packet in many queues immediately.  On the other hand, at a higher level such as those which come into play in IP protocols, the processing may include making an ARP request to find out the physical address of the destination before queuing the packet for transmission.  One may choose to call that a processing delay.


Training a neural net without labels in Reinforcement Learning

What you are looking for is DQN: Deep Q-Network.

You want to have a look at the example code, but the idea is as follows:

Input: The observation
Output: Reward - the action can either be in the input or better one reward-prediction per possible action, if the action is discrete.

For final states, you know the true reward. Hence your target is clear (see line 112). But if this is not the case, you need to adjust the target to the observed reward and the discounted expected reward (line 113ff).

Extremely important: The output layers activation function. Don't use softmax, as it is unlikely that your rewards sum up to 1. Don't use ReLU if the reward can be negtive. Simply using a linear output makes most sense in most cases.


are they any implications if i reduce a sha256 result into 248 bits?

You will get slightly more collisions, which is not a problem in many use cases, but overall hash properties are preserved.

If some hash loses its properties by omitting last few characters (or any selected ones), then hash is flawwed by having internal correlated structure.

In fact, NIST publication effectively trims hash to desired number of bits.


Explain this Neural Network used for Knowledge Graph Embedding

Well basically, without loss of generality, they use a single hidden layer for the neural network to show theoretical capabilities of those networks. Practically, sometimes it is better to use more hidden layers and sometimes, on the other hand, adding more hidden layers only adds complexity and it is more time consuming for a model to be trained. if your data is linearly separable (which you often know by the time you begin coding a NN) then you don't need any hidden layers at all. Of course, you don't need an NN to resolve your data either, but it will still do the job.

In their experiment, they are using 3 hidden layers. People usually come up with the best number of hidden layers by experiment. There is no magic formula for selecting the optimum number of hidden neurons. However, some thumb rules are available for calculating the number of hidden neurons. A rough approximation can be obtained by the geometric pyramid rule proposed by Masters (1993). For a three layer network with n input and m output neurons, the hidden layer would have $ \sqrt{n \times m} $ neurons.


Why do we not use CFGs to describe the structure of lexical tokens?

You don't use CFGs because typically lexical analysis can be performed using regular automata, and these are faster than context-free parsers. It's a question of efficiency.


Hint: Given a mixed strategy for both players, how can you verify that it's a Nash equilibrium? How many potential strategies do you need to consider in both cases?


Here is an example that will hopefully make things clearer. Consider the problem 3COL, which is the set of all graphs that can be legally colored using 3 colors. It is conjectured that no polynomial time algorithm can determine whether a graph belongs to 3COL (i.e., can be legally colored using 3 colors). However, given a 3-coloring of the graph, it is easy to check whether it is legal (that is, you can do it in polynomial time). In this case:

$L$ is 3COL.
$x$ is a graph.
$t$ is a 3-coloring of $x$.
$M$ is a machine that checks that $t$ is a valid 3-coloring of $x$.

If a graph $x$ is 3-colorable, then some witness $t$, namely a valid 3-coloring, will convince $M$ that $x$ is in 3COL. Conversely, if a graph $x$ is not 3-colorable, then no 3-coloring $t$ would be valid, and so $M$ will always reject given inputs $x$ and $t$ (for any $t$). This shows that 3COL is in NP.

What happens if $t$ is the same for all $x$? In this case we can hard-code $t$ into the algorithm, and do away with the witness. Under such a definition we get P rather than NP.

What if $t$ is allowed to depend only on the size of $x$? The corresponding class is known as P/poly, and is important in computational complexity. It is more generally known as the class of (languages accepted by) polysize circuits. If you find this interesting, many advanced textbooks discuss this topic.


Meaning of $\triangleright$ in programming language semantics

Most probably, in your context, ▹ is just a syntactic separator, meaning "in the environment to the left of ▹, the formula to the right of ▹ holds".

However, ▹ has no fixed meaning in general. I used it myself with completely different definitions.


How to tell if a spanning tree is a shortest-spanning tree of a DAG?

Draw the tree you're given and add all edges from the initial graph in a different color (e.g. red). Then the tree is a shortest-path tree of the graph (there might be several of them) iff. no red edge breaks "the shortest-path structure", i.e. iff. it is never faster to go through a red edge than only through tree edges.

Therefore, if you pre-compute the distance $d_T(u)$ from the source to every node $u$ in your input tree, you just have to check, for every red edge of length $l$ between two nodes $u$ and $v$, whether:

$$d_T(v) \le d_T(u)+l$$


You could use the breadth first search (BFS) algorithm. The knight may move at most to eight cell (from a single position) which means that if each cell is treated as a single node then degree of each node is at most eight and so the number of edges is at most $\frac{8N}{2} = 4N$, where $N = n^2$ is the total number of nodes/cells and $n\times n$ is the size of the chessboard. Since BFS' complexity is $O(V + E)$ your algorithm will run in $O(N+ 4N) = O(N)$.

Warning: do not try to create a graph from the chessboard. It is overkill. You just need to maintain queue and mark all visited cells as you iterate. While the knight is at the position $(i,j)$ just compute all possible moves from this position and push them into the queue if they are not already visited and you haven't yet reached $(n-1, n-1)$.


What is a regular expression that matches all strings over the alphabet except a particular substring?

Just draw the minimal complete DFA accepting your string, change the final states to get the complement and now convert this new DFA to a regular expression.

In your case, you will get $\mathcal{A} = (Q, A, \cdot, 1, F)$ with $Q = \{0, 1, 2, 3\}$, $A = \{a, b, c \}$, $F = \{3\}$ and $1 \cdot b = 2$, $2 \cdot a = 3$ and $q \cdot x = 0$ for all other transitions. Thus the automaton for the complement is $\mathcal{A}' = (Q, A, \cdot, 1, F')$ with $F' = \{0, 1, 2\}$.

Converting $\mathcal{A}'$ to a regular expression gives
$$
  1 + b + (c + bc + baA)A^*
$$


How to perform bottom-up construction of heaps?

Five nodes is plenty to make a tree. See for example here. His first example has 6 nodes, not 5, but it should get you started.

A heap is a binary tree with all levels filled except, perhaps, the last. The last level is filled in left-to-right until you run out of elements.

So yours would start out like this:

The heap invariant is that each parent is smaller than both its children. In the heap construction algorithm you work bottom up, restoring the heap invariant. One way to do this is a recursive post-order tree traversal:

Heapify (x):
    if (x->is_leaf) return x
    l = Heapify (x->left_child)
    if (exists(x->right_child)):
        r = Heapify (x->right_child)
        if ((r->value < x->value) && (r->value < l->value)):
            swap(r->value, x->value)                    # r->value was smallest
    if (l->value < x->value):
        swap(l->value, x->value)                        # l->value was smallest
    return x

In actual code for heaps the heap is often represented as an array with the elements stored top-to-bottom and left-to-right in each level. The first element is the root, the second and third elements are the children of the root, and so on. In this case you can do the initial heap creation by working backwards through the array to get a post-order tree traversal for cheap (i.e., as an iterative algorithm that doesn't need to recurse).


Finding the cheapest buy order with fixed inflation for each product

The problem in the question
The price of product $p$ at time $t$ is $b_p{r_p}^t $, where $p$ and $t$ are integers between 1 and $n$.. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nb_pr_p^{f(p)}$ is minimum.
A more general problem and polynomial-time algorithms
The price of product $p$ at time $t$ is $c(p,t)$, where $p$ and $t$ are integers between 1 and $n$. We want to find a permutation $f$ of $1,2,\cdots,n$ such that $\Sigma_{p=1}^nc(p,f(p))$ is minimum.
The problem above is none other than the famous assignment problem. There are various polynomial-time algorithms to solve it. For example, this version of Hungarian algorithm runs in $O(n^4)$ time.
For the problem in the question, it can also be solved in polynomial time since we can compute all $b_pr_p^t$ for $1\le p, t\le n$ in $O(n^2)$ time.


I would not know what you learned or did not learn, What is surprising depends a lot on who is to be surprised. So your question is pretty much undefined.

All I can do for you (but I am no expert) is to mention one technique that impressed me when I first saw it, the skip lists of William Pugh. And more generally the use of randomness and  probabilistic techniques, actually not just in algorithmics but also in "proving" or in quickly identifying things that can then be formally proved (at high computational cost) to have this or that property.


Why are problems in P easy and other problems not

Your definition of "easy" doesn't make much sense. What exactly does "solving more instances at each time unit" mean?

Usually our notion of hardness refers to our ability to "solve" one instance. More formally, let $T(n)$ be the amount of operations required (proportional to time) for inputs of size $n$, then by "hard" we usually mean that $T$ grows too fast.

As for why polynomial $T(n)$ is considered easy, see this question.


Incomputable sets of low degree vs Rices theorem?

This is not an answer, but way too long to be a comment.  I just wanted to cite Robert I. Soare's Recursively Enumerable Sets and Degrees, Chapter V: Simple Sets and Post's Problem.

1: Immune Sets, Simple Sets, and Post's Construction
The only r.e. degrees constructed so far are $\textbf{0}$ and
$\textbf{0}'$.  Post's Problem was to construct other r.e. degrees,
i.e., to construct an r.e. set $A$ such that
$\emptyset \lt_\text{T} A \lt_\text{T} \emptyset'$.  Post's Program
for constructing such a set $A$ was to ﬁnd some easily deﬁnable property
on $\overline{A}$ (compatible with $A$ being nonrecursive) which
guarantees incompleteness ($K \not\leq_\text{T} A$).
Recall (from Theorem II.4.5) that $K$ (and hence any creative set) has
an inﬁnite r.e. set (and therefore inﬁnitely many inﬁnite r.e. sets)
contained in its complement. Post's idea for constructing $A$ incomplete
was to make $\overline{A}$ sufﬁciently "thin" with respect to
containment of inﬁnite r.e. sets so that $\overline{K}$ could not be
Turing reduced to $\overline{A}$.
1.1 Deﬁnition. (i) A set is immune if it is infinite but contains no
infinite r.e. set.
(ii) A set $A$ is simple if $A$ is r.e. and $\overline{A}$ is immune.
1.2 Proposition. If $A$ is simple then:
(i) $A$ is not recursive;
(ii) $A$ is not creative;
(iii) $A$ is not $m$-complete (i.e., $K \not\leq_m A$).
Proof. (i) $\overline{A}$ cannot be r.e., since otherwise it contains an
inﬁnite r.e. set (namely $\overline{A}$).
(ii) The complement of a creative set does contain an inﬁnite r.e. set (by
Theorem II.4.5).
(iii) If $K \leq_m A$, then $A$ is creative (by Corollary II.4.8). $\Box$
1.3 Theorem (Post [1944]). There exists a simple set $S$.
Proof. Let $A = \{(e,x) \;:\; x \in W_e \;\&\; x > 2e \}$.  Now $A$ is
$\Sigma_1$ and hence r.e. Let $\psi$ be any p.r. selector function for
$A$ (in the sense of Theorem II.1.6) and let $S = \text{rng}\; \psi$.
(Intuitively, enumerate $W_e$ until the ﬁrst element $\psi(e) > 2e$
appears in $W_e$, and then put $\psi(e)$ into $S$.) The following facts
give the simplicity of $S$.
(1) $S$ is r.e. ($S$ is the range or a p.r. function.)
(2) $\overline{S}$ is inﬁnite.  To see this, note that $S$ contains at
most $e$ elements out of $\{0,1,2,\dots,2e\}$, namely $\psi(0),\psi(1), \dots, \psi(e-1)$. Hence $e + 1 \leq \text{card}(\overline{S} \upharpoonright (2e+1))$, so $\overline{S}$ is inﬁnite.
(3) If $W_e$, is inﬁnite, then $W_e \cap S \neq \emptyset$, because
$(e,x) \in A$ for some $x > 2e$ and so $\psi(e)$ is deﬁned and $\psi(e) \in S \cap W_e$. $\Box$


Exponential nested Loop Big O complexity calculation

Let n = 65,536 and write down what exactly happens. That should be enough to figure it out.


Bipartite Graph - How to determine largest subsets that are all connected

Rephrasing from On Bipartite and Multipartite Clique Problems:

You can formulate the problem as an Integer Linear Program. Let the vertices in each partition be $V_1,V_2$ respectively. Take a (binary) variable $x_v$ for each $v\in V_1\cup V_2$. Then the problem is do determine

$$\textrm{maximize } \Sigma_{v\in V_1\cup V_2} x_v \textrm{ subject to}$$

$$x_v+x_u\leq 1 \textrm{ for all } u\in V_1, v\in V_2 \textrm{ so that } (u,v)\notin E$$

In general, solving ILP's is $NP$-complete. However, in this case, the corresponding constraint matrix is totally unimodular. Consider the relaxed problem: instead of requiring all $x_v$ to be binary, we instead only require that $0\leq x_v\leq 1$ (dropping the integrality constraint). Because the constraint matrix is totally unimodular, the optimal solution to the LP will be integral (and thus also a solution for the ILP). You can use the simplex method (or if you insist on wost-case polynomial time, the ellipsoid method) to obtain a solution for the LP, which is automatically a solution for the ILP.


Solving $T(n) = 4T(n/2) + n^3$ with substituton method

Your guess works: if $T(n) \le c n^3$ and $c \ge 2$ then
$$
T(n) = 4c \frac{n^3}{8} + n^3 = \frac{c}{2} n^3 + n^3 = cn^3 \left(\frac{1}{2}+\frac{1}{c} \right) \le cn^3.
$$


Is clrs really needed to be a computer scientist

To be a computer scientist you need to be able to reason abstractly.  The reasoning expected in CLRS is an example.  You can find books with titles such as Discrete Mathematics that will help with some of the prerequisite material, and with some of the reasoning strategies.


What are some good hints for proving non-regularity with the pumping lemma?

Always notice that you apply the reverse direction of the implication stated in the lemma when proving non-regularity. That is for any $k\in \mathbf{N}$ you pick a word $w\in L$ (depended on $k$) that has length at least $k$ and there is no way to split the word into three parts, such that pumping the middle parts in or out keeps the word in the language. Notice that you only consider partitions where the first two words together have length $k$ or less, and of course the middle part is not the empty word.

So here are a few general ideas.

Keep in mind that you pick the word dependent on $k$, so $k$ usually appears in the word $w$ as a parameter. For example in $\{a^nb^n \mid n\ge 0\}$ you pick $w=a^kb^k$.
It is crucial to pick the right word $w$. Pick a word that has an easy structure. Make it as easy as possible.
Notice that you are only allowed to pump at the beginning of the word. Use this restriction, by choosing a word in which the first $k$ letters have a simple structure.
For unary languages like $\{a^{n^2}\mid n\ge 0\}$ pick a very large word and hope that the distance to the next word in $L$ is larger than $k$.  In the example pick $w=a^{k^2}$, the the next larger word in $L$ is $a^{(k+1)^2}$, but $(k+1)^2-k^2=2k+1$. Pumping the middle words once, gives a word that is too short. Another idea for unary languages is to pick $i$ in terms of $k$.
Don't forget to cover the case of pumping the middle word out.

You can see the (reverse direction) of pumping lemma as a two player game. Someone picks a $k$ then you pick the $w\in L$, then he splits the $w$ according to the rules, then you pick a repetition of the middle word. If the pumped word is not in the language then you win. If this game has a winning strategy for you, then $L$ is not regular.


What difference does it make when universal classical gates in quantum computation are reversible but not unitary?

Reversible gates are unitary, see for example https://en.wikipedia.org/wiki/Quantum_gate. The eigenvalues are $\pm 1$. The quantum computation model requires all gates to be unitary, so you can't just use classical gates.


Let $(G,k)$ be an instance of vertex cover, where $G$ is a graph on $n$ vertices, and $k$ is the threshold. Suppose furthermore that the minimum vertex cover of $G$ has size either at most $k$ or at least $ck$ for some $c > 1$; this version is already NP-hard.

Consider $n$ copies of $G$, with the addition of a clique of size $n^D$. If $G$ has a minimum vertex cover of size $\ell \leq k$ then the new graph has a vertex cover of size $n\ell+1$, and at most $\binom{n^2}{3nk+3} \binom{n^D}{2nk+3} \leq n^{(6+2D)nk + 6+3D}$ vertex covers of size $3(n\ell+1)$. If the minimum vertex cover of $G$ is $\ell \geq ck$ then the new graph has a minimum vertex cover of $n\ell+1$, and at least $\binom{n^D}{2n(ck)+3} \approx n^{2Dcnk+3D}$ vertex covers of size $3(n\ell+1)$. We can choose $D$ so that $2Dc > 6+2D$, and then the gap between the two cases is roughly $n^{(2Dc-2D-6)nk-6} = e^{\Omega(n\log n)}$.

This reduction shows that it is NP-hard to approximate the number of vertex covers of thrice the minimum size within $e^{O(n\log n)}$. The interested reader can get even better results by slightly tweaking the construction.


Determine minimum and maximum number of leaves on a complete tree

Hint:

   Try the case $h=1$.  What's the minimum?  What's the maximum?


I guess it depends on your point of view, but the proof via approximating polynomials (along the lines of Razborov-Smolensky) that Parity isn't in AC0 is not so involved...

The natural way in which one would modify the proof that "NEXP is not in ACC0" to yield "NEXP not in AC0" would be to give a SAT algorithm for AC0 circuits that beats exhaustive search. However, all known SAT algorithms of this kind actually use the same or similar techniques as the "Parity not in AC0" lower bounds, so the proof would not get any simpler. (It would be interesting to find an AC0 SAT algorithm where this is not the case.)


Is a Petri net without places well-defined?

A net without place does have "state", or a marking in proper terminilogy; as that is a mapping from the set of places into $\Bbb N$, technically this does exist even when the set of places is empty (as a kind of empty relation).

A net with one place and one transition can even change state. If the transition has an outgoing arrow to the place, the transition can add tokens into the place. (Tokens can be created, they aren't physically moved from one place to another.) Effectively the behaviour will be that of a upward counter.


Assumption: A PSPACE-hard problem can be solved in polynomial time

Your argument is perfectly fine. However, you actually do not even have to argue with polynomial reduction.
Since $\textsf{P} \subseteq \textsf{NP}, \textsf{coNP} \subseteq \textsf{PSPACE}$, under the assummption that there is a $\textsf{PSPACE}$-hard problem solvable in polynomial time (i.e. it is in $\mathsf{P}$), you also have $\textsf{PSPACE} \subseteq \mathsf{P}$. Now $\textsf{NP}, \textsf{coNP}, \textsf{PSPACE}$ are sandwiched in $\mathsf{P}$ and thus, equality holds for the $\subseteq$ relations above.


Interview Questions for Minimum Cost of Tasks

Equivalence to another question
Here is how we can find the problem in the question is basically the same as the problem in another question. Hence the answer over there can be adapted easily to this problem.
     the problem here <---> the problem over there
           home tasks <---> weekly shipments
cost c[i] by yourself <---> cost s_i * r by company A
         next 4 tasks <---> next 4 weeks
   cost h by handyman <---> cost 4c by company B
         minimum cost <---> minimum cost

For example, for cost array [1,3,5,6,7,2,1,3,1000] and handyman cost  11 here, we have the corresponding problem of $r=1$, frights by pounds[1,3,5,6,7,2,1,3,1000] and $c=11/4=3.75$.
You might want to ask why or how I can connect these two problems together. A simple reason is that I wrote the answer to the other question. Another reason is that I have been solving, modifying and creating problems about algorithms constantly. I would encourage you to try that kind of exercises from time to time.
Exercises
Exercise 1. Imagine a different backdrop of this problem.

Exercise 2. (A slight generalization) Let us have the same problem as in the question, the same list of $n$ consecutive tasks and a handyman with the following change. Besides 4 consecutive tasks of the fixed cost $h$, the handyman can also do the next 3 consecutive tasks on your list for the fixed cost of $g$, regardless of how much time and effort those 3 tasks would cost you. Find an $O(n)$-time recursive algorithm that calculates the lowest cost for completing the tasks. (This problem degenerates to the original problem if we let $g$ be sufficiently large.)
Here is the idea to solve exercise 2.
Let $dp[i]$ be the lowest cost to do tasks 1 to $i$ inclusive. The base cases and the recurrence relation for $dp[i]$ is given by the following description.

When $1 \leq i \leq 2$, you have to do all the tasks by yourself.
When $i=3$, either you do all the tasks or let the handyman does all 3 tasks.
When $i\geq 4$, the arrangement of lowest cost to complete all tasks must be one of the following ways.

You will do the last task by yourself. Complete the other $i-1$ tasks with the lowest cost.
Let the handyman do the last three tasks with cost $g$. Complete the other $i-3$ tasks with the lowest cost.
Let the handyman do the last four tasks with cost $h$. Complete the other $i-4$ tasks with the lowest cost.


A good introductory book on cryptography

"Introduction to Modern Cryptography", Jonathan Katz and Yehuda Lindell. This is a great book for learning about provable security.

And for actual crypto protocols and algorithms, there's always the classic: "Handbook of Applied Crypto" by  Paul van Oorschot, A. J. Menezes, and Scott Vanstone. This is more a reference book than a textbook. And its available free of cost on one of the authors web-pages.


Are all $\Sigma^0_1$ sets of infinite sequences infinite?

First observe that any $S \subseteq \{0,1\}^\mathbb{N}$ described by a $\Delta^0_1$-formula is clopen (open and closed subset), where we topologize with the product topology. Indeed, the subbasic sets of the form $B_{i,k} = \{x \in \{0,1\}^\mathbb{N} \mid x(i) = k\}$ are clopen by definition, and then complements (negation), finite unions (disjunction and bounded $\exists$) and intersections (conjunction and bounded $\forall$) of those are still clopen.
A $\Sigma^0_1$ subset $S \subseteq \{0,1\}^\mathbb{N}$ is a countable union of $\Delta^0_1$ sets, therefore it is open. But every open subset of $\{0,1\}^\mathbb{N}$ is either empty, or it contains a basic open set and is therefore uncountable.


NFA - string acceptance (decision problem) test

A naïve backtracking algorithm will still result in exponential behaviour ($O(2^{n})$ where $n$ is the length of the input string). This behaviour can occur even with very small automata (i.e. where the number of states $m$ is a fixed constant).

Consider for example the NFA $M$ below:

The alphabet is simply $\Sigma =\{0\}$, and the language is $L(M) = \{0^{k}\mid k \in \mathbb{N}\} = \Sigma^{\ast}$. If our algorithm chooses poorly for even the first step (for example if we use the obvious choice and go by state ID), then we're stuck between $q_{0}$ and $q_{1}$, where at each point in the input, we have the choice of moving to the opposite state, or staying where we are - i.e. a binary choice for each character, for the entire length of the string, giving $2^{n}$ steps before we manage to backtrack to $q_{2}$ and then move along the correct path to $q_{4}$.

So even with only 4 states and where every string is valid, we can still get terrible performance from a backtracking approach.

There is a much better approach however. Even without converting the NFA to a DFA we can decide acceptance in polynomial time. As we are dealing with a regular language, we don't need to remember the entire computation history up to this point (which is what backtracking does), we only need to know what state we are up to at the current point. In a DFA this is very easy, as we can only be in one state at any point, but an NFA (without knowing the final computation path) allows more possibilities. However we can simply keep track of these possibilities. The algorithm is as follows:

Initialise $S_{0}$ to $\{s_{0}\}$ where $s_{0}$ is the start state.
For each symbol of the input $c_{i}$ with $1 \leq i \leq n$, for each state $s \in S_{i-1}$, let $E(s,c_{i})$ be the set of states reachable from $s$ using $c_{i}$ and any number of $\varepsilon$-moves1. Set $C_{i} = C_{i} \cup E(s,c_{i})$.
If there is an accepting state in the set $C_{n}$, return $\mathrm{YES}$, otherwise return $\mathrm{NO}$.

So all the algorithm is really doing is keeping track of all the states we could be up to after having read $k$ symbols from the input.

Assuming that the NFA is fixed, this algorithm is $O(n)$-time in the length of the input string. If the NFA is part of the input, it's a little more complicated, but still polynomial time - $O(m^{2}n)$ where $m$ is the number of states (if I haven't missed an implicit loop in there).

Footnotes.

That is, we take the $\varepsilon$-closure of the state $s$, then from each of these states see if we can move using symbol $c_{i}$, then for those where we can, we take the $\varepsilon$-closure again, and this gives us $E(s,c_{i})$.


Query Logs and evaluation of search engines

I would have selected option C.

I don't think option A is correct.  We probably can learn common typos, but that doesn't affect the time to process a search query, and it's not clear how you'd use that to speed up search queries.  (I'm assuming that "time to process a search query" is what is meant by "retrieval efficiency".)

Similarly, I don't think option B is correct.  We probably can learn the connection between different pages that a user clicked, but that doesn't appear to affect the time to process a search query, as far as I can tell.


Is process address space part of Process Control Block(PCB)?

Let me start off like this.

The process state includes all the registers that the process may be using, especially the Program counter, plus any other operating system-specific data that may be necessary. This is usually stored in a data structure called a process control block (PCB) or switch frame.
This is what happens in context switching.
The PCB is stored on a per-process stack in kernel memory (as opposed to the user-mode call stack), or there may be some specific operating system-defined data structure for this information.
When a process is ready to run again, its PCB is restored. The program counter from the PCB is loaded, and thus execution can continue in the chosen process.
So, the process's address space is not a part of the PCB data structure.


What would be the over all speed-up achieved?

Hint: Look up Amdahl's Law on your favorite search engine and plug your question into the equation you find.


Why is 2s complement of 000 equal to 111, but 9s complement of 000 is not 888?

You are very confused due what is simply poor terminology, to be honest. Both your statements 2 and 3 are false due to the same misunderstanding.
For each base $b$ there are two mainstream variants of the 'complement', the radix complement and the diminished radix complement.
The two most common bases in computer science are base $2$ and base $10$. Confusingly, the definitions usually used are:

one's complement: the diminished radix complement of base $2$
two's complement: the radix complement of base $2$
nine's complement: the diminished radix complement of base $10$ (not $9$!)
ten's complement: the radix complement of base $10$.


When using the convention that i and j are in the same square then they are for all intents and purposes regarded as the exact same letter, both in the key and in the plaintext. In the ciphertext, whenever it is required to write 'i/j' you can choose which one to write, while introducing no ambiguity for the decoder (in order to make the ciphertext 'look more random' it is probably best to flip a coin).

In particular, the Playfair tableau with key 'jargon' is the same as the tableau with key 'iargon': both have 'i/j' in the upper left-hand corner. HOWEVER, if you use an online solver tool it may be (the first site I checked had this implem bug) that j is not parsed, and the tableau is built as if the key were 'argon'; this is a (common?) implem bug though.

Note also that there other conventions than placing i and j in the same square.


Your post-traversal numbering of the component $C$ is incorrect. The vertex labeled as $1,6$ was assigned its post-traversal number too early; a depth-first search will also explore the vertices of $D$ before assigning the post-traversal number to this vertex.


Is the capacity of a hash table a constant value?

There are rare cases where the number of entries in a hashtable is fixed. There are some more cases where the number of entries in one particular situation is known, and the right number of slots can be allocated before you start filling the hash table.

But typical implementations start with a small number of slots, and if enough items are added so the expected number of collisions becomes too large, more slots are allocated and all items rearranged in the new slots.

Usually the implementation tries to keep the percentage of used slots in some range, say (just an example) between 45% and 70%, compromising between efficiency and used space. So as you add items and use more than 70% of slots are used, the implementer would increase the number of slots so that now 45% are used, and more items can be added. An implementer might also shrink the table if items are removed and say less than 30% of slots are used, but in practice hash tables tend to grow.


There are many theoretical ways to express an (arbitrarily complex) function in numbers, historically starting with the abstract model known as the Turing Machine. Those aren't always efficient for real problems, and in engineering we've settled on a pretty straightforward model.

Microprocessors (CPU's) have an associated memory which holds instructions. (1)
Instructions are discrete operations, which change the CPU is a well-defined way. There is a finite and numbered set of instructions. Instructions may have operands, such as registers to operate on, or constants to use, and these operands are also encoded as number.

The instruction pointer (or program counter) indicates where exactly in memory the next instruction is stored. It normally increments if an instruction finishes, but a jump or branch instruction can change it in different ways.

As instructions are stored as numbers, they must be decoded when the numbers are retrieved from memory. As you correctly assume, this is non-trivial. The instruction decoder will map an instruction number to a particular bit of hardware to implement the actual instruction.

Let's assume a new CPU design, not compatible with an existing CPU, to keep this simple. As a designer, we know have the freedom to choose which numbers are associated with which instructions. We're still talking CPU's, so a number is a bitstring. We can therefore decide that an instruction is a 32 bit number. We can say that the first bit decides whether the instruction is some type of jump instruction. If so, we send off the number bits to the hardware that changes the instruction pointer. Here we look at the 2nd bit to decide whether it's an unconditional jump. For simplicity, let's assume it is. The third bit may decide whether it's a branch (push IP on stack) or not. Decoding this bit is simple: if set, push. The 4th bit may indicate whether it's an absolute or relative jump. A relative jump would require us to use the arithmetic hardware of the CPU, so for simplicity assume we have an absolute jump. The 5th bit can decide whether to take the destination address from a register, or from an operand. Assuming we use an operand, we see that another number is needed from the instruction stream. This means we issue another read, using the incremented instruction
pointer (operand follows instruction). The fetched operand value becomes the new instruction pointer.

1) It's irrelevant here whether this memory is shared with data, or if it's augmented with caches.


A and B are Turing recognizable, is A - B Turing recognizable?

Suppose that $L$ is a Turing-recognizable language and $L^C$ is its complement. Let's assume, for the purposes proof by contradiction, that $L^C$ is also Turing-recognizable. This means that a recognizer exists for each of these two languages: we will call them $M_L$ and $M_{L^C}$. How might we use these two recognizers to do something absurd?

For starters, we can construct a decider for the language $L$. Given any string $w$, we can use it as input for both $M_L$ and $M_{L^C}$. $M_L$ will halt and accept if $w$ is in $L$ (and halt and reject or loop forever if not). Conversely, $M_{L^C}$ will halt and accept if $w$ is in $L^C$ (and halt and reject or loop forever otherwise). In any case, our constructed machine will halt with a decision about $w$, and so we've proven the existence of a decider for $L$.

By assuming that any Turing-recognizable language $L$ is closed under complement, we can show that $L$ is also Turing-decidable, which implies that $R=RE$. So we must conclude that Turing-recognizable languages are not closed under complement!

If they're not closed under complement, is it possible for them to be closed under set difference? (Hint: the set of Turing-recognizable languages is closed under intersection. Can you rewrite $A-B$ in terms of complement and intersection?)

(Solution: $A-B$ can be written $A \cap B^C$; loosely speaking, both describe the set of elements which belong to $A$ but not to $B$. Since set difference can be expressed using intersection and complement operators, and since Turing-recognizable languages are not closed under complement, we conclude that Turing-recognizable languages are not closed under set difference.)


Intelligent use of XOR operator to find missing number

Start with a list of any n integers. Duplicate the integers and calculate the XOR if these 2n integers. What’s the result? Rearrange the 2n integers in any way and calculate their XOR. What’s the result. Remove a number x from the list and calculate the XOR. What’s the result? Remove another number y and calculate the XOR. What’s the result?
Now go back to your problem, and the answers you gave before tell you immediately what your result will be.


Is there a problem which can be solved in $O(f_k(n))$ time for any $k$ where $\lim_{k \to \infty} f_k(n) = 0$ but no constant time solution is known?

You can sort numbers in $O(\frac{n\log n}{k})$ for all fixed $k$, and $\lim_{k\to\infty} \frac{n\log n}{k} = 0$ for all fixed $n$.


"Divide & Conquer" is not a very fixed notion. It usually goes along the lines of

  D&C algorithms divide the problem and solve recursively.

That's not very strong, for the following reasons.

What I would call inductive algorithms do this, but are usually not considered divide & conquer algorithms. Given a problem of size $n$, inductive algorithms solve subproblems (typically one) of size $n-c$ for some constant $c$ and derive a solution for the original problem. See here for an example.
Dynamic programming does exactly that, but it's not usually considered d&c. The difference is that in DP, subproblems overlap, which they don't in d&c. Also, we often don't know which subproblem is the "right" one, so we try out all possible partitionings (which causes overlapping).

Now, one might say that inductive and d&c algorithms are orthogonal special cases of dynamic programming, but that's for another discussion.

In order to "define" divide & conquer against those other types of algorithms, consider this:

  D&C algorithms divide the problem of size $n$ into non-overlapping¹ subproblems of size $\frac{n}{c}$, solves (some of²) them recursively and combines the solutions to a solution of the original problem.

By this "definition", your algorithm is not divide & conquer.

As for runtimes, d&q algorithms can typically be analysed (roughly) using the
master theorem. As you can see from the three cases, all kinds of runtimes of the form $n^a\log^bn$ can result, depending on the quality of the division and the runtime of the combining step.

As I write the part about runtimes, it occurs to me that this may be too strong. Overlaps by a constant (sized part) are fine.
Binary search can be considered the ultimate divide & conquer: by dividing cleverly, combining is unnecessary.


Is the question of whether the language of a DFA/CFG is equal to a particular set of string decidable?

Let's assume that $S$ is regular and given in some explicit form (DFA, regular grammar, regular expression, what have you). Given a DFA $D$, we can compute a DFA for $L(D) \triangle S$ (here $\triangle$ is symmetric difference) and check whether it is empty or not. This allows us to decide whether $L(D) = S$ or not.

Given a CFG $G$, we can compute a CFG $G'$ for $G \cap \overline{S}$, and then check whether $L(G') = \emptyset$. This allows us to check whether $L(G) \subseteq S$. However, in general we cannot check the opposite inclusion: determining whether $L(G) = \Sigma^*$ is undecidable (the universality problem). However, if $S$ is finite, we can check whether $G$ generates each of the strings in $S$, and thereby solve the problem.


What do two non-terminal symbols on the left hand side of a BNF grammar mean?

That seems unorthodox to me, but I'm certainly not current with all the formal language theory textbooks being used these days.

The point is that in

$$\langle expression\rangle :=\langle number\rangle \;| \;\langle expression\rangle\langle operation\rangle\langle expression \rangle$$

the two instances of $\langle expression\rangle$ on the right-hand side are unrelated to each other. In a derivation, they are derived independently and nothing constrains their derivations. Sometimes we need to refer to them (for example, when we get to semantic analysis) and then it might be convenient to give them different spellings.

I would normally use subscripts:

$$\langle expression\rangle :=\langle number\rangle \;| \;\langle expression_1\rangle\langle operation\rangle\langle expression_2  \rangle$$

but your professor seems to want to be able to say that $e$ and $f$ are aliases for the same non-terminal (but not the same derivation). This seems confusing to me. Is it really so hard to write:

$$e \Rightarrow n \; | \; e_1\; o \; e_2$$


Is the terminology of the word optimal substructure same for divide-conquer and dynamic programming technique?

The CLRS definition of optimal substructure:

  A problem exhibits optimal substructure if any optimal solution to the
  problem contains within it optimal solutions to subproblems.

This make sense for both methods.

Divide&Conquer is used when subproblems are independent, there is no overlapping subproblems. In this case you just combine solutions to resolve the main problem.

Dynamic Programming is used when subproblems are dependent, there are overlapping subproblems and results are typically stored in some data structure for later reuse.


Can repeated runs of a Las Vegas algorithm equate to a better Las Vegas algorithm?

Monte Carlo and Las Vegas algorithms are equivalent and this question is more naturally asked in terms of the former so I will pretend you asked about Monte Carlo.

Any Monte Carlo algorithm can be run multiple (say, a constant number of) times to amplify the probability of success while slowing down the algorithm. And in fact you can achieve any fixed probability of success $< 1$ while slowing down by a constant factor.

Where you "cheat" is that you adopt the convention of ignoring the constant factor in run time while simultaneously caring about the constant probability of success. As the probability can be freely adjusted by multiplying run time by a constant, caring about its particular value is equivalent to caring about the constant factor in run time so big O is inappropriate in this situation.


Creating a single layer perceptron for the OR problem

The fact that you mention linear least squares error seems to hint that they want you to use a completely linear model $u_i=Wv_i$ for your perceptron. In this case you won't get exact answers like $0$ and $1$; you will only get approximations with some amount of error.

That said, I don't think a linear model makes sense for this problem, since it is a classification problem with two classes. Using a non-linear step-like function $f$ before the final output of a perceptron classifier is a pretty standard thing to do, so I see no problem with using $u_i=f(Wv_i)$.

Assuming you can use $f$, using the weights $x_1 = x_2 = 1$ as you mentioned solve this problem exactly with zero error.


Scaling down a set of points into a smaller area

The following procedure achieves your requirements:
Step 1: Find the smallest circle that encloses all points.  (There are standard algorithms for this.)
Step 2: Compute the area of that circle.
Step 3: Compute the scaling ratio $c$ needed to achieve the desired area.  (For instance if the area of that circle is 100 and you want area 5, then your scaling ratio is $c = \sqrt{100/5} = \sqrt{20}$.)
Step 4: Scale everything down by a factor of $c$, centered at the center of the circle found in Step 1.
This can be implemented in linear time, so it should be very efficient.


Does this article imply that Turing-Computability is not the same as "effectively computable"?

First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, we want to know more than just whether a problem is computable. Most problems considered by this field are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.

As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)


Could be solved a NP-complete problem in constant time?

Write down the definition of NP-complete. Then take your assumption that P = NP, so in the definition of NP-completeness you can replace "NP" with "P". Figure out which functions exactly are NP-complete. (Hint: There is a simple and obvious solution that is almost but not quite correct. Read the definition carefully). Do these functions contain any constant time solvable problems?

Each step is actually quite simple, you just have to follow all the definitions very precisely.


The meaning of modulo in “formula modulo a background theory”

A theory, in this sense, is an equivalence relation on the formula, which states when these formula are equivalent (as in: $F$ is equivalent to $G$ iff $F$ implies $G$ and $G$ implies $F$). The theory is usually presented by a set of deduction rules, though this is not an obligation.

The word theory is often used in the context of rewriting systems: if you have rules to rewrite terms (which may be formulas, but the concept is more general) of the form $t \rightarrow t'$, then the induced equivalence relation $t_1 (\leftarrow \cup \rightarrow)^* t_2$ (any number of rewriting steps, alternating directions as often as desired) is the equational theory of this rewriting system.

Technically, “first-order formula modulo a theory $T$” means that you are manipulating equivalence classes which are sets of formulas. Intuitively and practically, this is saying that we are manipulating formulas, but we may replace a formula by some other equivalent formula at any time.


How was multiprogramming brought into computer languages

If you're really interested in all that's needed, your best choice would be to look at the standardisation process of C++11 by the ISO Working Group on C++ (WG21). All the relevant papers are available online.

Keywords are not important at all. In fact, C++ defined just one new keyword (thread_local) and that's mostly for convenience.

What is important is the memory model. Programs work by altering state, which logically exists in memory. With multi-programming, there are concurrent changes to the state of a program. This requires a reasonably precise definition of said state. To make things more complex, you want a definition of state that is compatible not just with the abstract language definition, but which is also implementable on real hardware. That gets you into problems like registers and  caches (state outside ordinary memory), the exact details of which vary significantly between real hardware architectures.

A key insight here is the sequenced concept. Two C++ operations can be sequenced, which means they cannot operate at the same time. This means they are allowed to use the same data in memory without risk. A special kind of sequencing is sequenced before, which means one operations happens before the other. This means a write sequenced before a read guarantees that the read sees the value of the write.

With C++11, there are library calls defined which can guarantee such sequencing across different threads of execution.

The comments of @rcgldr suggest that function calls like WaitForSingleObject alone are sufficient, but this isn't actually the case. You need an associated memory model. That's why you have Win32 macro's like InterlockedIncrement - these macro's provide the mapping between the language memory model and the hardware memory model. There's no Read(DWORD*) macro, though - the language memory model is that aligned DWORD reads are atomic, and it's implicitly assumed that the compiler can efficiently map every read to atomic hardware instructions.


Can number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states?

it surely can, but it needs not. Using the powerset construction you can convert any $n$-state NFA into a DFA with at most $2^n$ states.


Let the integers be $a_1,a_2,\dots,a_n$ sorted in decreasing order of magnitude, so $|a_1| \ge |a_2| \ge \cdots$, and suppose you want to find the product of $k$ of them that is as large as possible.
Then:

If $a_1 \times \cdots \times a_k$ is positive, it is the solution.

Otherwise, if $a_{k+1}$ is positive, the solution is $a_1 \times \cdots \times a_{k+1}$ (but omit $a_i$ from the product, where $a_i$ is the largest of the negative numbers in $a_1,\dots,a_k$, i.e., closest to zero).

Otherwise, if $a_{k+1}$ is negative and at least one of $a_1,\dots,a_k$ is positive, the solution is $a_1 \times \cdots \times a_{k+1}$ (but omit the smallest positive number of $a_1,\dots,a_k$ from the product).

Otherwise, if at least one of $a_1,\dots,a_n$ is positive, the solution is $a_1 \times \cdots \times a_{k-1} \times a_j$ where $a_j$ is the largest positive number in $a_1,\dots,a_n$.

If all of $a_1,\dots,a_n$ are negative and $k$ is odd, then the solution is $a_{n-k+1} \times \dots \times a_n$.

This can be computed in $O(n \lg k)$ time using a heap of size $k$.


Predicting the outcome of sporting events with multiplicative scoring

Brute force

If you want something easy to implement, brute force might be fast enough, assuming at least one round has been completed.

There are $8! = 40320$ possible permutations of the athletes, so in any round, there are 40320 possible rankings.  Assuming the first round has been completed, there are only $40320^2 \approx 1.6 \times 10^9$ possible rankings for the next two rounds, all of them equally likely.  A program should be able to enumerate all of them in a few seconds or minutes and compute the probability distribution of the final rankings for each athlete.

There are faster algorithms, and I will describe them below, but I'm unsure whether the time it takes to understand and implement them will outweigh the amount of CPU time they save.

Convolution

Let the random variables $X_1,X_2,X_3$ denote the athlete's ranking in the first, second, and third rounds.  Then their final score will be $S = X_1 \times X_2 \times X_3$.  Our strategy will be to compute the probability distribution for each $X_i$, then use that to compute the probability distribution for $S$.

Note that if a round has been completed, then the corresponding probability distribution is easy to compute: it assigns probability 1 to the rank the athlete actually obtained, and 0 to all others.

We can compute the probability distribution for a round that hasn't begun by enumerating all $8! = 40320$ possible permutations, observing the athlete's rank in each, and summing up how often each occurs.  Or, more simply, we can note that since all permutations are equally likely, the distribution on the athlete's rank in this round is uniform, i.e., all possibilities have probability $1/8$.

We can compute the probability distribution for a round that has been partly completed by enumerating all $8! = 40320$ possible permutations, filtering out all of them that are incompatible with the results observed so far, then observing the athlete's rank in each that remains, and summing up how often each occurs.

So in this way we can obtain the probability distribution for $X_1$, $X_2$, and $X_3$.  Now we obtain the probability distribution for $S$ from these distributions.  In particular, the probability distribution for $T = X_1 \times X_2$ can be obtained as

$$\Pr[T=t] = \sum_{i=1}^8 \Pr[X_1 = i] \Pr[X_2 = t-i].$$

This requires 8 simple steps for each value of $t$, and there are $30$ possible values of $T$, so this can be done in $8 \times 30$ steps.  Next, the probability distribution for $S = T \times X_3$ can be obtained in the same way.  There are $80$ possible values of $S$, so this can be done in $8 \times 80$ steps.

The result is the probability distribution for $S$, the athlete's final score.  This works with any number of unfinished rounds, even if one round is partly completed.  The total running time is at most $40320 + 8 \times 30 + 8 \times 80$ simple steps, which is very fast; an implemention should complete the computation in millliseconds.

Related:
Estimate distribution of a composite variable, largest samples of set of random variables, Polynomial Computation of the probability of a number of independent events.


$L$ is a context free language so prefix$(L)$ is also context free language

Let $G$ be a Chomsky's normal form grammar for $L$. So $G = (N,T,S,P)$ when $P\subseteq\{A\rightarrow BC , A\rightarrow a  : A,B,C \in N , a\in T \}$. We will defined $G'$ as follows: $G'= (N\cup N'\cup \bar{S} ,T,\bar{S},P')$ when:

$N' = \{A' : A\in N\} $
$P' = P\cup\{\bar{S} \rightarrow  S' | \varepsilon \} \cup \{A'\rightarrow BC'|B' : A\rightarrow BC \in P\} \cup \{A'\rightarrow a|\varepsilon : A \rightarrow a \in P\}$

Observation - let $A \in N$ we define $L(A) = \{w\in T^* : A\Rightarrow^{*}_G w \}$, So, in $G'$ , $A'\Rightarrow^{*}_{G'} w\in prefix(L(A))$.

proof, by induction over production steps:

$A'\rightarrow^1w\in T^* \Rightarrow w \in \{a,\varepsilon\}$ due to $P'$ definition. So in $G$ ,$A\rightarrow a$ thus $\{a,\varepsilon\} \in prefix(L(A))$.
assumption - $\forall A'\in N'$, $A'\Rightarrow^{k <n}w\in prefix(L(A)) $
$A'\Rightarrow^n w\in T^*$, so $A'\rightarrow^1 \gamma\Rightarrow^{n-1} w$, thus $\gamma \in \{BC' , B'\}$: In case $\gamma = B'$ then $B'\Rightarrow^{n-1} w\in prefix(L(B))$ and $A'\rightarrow B' \Rightarrow A\rightarrow BC \in P$ then $prefix(L(B)) \subseteq prefix(L(A))$. If $\gamma = BC'$, $B$ products $w_1 \in prefix(L(A))$ because $A\rightarrow BC \in P$, and $BC \Rightarrow^* w_1w_2\in L$ when $B \Rightarrow^* w_1 , C\Rightarrow^*w_2$, and $C'$ products $w_{2}' \in prefix(L(B))$ from the assumption. Thus $A' \Rightarrow w_1w_2'$ which is a prefix of $w_1w_2 \in L(A)$.

$L(G') \subseteq  prefix(L)$:

$\bar{S} \rightarrow^1 \varepsilon$ , $\varepsilon \in prefix(L)$.
$\bar{S} \Rightarrow ^n w\in T^* \setminus \{\varepsilon\}$ , so $\bar{S}\rightarrow S'\Rightarrow ^{n-1}w$ now, using the first observation we made $S' \Rightarrow^* w\in prefix(S) = prefix(L)$.

So $\bar{S} \Rightarrow^* w\in T^*$ means $w\in prefix(L)$.

$prefix(L) \subseteq L(G')$:

Observation : in case $A\Rightarrow^* w\in T^*$, then $A' \Rightarrow^* w' \in prefix(w)$ for all $w'\in prefix(w)$.

proof by induction over $w$'s length:

$A\rightarrow a$ $\Rightarrow$ $A' \rightarrow a$ and $A'\rightarrow \varepsilon$, due to $P'$ definition, when $prefix(a) = \{a,\varepsilon\}$.
$A\Rightarrow^* w, |w|=n$, so $A\rightarrow BC \Rightarrow^* w_1w_2 =w$ when $B \Rightarrow^* w_1 ,C \Rightarrow^* w_2$ (from $P$'s definition in chomsky's form). For $w'\in prefix(w)$:

in case $w' \in prefix(w_1)$, then $B'\Rightarrow^* w'$ from the induction assumption ($|w'|<n$, and the assumption stands for every $A'\in N'$ ). So $A'\rightarrow B' \Rightarrow^* w'$ as wanted.
in case $w' = w_1w_2'$ when $w_2'\in prefix(w_2)$ the same arguments holds for $c' \Rightarrow^* w_2'$, thus $A'\rightarrow BC' \Rightarrow^*w_1w_2'$.

For $w \in prefix(L)$:

in case $w = \varepsilon $ , $\bar{S} \rightarrow \varepsilon$.
otherwise $\exists z\in T^*$ such that $wz \in L$, so $S\Rightarrow_G^{*} wz$ and by the observation we made $S'\Rightarrow^* w'\in prefix(wz)$ for all $w'\in prefix(wz)$ and particularly $w$ it self. So $\bar{S} \rightarrow S'\Rightarrow ^* w$. Thus $w\in L(G)$


How is parallel tag checking achieved in associative Mapping?

[I don't have this book]

Let's take a common example : A 4 ways, 16kB cache made of 4 ways of 4kB.
And a cache line of 32 bytes.

Each way of the cache is made of a 4kB RAM containing data and another RAM which stores cache tags, its size is 4096/32 = 128 lines, each tag can probably fit in a 32 bits.

The tag RAM is indexed with the low address bits (here A[12:6]), and its content is compared with the high address bits A[31:7].

If you have 4 ways, you have 4 tag RAMs, the address bits are the same, but you have 4 comparators.

Cache is made of ordinary RAM blocks.

(In current advanced CPUs, to save power and complexity, the cache ways are often not compared at the same time, there is a preferred way, selected with some heuristics, wich is tested first, the other ways are tested only if the first one do not match)


Isn't First/Best Fit Decreasing always considered offline (requiring sorting the input assumed unsorted)?
Anyway, let me assume "performs better" to mean uses less bins.
I find it annoyingly hard to try to find an example using a minimum number of items, of item values and minimum item values - and to argue convincingly that it is minimal, but

   try a bin size of 16 and items of 11, 6, 6, 3, 2, 2, 2. Bin contents after adding each item:
 - FF: 11 11,6 11,12 14,12 16,12 16,14 16,16
 - BF: 11 11,6 11,12 11,15 13,15 15,15 15,15,2


determining whether a program halts or not

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.

The Halting problem for a specific (narrow) class of programs (Turing machines) may be decidable. But in general, for arbitrary TM $M$and input $w$, the Halting problem is undecidable.


Hoare triple for assignment P{x/E} x:=E {P}

Notice that what Wikipedia is saying is that

  The assignment axiom means that the truth of $\{P[x/E]\}$ is equivalent to the after-assignment truth of $\{P\}$.

In other words, ($P$ holds after the execution of $x:= E$) if ($P[x/E]$ holds before the execution). This is equivalent to the definition $A$ you provided, which is generally a more intuitive definition for Hoare triple.


Why does Bellman-Ford algorithm use < rather than ≤?

First of all, let me clarify a few points about your example:

Bellman-Ford-Moore consists of two phases, stages or steps, each one consisting of a number of iterations as they are implemented with loops. The first phase computes the cost of the shortest-path to reach each vertex from the start vertex and it consists of two nested loops; the second one consists of a single loop which checks whether there are negative cycles or not. I mention this because it seems to me that you refer to the phases as iterations.
Let me also note that in the first phase you skip the evaluation of reaching $S$ from $C$. I assume you just simply avoid making the computation because it is pointless for exemplifying your case, but let me just highlight that Bellman-Ford-Moore would also perform that evaluation. By the way, it is unclear whether you are considering a directed or undirected graph. I just assumed it is directed: $S\rightarrow B\rightarrow C\rightarrow S$.
As noted in the comments by xskxzr, there is no negative cycle in your exmaple. A negative cycle is defined as a path which starts and ends in the same vertex whose overall cost (defined as the sum of all edge costs) is strictly negative. In your case, there is only one cycle from $S$ to it, but it has a cost which is is strictly positive: $c(S, B) + c(B, C) + c(C,S)=1-1+1=1>0$.

I mention these points only to make the answer clearer (if possible) and more useful to other readers.

I will try now to address your question. Once the first phase is over, the distance of the shortest-path from the start vertex $S$ to all other vertices in your graph has been already computed. Let $d_i$ denote the cost of the shortest path from $S$ to the $i$-th vertex.

Consider now any vertex of your graph, $v_i$, and all incident edges to it. Clearly, at least one should be in the shortest-path from $S$, whereas all the others should not. Take any vertex $u$ which has an edge from it to $v_i$:

If the edge $\langle u, v_i\rangle$ is part of the optimal path from $S$ to $v_i$ then clearly $d_u + c(u, v_i)=d_{v_i}$
Otherwise, $d_u + c(u, v_i)>d_{v_i}$ as this is not part of the optimal path.

Thus, when starting the second phase (for detecting negative cycles), there is at least one edge for each vertex for which equality holds without the presence of negative cycles! This is just a consequence of the definition of shortest-path as shown above. This observation precludes the usage of $\leq$ for detecting cycles, as equality holds without negative cycles.

Let us now consider the case of negative cycles. Their essential property is that they  decrease the value of reaching its final vertex indefinitely (as crossing it again would reduce the cost to reach its end vertex), i.e., negative cycles strictly decrease the cost of reaching its end vertex and hence, the only way $d_u + c(u, v_i) < d_{v_i}$ is because there is at least one negative cycle.

In your specific example, make $c(C,S)=-1$. Now you have a negative cycle from $S$ to itself. Clearly, once the first phase is over, the cost of the shortest distances computed by Bellman-Ford-Moore would be: $d_S = -2, d_B = 0, d_C = -1$. I assume the following order of edges: $\langle S, B\rangle$, $\langle B, C\rangle$ and $\langle C, S\rangle$ and recall that the first phase is ran as many times as edges minus 1, i.e., twice in your example. So far, after the first iteration (which considers updating the target vertex of all edges in the order given above) of the first phase $d_S = -1, d_B = 1, d_C = 0$. Because Bellman-Ford-Moore dictates to run the first phase as many times as vertices minus one (the reason beig that the costs computed in the previous iteration should be propagated to the longest path whose number of edges is upper bounded by the number of vertices minus 1), a second iteration of the first phase is conducted and the cost of the shortest-path to all vertices gets decremented again, $d_S = -2, d_B = 0, d_C = -1$.

Next, when running the second phase it turns out that $d_S + c(S,B) = -2 + 1 = -1 < d_B = 0$ which reveals the presence of the negative cycle using $<$.

Hope this helps,