Is it possible for a maximum weight edge of a cycle being included in MST?

The answer to the question in the title, "is it possible for a maximum weight edge of a cycle being included in MST?", is "not necessarily".

The correct answer to the multiple-choice question is (B).

A counterexample to (A): Let $G$ be an triangle with weight $1$, $1$ and $1$. Let $e$ be any edge of $G$.

The answer by raindrop says (A) is correct. However, he/she also points out that "A possible exception is if multiple edges have the same maximum weight, e.g. there are multiple maximum edges on $C$ which qualify to be labeled $e$. In that case, a minimum weight spanning tree may contain $e$". Let me repeat the condition about $e$ in OP's post is Let "$e$" be an edge of maximum weight on $C$. The article "an" in "an edge" does indicate that possibility. Since we are in math or computer science, one counterexample or one exception is enough to prove the fallacy of a statement.

Proof of (B): Let $m$ be an MST of $G$. If $e$ is not in $m$, we are done. Now suppose $e$ is in $m$. If we remove $e$ from $m$ (but do not remove $e$'s vertices), $m$ will be split into two trees, which we name $m_1$ and $m_2$. As a cycle that connect $m_1$ and $m_2$ by $e$, $C$ must also connect $m_1$ and $m_2$ at another edge, which we name $e'$. Then $m_1$ together with $m_2$ and $e'$ is an MST of $G$ that does not contain $e$.

A counterexample to (C): Let $G$ be an triangle with weight 1, 1 and 1. Let $e$ be any edge of $G$. The shortest path between $e$'s two vertices contains one edge, $e$ itself.

(D) is wrong since (B) is correct.


Finding the smallest string that contains a given set of substrings

This problem is called shortest superstring problem. John Gallant, David Maier and James Astorer proved it is NP-hard in 19791.

Given two strings $A$ and $B$, let $|A|$ denote the length of $A$, and let $S(A,B)$ denote the shortest superstring of $A$ and $B$ where $A$ occurs before $B$. It is easy to reduce this problem to travelling salesman problem, where nodes represent strings, and the distance from string $A$ to $B$ is $|S(A,B)|-|A|-|B|$. So you can use known algorithms for travelling salesman problem to solve this problem.

There are several polynomial approximation algorithms. The best known approximation factor is $2\frac{11}{23}$, and the corresponding algorithm is proposed by Marcin Mucha in 20132.

1Gallant, J., Maier, D., & Astorer, J. (1980). On finding minimal length superstrings. Journal of Computer and System Sciences, 20(1), 50-58.

2Mucha, M. (2013, January). Lyndon words and short superstrings. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms (pp. 958-972). Society for Industrial and Applied Mathematics.


Flow graph that requires pushing back flow in Ford Fulkerson

I think it is possible to reason backwards from an optimal solution$^1$ to the order in which the paths have to be augmented to not have any pushing-back:

In the solution, for any path from the source to the sink, where the flow is larger than zero, there is at least one edge, that constrains that flow, i.e: its flow is at capacity.
If it were not, there would have been an augmenting path along that path, i.e. the solution would not be optimal.
Also, of the edges that are at capacity, there has to be one (or multiple) with the lowest possible capacity. Furthermore, this edge has to be part of some path between source and sink where each edge has a flow at least as high.
We take such a path, call it $P_1$ and remove its 'flow capacity' from the initial graph (i.e. reduce the capacity of the edges along the path).
We repeat this with the remaining graph (resulting in $P_2, P_3, \ldots, P_n$) until there is no path between source and sink remaining, where all edges have a non-zero capacity.

Then, $P_1, P_2, \ldots, P_n$ is the order in which the paths have to be chosen s.t. there is never any pushing back necessary.

$1$: This only holds for optimal solutions that have been found with the FF algorithm. E.g. in a graph where 5 edges with capacity 2 go into node X and only one edge leaves it with capacity 5, there would be a max flow where each of the 5 edges has a flow of 1/2 and the outgoing has a flow of 5/5. Then the 5/5 edge would be the lowest edge at capacity but there is no path from source to sink in that graph where each edge has a flow of 5 or more. This is no problem for the algorithm outlined above because such a max-flow solution would not be found with FF.


Is this an $NP$-complete problem: Product-2-Partition

Denote these integers by $x_1\ge x_2\ge\cdots\ge x_n$. We assume these integers are all positive (it is not hard to revise the following algorithm for instances including both positive and negative integers).

In a valid solution, the greatest element must match the smallest element. Otherwise, say $x_1$ matches $x_i$ where $x_i>x_n$, and $x_n$ matches $x_j$, then $B=x_1x_i>x_1x_n\ge x_jx_n=B$, a contradiction. Hence a valid solution can only be $\{x_1,x_n\},\{x_2,x_{n-1}\},\ldots$ We only need to check whether this partition is valid, i.e. whether $x_1x_n=x_2x_{n-1}=\cdots=B$.


A 2D Layout Algorithm for Small, Sparse, and Undirected Graphs with a Specific Edge Length

"Planar Embeddings of Graphs with Specified Edge Lengths" by Cabello, Demaine, and Rote (or one of the references they cite) seems to solve your problem.

If you don't care about edges crossing too much, a simple heuristic approach could be gradient descent. Start with a random position and iteratively wiggle the nodes a bit to decrease the sum of differences of the current edge lengths to your desired lengths.


Is greedy algorithm the best algorithm for set cover problem?

The result you quote, due to Feige, has actually recently been improved by Dinur and Steurer (based on earlier work of Moshkovitz), who showed that unless $P = NP$, there is no polynomial time $(1 - o(1))\ln n$-approximation algorithm for set cover.

This result states that if all you care about is the worst case approximation ratio, then you cannot substantially improve on the trivial greedy algorithm. (There are also other algorithms achieving the same $\ln n$ bound.) In particular, no polynomial time algorithm gives a constant factor approximation for set cover on all instances.


Minimum number of edges to add such that there are no bridges on a tree

Let me describe the following algorithm. The basic idea is to add edges such that for any pair of vertices $v_i$ and $v_j$ there is at least two different simple paths between $v_i$ and $v_j$.

Initially all edges are unmarked
Select a simple path $v_i\dots v_j$ containing at least two unmarked edges such as $(v_i,v_j) \notin E$ (vertices $v_i$ and $v_j$ are not connected). If there is no path containing two unmarked edges, then select a path containing one unmarked edge (this means we are done)
Connect $v_i$ and $v_j$ (thereby creating a cycle).
Mark all edges of the (newly created) cycle $v_i\dots v_j$
If there is unmarked edge then go to step 2
Halt

Claim 1: The algorithm adds at most $\frac{|V|}{2}$ edges.
Proof: At step 2 we select a path whose length is at least $2$ (i.e. has at least two edges) containing at least two unmarked edges. Such path exists as long as we have two unmarked edges since there is always a simple path between any two vertices $v_i$ and $v_j$ in a connected tree. So, at each step 2 we decrease the number of unmarked edges by $2$. Since the tree initially has $|V|-1$ unmarked edges, the algorithm adds at most $\big\lceil{\frac{|V|-1}{2}}\big\rceil$ edges. But $\big\lceil{\frac{|V|-1}{2}}\big\rceil \leq \big\lfloor\frac{|V|}{2}\big\rfloor \leq \frac{|V|}{2}$.

Claim 2: The resulting graph created by the algorithm has no bridges.
Proof: Consider a partition $(V',V- V')$. Let $v_i \in V'$ and $v_j \in V-V'$ such that $(v_i, v_j)$ is an edge of the initial tree. Such edge obviously exists since the tree is connected. At some point the algorithm selects a path containing the edge $(v_i, v_j)$ and creates a simple cycle which includes the edge $(v_i, v_j)$. So, there are two different paths between vertices $v_i$ and $v_j$, and hence there are at least two paths (or edges) connecting the partitions $V'$ and $V-V'$.

This algorithm does not compute the optimal number of edges for all possible input instances. For example for a tree which is a path it is enough to add a single edge connecting two end points to transform the tree into a bridgeless graph. My goal is to establish the least upper bound for the number of edges required to add to a tree to transform it into a bridgless graph. For example a star-like tree with even number of vertices is a worst case in which case we need exactly $\frac{|V|}{2}$ edges.


A simple way to find the feasible region of a system with simple constraints

This can be formulated as a linear programming (LP) problem. Arbitrarily state that $A$ is at coordinate 0, then for your example graph we get equations

$$ A = 0$$
$$ B-A \ge 1 $$
$$ C-A \ge 1 $$
$$ 1 \ge C-B \ge 0 $$
$$ \dots $$
$$ F - E \ge 3 $$
$$ F - A = 15 $$

In particular, with $V$ nodes and $E$ edges, we have $V-1$ variables and at most $2E$ linear constraints. Linear programs can be solved in polynomial time (via e.g. the ellipsoid method), but it's not necessarily linear -- more like quadratic or cubic. However! You have a very sparse system: each constraint has only two nonzero entries. This means it will likely perform very well in practice. If you use a free (and usually very well optimized) library, like Gurobi or GLPK, they can use the Simplex method and pretty efficiently use the sparsity.

I realize this might not be completely satisfactory, but: LP solvers are pretty intelligent, and I'm not convinced there's a whole lot more structure to your problem that you could take advantage of that they won't. They will probably do something sort of like your take-min-first strategy, and then "fix" appropriately, and efficiently.

Finally, quick note: You didn't really specify what your goal is, but the solver will want some function to minimize. I would have suggested just saying "minimize $F$", but in your example graph $F$ is actually fixed. So a reasonable objective function might be "minimize $B+C+D+E+F$" or something. Depends on your application. But this should get you basically linear runtime on nearly all cases.


Regularity of a language with odd and even positions containing an even number of 1's

To create the DFA, just start doing it. I assume there is no requirement that the number of elements in the string is even.

You start in the state A. In state A, you have an even number of 1's in the even and odd positions (initially, both counts are 0), so A is an accepting state. To get to an accepting state again, there must be a string following with an even number of 1's in the even and odd positions.

In state A, the next symbol can be 0 or 1. In case of 0, you have the exact same situation again, you need another string following with an even number of 1's in the even and odd positions. So A followed by 0 goes to A.

If the next symbol is 1, then the rest of the string must have an even number of 1's in even positions, and an odd number of 1's in odd positions. That's another state B.

In state B, if the next symbol is 0 then you now need an even number of 1's in odd positions, and an odd number of 1's in even positions. That's a new state C. In state B, if the next symbol is 1 then you now need an odd number of 1's in even and odd positions. That's a new state D.

Now you do the same for states C and D, and you find that whatever the input, you'll end up in one of the states A, B, C and D.

Don't think about "state" as some abstract state in a DFA. Think of it as something that you can describe in words. From any state, which you can describe in words, you get to another state, which you can describe in words again. If you compare those descriptions, and they are the same, then the state is the same.

The case where you don't get a DFA is when the number of states is not finite. For example, for $0^n1^n$, the initial state is "I need any number n of 0's and the same number n of 1's". If you get a 0 then you get a state where you need any number n of 0's and n+1 1's. Another 0 and you need n 0's and n+2 1's. And so on. The number of states is not finite. In your problem, there are only four states needed.

If that's too practical, then given any prefix X of a string in the language L, define the set of suffixes Y such that XY is in the language. Any such set of suffices is a state.  An accepting state is one where the set contains the empty string. The initial state is the set of suffices when X is the empty string. In your case, there are only four different sets of suffices.


How to prove that algorithm returns the value which appears more than $n/2$ times in the array?

Note: In my opinion, although the answer given by @Sunny Wang is slightly hard to follow, it is in the right direction. Maybe the author would like to come back and improve his/her answer. Therefore, I will only give some high-level hints here.

Playing with some examples, you will find that the program amounts to keeping eliminating (by decreasing the counter, of course) a pair of distinct elements. Therefore, if a value appears more than $\frac{n}{2}$ times, it (and only it; this is also important) survives and will be returned.


Proving the lower bound of compares in comparison based sorting

A sorting algorithm using at most $h$ comparisons on all inputs corresponds to a tree of height at most $h$. Such a tree has at most $2^h$ leaves. On the other hand, each permutation of $1,\ldots,N$ must land at a different leaf, and so there must be at least $N!$ leaves. Putting these together, we deduce that $2^h \geq N!$ and so $h \geq \log_2 N! = \Omega(N\log N)$ (using Stirling's approximation). So every sorting algorithm must use at least $\log_2 N! = \Omega(N\log N)$ comparisons in the worst case (on some inputs it can use less).


From Whence the Randomization in Randomized Quicksort

Take a look at McIllroy and Douglas' "A Killer Adversary for Quicksort" (Software -- Practice and Experience 29(4): 341-344 (1999)) or Crosby and Wallach's "Denial of Service via Algorithmic Complexity Attacks" for the reason behind randomizing. Quicksort behaves very badly if you pick (nearly) the largest/smallest as pivot each time. For randomization to make sense, it has to be random (if I know how you pick pivots deterministically, I can cook up an array that forces you to go into $O(n^2)$ behaviour, see the paper mentioned for details). But a fancy RNG is costlier than, say, taking 3 or another smallish odd number of elements, and pick the median of those as pivot, which is another way to counteract bad behaviour. So if you choose randomization, use a fast RNG seeded appropiately (probably a linear congruential scheme will be enough).

Algorithms can (and should) be compared by $O(\cdot)$, but if you are talking about different implementations of the same algorithm one must switch to more detailed analysis. In fact, Sedgewick and Flajolet in "An introduction to the analysis of algorithms" argue that one shouldn't use $T(n) = O(f(n))$ at all, but should strive to get $T(n) \sim f(n)$ type asymptotics.


Time complexity of Dijkstra's algorithm for sparse graph

Discrete Lizard's answer explains various aspects of the question.

Here is an explicit calculation when $E=o(V^2/\log V)$.

$$\lim_{V\to\infty}\frac{(E+V)\log V}{V^2}=\lim_{V\to\infty}\frac{E}{\dfrac{V^2}{\log V}}+\lim_{V\to\infty}\frac{V\log V}{V^2}=0+0=0$$

That means $O((E+V)\log V)\subsetneq O(V^2)$. So $O((E+V)\log V)$ is a tighter bound than $O(V^2)$ when $E=o(V^2/\log V)$.


Why is Scale Space Needed to Detect Scale Invariant Features?

If a maximum is found at a given octave X in the original image, then, if we have the scale-invariant property, this maxima will be found on the zoomed down (downscaled) image at octave X-1.


How can a stack-based VM be Turing-Complete?

If the stack machine is only allowed to access the top of the stack, and apart from the stack it only has a finite amount of storage, then it's a pushdown automaton. Pushdown automata are not Turing-complete; non-deterministic pushdown automata can only recognize context-free languages, and deterministic ones even less.

With two stacks, such that the machine can push and pop from either stack, the machine is equivalent to a Turing machine. This is fairly easy to see: given a Turing machine, you can build an equivalent two-stack automaton by pushing the input onto one stack, and then treating forward motion on the tape as popping from the first stack and pushing onto the second stack, and vice versa for backward motion.

If the stack machine is allowed to access data from any point in the stack, which is normally the case when a stack machine is used to build a virtual machine, it's a different story. In this case the shape of the stack doesn't matter, what you have is a random-access machine. From the point of view of computability, it's the same thing as a register machine, it's just a matter of how you name the registers: by calling it “stack machine”, you're just saying that the registers are numbered in a certain way.

RAM are equivalent to Turing machines. There is a subtlety with RAM: the registers are not finite registers, they are “variable-sized” registers that can accommodate numbers that are as large as needed for the computation. In practice, most concrete machines are like that — a register or memory cell is as large as it takes to store a pointer, and if the size of a pointer exceeds the register size, it means that you've overflowed the memory of your machine and you start the computation again on a machine with more memory and bigger registers.


Big-O notation for lower bound instead of Big-Omega

If you consider the problem Tree traversal, then the correct answer is indeed:

Traversal requires $\Omega$(n) time, since it must visit every node.

We are here talking about requirement and lower bound, as in "what is necessary".
If you want to talk about common algorithms for tree traversal, then it is true that they also have a complexity $O(n)$, which means that it is an upper bound in "what we can do".
However, since your question, the wikipedia page was modified and the current sentence does not really make any sense (basically "Tree traversal is $O(n)$. Since it is also $O(n)$, it is optimal.").


MST - algorithm to add an edge to the graph

Let $T$ be the MST of the original graph $G$ and let $e'$ be the newly added edge.
Suppose for simplicity that all edge weights are unique (if they are not, fix any arbitrary linear order among $E(G)$ that prioritizes the edges in $E(T)$. Then break weight ties according to this order).

Let $e$ be the edge of maximum weight in the unique cycle $C$ of $T + e'$. And assume that $e \neq e'$ (otherwise the proof is trivial).

One way to prove that $T-e+e'$ is a MST of $G+e'$ is showing that no edge $f \in \{e\} \cup E(G) \setminus E(T)$ can belong to any MST of $G+e'$ using the cycle rule.

If $f=e$, $f$ cannot belong to any MST of $G + e'$ because it is the edge of maximum weight of the cycle $C \subseteq T+e' \subseteq G + e'$.

If $f \in E(G) \setminus E(T)$ then, since $f \not\in E(T)$, $f$ must be the edge of maximum weight of some cycle $C' \subseteq G \subset G + e'$ and hence it cannot belong to any MST of $G + e'$.


You are right. Checking k < d[u] is not sufficient and updating d[u] on the next line is not necessary.

The check prevents proceeding when the source is picked up from the queue (then k = 0 and d[s] = 0). Also, d[u] (u is fixed) is monotonically decreasing as loop proceeds, so even though it is updated after (u, d[u]) is put on the queue, k >= d[u] holds when (u,k) is picked up from the queue. Moreover, if d[u] is strictly smaller than k , the element should simply be ignored since it cannot be the shortest path to u.

You can change the condition to k == d[u] and remove following update to d[u].


Is there any algorithm which takes regular expression as input and finds if the regular language which expression describes is infinite?

Yes, there is such an algorithm, and (if I am not mistaken) you can actually use a recursive evaluation of regular expressions.

Recall that regular expressions are composed from $\varnothing$, $\varepsilon$ and $a$ (for $a$ in some alphabet) using the operations $\cdot$, $+$ and $*$ (concatenation, union and iteration).

Observe that a language can only be infinite if it is based on the iteration of any language that contains a string that is not empty ($\varepsilon$). Then such an iteration can be repeatedly concatenated and unioned with other languages.   The result will be infinite again, except in the case we concatenate with the empty set.

Now introduce language 'classes' NUL, ONE, FIN, and INF for the empty set, the empty string, any (finite) language that contains a string other than $\varepsilon$, and any infinite set.

Start by replacing in your regular expression any occurrence of $\varnothing$, $\varepsilon$ and $a$ by NUL, ONE and FIN respectively.

Now use a set of reductions (equalities) on the new expression, and repeat those:

NUL* = ONE* = ONE
NUL + FIN = ONE + FIN = FIN + FIN = FIN
NUL NUL = NUL ONE = NUL FIN = NUL INF = NUL
ONE FIN = FIN FIN =  FIN
ONE INF = FIN INF = INF INF = INF
FIN* = INF* = INF

And many more, try to find what is needed.

And it seems to solve the empty set problem at the same time?


Minimum # toggle (3 consecutive elements) operations to convert ring A into ring B (rings made of Xs and Os: X->O and O->X)

You can represent a ring as a $n$-bit string, where $n$ is the number of positions in the ring.  Encode an X as 1, and encode a O as 0 (zero).  That gives you a $n$-bit string, say $x$.

The # operation on index $i$ corresponds to xor-ing the string representing the current state of the ring with the string $c_i = 0^{i-1} 111 0^{n-i-3}$.  In other words, if the ring is currently $x$, then the # operation on index $i$ changes the state of the ring to $x \oplus c_i$.

Suppose you're given two rings $x,y$ and you want to find a way to transform $x$ into $y$.  Then all you need to do is find a subset of $c_1,\dots,c_n$ whose xor is equal to $x \oplus y$.  This will be the solution to your problem.  Can you see how to do that?  Solution below (don't mouse over until you've thought about it for a while):

   You can find that solution using linear algebra in modulo 2 arithmetic (i.e., Gaussian elimination modulo 2).


Tag storage when using HBM as an L4 cache

Disclaimer: It's been a while since I last read that book. It was an edition that pre-dated HBM. So I can't really refer to the book to find out what it's saying.

The "level" of a cache refers to how many steps removed it is from the CPU's load/store hardware. It means nothing beyond that. You can't just say "L3" and assume that it refers to the same organisation.

In a modern machine, there is usually one L1 cache per core, split between instruction and data. It may be virtually addressed or physically addressed depending on the architecture.

L2 cache is typically unified, instructions and data. But is there one per core, or one per die?

And what does L3 cache mean? Is that the one shared between cores on a die? Is the GPU on the die, and the L3 is shared between the CPU cores and the GPU? Is the L3 cache off-chip? Or perhaps the tags are on-chip and the data is off-chip? Maybe this is a NUMA machine, and the L3 is shared between all processors on the same board?

I think the issue here may be that any signal that has to go off the chip is more expensive than one that stays entirely on the chip. It usually requires higher electrical currents, and more time since the tolerances of a circuit board aren't as tight as they are on a die. So if you can't fit an entire cache on a single chip or package, it can make sense to split the tags from the data.

If you are a CPU die, for example, and a different die invalidates a cache line (e.g. it changes state from Shared to Exclusive in the MESI model), then all levels of your cache need to be potentially invalidated. That is an operation that only requires accessing and modifying the tags, not the data. So keeping the tags on-chip and storing the data off-chip could make sense here. This was extremely common back when you couldn't pack quite so many transistors on a die.

I don't know if any of that helped.


Is $\{ w \in L : wx \in L, \textrm{for some } x \neq \epsilon\}$ a CFG language if $L$ is CFG?

Consider the language
$$
L = \{ a^n b^m c^nd : n,m \geq 0 \} \cup \{ a^n b^m c^m d^2 : n,m \geq 0 \}.
$$
Then $\{ w \in L : wx \in L \text{ for some } x \neq \epsilon \} \cap a^* b^* c^* d = \{ a^n b^n c^n d : n \geq 0 \}$.

Here is a similar example, showing that if $L$ is context-free then $L \cap L \Sigma^+$ is not necessarily context-free:
$$
L = \{ a^n b^n : n \geq 0 \} \cup \{ a^n b^m c^m : n,m \geq 0 \}.
$$
Indeed, in this case $L \cap L\Sigma^+ = \{ a^n b^n c^n : n \geq 0 \}$.

The situation is likely different for deterministic context-free languages.


Calculate the amount of formal languages

That would be eight combinations, as $2^3=8$. You missed $aba$, and another one.


Remember that an in-order traversal lists the elements from left-to-right, descending the tree: Left, Root, and Right. This means that starting from the root (a), we will traverse the whole left branch, then print a, and finally traverse the right branch.

You started off correct; however, your mistake was that you put m beforee h. It is an easy mistake to make so you have to be careful. The m node is the right node of h so the traversal for that subtree will be h, m. The same goes for i and e in your traveral---they should be flipped.

The correct answer for this in-order traversal is d b h m e i a j f k c g.


It's a perfectly valid grammar, and it's certainly LL(1). But since it only generates three sentences, it's probably not what you are looking for.

The three sentences:

a < a
a | a
a / a

For precision: As written, it's not quite correct. In order to achieve what I imagine you meant by the FIRST sets, you'd actually need to he a bit more precise. Instead of using $op$, you write:

$$\begin{align}B& \to \mathbb{<}\\
B&\to\text{|}\\
B&\to\text{/}
\end{align}$$

Alternatively, you could define $op$ as the three possible operators, as above, and leave $B\to op$.

Also: $FOLLOW$ sets (like $FIRST$ sets) are sets of terminals. So $S$ and $C$ are not going to be found in any $FOLLOW$ set. $FOLLOW(B)$ is $\{a\}$.


Is the language of all ucv with u ≠ v context-free?

This is a CFL, but the complement (with equality) is not. Notice that both the language and the complement become CFL when you mirror one of the two words.

To show that this is a CFL, you can design a PDA that guesses the letter at position $i$ that will be different in $w_1$ and $w_2$. It start by reading the first $i$ letters of $w_1$ and pushing $i$ symbols to the stack up to this letter, and remembers the letter $a$ in $w_1$ at position $i$. Then, it waits to read $c$, and pops the $i$ symbols off the stack. It accepts if the current letter (at position $i$ in $w_2$) is not $a$.

You have to also treat the case of different lengths, but it's not hard, I leave it as exercise ;)


What is a good design for expanding opcodes?

It looks like this is simply the problem of mapping a set of possible values (i.e., possible instructions) to some bit encoding.

You haven't specified whether all instruction encodings need to have the same length.

If they can have different lengths, usually you'll want them to form a prefix-free encoding (no encoded value is a prefix of any other).
If all instruction encodings must have the same length,any mapping that gives different instructions different encodings is acceptable.

Your solution doesn't look OK to me.  00 00 yy zz is a prefix of 00 xx yy zz if xx, yy, and zz are the addresses 00000000.

Editorial comment: the exercise is a bit boring and trivial, and doesn't involve much in the way of deep concepts.  It's just a matter of "bit-packing".


The original problem is, I believe, the following.

When using Hamming code with EVEN parity for 7-bit ASCII characters, the following symbol is retrieved: 01100110101.
Assuming a 1-bit error, what was the original stored symbol? Write down your answer as a 7-bit binary, with no spaces.

OP's statement, "..., which contains an ASCII value: 01100110101", rephrases the original problem statement in a slightly confusing way,  as pointed out by Yuval Filmus.
OP's procedure and result is correct, as said in Jakube's comment and indicated in D.W.'s comment. I have verified it as well according to Hamming code at wikipedia.
OP's procedure and result will not be repeated here.
Someone mentioned that "The usual Hamming code has length of the form $2^\ell−1$". For $\ell=4$, the usual Hamming code of length 15 is defined by the following table from wikipedia.  If we truncate the last 4 columns, we will get the truncated Hamming code of length 11, which should be, presumably, the Hamming code used in OP's question.

"Supposedly this value is incorrect - can anyone point out the mistake I made?"
This is the turning point to the climax (or anti-climax). There are four possibilities.

A different kind of (truncated) Hamming code is used.
For example, all four parity bits could have been specified to be put together in the first four bits. That is, the first four bits, 0110 are the usual p1, p2, p4 and p8 parity bits while the remaining 0110101 are the data bits. In that case, we rearrange the bits to form the usual Hamming code as (p1)(p2)0(p4)110(p8)101, which is 01011100101. Then p1, p2, p4 check are odd while p8 is OK. So we flip the $1+2+4 =7$-th bit to obtain 01011110101. So the corrected data bit will be 0111101. Well, OP can check if this or something similar is the case.

"This is from a quiz on my university's LMS, the site is saying my answer is incorrect."
As D.W. suggested, maybe they are wrong. Maybe whatever you read was in error. There might be a typo in the statement of the quiz. There might be an error in the original answer by the quiz owner. There might be an error in the answer-checking process by the site. There might be a critical typo in OP's post. And so on.

Jakube, D.W., I, and, apparently, many others have not been able to find the mistake. That is very unlikely, though.

The last possibility stands for, as always, all other probably even lesser possibilities.


How can the length of a string be $O(\log n)$?

The length of the binary representation of a natural number $n$ is roughly $\log_2 n$. As an example, the number represented by the binary string $10^{n-1}$ of length $n$ is $2^n$.

Your sources are misleading. Usually $n$ is reserved for the input length or a related quantity, not the input value. If the input to a function is an integer $m$, then the input length is only $\sim \log_2 |m|$. In particular, intToStr actually runs in linear time in the input length, rather than logarithmic time.


Optimal data structure for a time-windowed streaming graph in order to compute fast statistics

There's an efficient streaming algorithm for computing the average degree.  Note that if you have the sum of the degrees and the number of vertices, you can compute the average -- so we'll try to keep track of those two values.

Also note that if you delete or insert an edge, it is easy to update the sum of the degrees.  If you delete or insert a vertex, it is easy to update the number of vertices.

Taking all of this into account, we do $O(1)$ work (amortized) per time step, and at every time step we can infer the average degree.  This is as efficient as one could possibly hope for.


Vertex cover problem with 2-element vertices

Assuming you want the resulting graph to be disjoint (contain only isolated vertices), then your problem is as hard as the vertex cover problem.  There is a simple reduction.

Let $G^*=(V^*,E^*)$ be an undirected graph, where $V^* = \{v_1,v_2,\dots,v_n\}$.  Define $V = \{v_1,\dots,v_{2n}\}$, and define $E$ by creating edges $((v_i,v_{i+n}),(v_j,v_{j+n}))$ for each $i,j$ such that $(v_i,v_j) \in E^*$.  Note that this automatically satisfies all of your constraints, as there are no pair of edges $(w_1,w_2)$, $(w_1,w_3)$ in $E$ that share a common $v_i$.  Thus, given $G^*$, we can define a new graph $G$ of your form.

Any way to remove vertices in $G$ corresponds immediately to a way to remove vertices in $G^*$, and vice versa.  Moreover, the minimum number of vertices you can remove from $G$ to leave every vertex isolated is equal to the minimum number of vertices you can remove from $G^*$ to leave every vertex isolated.  The latter is exactly the vertex cover problem.  Therefore, we've shown a reduction from vertex cover to your problem: if we could solve your problem for $G$, we could solve vertex cover for $G^*$.


What is the computation model of Prolog?

I think the computation model of Prolog is the SLDNF resolution of Horn clauses.

Prolog is actually very procedural. Kowalski 1974: "The interpretation of predicate logic as a programming language is based upon the interpretation of implications [...] as procedure declarations [...]" (emphasis mine)

https://www.doc.ic.ac.uk/~rak/papers/IFIP%2074.pdf

(However, lambda calculus, theorem provers, and Turing machines are term rewriting systems indeed. What is a computational model then, if everything is a term rewriting system?)


Algorithm for simplifying ANF or polynomials?

The algebraic normal form (ANF) is unique.  You can't "simplify" the ANF; each formula has a single, unique ANF, and there's only one.  Once you've found it, that's it; there's no other, "simpler" ANF for the same formula.

Perhaps what you want is, given a formula, find the smallest circuit that uses only XOR and AND logic gates.  In general, that circuit won't necessarily be in algebraic normal form.  (For instance, $B_1 (B_2 \oplus B_3)$ is not in ANF; the ANF of that formula is $B_1 B_2 \oplus B_1 B_3$.)  That's called "logic minimization" or "logic synthesis" or "circuit minimization".  Most prior work has considered how to use a gate basis of NAND or {AND, OR, NOT}; you are looking for an algorithm that uses the basis {AND, XOR}.

If you want to minimize the total number of gates, I'd suggest you do a literature search on the literature on logic minimization, looking for methods that work with an arbitrary basis, or that work with the basis {AND, XOR}.  (One possibly buzzword or phrase to search for is exclusive-or sum-of-products minimization; this covers the special case of circuits that have multi-input AND gates on the first level and a single multi-input XOR gate at the second level.)

In general, essentially all of these circuit minimization problems are NP-hard, so you shouldn't expect any efficient algorithm that will always work.  Instead, people rely on heuristics that sometimes work or are sometimes efficient.

You can find people who have studied a similar problem in the cryptography world, because Yao-style garbled circuits naturally support AND and XOR gates.  Cryptographers have studied how to implement various functions efficiently using only AND and XOR gates.  However, in that world, for various reasons we can make XOR gates effectively free, so they generally try to minimize the "multiplicative complexity", i.e., the minimum number of AND gates needed in any circuit over the basis {AND,XOR}.  I couldn't tell whether that was what you wanted or not.  If it is, you might enjoy the following page, which lists circuits of minimal multiplicative complexity for a variety of functions of cryptographic interest:

http://cs-www.cs.yale.edu/homes/peralta/CircuitStuff/CMT.html

Perhaps this will help you articulate a more precisely defined question.


Finding context free grammar for this language?

When looking for CFGs for an expression like yours, it is often handy to work from the inside out, especially whan you need to match symbols. Think of your expression as $1(0^n10^n)1$. The interior part, within the parentheses, consists of a $1$ surrounded by an equal number of zeros on each side. We could generate this by the production $T\rightarrow 0T0$, since repeated use of this production would result in derivations like
$$
T\Rightarrow 0T0\Rightarrow 00T00\Rightarrow 000T000
$$
and so on. In other words, we could have $T\stackrel{*}{\Rightarrow} 0^nT0^n$, where the star over the arrow means "eventually results in". Now all you have to do is get the $1$ in the middle. That's easy: just add the production $T\rightarrow 1$. In sum, you can get the part in parentheses by the productions
$$
T\rightarrow 0T0\mid 1
$$
Now that you have the middle part, just add the external $1$s to a start variable production $S\rightarrow 1T1$, giving the full grammar
$$\begin{align}
S&\rightarrow 1T1\\
T&\rightarrow 0T0\mid 1
\end{align}$$

Your attempt was a good start, since you did generate the correct number of $1$s, but there was no guarantee that the two $S$ variables in $S\rightarrow1S1S1$ would generate the matching $0$s you need.


Getting the sorted sequence from a level-wise sorted min-heap

Use a recursive algorithm.  Suppose the heap has depth $D$.  Recursively compute a sorted list of all the numbers in the top $D-1$ levels (i.e., all but the bottom level); let $L$ be this list.  Let $L'$ be the list of numbers in the bottom level.  Note that both $L$ and $L'$ are in sorted order, so we can use the Merge procedure from Mergesort to compute a sorted list of all of the numbers.

If you work out the recurrence relation, you'll see that the running time of this algorithm is $O(n)$.  Indeed, Merge runs in $cn$ time, for some constant $c$, so the total running time will be $cn + cn/2 + cn/4 + \dots \le 2cn = O(n)$.


How to define the natural numbers as a W-type?

The formation and introduction rules for W-types, as given on n-cat lab, are:

$$\frac{A:Type\quad x:A⊦B:Type}{(W x:A)B(x):Type}-\text{Formation}$$

$$\frac{a:A\quad t:B(a)\rightarrow W}{sup(a,t):W}-\text{Introduction}$$

You can define the natural numbers by setting $A=Bool$ and $B(a) = \text{if}\; a\; \text{then}\; ⟂\; \text{else}\; Unit$. Where $⟂$ is the empty type and $Unit$ is the unit type.

Zero is then $sup(a,t)$ where $a=true$ and $t: ⟂ \rightarrow Nat = λn. abort(n)$. eg. we use the zero constructor (by choosing $a=true$) and fill in the only possible value of a function from $⟂$ to $Nat$.

The successor of $p$ can be defined as $a=false$, $t:Unit \rightarrow Nat = λx.p$.


How much information, in bits, is conveyed by a 3-bit output representing how many 1s in a 7-bit input?

Assuming the 7-bit input is chosen randomly, the entropy of the number of 1s is
$$
 \sum_{i=0}^7 \frac{\binom{7}{i}}{2^7} \log \frac{2^7}{\binom{7}{i}} \approx 2.45 \text{ bits}.
$$
This is because the probability that the number of 1s is $i$ equals $\binom{7}{i}/2^7$.

You are asking how much information is conveyed by particular outputs, and this can be interpreted as the loss in entropy: if $X$ is the random 7-bit input and $Y$ is its sum, you could define the information conveyed by $Y=i$ as $H(X)-H(X|Y=i)$. Since $X$ has uniform distribution,
$$
 H(X) - H(X|Y=i) = \log 2^7 - \log \binom{7}{i} = \log \frac{2^7}{\binom{7}{i}}.
$$
The information conveyed by different outputs, under this definition, works out to be roughly (in bits):
$$
\begin{array}{|c|c|c|c|c|c|c|c|c|c|} \hline
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\\hline
H(X) - H(X|Y=i) & 7 & 4.19 & 2.61 & 1.87 & 1.87 & 2.61 & 4.19 & 7
\\\hline
\end{array}
$$
The weighted average of these values equals the entropy calculated above.


Designing a CFG that produces as many c's as the difference of numbers of a's and b's

Yuval's answer is headed in the right direction: consider $L_1 = \{a^lb^mc^n \mid n = l - m\}$ and $L_2 = \{a^lb^mc^n \mid n = m - l\}$. Also, as he points out, it's helpful to think of these conditions as $l = n+m$ and $m = n + l$, respectively.

I propose the following grammar for $L_1$:
$$S' \rightarrow aS'c \mid B' \mid \epsilon$$
$$B' \rightarrow aB'b \mid \epsilon$$

I propose the following grammar for $L_2$:
$$S'' \rightarrow A''C''$$
$$A'' \rightarrow aA''b \mid \epsilon$$
$$C'' \rightarrow bC''c \mid \epsilon$$

Now, what remains is to show these grammars generate $L_1$ and $L_2$, after which you can give your answer as the following:
$$S \rightarrow S' \mid S''$$

(You could even use just one symbol for $B'$/ $A''$, since they have the same rules.)

To show each of the proposed grammars works, you'll need to show two things: each proposed grammar generates only strings in the target language; each proposed grammar generates all the strings in the target language.

Arguing informally, we can say the proposed grammar for $L_1$ generates only strings in $L_1$ since whenever we add an $a$, we add either a single $b$ or a single $a$; furthermore, we have all $b$ coming after $a$, and all $c$ coming after $b$. To show that all the strings are generated, consider that applying the rule $S' \rightarrow aS'c$ a number of times equal to $\#_c(w)$, then the rule $S' \rightarrow B'$, then the rule $B' \rightarrow aB'b$ a number of times equal to $\#_b(w)$, then the rule $B' \rightarrow \epsilon$, yields the string $w = a^{\#_b(w)+\#_c(w)}b^{\#_b(w)}c^{\#_c(w)} \in L_1$ for any non-negative $\#_b(w), \#_c(w)$.

The arguments for the second proposed grammar are similar.


It depends on how you define subexponential. The definition I generally use is:

$$\textsf{SUBEXP} = \bigcap_{\varepsilon > 0}\textsf{DTIME}(2^{n^\varepsilon})$$

However some authors define:

$$\textsf{SUBEXP} = \textsf{DTIME}(2^{o(n)})$$

Since your function is $2^{n^c}$ for some constant $c<1$, it would be subexponential according to the second but not to the first.


Dynamic programming: Knapsack with repetition, Find the number of redundant machines

the maximum sucesss probability would be the minimum failed probability, and each machine should be at least 1, so we can reduce the original package B into B'= B-sum(c_i), and each machine's dp[i][0] should be initialized as fail probability (1 - r_i).

so, we can find the dp state transition based on the modified knapsack(size is B') problem as above:

dp[i][c]    = min(dp[i-1][c], dp[i-1][c-cost[n]]*(1-r_i))
    0<= c <=B' , 1<=i<=n, B' = B-sum(c_i)

intitial of the dp array would be like this:

dp[0][0~B'] = 1
dp[i][0]    = 1-r_i, 1<=i<=n

so the pseudocode would be like :

 for(int i = 1 ; i<=n;++i)
  for(int c = cost[i] ; c<=B';++c)
     dp[i][c] = min(dp[i-1][c], dp[i-1][c-cost[n]]*(1-r_i)))


Difference between greedy and work conserving scheduler for DAG

If I understand well, it is the same scheduling method with different names. I think Work-conserving Scheduler is the more "official" one. "greedy" can indeed qualify many aspects of the problem and one should always precise which. greedy algorithm is a paradigm not a specific method for a specific problem.

Anyway about the upper-bound, the presentation of your last link says that it is:

$T < (T_1-T_\infty) / m + T_\infty$

but that a simpler one is generally used:

$T < T_1 / m + T_\infty$

Of course the latter is greater than the former but both are true. Also note that they are both equivalent to $T_\infty$ when $m$ tends to $+\infty$.


Are SAT problems with at most one false clause NP-complete?

Given a CNF with $n$ variables and $m$ clauses, we denote by $A_i$ the set of truth assignments that do not satisfy clause $i$. Then the number of satisfiable assignments is
$$2^n-\left|\bigcup_{i=1}^m A_i\right|.$$
Since each assignment makes at most one clause false, $A_i$ and $A_j$ are disjoint for $i\neq j$. Also note $|A_i|=2^{n-n_i}$ where $n_i$ is the number of variables in clause $i$. Hence, the number of satisfiable assignments is exactly $2^n-\sum_{i=1}^m 2^{n-n_i}$ (this result is also given as lemma 2 in [1]).

So we can decide whether the CNF is satisfiable by checking whether $2^n-\sum_{i=1}^m 2^{n-n_i}>0$, which can be done in polynomial time.

[1] Nishimura, N., Ragde, P., & Szeider, S. (2007). Solving #SAT using vertex covers. Acta Informatica, 44(7-8), 509-523.


What is the error-detection-probability of CRC

There's nothing in your requirements that forces you to use a CRC32.  You could use any checksum.  If the collision probability for a CRC32seems too high, use a different checksum.

For instance, if you use SHA256, you will never have to worry about collisions -- for all engineering purposes, you can treat them as impossible (something that will never happen in your lifetime).  And then you won't need to worry about selecting generator polynomials or anything like that; someone else has done all that work for you.  You just use the standard SHA256 algorithm.

P.S. Using a basic checksum algorithm will require you to recompute the checksum on the entire table any time you insert or delete one row.  If that's too slow, there are a number of schemes to speed that up, such as a Merkle hash tree.


How can I verify a solution to Travelling Salesman Problem in polynomial time?

The crux is that you have to consider the decision problem:

  Travelling Salesman Problem (Decision Version). Given a weighted graph G and a target cost C, is there a Hamiltonian cycle in G whose weight is at most C?

For a 'yes' instance, the certificate is just some Hamiltonian cycle whose weight is at most C. If you could solve this problem efficiently, you could find the cost of a minimum tour by binary search, starting with the weight of the entire network as an upper bound.


Linear time algorithm for finding $k$ shortest paths in unweighted graphs

No. The best times known can be found in the survey "Implementations and empirical comparison of k shortest loopless path algorithms".

As a note, it is impossible to get linear times in the weighted case. There are lower bounds for the shortest path (i.e., k=1), which are not linear.

In the directed acyclic case you might have linear times for the k-SP, but I think is an open problem.

Cheers


Proving intuitionistic tautologies in Agda

For examples like this, they can often by easily written interactively just looking for the only thing possible to do at each stage. So for instance, you start with:
wp e = ?

and the only option is to apply e, at which point Agda will tell you you need to provide $((A → B) → A) → A$, so you introduce a lambda:
wp e = e (λ k -> ?)

Now you need to give an A, which is the result type of k, so you apply k and abstract again:
wp e = e (λ k -> k (λ x -> ?))

Now you need to give a B. The only thing that results in a B is e, so you apply it again. However, now your situation is different, because x is in scope. And presumably you don't want to follow the same pattern as you did before, so you can write:
wp e = e λ k → k (λ x → e (λ _ -> x))

In this case, the process is constrained enough that the auto-solver comes up with this solution.
As for what the type means, Peirce's law is similar to double-negation elimination with the $⊥$ replaced with $B$: $$((A → B) → B) → A$$ Peirce's law follows from the above type, because you can massage an $(A → B) → A$ into an $(A → B) → B$ by duplicating the function argument.
So, your overall type can be read as similar to:
$$¬¬(¬¬A → A)$$
Which fits the theme of double-negated classical (propositional) theorems being intuitionistic theorems.


Cost to convert one integer array into another

Let $\ell_{i}$ denote the number of digits in $a[i]$. Then the complexity of the naive algorithm as suggested by you is $O(\ell)$, where $\ell = \sum_{i = 1}^{n} \ell_{i}$.
Moreover, the algorithm must visit every digit at least once. For the sake of contradiction, suppose the algorithm did not visit some digit in the array. Then an adversary can modify the unvisited digit to a different digit. This will prove that your algorithm's output is incorrect. Therefore, any correct algorithm must require at least $\Omega(\ell)$  comparisons. Thus, you can not expect better than $\Theta(\ell)$ complexity for this problem.


More efficient maximum bipartite matching

The Hungarian method can be implemented in time $O(mn + n^2 \log n)$. Details are found for example in Alexander Schrijver's book on Combinatorial Optimization, Chapter 17. For a more implementation-oriented guide to this version of the algorithm, have a look in Chapter 7 of Mehlhorn and Näher's book.

The running time is dominated by the time it takes to compute $n$ shortest paths via Dijkstra's algorithm. Each invocation of Dijkstra's algorithm costs $O(m + n \log n)$. (This assumes that Dijkstra's algorithm is implemented with Fibonacci heaps; the simpler implementation based on standard heaps would give $O(m \log n)$ for each invocation.)


Proving correctness of the Newton's Method for finding the square root of a number

I suggest you take some example values and see the pattern how Y actually changes. Observe that at the first iteration of the loop, Y may be too small, but only on the first iteration. Then you should see how Y changes after that.

With that, you should find a much stronger loop invariant that lets you actually prove convergence (if TOL is small enough and we ignore arithmetic overflow).


How do you describe a language that is generated by Context Free Grammer

Hint: How many $b$s are there in each word generated by this grammar?

Guidance: What is the language generated by $X$? What is the language generated by $XXX$? What is the language generated by $S$?


Your language is indeed co-c.e.; the mistake is in the argument claiming recognizability of $L$. You have the existential and universal quantifier mixed up.


As it turns out by a rather complicated chain of reductions starting from three dimensional matching, which is too involved to be discussed here, bin packing remains NP-hard for twin items. It even remains hard for triplets, quadruplets or any fixed number of similar items.


Can we find a computable function which cannot be calculated faster for any given time?

The "$f$-bounded halting problem" takes time at least (roughly) $f$ (for infinitely many $n$). The $f$-bounded halting problem asks whether a Turing machine halts on the input $0^n$ within time $f(n)$. Suppose we could solve this problem in time $g(n)$. Consider the following machine:

  On input $0^n$, ask whether the $n$th Turing machine halts within time $f(n)$ on the input $0^n$. If so, go into an infinite loop, and otherwise, halt.

This takes time $g(n) + Cn$ for some constant $C$. If $g(n) + Cn \leq f(n)$ then we obtain a contradiction by taking $n$ to be the code of this machine. Hence the $f$-bounded halting problem cannot be solved in time $f(n) - Cn$.

This argument only shows that we need time $f(n) - Cn$ for some $n$. But we could consider an infinite sequence of Turing machines equivalent to the one described above, and so obtain an "infinitely often" version of this statement.

It is possible that through trickery we can improve this to all $n$ (for reasonable functions $f$), and leave this for the reader to ponder.


Yes, if you can come up with any of the following:

deterministic finite automaton (DFA),
nondeterministic finite automaton (NFA),
regular expression (regexp of formal languages) or
regular grammar

for some language $L$, then $L$ is regular. There are more equivalent models, but the above are the most common.

There are also useful properties outside of the "computational" world. $L$ is also regular if

it is finite,
you can construct it by performing certain operations on regular languages, and those operations are closed for regular languages, such as

intersection,
complement,
homomorphism,
reversal,
left- or right-quotient,
regular transduction

and more, or
using Myhill–Nerode theorem if the number of equivalence classes for $L$ is finite.

In the given example, we have some (regular) langage $L$ as basis and want to say something about a language $L'$ derived from it. Following the first approach -- construct a suitable model for $L'$ -- we can assume whichever equivalent model for $L$ we so desire; it will remain abstract, of course, since $L$ is unknown. In the second approach, we can use $L$ directly and apply closure properties to it in order to arrive at a description for $L'$.


As David Richerby pointed out $D^*$ will accept an arbitrary number of letters (including none). If I'm not mistaken you need to take all possible options to achieve not having more than 8 characters.
$$
K = ( PDD-PDEF ) \cup (PDD-PEFF) \cup (PD-PDEFF) \cup (PD-PEFFF) \cup (P-PDEFFF)
$$
This assumes the hyphen is one of the 8 letters and thus does not allow more than 8 letters. Less letters are allowed because of your definitions of $F$ and $D$ including the empty word $\varepsilon$.

EDIT: added missing cases from commenter.


new language accepted by FA when new transitions are added to a FA?

Your answers to (a), (b), and (c) seem correct to me. Here's something to think about for (d).
Hint for (d): Let's say $s = s_1s_2...s_k \in L$, and on input $s$ the original transition function follows the path $P = q_0, q_1... q_f$. Let $q_{s_i}$ denote the state $q_i$ closest to $q_f$ in $P$ after only reading up to $s_i$ in the original NFA. What are the strings can I generate by doing the following in the NFA defined by (d)? $\lambda$-transition from $q_0$ to $q_{s_i}$, follow $P$ up to $q_{s_j}$ (for any $1 < i < j < k$), and then $\lambda$-transition to $q_f$ and accept.


Changing from Kernel mode to User mode (and vice versa)

Usermode to kernelmode: Wrong! ;-) Yes, interrupts are processed in kernel mode, and originally the way to enter kernel mode was by an interrupt forced somehow by software. On the DEC 2020 there was a set of UIOs (Unimplemented Instruction Opcodes), calling any of those caused a trap to the operating system. They included floating point instructions (if not in hardware) and other exotic instructions, but also the means to do operating system calls. The i?86 family has the int (interrupt) instruction, traditionally used as you say. Newer members of the family have SYSTENT to do supervisor calls more efficiently. The means of going to supervisor mode can't be privileged, but must somehow be tightly controlled by the kernel (where you enter the kernel, what arguments you pass, ...).

Kernelmode to usermode: No need for the "drop privileges" operation to be privileged. If you don't have privileges, dropping them is a no-op. But the exact mechanism is architecture dependent in extreme.

Interrupts disabled in kernel: Interrupts indicate some condition that has to be handled as soon as possible (for example, if the data arrived over the net isn't saved from the card before the next arrives, it will get overwritten). Thus interrupts are very rarely disabled. In original Unix systems (and contemporaries), there was one CPU, and the simplest way to get a critical region ("nobody mess with my data while I modify it") was just to disable interrupts. Pains were taken to keep the "interrupt disabled" stretches as short as possible because of the above. On current multi-CPU machines, disabling interrupts on one CPU does nothing much in this direction; disabling interrupts globally is extremeñy costly in inter-CPU coordination, so it is not done (or extremely rarely).


How to find the equivalence classes of a regular language

You have to be creative. In this case, the equivalence classes are:

$X_a = \{0^a\}$ for $a \geq 0$.
$Y_a = \{0^{n+a} 1^n : n > 0\}$ for $a \geq 0$.
$Z = \{0^n 1^m : m > n \}$.
$W = \{w : w \text{ contains } 10\}$.

We can construct an infinite DFA to show that each of these classes consists of equivalent words:

The initial state is $X_0$.
The accepting states are $X_a,Y_a$ for $a \neq 0$ and $Z$.
$\delta(X_a,0) = X_{a+1}$, $\delta(X_0,1) = Z$, $\delta(X_{a+1},1) = Y_a$.
$\delta(Y_a,0) = W$, $\delta(Y_0,1) = Z$, $\delta(Y_{a+1},1) = Y_a$.
$\delta(Z,0) = W$, $\delta(Z,1) = Z$.
$\delta(W,0) = \delta(W,1) = W$.

This also shows that the classes cover all of $\Sigma^*$. Finally, in order to show that these are the equivalence classes, we need to show that any two classes have a separating word:

$X_a,X_b$: $1^a$.
$X_a,Y_a$: $0$.
$X_a,Y_b$: $0$.
$X_a,Z$: $1^a$.
$X_a,W$: $0$.
$Y_a,Y_b$: $1^a$.
$Y_a,Z$: $1^a$.
$Y_a,W$: $1^{a+1}$.
$Z,W$: $\epsilon$.


There is definitely an inconsistency in what you've written here. My guess is that $t$ doesn't mean what you think it means. You are using it here to describe the size of the significand field, that is, the number of digits after the radix point. (It's not a decimal point in general!)

My guess is that your lecturer is using it to refer to the precision. The precision of the floating point format includes the implicit $1$. That is, your floating point number is:

$d_1.d_2 d_3 d_4 \ldots d_t \times \beta^e$

where $d_1$ is always $1$. If you interpret $t$ that way, the two epsilons make more sense.

This is the way that the IEEE-754 standard defines these constants. For example, a binary32 (formerly called "single precision") floating point number has a precision of 24 bits, in that the mantissa is 24 bits. However, the significand field is only 23 bits, because the leading one bit is implicit.


Could following be a counter example to Church-Rosser (Confluence) theorem?

If we keep reducing the right subterm, then yes, we will never get to $v$. But noone says that we are restricted to this decision. The Church-Rosser theorem does not claim that any possible reduction series must lead to $N_3$. Church-Rosser just states that $N_2 \twoheadrightarrow_\beta N_3$, i.e. that there exists some beta reduction series that will lead from $N_2$ to $N_3$. And it is obvious that no matter how many times we just reduce back to $(\lambda u.v)((\lambda x.xx)(\lambda x.xx))$, at any point we can choose our next reduction step to be on the left-hand side, which will immediately get us to $v$. So it is possible to find a reduction series from both $N_1: v$ and $N_2: (\lambda u.v)((\lambda x.xx)(\lambda x.xx))$ to $N_3:v$ -- and that's all the Church-Rosser theorem states.


An algorithm is informally described as a finite sequence of written instructions for accomplishing some task. More formally, they're identified as Turing machines, though you could equally well describe them as computer programs.

The precise formalism you use doesn't much matter but the fundamental point is that each algorithm can be written down as a finite sequence of characters, where the characters are chosen from some finite set, e.g., roman letters, ASCII or zeroes and ones. For simplicity, let's assume zeroes and ones. Any sequence of zeroes and ones is just a natural number written in binary. That means there are at most a countable infinity of algorithms, since every algorithm can be represented as a natural number.

For full credit, you should be worried that some natural numbers might not code valid programs, so there might be fewer algorithms than natural numbers. (For bonus credit, you might also be wondering if it's possible that two different natural numbers represent the same algorithm.) However, print 1, print 2, print 3 and so on are all algorithms and all different, so there are at least countably infinitely many algorithms.

So we conclude that the set of algorithms is countably infinite.


Generally speaking, in algebra, a congruence relation is an equivalence relation such that operations on equivalent objects yield equivalent objects. In the lambda calculus, a congruence is an equivalence relation such that constructing terms from equivalent terms yields equivalent terms: if $M \equiv M'$ and $N \equiv N'$ then $M\,N \equiv M\,N'$, and if $M \equiv M'$ then $\lambda x.M \equiv \lambda x.M'$.
“Alpha congruence” is another name for alpha equivalence, which is the relation such that two terms are alpha-equivalent if they are, intuitively speaking, the same except for renaming internal variables. Since this is not only an equivalence but even a congruence, it's called both “alpha equivalence” and “alpha congruence”.


Determine the optimal strategy and maximize the reward

The key observation is that, for player A, picking an object which is not being picked by player B is equivalent to skipping the turn and saving this pick for later (for example use a variable savedPicks). Now instead of having to decide upon which object to pick the problem becomes deciding if player A should pick the current object picked by player B or save the pick for later. So we iterate through the objects depending on how player B picks them and either also pick the object as he does or save a pick for later.

Now the problem is solvable with DP, observe that your state consists of the current object which is targeted by player B, the remaining size of the object and the number of picks player A has saved.

There are three transitions:

Object is finished, move to the next one,
Player A skips the round and saves a pick for later (savedPicks++),
Player A uses a saved pick to pick the current object (potentially getting the reward if his pick finished the current object).

Solve each of the three transitions, apply memoization (save already computed states, use a 3 dimensional array for example), don't forget the base case (all objects have been finished).

Happy coding!


Complexity time $O(2^n)$ is called $\text{DTIME}(O(2^n))$ and is a sub-complexity class of E which is in turn a sub-complexity class of EXPTIME.
To prove you can do it within $O(2^n)$ time, you have to provide an algorithm for that and show the algorithm runs in no more than $O(2^n)$.


Visualization of Lamport's three-dimensional "space-time diagram" with introduced "tick lines"

Here's my take:

...and here's a 3D version without the nice colors.

Vertical black lines are processes; magenta lines are messages (wavy lines); spheres are events, and time is on the vertical (blue) axis.  The planes are 'tick lines.'

In Dr. Lamport's original diagrams, messages are only passed between "adjacent" processes.  Presumably in a real distributed system any process can send a message to any other process, but this is hard to draw clearly in a 2D diagram.


Incremental strongly connected components

To the best of my knowledge, the best algorithm for decremental strongly connected components is presented in [1] with $O(m \sqrt{n} \log n)$ total expected update time.

  [1] Decremental Single-Source Reachability and Strongly Connected
  Components in Õ(m√n) Total Update Time - Shiri Chechik, Thomas Dueholm  Hansen, Giuseppe F. Italiano, Jakub Łącki, Nikos Parotsidis -  https://ieeexplore.ieee.org/document/7782945 - FOCS 2016

Update: The new best Algorithm for decremental SCCs is $O(m (\log n)^4)$ presented in [5]

  [5] Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time
   - Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen -https://arxiv.org/abs/1901.03615 - accepted at STOC 2019

The best algorithm for incremental strongly connected components is presented in [2] with $O(m^{1/2})$ update time per edge.

  [2] Incremental Cycle Detection, Topological Ordering, and Strong
  Component Maintenance - Bernhard Haeupler, Telikepalli Kavitha, Rogers
  Mathew, Siddhartha Sen, Robert Endre Tarjan -https://arxiv.org/abs/1105.2397 - 2012 ACM Trans. Algorithms

It is an open question if those two problems can be solved faster.

For fully dynamic strongly connected components conditional lower bounds are known. Worst-case lower bounds are also known for decremental/incremental strongly connected component maintenance. For details look in [3] and [4].

  [3] Unifying and Strengthening Hardness for Dynamic Problems via the
  Online Matrix-Vector Multiplication Conjecture - Monika Henzinger,
  Sebastian Krinninger, Danupon Nanongkai, Thatchaphol Saranurak -  https://arxiv.org/pdf/1511.06773.pdf - STOC 2015

  [4] Popular conjectures imply strong lower bounds for dynamic problems
  - Amir Abboud, Virginia Vassilevska Williams - https://arxiv.org/pdf/1402.0054.pdf - FOCS 2014

All of these results hold for general graphs. Better results are known for planar graphs.

The result you mention about DAGs is well known:

  Amortized efficiency of a path retrieval data structure - G. F. Italiano - https://www.sciencedirect.com/science/article/pii/0304397586900988 - TCS 1986


Solve the recurrence relation T(n)=3T(√n)+lg(n)

Define $X(n) = T (2^n)$.

Then $X(n) = T (2^n) = 3T(2^{n/2}) + n = 3X(n/2) + n$.

You solve the recurrence for $X(n)$, and $T(m) = X (\log m)$.


How does the Vertex Cover algorithm by Chen et al find its tuples?

The beginning of Section 4 states:

  A tuple, a good pair, or a vertex of degree at least seven, will be referred to by the word structure. The algorithm will
  maintain a list of structures $\mathcal{T}$, and then it will pick a structure and process it. ... We will assume that the algorithm implicitly
  updates the structures in $\mathcal{T}$ and their priorities after each operation.

It seems that you shouldn't really think of $\mathcal{T}$ as a parameter, but as a dynamically updated list. As for intuition, I suggest that you read the full paper. Once you understand the proof, you should be able to come up with some sort of intuition.


Why is determining if there is a solution to a Battleship puzzle NP-Complete?

As Andreas T mentions, what you're missing is that the grid is part of the instance.
The instance specifies both the grid and the ships.

Why can't the Battleship puzzle be solved in polynomial time? This is the one million dollar question (literally). But since the paper you mention proves that Battleship is NP-complete, the widely believed conjecture P≠NP implies that Battleship cannot be solved in polynomial time.

The paper goes on to prove that Battleship cannot be solved in polynomial time even when the solution is unique, unless NP=RP, which is also considered unlikely. This is a more realistic version of the problem, since in practice Battleship problems have a unique solution.


Proof of uniform convergence if VC dimension is finite

Let $X = |L_\mathcal{D}(h) - L_S(h)|$. The statement on the expectation of the supremum of $X$ implies, in particular, that for some $M$,
$$
\mathbb{E}[X] \leq M.
$$
Since $X \geq 0$, Markov's inequality implies that
$$
\Pr\left[X \geq \frac{M}{\delta}\right] \leq \delta.
$$
This implies that
$$
\Pr\left[X \leq \frac{M}{\delta}\right] \geq
\Pr\left[X < \frac{M}{\delta}\right] =
1 - \Pr\left[X \geq \frac{M}{\delta}\right] \geq 1 - \delta.
$$


no of times partion is called in quick sort, assuming array is always halved

The number of times the partition algorithm is called does not actually depend on where the array is partitioned (asymptotically).
To count the number of partitions you just need to count the number of internal nodes in the recursion tree. Since each internal node has at least two children, the recursion tree is a full binary tree. In a full binary tree, the number of leaves and internal nodes are linearly related (see this link). So the number of internal nodes would be $\Theta(n)$, no matter where the partition happens. You can easily prove this using induction on the number of nodes in the tree.


Algorithm to find individual, closed groups of lines in a large set of connected lines

Assuming you essentially want to partition the 2D space into pieces using the given lines and border where

no two pieces overlap
all pieces sum to the original space
all the pieces primitive i.e. can not be split further

Consequently, there is a nice property that each line that actually border a polygon will be between exactly 2 polygons. This is more apparent when thinking about the notions of dual graph of plane graph

Note the outer partition piece formed with the border of the whole picture.
Algorithm
Initialise
Each line has 2 pointer to be pointed to the partition it borders (red dot).
These pointer are initialised to empty.
Our algorithm terminates when all of these pointers are non empty.
Main

Pick a line with at least one still empty partition pointer.
Walk along the adjacent edge that makes the least angle from the side of the line that still has a free pointer. (do remember the properties of vector's cross product and dot product. These will be your tools in calculating the angle and determining the side.)
[If there is no adjacent line to walk at all, you need to mark the current line as not being part of any polygon and backtrack]
Once you complete a cyclic walk, update all the "sides" used and point them to a newly created "partition" object.
Repeat step (1) until all lines has been assigned 2 pointers to its bordering partition. (except if that line is marked as not a part of any polygon or is the border of whole picture.)


$O(\log n)$ search algorithm for a sorted natural number array with block of 0s on right

A two-stage binary search works. First, for the purposes of this search define $0$ to be greater than any positive integer.

Then, let $l = 1$ and $h = 2$ and:

While $A_h \leq x$ let $l \leftarrow h$ and $h \leftarrow 2h$. Since for all $h > n$ we have $A_h = 0$, which we defined to be greater than any positive number, this loop must exit within $O(\log n)$ iterations.
Now $A_l \leq x < A_h$, and $A$ is sorted, so we can do a binary search in range $[l, h]$. This also takes $O(\log n)$ steps since $l,h \leq 2n$.


Q1. The empty language is decidable however you encode it.

Q2. Represent the natural number $n$ as the encoding of the $n$th Turing machine that halts when started with a blank tape. Under this encoding, any set of natural numbers, except for $0$ and $\mathbb{N}$ is undecidable.


Contradiction in regularity of a language

There is a difference between $L_2 = \{ww\mid w \in L_1\}$ and $L_3 = L_1 L_1$. $L_3$ is $\{wx\mid w, x \in L_1\}$; in, other words all strings consisting of two sentences from $L_1$, which is regular / context-free if $L_1$ is regular / context-free.

$L_2$ is the set of all strings consisting of one repeated string from $L_1$, which is not in general context-free. (It is regular if $L_1$ is finite or is a regular language over a singleton alphabet. But your example does not fall into either of these categories.)


Complexity of inverting a diagonal matrix

It's unclear what $n$ is in your question. If your matrix has dimensions $n \times n$ and your model of computation allows you to perform
basic arithmetic operations in constant time then, yes, computing the inverse matrix takes $O(n)$ time.


Converting a Mixed SUBSET-SUM Problem To All-Positive Case

Both variants are NP-complete, so such a reduction surely exists: the definition of NP-completeness guarantees it.
If you want an explicit reduction, you can reduce one to the other (reduce to 3SAT using Cook's theorem, then reduce 3SAT to the other using its NP-completeness).  The resulting reduction will be ugly, though, so I suspect this might not be what you're looking for.
If you want a simple and natural reduction, I'm not sure how to achieve it.


Can every Turing Machine be translated into a SAT formula?

The proof of the Cook-Levin theorem shows that for any nondeterministic Turing machine $M$, any input $x$, and any (reasonable) time bound $t(n)$, we can construct (efficiently) a SAT formula of size proportional to $t(|x|)^2$ that is satisfiable iff $M$ accepts $x$ within $t(|x|)$ steps.

If you know that $M$ is supposed to halt within $t(n)$ steps, then the SAT formula captures the behavior of $M$ on $x$. But for a general Turing machine we don't possess any a priori bound on the running time. This is why you cannot solve the halting problem in this way.


Is this "cycle" condition sufficient for unique minimum spanning tree?

Answer My Own Question by attempting to prove that the condition above is sufficient for a graph $G$ to have a unique MST. I am asking for reviews. Thanks in advance.

First, for each cycle, the unique heaviest edge in it must be not in any MST. Consider the remaining graph $G'$, obtained by keeping removing the unique heaviest edges in cycles from $G$. All MSTs are part of $G'$. If we can show that $G'$ is a spanning tree, then $G'$ is the unique MST of $G$.

$G'$ is connected because each edge removed belongs to a cycle when it was removed.
$G'$ is acyclic because we are keeping breaking cycles.
Thus, $G'$ is a spanning tree.


Seems correct , cache hit gives you 0.95*20 ns if it misses then 0.05 or 5% of the time you consult memory that is 0.05*( no page fault hence 0.99*( 500 from mem to cache + 20 from cache to cpu) else if page fault occurs then 1% or 0.01 *( 10000 ns from disk to mem +  500 ns from mem to cache + 20 ns from cache to cpu))
Should be 45.5 ns which I would give as C


a cut containing exactly one edge in each path

It really depends on what do you exactly mean by "path".

Edge-disjoint paths -- Given a graph $G=(V,E)$, a minimum edge-cut consists of one edge for every edge-disjoint path between $s$ and $t$.

Vertex-disjoint paths -- Given a graph $G=(V,E)$, a minimum vertex-cut consists of one vertex for every vertex-disjoint path between $s$ and $t$. Therefore, the set of edges incident to the vertices in the cut (out-edges) consist of one edge per vertex-disjoint path between $s$ and $t$.

Having exactly one edge per every simple path between $s$ and $t$ is impossible. The reason is that the number of edges in the cut must be equal to the number of simple paths between $s$ and $t$, however, the number of simple paths between two vertices $s$ and $t$ can be exponential in terms of $n$, while the number of edges is at most $n^2$. Using Pigeonhole principle, it can be shown that it is impossible to find such solution.

The following example shows that the number of paths between $s$ and $t$ is $2^{(n-2)/2}$, while the number of edges between them is $2n-4$.

If you are interested in finding a set of edges that consists of at least one edge from every path between $s$ and $t$, then you can use the minimum edge-cut between $s$ and $t$.
If you are considering a case where you need at least one edge from each path, and no more than one edges per path, you can use an approach that is similar to minimum cut algorithm, but I am not sure how efficient it would be in practice.

Find the minimum edge-cut between $s$ and $t$;
Using a graph traversal algorithm (i.e. DFS), find if there is a path that goes over two of the edges in the cut;
If you find a such a path, remove those edges $(u_1, v_1), \cdots, (u_k, v_k)$ from the cut $C$ and replace them with the minimum cut from each $u_i$ to $t$ ($1 \leq i \leq k$), and repeat from 2;
If there is no such path then output $C$ and terminate;


Does there exist standardized language-agnostic data structure notation?

In terms of notation:

Isn't XSD exactly what you are looking for? (barring all the "severe criticism" ...). Also not sure if you are looking for a notation convenient to hand-write, that's certainly NOT XML :-).
Typedefs and preserves seem to have more of a mathematical basis, perhaps closer to what you are looking for. A related HN thread.

I suspect you already know a lot of these projects, usually the focus is in serialization:

The IDL list at wikipedia ...
Amazon's Smithy and Ion.
Microsoft's Bond.
And of course Google's protobuf and flatbuffers, but also Mojo, oriented to IPC, and Fuchsia FIDL which seems similar.

Investigating this space I found Arrow, "a language-independent columnar memory format" for sharing memory between programs, with libraries for a dozen of languages. Turns out it uses flatbuffers under the hood.
Now that I came up with this list and I suspect you may be familiar with a lot of them, perhaps will be useful to know in which way the thing you are looking for is different. I think the keyword "notation" on your question is the key.
Cheers!


Compiler - Why is the grammar not suitable for shift-reduce

The grammar is ambiguous, so no deterministic parsing technique will be able to handle it. The parsing techniques called "shift-reduce" are all deterministic.


Data structure for a tree of points moving in space

You can solve this with a heavy-light decomposition of the tree.  This will give you a data structure where the "rotate" operation runs in $O(\log n)$ time and the "retrieve position of leaf" operation runs in $O(\log^2 n)$ time, where $n$ is the number of nodes in the tree.  Heavy-light decomposition is a big cannon, so it's possible there might be some simpler solution, but this should work.  Let me explain the ideas in several steps.

Closure property of affine transformations

If $T$ is a a rotation around some point in space, note that it can be represented as an affine transformation.  Also, the set $\mathcal{T}$ of affine transformations is closed under composition.  In particular, if $T_1,T_2$ are two affine transformations, let $T_2 \circ T_1$ denote the result of first applying transformation $T_1$, then applying transformation $T_2$; then $T_2 \circ T_1$ is itself an affine transformation, and its parameters can be efficiently computed from the parameters of $T_1,T_2$.  So, if we have a sequence of transformations that should be applied to a point, we can concisely represent the composition of the sequence of transformations by $O(1)$ parameters (namely, the parameters of their composition).  This will be useful in a moment.

In particular, rather than updating the position of individual nodes, we will store information to help us recover the transformation that should be applied to any particular node.  When we want to retrieve up the location of a node, we first look up this transformation, then apply it to the original location of that node to obtain its current location, and output that.

Warm-up: a path

As a warm-up, let's consider the most extreme special case of your situation: where the tree is a path of length $n$, i.e., each node has exactly one child, and there is a single leaf.  I'll assume each node in this original tree may have a position associated with it.

Data structure. We can build a data structure for this case where all operations run in $O(\log n)$ time.  Build a complete binary tree (of height $\lceil \lg n \rceil$) over these $n$ nodes; to give it a name distinct from your original tree, call this the "index tree".  Each node of the original tree is a leaf in the index tree.  Each node $w$ of the index tree corresponds to a consecutive subpath of the original tree/path (namely, the ones corresponding to the leaves of the index tree that are descendants in the index tree of $w$).

Now each node $v$ of the original tree has a transformation $T_v$ associated with it.  Suppose a node $w$ of the index tree corresponds to the subpath of nodes $v_1,\dots,v_k$ in the original tree.  Then we will label $w$ with the transformation $T_{v_k} \circ \cdots \circ T_{v_1}$.  This will help us to retrieve the position of points in the original tree.

Rotation operations. To support rotation operations, if we want to rotate node $v$ in the original tree and all its descendents, then we follow the path  (in the index tree) from $v$ to the root of the index tree.  By construction, there are only $\lg n$ such nodes to visit.  We'll need to update the label on each of these nodes in the index tree.  That is easy.  In particular, the label $T_w$ on each node $w$ in the index tree can be computed from the labels $T_{w_1},T_{w_2}$ on its two children $w_1,w_2$ as $T_w = T_{w_2} \circ T_{w_1}$.  So, to handle a rotation operation on node $v$ in the original tree, we update the the label on $v$ in the index tree, then follow the path (in the index tree) from $v$ to the root of the index tree and recompute the label of each such node in the index tree.  All of this can be done in $O(\log n)$ time.

Retrieval operations. If we want to retrieve the location of the point associated with node $v$ in the original tree, we can do that in $O(\log n)$ time, too.  Consider the path in the original tree from its root to $v$.  This is a subpath of the original tree.  It turns out that it can be expressed as the disjoint union of $O(\lg n)$ subpaths, where each subpath corresponds to a node in the index tree.  Let $w_1,\dots,w_k$ be those nodes in the index tree.  Then the transformation that needs to be applied is $T_{w_k} \circ \cdots T_{w_1}$; we apply this to the original location of $v$, and output that.  This can all be done in $O(\log n)$ time.

So this handles the case of a path, i.e., a tree of depth $n$.  This shows that it is possible to handle imbalanced trees.  But how do we handle the general case?  I'll show that next.

General case: an arbitrary tree

To handle an arbitrary tree, we will first build a heavy-light decomposition of the tree.  This expresses the edges of the tree as a union of (disjoint) heavy paths, plus some light edges; with the property that any path from the root to some leaf visits at most $O(\log n)$ light edges.  We'll treat each individual heavy path as a case of the warmup above, i.e., we'll build one index tree per heavy path, to keep track of the transformations associated with the nodes in the heavy path.  Also, we'll have a path tree that stores the light edges, and we'll store the transformation associated with the head of a light edge in that node of the path tree.

Rotation operations. To handle a rotation operation, we update the associated node in the path tree (if it is the head of a light edge) or do the appropriate update operation on the corresponding index tree (if it is the head of a heavy edge).  This can be takes $O(\log n)$ time at worst.

Retrieval operations. To retrieve the location of a node $v$ in the original tree, we follow the path in the path tree from the root to $v$.  This will involve traversing at most $O(\log n)$ light edges.  It also traverses at most $O(\log n)$ heavy paths.  In each heavy path, we might potentially traverse many vertices of the heavy path (possibly much more than $O(\log n)$ of them), but we don't need to visit all of them; since that is a consecutive subpath of the heavy path, we can quickly retrieve the transformation associated with that subpath (i.e., the composition of the transformations of the nodes in that heavy path) using the index tree for that subpath.  This takes $O(\log n)$ time per heavy path, and there are at most $O(\log n)$ heavy paths to visit.  Finally, we compose all of these transformations and apply it to the original location of $v$.

Naively, the running time seems to be $O(\log n)$ time for the light edges, plus $O(\log n) \times O(\log n)$ time for the heavy paths, for a total of $O(\log^2 n)$ time.

This achieves all of your goals, and gives a guaranteed worst-case running time of $O(\log n)$ for the rotate operation and $O(\log^2 n)$ time for the lookup operation, no matter what shape the original tree has.


Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time?

I believe that this would qualify as pseudo-polynomial time.
See http://en.wikipedia.org/wiki/Pseudo-polynomial_time.

The idea is that, usually we represent the time complexity as a function of the length of the string (bit) representation of the input. So your algorithm runs in polynomial time, given a fixed (or at least bounded) value for $W$.

To follow your algorithm, if you perform $O(|w|) $ operations for each edge, you perform $O(2^{b})$ operations where $b$ is the length of the binary-representation of the weight. This means that overall, the algorithm runs in $O(|E|2^{b_{max}})$, where $b_{max}$ is the length of the largest edge weight.

In summary, if you fix an upper bound on the edge weights, $b_{max}$ becomes a constant and the algorithm runs in linear time, but if you allow edge weights to be unbounded, the algorithm is exponential.

This is a common pattern we see when dealing with numerical inputs. The Knapsack problem, as well as factoring the product of two primes, face the same issue.


Because $n + (n-1) + (n-2) + \cdots + 2 + 1 = \frac{n(n+1)}{2} \in \mathcal{O}(n^2)$.

Note that $n^2$ is polynomial, not exponential (that would be $2^n$ for example).


Trying to understand a token file for lexical analysis

* means that any number (including zero) of preceding expression can occur

+ means that at least one instance of preceding expression must occur


Consider Post correspondence problem (PCP). If $\alpha_1 \dots \alpha_n$ and $\beta_1 \dots \beta_n$ are the words of PCP, then $S \to \alpha_iS\beta_i^r$ and $S \to \#$ where $\#$ is a symbol not in any of $\alpha_i, \beta_i$ and $s^r$ is the string $s$ reversed, gives a grammar $G$ such that if $G$ generates a palindrome, then the corresponding instance of PCP has a solution. PCP is RE though.


What is the significance of primitive recursive functions?

The halting problem is undecidable, but one might object that for most programs, it is easy to check whether they halt or not, by looking for any obvious infinite loops. Conversely, if you wanted to ensure that your program always terminates, you could do so by bounding a priori the number of loop iterations for every loop. For example, consider the pseudocode for repeated squaring:

def power(x, y, p):
   "compute x^y mod p"
   assert y >= 0
   result = 1
   while y > 0:
     if x is odd: result = result * x (mod p)
     y = y div 2
     x = x * x
   return result

How do we know that this procedure always terminates? One way would be to a priori bound the loop:

def power(x, y, p):
   "compute x^y mod p"
   assert y >= 0
   bound = y
   result = 1
   loop bound times:
     if x is odd: result = result * x (mod p)
     y = y div 2
     x = x * x
     if y == 0: break
   return result

Now it's clear that this program terminates, and if we haven't made a mistake elsewhere, the two programs would produce the same output.

  Primitive recursive functions are those computed by programs in which all loops are bounded and there is no recursion.

While we do not allow recursion (since it is not bounded), we can simulate it with a loop. We can ask several questions now:

Is every computable function presentable in this form?
If not, what is the relation between this class and all computable functions?

To answer 1, one can show that certain computable functions which grow "too fast" are not primitive recursive, for example the Ackermann function. Conversely, every function whose growth rate is "reasonable" is primitive recursive. And every computable function can be stated in the form $f(x) = \psi(\min_y \phi(x,y))$ for primitive recursive $\phi,\psi$, where we think of $\phi$ as a predicate.


First of all, let's consider that we are talking about labeled trees. Otherwise it will be difficult to find bijection between trees and binary strings.

Then we can traverse a given tree in-order (https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)) and print $1$ each time, when we enter some vertex, and $0$ each time, when we leave some vertex.

Another possible encoding can be constructed in the following way. Let's enumerate all vertices by layers from root to bottom (and from left to right inside each layer). And then let's construct binary string of length $|V|$ where the $i$-th position is $1$ if the corresponding vertex has children and $0$ otherwise.


I don't understand the case 4 of red-black tree deletion

but both case {3,4} will not change the pointer , anyway so how case 4 work?

Let us check case 4. Although the parent pointer of node $x$ is not changed, i.e., the parent node of $x$ is still $B$, the color of $B$ is set to black and node $D$ is lifted to become $B$'s parent with $B$'s original color.

So, going from the graph on the left hand side of case 4 on the image in the question to the graph on the right hand side, we have added that "extra" black node that was supposed to attached to $x$, which is, in your words, an extra black node $B$ is passed for the paths going through $\alpha,\beta$.

Furthermore, for that graph on the right hand side, we can check that all simple paths from the node to descendant leaves that do not pass through $A$ contain the same number of black nodes as before. Since all properties of black-red tree have been restored, case 4 ends the while loop, which ends RB-DELETE-FIXUP$(T, x)$, which ends RB-DELETE$(T, z)$.


From a theoretical perspective, you can diagonalise (well, decompose to Jordan normal form) to do the matrix power. It costs $O(M(c_1+\dots+c_k))$ to decompose, $O(\log n \cdot (c_1+\dots+c_k))$ to raise the diagonal matrix to the $n$th power, and $O(M(c_1+\dots+c_k))$ to finish up.


Floor or Ceiling when getting results for N after doing Big O and Big Theta?

The reason we take floor or ceiling at all in this context is that the definition asks for an integer $N_0$. Now the definitions of big $O$ and big $\Theta$ are both of the form

  There exists a real constant $C > 0$ and an integer constant $N_0$ such that for all $n \geq N_0$, the following holds: ...

Let us denote what should hold by $P(n)$. If you have shown that $P(n)$ holds for all $n \geq N_0$, then it follows that it holds for all $n \geq \lceil N_0 \rceil$ as well, since if $n \geq \lceil N_0 \rceil$ then also $n \geq N_0$. It doesn't necessarily follow that $P(n)$ holds for all $n \geq \lfloor N_0 \rfloor$, since if $N_0$ is not an integer, $\lfloor N_0 \rfloor \not \geq N_0$.


Big-O when iterations do not correlate with input

The time complexity of doSomething is $O(\max(n,m))$, where $n$ is the length of the input, and $m$ is the maximum number in the input. The letter $m$ is not standard – you can use a different one if you prefer.


Relation of Space and Time in Complexity?

That's rather a lot of questions for one Stack Exchange post.  One or two closely related questions per post is best. But here goes...

  1.) Are PSPACE and NPSPACE the set of all problems that require at least polynomial space to be solved on Deterministic and Non-deterministic Turing machines respectively?

No. They're the set of all problems that require at most polynomial space to be solved on deterministic and nondeterministic Turing machines, respectively.

  2.) If so, is the actual size of the polynomial space required dependent on the size of the input?

No. For any given machine, the polynomial is fixed. The input to the polynomial is the length of the input.  (E.g., if the machine runs in space $3n^2+4$ and the input has length 3, the Turing machine will need at most 31 cells of storage on its work tape.)

  3.) For P and NP, they are each the sets of problems that require at least polynomial time to be solved on DTMs and NTMs respectively correct?

Again, at most.

  4.) Is the reason that the shortest accepting computation of a DTM simulating a target NTM is exponential with respect to the shortest accepting computation of an NTM due to the exponential explosion of the number of configurations that an NTM supports as input grows for a given problem?

We don't know for sure that there's any loss of efficiency at all when simulating a nondeterministic machine on a deterministic one. But the reason we don't know how to do it with better than exponential slowdown is, as you suggest, that we don't know any better technique than trying all the possible nondeterministic choices, one by one.

  5.) My last and overarching question is: Are the differences in the set of problems that can be solved in polynomial time on DTMs versus NTMs related to time/space tradeoffs where DTMs can't run some polynomial NTM algorithms in polynomial time because they don't have the same "space" that an NTM has available to it?

Not really. It's because the nondeterministic machine in a sense computes lots of options in parallel and it accepts if any of those parallel options accepts. As I said above, the only way we know how to simulate all of these parallel computations is to do them sequentially, one after another. But there isn't any particular time/space trade-off: if a nondeterministic machine makes some computation in time $t(n)$ and space $s(n)$, a deterministic machine can do the same computation in time $2^O(t(n))$ and space $s(n)+O(t(n))$. The exponential blow-up in time is because a $q$-state nondeterministic machine might make up to $q$ nondeterministic choices (i.e., spawn up to $q$ "parallel threads") at each step of its execution; the smaller increase in space is because of the book-keeping required to keep track of which choices we tried at each step.


Any very user friendly resources on the Baum-Welch algorithm?

A simple web search leads to a whole lecture by Christopher Lee. I did not watch it entirely, but it seems to be a slow, thorough take on the algorithm with an example walk-through on paper similar to the video you link (if longer).


Purely randomness is not possible but in real-world the most randomness that a neural network can process is enough to discover an approximation pattern; the precision depends on the model of the context (exactitude of the Digital Twins) and processing power.

To extract the exact pattern from the pure randomness (I think) is impossible even with a quantum computer and even having all the time and resources of the universe. The reason is that nothing in the universe happens randomly, every effect has a cause. So regarding to the third case (theoretically) if you can reproduce every cause of a "twin universe" you can predict the future.


How to get a heatmap of pixel influences from a Convolutional Neural Network

Yes, there are various proposals out there.  Many of them work by computing a saliency map.  If you search for "saliency map", you should be able to find multiple schemes for that.
Personal opinion: these methods give heatmaps that seem superficially plausible; but my sense is that they have major limitations.  So don't set your expectations too high, or you may be disappointed.


Minimum pumping length of concatenation of two languages

For a language $L$, denote $P(L)$ as the minimum pumping length of $L$. It is implied that $P(L)\ge1$.

Proposition. Let $A,B$ be two languages with finite minimum pumping lengths. We have $P(AB)\le P(A)+P(B)-1$. Moreover, there exist regular $A,B$ such that the equality holds.

Proof. Let $w=w_Aw_b\in AB$, where $w_A\in A, w_B\in B$. Assume $|w|\ge P(A)+P(B)-1$. Then either $|w_A|\ge P(A)$ or $|w_B|\ge P(B)$; otherwise, $$|w|=|w_A|+|w_B|\le P(A)-1 + P(B)-1\lt P(A)+P(B)-1,$$
which contradicts the assumption.

Now there are two cases.

$|w_A|\ge P(A)$. Since $P(A)$ is a pumping length for $A$, $w_a\in A$ can be written as $w_a=xyz$, satisfying the following conditions:

$|y|\geq 1$
$|xy|\leq P(A)$
$\forall n\geq 0, xy^{n}z\in A$

Hence, $w$ can be written as $w=xyz_B$, where $z_B=zw_B$, satisfying the following conditions:

$|y|\geq 1$
$|xy|\leq P(A) + P(B)-1$ (since $P(B)\ge1$)
$\forall n\geq 0, xy^{n}z_B=(xy^nz)w_B\in AB$.

That is, $w$ can be pumped with pumping length $P(A)+P(B)-1$.
$|w_B|\ge P(B)$. This case is similar to the case above.

Combining the two cases, we have proved $P(A)+P(B)-1$ is a pumping length for $AB$.

Let $A=\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{n-1}, \beta^n, \beta^{2n}, \beta^{3n}, \cdots, \}$, which is a regular language of minimal pumping length $n$.  Let $B=\{\epsilon,\alpha, \alpha^2, \cdots, \alpha^{m-1}, \beta^m, \beta^{2m}, \beta^{3m}, \cdots\}$, which is a regular language of minimal pumping length $m$. Since $\alpha^{n-1}\alpha^{m-1}$, which is a word in $AB$ of length $n+m-2$, cannot be pumped, $AB$ is a regular language of minimal pumping length $n+m-1$.


An algorithm is parallel if there are several processes (tasks, threads, processors) working on it at the same time. Often the tasks run in the same address space, and can communicate/reference results by others freely (low cost).

An algorithm is distributed if it is parallel and the tasks run on separate machines (separate address spaces), one task has no direct access to the work of the others. It has to request needed data, or just wait until it is sent to it.

Yes, it is a fuzzy distinction.


Is it possible to make partition of Quicksort run in O(lg n)?

No.  The partition operation must access every item in the list: if there is any item it does not look at, then you don't know which side of the partition it belongs on.  Consequently, the partition operation cannot run any faster than $O(n)$ time, where $n$ is the length of the list.


Yes. Using the convention that inputs and outputs are $\pm 1$, then the function is
$$
\frac{a(x+y)+b(x-y)}{2}.
$$
You could have found this function using exhaustive search – there are only $2^{16}$ functions on $4$ variables.


Can someone interpret what this is asking for

Guess anything at all for the cube root of $a$: call that value $t$. $t′=\tfrac13(a/t^2+2t)$ is closer to $\sqrt[3]{a}$ than $t$ is, so use $t′$ as your next guess. Keep going.


Tibor Jager and Jörg Schwenk show in The Generic Hardness of Subset Membership Problems under the Factoring Assumption that factoring reduces to distinguishing quadratic residues from numbers with Jacobi symbol 1, for generic ring algorithms. These are algorithms whose only "API" to integers are ring operations (addition, multiplication, subtraction, division), equality comparisons and generating a random element. They also show that the Jacobi symbol, which can be efficiently computed in polynomial time, has no efficient generic ring algorithm. So their result doesn't answer your question, other than implying that the answer isn't known.


Virtual Memory - Non-contiguous Memory Allocation

Your professor asked you a tricky question. The answer is - by definition.

The virtual memory is a mechanism to map non-contiguous physical memory to contiguous logical memory (for each running process). Why does the free physical memory become non-contiguous? Well, processes start and stop in unpredictable order, so the memory of stopped processes ought to be reused.


Linear programming, Checking a constraint based on condition

If $X$ and $Y$ are zero-or-one (binary) integer variables, then this is encoded as

$$X \ge Y.$$

Why does this work?  If $Y=1$, then this enforces the constraint $X \ge Y$, as you wanted.  If $Y=0$, this enforces the constraint $X \ge 0$, i.e., it doesn't impose any rstrictions on $X$, which is also as you wanted.

In general, conditional constraints can be handled using the techniques found on page 7 of AIMMS Modeling Guide - Integer Programming Tricks, which is a helpful tutorial on how to encode constraints in integer programming.  Thanks to @adrianN for pointing to that resource.

You can also take a look at https://cs.stackexchange.com/a/12118/755 and at Formulating Integer Linear Programs: A Rogues' Gallery for other techniques and practice problems.


This problem is NP-hard.

Assume every vertex is a splitter that can split to any number of degrees, then your problem is precisely the Steiner tree problem on a graph, where the set of source and sink vertices are the required vertices.