Is there a formalization of a general version of the sweep line algorithm? If not is it easy to derive?

Perhaps this is too broad a question for a coherent answer, so let me first try to say something about line segment intersection, at least. The main reason the sweep-line algorithm is efficient is that we only have to worry about neighboring line segments. We can generalize this procedure to $\mathbb{R}^n$ by noting that if we sweep a line over a sub-plane of $\mathbb{R}^n$ (i.e. the projections of all segments from $\mathbb{R}^n$ on this plane), any intersecting segments in $\mathbb{R}^n$ cannot be 'separated' on this line by a segment that intersects neither of them (If such a segment exists, the segments would be separated by the $n-1$-dimensional hyper-plane orthogonal to the projected plane). So, we can in fact apply the $2D$ algorithm on some plane projection, with the only difference being that we test individual intersections in $\mathbb{R}^n$. (some non-general position edge-cases might get even nastier, but I think the general procedure still applies)

Now, for the sweep line paradigm in general:

I think the main algorithmic idea is that if we want to answer questions about objects in $\mathbb{R}^n$ that concern only their 'neighbor' objects (line segment intersection is the most clear, but Voronoi diagrams and even triangulation fit this description to a certain extent), it is efficient to only query for 'local' objects. To achieve this, sorting seems like a good idea. However, there is no clear method to sort points in $\mathbb{R}^n$ in an useful way, for $n>1$ (I will explain why later*), while sorting in $\mathbb R$ can be efficiently maintained, using binary search trees.

So, the sweep line algorithm attempts to solve this problem by sorting on the order in one direction, on the sweep line. The main thing that the algorithm has to do is to 'make up' for this simplification by traversing the space in a structured matter. Therefore, it makes little sense to use an $n-1$-dimensional hyper-plane to sweep the space with, as we cannot sort the projections on this plane.

Another idea is that the sweep line paradigm allows the algorithm to 'ignore' already visited points. While this is intuitive, I don't think that this idea is the key to efficiency. This idea leads to replacing $n^2$ by $\sum_{i=0}^n i$, so it gives no asymptotic improvements.

So, I think that we have an answer to your statement:

  I believe it could be formalized recursively (like sweeping hyper planes from dimension $n−1$
  downto $2$. But I need to be sure.

The sweep line paradigm uses a line**, even in $\mathbb{R}^n$.

*: Why can't we just use a lexicographical sort on a 2D-plane and call it a day? Recall why we sort: we want to find 'neighbors' of the objects since we don't need to compare non-neigbors. In $\mathbb{R}^n$, point $p$ being a neighbor of some point $q$ usually means that the (Euclidean) distance between them (in some direction) is minimal, i.e. there is no closer point $r$ 'in between them'. So, our order must be 'distance preserving'. This property is not satisfied by a lexicographical sort.

For example, draw a 4x4 grid of dots, choose to sort by row major or column major order, give them a number to indicate their rank and observe that some neighboring dots differ by 5, more than all other points in the same row/column! We can show that there is no (total) ordering on $\mathbb{R}^n$ that preserves 'neighbors' of points.

However, we must first make this more precise. Observe that an ordering of $\mathbb{R}^n$ is actually a function to some subset of $\mathbb{R}$! (You can also consider it a space-filling curve, the idea is similar) That is, given a total ordering on $\mathbb{R}^n$, there is a function $F : \mathbb{R}^n \rightarrow \mathbb R$ that completely characterizes it (I could make this more precise, but I feel that that's for another question). For a function $F$ (or functional, in this case) to be 'distance preserving', it means that there exists some $c\in \mathbb R$ such that $\|Fx\| = c\|x\|$ for all $x\in \mathbb{R}^n$. If $F$ is non-linear, it is not distance preserving (again, showing this is out of scope).

If $F$ is linear, our condition implies that it is an (linear scaling of an) orthogonal linear map (by definition, depending on your point of view), which means in particular that $F$ is of full rank. This means that $F$ cannot map from a subspace (the plane) to one of strictly lower dimension (a subset of $\mathbb R$). Therefore, there exists no distance preserving $F : \mathbb{R}^n \rightarrow \mathbb R$ and therefore no 'distance preserving' ordering of $\mathbb{R}^n$ for $n>1$ exists. Finally, this means (here I'm making an 'informal leap') that there is no 'neighbor preserving' ordering on planes and hyper-planes.

**The key part of the sweep line paradigm is the projection to a one-dimensional space to be able to use sorting, such as a line. This space does not have to be linear, however. Therefore, we can in some cases (line segment intersection is  not such a case) do something similar with not a line, but with a curve (In the setting when our objects are lines, this curve needs to always intersect each line exactly once, so we cannot use a space-filling curve). This is called a topological plane sweep. See the lecture notes by David M. Mount for more information.


Greedy Heuristics with an Altered Subset Sum/Partition Problem

Suppose that a set $S$ of size more than 2 can be partitioned into two subsets of identical sum. One of these subsets contains at least two elements. If you merge these two elements (that is, replace them with a new element whose value is the sum of the values of the two elements), then the partition property still holds; and furthermore, given a partition of the new set, you can construct a partition of the original set.

You can find two elements in the same part by considering any three elements – two of them will be in the same part and so can be merged. This gives an algorithm for your problem with $O(n)$ oracle calls, where $n$ is the number of elements in the original set.


Inplace sorting of variable length records

If we're just dealing with packed variable-length records, swapping two adjacent elements is not difficult, so bubble sort will work.

There are some techniques for creating space while sorting to use for auxiliary data structures, based on the fact that (partially) sorted data has less entropy than unsorted.  See Radix Sorting With No Extra Space by Franceschini, Muthukrishnan, and Patrascu for examples.  They don't deal with variable length records specifically, but some of the ideas there might be useful.


Bayes net: algorithm to calculate joint distribution?

You already have the result of the chain rule - this is your networks topology basically. Now you need to compute the joint. I would start from "root nodes", i.e. nodes with no parents, and proceed forward (I'm sure you can go the other way too, just more pain):

Each of the "root nodes" has its "own" joint already. I.e. if your network was just one root node, you're done - just output the CDF.
Now suppose your network is two "root nodes". What's the joint? Suppose you have two boolean variables A,B with values a,~a,b,~b. The joint is:

(a,b, P = a*b)

(a,~b, P = a*~b)

(~a, b, P = ~a*b)

(~a,~b, P = ~a*~b)
This looks like a cartesian product. I.e. you have a cartesian product in the variables, and the value is the product of terms. This is the simple version of a "factor product" - where factor is some unnormalized discrete distribution.
In general the product of two factors will encounter variables that are common to the factors. Do the cartesian product and throw out all tuples that match on the common variables - this is the join in databases. Compute the probability as before.
Now you have the factor product. Just use on your graph to compute the joint. Be careful with paths that separate and then join back in the graph.


It's part of the solution to the cryptopuzzle.  The goal is to find $x$ that makes $P$ satisfy the criterion; once you've found such an $x$, you can verify that it is a valid solution (and so can anyone else).


How do I find a regular expression for a particular language?

Occasionally you can just stare at the language, get insight, and write down a regular expression just like that.  However, more typically, we need a systematic procedure.  Fortunately, the field of formal languages provides a more systematic approach that will help you structure your approach to this problem.  Often, one effective approach is as follows:

Step 1. Find a non-deterministic finite-state automaton (NFA) for the language.

Step 2. Convert the NFA to a regular expression.

Step 3. Double-check whether your regular expression is correct.

In more detail, here is how you do each of those two steps:

Step 1. To find a NFA for your language, you can think of this as a programming problem, where you have to write a program that works in a very limited programming language where you are only allowed to have a fixed, finite amount of state.  Try to write a program that reads in a string one letter at a time and decides whether the input string belongs to the language or not, using only a fixed amount of memory (say, $c$ memory cells, where $c$ is some constant that does not depend on the input string, not even on the length of the input string).  This program then corresponds naturally to a NFA, where the NFA has one state per possible value of the program's memory.

Sometimes, it can also be helpful to use the closure properties of NFA.  For instance, if the language $L$ is specifies as $L = L_1 \cup L_2$, then it suffices to build a NFA for $L_1$ and a NFA for $L_2$; then the closure properties for regular languages allow you to derive a NFA for $L$.  For more techniques to build a NFA, take a look at our reference question How to prove a language is regular? for more approaches.

Step 2. To convert the NFA to a regular expression, apply the algorithm described in How to convert finite automata to regular expressions?.

Step 3. To check whether your regular expression seems to be correct, you can try testing it on a few example strings to see if it seems to give the correct answer.  Try both several examples that are in the language and several that are not.

This is just one approach.  There are other approaches, including writing down a regular grammar and converting it to a regular expression, or writing a system of linear expressions in regular languages and converting to a regular expression using Arden's Lemma, or others.  For an overview of those methods, take a look at How to prove a language is regular?, How to convert finite automata to regular expressions?, and Known algorithms to go from a DFA to a regular expression.

You can also look at other examples of this kind of problem on this site, e.g., by looking at questions tagged regular-expressions.


Why don't we scale the cost of memory access when analyzing runtime of algorithms?

You are totally right in your observation. If complexity analysis would be done on a Turing machine level the memory distance would be taken into account. You may use a 3 dimensional tape if you like and your analysis is on sub-polynomial level.

My Master thesis in 1990 was about the same topic. In that thesis I argued that instead of looking at the number of transistors/gates we should look at the length of the wires. Looking at it that way some seemingly smart ideas to reduce complexity break down. One example I used was Lupanov's method to represent an arbitrary function in a circuit taking $O(\frac{2^n}{n})$ gates. This is actually not much more efficient than a regular ROM when the average length of the wires is taken into account.

Things can get worse. If you consider a RAM machine where registers can be addressed from another register (pointers) and multiplication can be done in unit time, then it has been shown that PSPACE problems can be solved in polynomial time. I don't have a reference at hand, it was folklore at the time of my college years.

In answer to the question below. The crux of the method consists of (ab)using the fact that all registers are initially zero and the pointer arithmetic is used to leave the majority of registers at 0 and sparsely put a value in others. The registers now serve as a huge lookup table, without the burden of initializing the table.

On the wiki page for Pointer machine you will find a quote from Peter van Emde Boas:

  an interesting theoretical model, but ... its attractiveness as a fundamental model for complexity theory is questionable. Its time measure is based on uniform time in a context where this measure is known to underestimate the true time complexity. The same observation holds for the space measure for the machine (van Emde Boas (1990) p. 35)

The referred book of Van Leeuwen most likely describes the method to solve PSPACE problems on these machines in polynomial time. You may actually want to check, because it is quite some time ago for me and the machine might also need the parallelism of the PRAM model.


Time complexity of a recursive function which generates all combinations of an array

Denote by $T(n)$ the running time of your function on an input of length $n$, assuming that all operations are $O(1)$. Then $T(0) = O(1)$, and for $n > 0$,
$$
T(n) = O(n) + \sum_{m=0}^{n-1} T(m).
$$
Let us replace $O(n)$ with $Cn$. Then
$$
T(n) - T(n-1) = Cn + \sum_{m=0}^{n-1} T(m) - C(n-1) - \sum_{m=0}^{n-2} T(m) = C + T(n-1),
$$
and so $T(n) = 2T(n-1) + C$, implying that $T(n) + C = 2(T(n-1) + C)$. Therefore $T(n) = 2^n(T(0) + C) - C = O(2^n)$.


What would you think about a proof that says the following?

$NP \subset DTIME(2^n)$
let $m = \log n$, then $DTIME(2^n) = DTIME(m) \subset P$
Therefore $P = NP$

Here, you have indeed $DPSACE(log^2n)\subset PSPACE$ but the argument is weird.
Also please note that Savitch's theorem already proves that $NPSPACE \subset PSPACE$, and you have the result you want, since $NLOGSPACE \subset NPSPACE$.


The predicate transformer is just a formalization of the idea that you can produce a precondition given a program and its postcondition.

For example, given a program sqrt with the postcondition that sqrt(x) = y and y*y = x, what are some valid preconditions?

x > 10
x > 20
x > 1

Some invalid preconditions would be

x < 0
x > -10

One predicate P1 is weaker than another predicate P2 if P2 => P1, but it is not true that P1 => P2. For example, x > 1 is weaker than x > 10 because x > 10 implies x > 1 as well, but x > 1 does not imply x > 10; x == 3 would be a counterexample.

Given all possible preconditions for our square-root program, one must be the weakest of them all; we denote that with the function wp.S.Q (which you could also write in the more familiar notation wp(S, Q)). In this case, wp.S.Q = {x >=0 }. You can prove that if x satisfies any precondition P, then it must satisfy x >= 0, and that if it does not satisfy x >= 0, it cannot satisfy any other precondition P.

The idea of a weakest precondition is useful because it allows a program to work with as many values as possible. Using a precondition of x >= 20 isn't useful because it doesn't allow us to compute the square root of 4.

Note that just because wp.S.Q is defined, that doesn't mean we have to provide an algorithm to actually compute its value. Doing so would provide a constructive proof of its existence, but non-constructive proofs could be found as well.


Algorithm Question: Stacking bricks of different colours?

Let $n$ be the number of bricks and $c_i$ be the number of bricks of color $i$.
First notice that in a $w \times h$ grid we can fit at most $wh$ bricks.
Therefore, $\lceil \frac{n}{Y} \rceil$ is a lower bound on your height. The
minimum height $h$ to stack all your bricks without violating the constraint will be
$\max(\max_i(c_i), \lceil \frac{n}{Y} \rceil)$.

The idea is to go from left to right (column 1 to X) and keep pushing a brick of the same color on to the left most non-full stack. And by non-full I mean that the size of the stack is lower than our defined height $h$. No two colors will be in the same row and it is also obviously true, that we have enough room for all $n$ bricks.

A pseudo code is also provided:

color_count[i] = number of bricks of color i
height = max(max(color_count), ceil(n / Y))

current_column = 1
current_row = 1
current_color = 1
while current_color <= X
  while color_count[current_color] > 0
    put a brick at (current_row, current_column) with current_color
    color_count[current_color] -= 1
    if current_row == height
      current_column += 1
      current_row = 1
    else
      current_row += 1
  current_color += 1


How do you compute the Pareto Front of a set?

A multi-objective optimization problem can be formulated as

\begin{align}
    \min\limits_{\phi \in \Phi} & \quad [f_1(\phi), f_2(\phi), \ldots, f_m(\phi)]^T \label{eq:mo-objectives} \\
    s.t. & \quad g_j(\phi) \leqslant 0,~j = 1, \ldots, J \label{eq:mo-constraints}
\end{align}

Without loss of generality, assume that all objective functions are minimization functions. In this problem, the first equation represents the set of $m$ objective functions and the second denotes the problem constraints, which generate a polytope $\mathcal{P}$. Furthermore, $\Phi$ denotes the set of feasible solutions contained in $\mathcal{P}$ and $\phi \in \Phi$ represents a feasible solution.

A solution $\phi_1 \in \Phi$ dominates another solution $\phi_2 \in \Phi$ if and only if $f_i(\phi_1) \leqslant f_i(\phi_2)$ for all objective functions $\{f_1, f_2, \ldots, f_m\}$ and $f_i(\phi_1) < f_i(\phi_2)$ for at least one objective function $f_i$.

A solution $\phi' \in \Phi$ is said to be non-dominated if and only if there is no solution $\phi \in \Phi$ such that $\phi$ dominates $\phi'$.

A non-dominated solution $\phi^* \in \Phi$ is said to be Pareto-optimal if and only if, for all solutions $\phi \in \Phi$, $f_i(\phi^*) \leqslant f_i(\phi)$ for all objective functions $\{f_1, f_2, \ldots, f_m\}$ and $f_i(\phi^*) < f_i(\phi)$ for at least one objective function $f_i$.

The Pareto-front is the set of the Pareto-optimal solutions.

We can derive a simple algorithm to compute the Pareto-front of a given subset of solutions $\Phi' = \{\Phi'_1, \ldots, \Phi'_n\} \subseteq \Phi$. This algorithm will be specifically designed for your case (two objectives), but can easily be generalized to any number $m$ of objective functions.

First of all, assume that the solutions in $\Phi'$ are ordered in increasing order of the first objective (energy used). In addition, ensure that, for a given value of energy used, the solutions are also ordered in increasing order of their second objective (weight).

Let $i \gets 1$.
Add $\Phi'_i$ to the Pareto-front.
Find smallest $j>i$ such that $\operatorname{weight}(\Phi'_j) < \operatorname{weight}(\Phi'_i)$.
If no such $j$ exists, stop.  Otherwise let $i \gets j$ and go to step 2.


The phrase "the element being searched for is equally likely to be any element in the array" is ambiguous. It might mean two different things:

The element is at a uniformly random position in the array.
The element is chosen uniformly at random from the set of elements in the array.

This ambiguity suggests that the authors are making the hidden assumption that all elements are distinct, in which case both meanings coincide. Moreover, without this assumption it is impossible to determine the average-case complexity (consider what happens if all elements in the array are identical).


1) is easy. As you say the algorithm can perform at most $O(|E|)$ iterations. Initially $c(V_1, V_2)=0$. Each iteration, except the last, increases $c(V_1, V_2)$ by at least $1$. The claim follows since $c(V_1, V_2) \le |E|$.

2) Suppose that, for some $v \in V_1$, $|\alpha(v)| > |\beta(v)|$ Then moving $v$ from $V_1$ to $V_2$ increases the value of $c(V_1, V_2)$ by $|\alpha(v)|$ and decreases it by $|\beta(v)|$, therefore $c(V_1 \setminus \{v\}, V_2 \cup \{v \}) = c(V_1, V_2) + |\alpha(v)| - |\beta(v)| > c(V_1, V_2)$. This shows that  the algorithm could not have terminated. The case $v \in V_2$ is symmetric.


Selecting a random 'bad' element from an array of $n$ values in $O(n)$ time and $O(1)$ space without knowing how many bad elements or where they are

You can do better than $O(n)$ time: indeed $O(n/k)$ time and $O(1)$ space is achievable, with a perfectly uniform distribution on bad elements.  Let me explain how, by starting with a simple strategy and building up to a solution that meets all of your requirements.

If we didn't have to deal with the possibility that no bad element exists, then a simple (but sub-optimal) method is to apply rejection sampling: repeatedly pick a random element, test if it is bad, and if it is bad, return it.  In other words, you return the first bad element found.

If there is at least one bad element, this method is within a constant factor of optimal; the average running time is $O(n/k)$, and it uses only $O(1)$ space.

The big flaw with this simple approach is that if there are no bad elements, this algorithm runs forever.  Fortunately, we can repair that with a simple fix, and at the same time improve running time to optimal.

Here's how.  Pick a random permutation $\pi$ on $\{1,\dots,n\}$.  Then, sequentially test $A[\pi(1)]$, $A[\pi(2)]$, ..., and return the first bad element you find.  If you have tested all $n$ array elements and found no bad element, terminate and return -1.

This algorithm requires (on average) $\min(n/k,n)$ queries to the oracle, which is optimal -- you can't do better than that.  The space requirement, apart from the time to store $\pi$, is $O(1)$.  This also provides a perfectly uniform distribution on the set of bad points: because it is essentially a rejection sampling strategy, it is correct for the same reason that rejection sampling is.

At this point you might object that storing the permutation $\pi$ explicitly requires $O(n)$ space.  You would be correct, but fortunately there is a fix to that: you can construct a pseudorandom permutation on $\{1,\dots,n\}$ with $O(1)$ space to store it, and $O(1)$ time to evaluate the permutation.  See Lazily computing a random permutation of the positive integers and https://crypto.stackexchange.com/q/20035/351 and links there.  Technically speaking, the space and time to evaluate the oracle is probably more like $O(\log n)$ than $O(1)$, but given that $n\le 2^{64}$ in practice, the difference might or might not be critical.

Caveat: This is an engineering-oriented answer.  From a theoretical perspective, it's probably not fully satisfying.  The use of a pseudorandom permutation means that the distribution on bad instances is not perfectly uniformly random; it is close to random (indistinguishable from random).  Also, I haven't been fully-rigorous about the running time or space requirements for the pseudorandom permutation.  Finally, the use of pseudorandom permutations relies on unproven assumptions (that certain crypto primitives are security).  See the comments for more discussion of caveats.


Does an RL agent need to experience a complete episode in order to learn?

If the agent gets no feedback whatsoever and has no information about the structure of the search space (just blind search, hoping to get lucky), then no, it can't learn.  It has nothing to learn from.  In your scenario, it has no information to enable it to improve: the feedback is always the same -- always an unending stream of -1,-1,-1,-1,-1,... unless it happens to get lucky.  Without feedback, there's no basis for learning.


Create an algorithm for computing the shortest path in O(m + nlogn)

Many such problems can be solved by modifying the input instance rather than a known algorithm.  In your case you can consider your graph as directed and create a new directed graph $G'$ the is split into $2$ "layers", $A$, and $B$.

Layer $A$ contains a copy of all the vertices in $V$, layer $B$ contains a copy of all the vertices in $V \setminus X$. Given a vertex $v$ let $v_A$ be it's copy in $A$ (if any) and $v_B$ be its copy in $B$ (if any).

The edges of $G'$ are as follows:

For each edge $(u,v) \in E$ with $u,v \in V \setminus X$ add to $G'$ the edges $(u_A, v_A)$ and $(u_B, v_B)$ with the same weight as $(u,v)$.
For each edge $(u,v) \in E$ with $u \in V \setminus X$, and $v \in X$, add the edge $(u_A, v_A)$ with the same weight as $(u,v)$.
For each edge $(u,v) \in E$ with $u \in X$, and $v \in V \setminus X$, add the edge $(u_A, v_B)$ with the same weight as $(u,v)$.
Ignore all the edges $(u,v)$ with $u,v \in X$.
Finally, for each vertex $v \in V \setminus X$, add the edge $(v_A, v_B)$ with weight $0$.

Your problem now amounts to that of finding the shortest path between $s_A$ and $t_B$ in $G'$, which can be done in $O(m + n \log n)$ time using Dijkstra's algorithm.


Finding $t$, $r$ and $w$ in Cache - Direct Mapping

I think i found out the solution, may be helpful for others reading this.

The size of a block is 8 bytes. And the memory is adressed with 2 bytes. So each block contains 4 words (considering 1 adressible unit = 1 word).

4 = 2^2, Then $w$ = 2 bits

Since cache has a size of 64 bytes which is 2^6, than $r$ + $w$ must be 6.

$r$ + $w$ = 6, $w$ = 2 so $r$ = 6-2 = 4 bits

Lastly the MAR is 10 bits so the length of RA ($r$ + $w$ + $t$) must be 10.

$r$ + $w$ + $t$ = 10, $r$ + $w$ = 6, then $t$ = 10 - 6  = 4 bits .

So the RA distribution will be like:

+----------------------------------------+
| t = 4 |       r = 4      |    w = 2    |
+----------------------------------------+


Minimize number of DFS searches in a graph

Your problem has two clauses:

A) Given a set $V$ of houses, decide on the set of existing edges $\{(u,v)\}$ with a minimal amount of queries (=helicopter landings), when a single query $Q(v)$ reveals all the edges $(v,u)$.

B) Given a graph $G=(V,E)$, find a path that visits all vertices, that traverses at most $2n$ edges.

The connectivity problem A has a trivial solution of $O(n)$, which under the model you describe can be easily bounded below by an adversary argument, showing it is also optimal.

Consider the following adversary:

Choose arbitrary $v_k$ that was not queried before.
Given query $Q(v_i)$:

If $i$ has been asked before, answer accordingly
If $i$ is new and $i \neq k$ answer that $v_i$ is only connected to $v_k$
If $i$ is new and $i = k$ answer that $v_i$ is connected all previous vertices connected to $v_k$ through previous phase, and to a new vertex $v_j$. Set $v_k \leftarrow v_j$

It is clear any query connects at most $1$ vertex (beside the very first), so regardless of the order of queries an algorithm makes, it must make at least $n-1$ queries to reveal the set of edges, and the connectivity status of the graph.

It follows the naive algorithm of asking all vertices for neighboring edges is also optimal.

The traversal problem is simple; find a spanning tree of $G$ (denoted by $T$), after its been revealed by your helicopter. To visits all vertices, do an euler-tour on $T$. Since $T$ has $n-1$ (or less, if it's a spanning forest and $G$ is not connected) edges  and an euler tour visits each edge twice, you visits all vertices at the maximal cost of $2n-2$ edges.


Solving $T(n)=3T(\lfloor \frac{n}{3}\rfloor) +2n\log n$

Ignoring floors (see, e.g., the paragraph "Ignoring Floors and Ceilings Is Okay, Honest" in Chapter 1 of Algorithms for a discussion), your recurrence is of the form
$$
T(n) = aT(n/b) + f(n),
$$
with $a=b=3$ and $f(n) = 2 n \log n$.
You can then immediately apply the master theorem since, for $k=1$, $f(n) \in \Theta(n^{\log_b a} \log^k n) = \Theta(n \log n)$.
The solution to the recurrence is then:
$$
T(n) \in \Theta(n^{\log_b a}  \log^{k+1} n) = \Theta(n \log^2 n).
$$


Complexity of algorithm partitioning input into parts of size $n/100$ and $99n/100$

The simplest way to answer this question is using the Akra–Bazzi theorem, a vast generalization of the Master theorem. Using the Akra–Bazzi theorem, you can show that the solution of the recurrence $T(n) = T(\alpha n) + T((1-\alpha) n) + O(n)$ is $T(n) = \Theta(n\log n)$ for all constant $\alpha \in (0,1)$.
You can also use a recursion tree. This is a tree in which the root is $n$, and any node whose value is $m \geq n_0$ has two children labeled $\alpha m$ and $(1-\alpha) m$. The total cost of the algorithm is proportional to the sum of all values in the tree.
Suppose that $n$ is very large, and consider the first few levels of the tree:

The first level consists of the root, labeled $n$.
The second level consists of two nodes, labeled $\alpha n$ and $(1-\alpha) n$.
The third level consists of four nodes, labeled $\alpha^2 n$, $\alpha(1-\alpha) n$, $\alpha(1-\alpha) n$, and $(1-\alpha)^2 n$.

You can see that the labels in each level sum to $n$. At some point this will stop happening because the tree has leaves when the value drops below $n_0$, but the first $\min(\log_{1/\alpha} (n/n_0), \log_{1/(1-\alpha)} (n/n_0))$ are complete. In contrast, each level sums up to at most $n$, and there are at most $\max(\log_{1/\alpha} (n/n_0), \log_{1/(1-\alpha)} (n/n_0))$ levels. Putting the two together, we see that the complexity is $\Theta(n\log n)$.

With more effort we can find the dependence of the complexity on $\alpha$. For concreteness, let us assume that the recurrence is $T(n) = T(\alpha n) + T((1-\alpha) n) + n$, and consider $S(n) = T(n)/n\log n$, which satisfies the recurrence
$$
S(n) = \frac{\alpha n \log (\alpha n)}{n \log n} S(\alpha n) + \frac{(1-\alpha) n \log ((1-\alpha) n)}{n \log n} S((1-\alpha) n) + \frac{1}{\log n}.
$$
Suppose that $S(n) \longrightarrow C$. Substituting $S(n) = C$ in the recurrence, we obtain
\begin{align}
C &= \frac{\alpha n \log (\alpha n)}{n \log n} C + \frac{(1-\alpha) n \log ((1-\alpha) n)}{n \log n} C + \frac{1}{\log n} \\ &=
\alpha C + (1-\alpha) C + \frac{\alpha \log \alpha C + (1-\alpha) \log (1-\alpha) C + 1}{\log n} \\ &=
C + \frac{1 - h(\alpha) C}{\log n},
\end{align}
where $h(\alpha)$ is the entropy function. Thus, if $S(n) \longrightarrow C$ then $C = 1/h(\alpha)$, which is indeed minimized when $\alpha = 1/2$ and symmetric with respect to $\alpha$ and $1-\alpha$.
Here is another way to see where $h(\alpha)$ is coming from. Consider a random element from the original array. With probability $\alpha$, it belongs to the first half of size $\alpha n$, and with probability $(1-\alpha)$ it belongs to the second half of size $(1-\alpha) n$. In this way, we can trace what happens to the element until it reaches a subarray of size $n_0$ or less. The contribution of this element to the total complexity is the depth at which the terminal subarray is reached, so we are interested in the expected depth of this process.
Let $N_t$ be the size of the subarray at time $t$. Thus $N_0 = n$, and if $N_t \geq n_0$, then $N_{t+1} = \alpha N_t$ with probability $\alpha$, and $N_{t+1} = (1-\alpha) N_t$ with probability $(1-\alpha)$. It is easy to check that $\mathbb{E}[\log (N_t/N_{t+1}))] = h(\alpha)$. Since $\log(N_t/N_0) = \sum_{s=0}^{t-1} \log(N_{s-1}/N_s)$, linearity of expectation shows that $\mathbb{E}[\log (N_t/n_0)] = t h(\alpha)$ (assuming the the process continues forever, even after reaching size $n_0$), and so the expected time to hit a leaf is $\log(n/n_0)/h(\alpha)$.


How specifically do I need to describe (in words) the language of a regular expression?

The first language can be described as the set of words on the alphabet $\{a,b\}$ with an even number of $b$'s.

The second one is not the language of words on the alphabet $\{a,b,c\}$ with an equal number of $b$'s and $c$'s (this condition would define a non-regular language). You could use greybeard's description or say: the language contains the empty word, the last letter of the nonempty words of the language is a $c$ and if you delete the $a$'s, you are in $(bc)^*$.

It would be safe to provide a formal proof by computing the minimal automaton corresponding to each description.


Problem about getting a value of the hashed password

The problem asks to be creative about breaking hash attempt, well it is a big stretch even for simplistic example, but let's try.

You are given a password 12345 from user admin with 827ccb0eea8a hash, that is first 6-bytes of the hash.
A standard hashing function has been used - it means MD5. Why?

The construction of the task asks for preimage attack, it must be homemade breakable and possibly already hashed and shown online, otherwise it would not be possible to crack without substantial resources.
It cannot be salted, because the salt was not given in the task, but using salt is a wise thing to do - it prevents the rainbow tables attacks and in the case like here, you have a collection of hashes would be harder to recover in batches.
The MD5 is built-in into PHP and easily accessible in the most programming languages (MD5 implementations)

Try them until the match is found and then take the steps to hash your password.

Make the test of standard functions (like MD5, SHA256) of any combination of admin and 12345, it may be concatenated or xored, in fact it is not. First try out of lazy guess,
MD5(12345) =$\color{maroon}{\text{827ccb0eea8a}}\color{gray}{\text{706c4c34a16891f84e7b}}$
It tells that no salt or username was used, just plain password hashed with deprecated function. The other hashes are irrelevant at this point, but seeing the pattern, find simple MD5 of potential passwords until the first 6 bytes are like in the list.

After the scheme is known, the task is to produce the output from qwerty123, so MD5(qwerty123) =$\color{maroon}{\text{3fc0a7acf087}}\color{gray}{\text{f549ac2b266baf94b8b1}}$


Construct a computable function from non-computable funciton

There are many ways to do this, here is one example.

To make $h$ uncomputable, you can choose $f_1$ to be the constant $1$ function, and $f_2$ to be any non computable binary function, i.e. whose range is $\{0,1\}$. In that case $h=f_2$ is not computable. In fact, when $f_1,f_2$ are binary functions, $h$ is never computable (why?).

To make $h$ computable you can let $f_1$ be the constant $1$ function, and $f_2$ be any non computable function whose range is $\mathbb{N}\setminus\{1\}$. In that case $h$ is zero everywhere.


The statement is correct for exactly the reason you started with: $\mathsf P$ is a subset of $\mathsf{NP}$ which means that every problem in $\mathsf P$ is also in $\mathsf{NP}$. You can also go through the definitions and find that a deterministic TM running in polynomial time is merely a special kind of nondeterministic TM running in polynomial time and take it from there.
However, while being true, the statement "MST is in $\mathsf{NP}$" holds less value than the statement "MST is in $\mathsf P$" as complexity theory is, at large, concerned with lower bounds. A decent analogy in my opinion would be that the statement $\pi \geq 3$ is stronger than the statement $\pi \geq 0$ eventhough both are true.


What's wrong with this "proof" that $\mathbb{R}$ is enumerable?

"Do this ad infinitum and you will eventually describe $\mathbb{R}$."

The "ad infinitum" takes uncountably many steps to complete.


How can I find minimum number required to add to sequence such that their xor becomes zero

It seems to me that $a = a_i \oplus \dots \oplus a_n$ holds all necessary information: the $1$bits in $a$ are the bits you need to flip in (exactly) one of the $a_i$. As you are only allowed to add, you have to find one $a_i$ where the corresponding bit $j$ is $0$ and flip it -- this causes the same cost for all $a_i$, that is $2^j$, so the choice does not matter. Trouble begins if there is no such $a_i$.

That is why you have to do this iteratively and work from the least significant bit upwards. Proceed as above; if there is no suitable $a_i$, choose the $a_i$ with the maximum number of $1$ bits left of the current position -- this increases the chance of finding a suitable candidate in future iterations --, flip the bit and carry over, that is flip all ones to the left until you flip a zero to a one. Note that we still add $2^j$). As carry propagates only to the left, earlier choices are not invalidated. Recompute $a$ and continue with $j+1$; iterate until you have $a=0$.

Note that this is only a heuristic as far as I can tell: the choice of $i$ may be suboptimal if it causes many bits in $a$ to become non-zero. I am not sure if this can be avoided.


How would you construct a TM for $\{a^i b^j \mid i \le j\}$? Well, the easiest solution is to keep removing letters on both sides until you run out of $a$s or $b$s. At this point you can look at what you are left with and decide whether $i \le j$ was initially true.

Now, what if, instead of removing $a$s, you were moving them somewhere to keep for later use? This way you’d be able to test for $i \le j$ and still have all your $a$s available. By doing something similar with all those saved $a$s and the remaining $b$s you will be able to check the second condition, $j \le 2i$.


smallest circle that covers two points with its center in x axis

Don't solve it mathematically. Solve it by hand for a few cases first, and then have a go at making it mathematical. That way you will actually understand what you are doing.

The plane is divided up into points which are closer to $(a_1,b_1)$ than to $(a_2,b_2)$, points which are further away, and points which are equidistant. The $x$-axis is divided in the same way.

In the zone where points are closer to $(a_1,b_1)$, the radius of the circle (with a centre at such a point) is governed by the distance to the further point, $(a_2,b_2)$. So, in that part of the $x$-axis, you are trying to minimise the distance to $(a_2,b_2)$. That is a quadratic function of $x$ (or rather, its square is; but minimising the distance is the same as minimising the square).

In the zone where points are further from $(a_1,b_1)$, the radius of the circle is governed by the distance to $(a_1,b_1)$. So minimise that.

The zone (or, rather, the point on the $x$-axis) where the points are equidistant doesn't need special treatment because you can treat it as being a member of both the above zones at once.

So you already have an algorithm, more or less: find the minimum radius for the "closer to $(a_1,b_1)$" part of the $x$-axis, find the minimum radius for the "closer to $(a_2,b_2)$ part, and pick the minimum of the two minima.

But for real understanding, consider the possible geometries of the distance function in each of the two halves, and how the geometry of one half might relate to the geometry of the other half. Because nobody wants a solution to the question (it is known!) so the only benefit of doing the work is to gain understanding.


Making a CFG for a^i b^j c^k such that i+k < 3j

$$
\begin{align*}
S \to & AbBC \mid AbBCc \mid AbBCcc \; \mid \\
& aAbBC \mid aAbBCc  \mid aAbbBCcc  \; \mid \\
& aaAbBC \mid aaAbbBCc \mid aaAbbBCcc \\
B \to & bB \mid \epsilon \\
A \to & aaaAb \mid \epsilon \\
C \to & bCccc \mid \epsilon
\end{align*}
$$

The intuition is as follows:

The nonterminal $B$ encodes the fact that we can have any number (possibly 0) of extra occurrences of $b$s in addition to those strictly needed to satisfy $i+k < 3j$.

For every $3$ occurences of a $a$s or $c$s we have to "pay" by adding one $b$ to our word.
The nonterminal $A$ (resp. $C$) represents a triplet of $a$s (resp. $c$s) along with the occurrence of $b$ that is used to "pay" for the triplet.

Clearly, our word might have a number of $a$s (resp. $c$s) that is not a multiple of $3$, however there are only $9$ possible cases for the combinations of the remainders $i \bmod 3$ and $k \bmod 3$.
These cases are explicitly handled in productions from the axiom $S$, in which we make sure to add at least $\left\lceil 1+\frac{(i \bmod 3) + (k \bmod 3)}{3} \right\rceil$ additional "b"s to "pay" for the $(i \bmod 3) + (k \bmod 3)$ extra characters (the $+1$ ensures that the "greater than" in the inequality $i+k < 3j$ is satisfied).


What are the design issue with today's micro processor

There are inherent tradeoffs in targeting a given use. An implementation optimized for one workload, power budget, and cost (at a particular volume of sales) will necessarily be less than optimal for some other use.

Binary compatibility places another constraint on optimization. An ISA which is a good/easy compiler target and which is not strongly tied to a particular set of implementation techniques and technologies will be less than optimal for a given implementation technology (i.e., some optimizations are hindered by the abstraction presented in the ISA) and will sacrifice some benefits in performance, energy-efficiency, etc. for these other goals.

(Redesigning the ISA for every implementation is not a solution, even when using an intermediate-level software distribution format to provide compatibility. The cost and delay of ISA design (including developing an optimizing compiler for the software distribution format) constrains how extensively changes can be made to optimize for particular targets. Even microarchitectures are typically extensively reused because of development costs, including time to market and risk.)

Time to market also constrains optimization. High performance designs targeting new manufacturing processes begin work years before the process characteristics are defined. (This also applies to application targets. Algorithms and use patterns change.) There is also a limited amount of design effort that can be reasonably applied. Even if the value of optimizations could justify the development costs, worse but available products can establish market momentum.


Why create more faster processors despite of Processor Memory Bottleneck?

Creating faster processors with more cores makes sense because more speed and more cores is not the only change.

Big changes are:

Bigger caches. Ryzen Threadripper has up to 288MB of cache. My iPhone has more than 16 MB of cache. Your processor can do an awful lot of work without ever touching RAM.
More memory bandwidth. Data transfer has gone from 32 bit to 64 bit to 128 bit to 256 bit transfers in parallel and not stopping there.
Improved streaming. The time needed to move consecutive data is very much improved, so the right algorithms can process data at massive speed.
Changed algorithms. If I know that memory access speed has become the bottleneck, then I can change algorithms that were optimal with a processor of ten years ago to be optimal on today's processors.


A way to express LTL (varient) to enforce a stream of data to satisfy some linear time logic

This is an interesting question.
It is not directly an LTL (Linear Temporal Logic) question -- rather a question about whether there is an algorithm or tool that takes an input stream and modifies it a somewhat minimal way to satisfy a given LTL property.
Whether that you want can be done or has been done depends on what exactly the allowed modifications to the stream are. In your example, you are, in a sense, remixing two streams. Note that LTL is defined over alphabets in which every character can have multiple propositions that are TRUE at the time. So in your example, you could have just mixed the u and v stream together to obtain:
u,u,u,u,{u,v},{u,v},....

This would have satisfied the LTL formula as well. If the way in which you remix is that the proposition in the output stream is always a subset of the propositions set in the input stream, then you can use reactive synthesis to obtain a transducer that does the stream mixing/fixing. However, this will only work if for every output stream there actually is a way to perform the mix.
If there is some quantitative notion of mixing/fixing, then quantitative synthesis may be a research area that may have some results. But you would need a description of the precise stream modification optimization criterion to see if any of the results from that area are applicable.


To answer the question: No implementation of Haskell to my knowledge has ever represented datatypes as church encodings.

I believe that church-style encodings (or variants such as Scott encodings) work equally well for coinductive types.


Is There Any Shortest Path Algorithm That Finds The Shortest Path Between Only Two Nodes

Nope.  The best you can do is to use Dijkstra's or Bellman-Ford.  With Dijkstra's algorithm, you can stop the iteration as soon as you reach the target node, but this doesn't improve the worst-case asymptotic running time.


Not clear of your process, but here is how it can be done:
$\tfrac{9}{16} = \tfrac{1}{16} + \tfrac12$,
which gives you $0.1001$ in binary form. To normalize, take the first bit to be 1, which gives you $1.001 \times 2^{-1}$ which makes 3 bits for the mantissa $001$ and some bits for the exponent to represent $-1$ in twos' complement.

IEEE floating point formats don't use twos' complement for negative mantissas: they use an extra bit to indicate the sign (1 means negative).

So in the end, if exponent is 4 bit (and without any excess exponent): $1\,1111\,001$.


Density of regular language containing all squares

Suppose that the Myhill–Nerode relation of $L$ has the equivalence classes $C_1,\ldots,C_m$. Let $N_i(n) = |C_i \cap \{0,1\}^n|$. If $x,y \in C_i \cap \{0,1\}^n$ then $x^2,y^2 \in \mathbf{S} \subseteq L$, and so $xy,yx \in L$ since $C_i$ is an equivalence class. Therefore
$$
|L \cap \{0,1\}^{2n}| \geq \sum_{i=1}^m N_i(n)^2.
$$
Since the function $x^2$ is convex, the right-hand side is minimized (under the constraint $\sum_i N_i(n) = 2^n$) when all $N_i(n)$ are equal. Therefore
$$
|L \cap \{0,1\}^{2n}| \geq m (2^n/m)^2 = \frac{2^{2n}}{m}.
$$

The same argument works if we replace $\mathbf{S}$ with similar languages. Suppose for example that $L$ contains the language of all palindromes $\mathbf{P}$. If $x,y \in C_i \cap \{0,1\}^n$ then $yy^R \in \mathbf{P} \subseteq L$, and so $xy^R \in L$. Just as before, this shows that $|L \cap \{0,1\}^{2n}| \geq 2^{2n}/m$.

Furthermore, for each letter $\sigma \in \{0,1\}$, we have $y\sigma y^R \in L$, and so $x\sigma y^R \in L$. Therefore
$$
|L \cap \{0,1\}^{2n+1}| \geq \sum_{i=1}^m 2N_i(n)^2 \geq 2m(2^n/m)^2 = \frac{2^{2n+1}}{m}.
$$
In total, we get, for all $n$,
$$
|L \cap \{0,1\}^n| \geq \frac{2^n}{m}.
$$

Consider now the language $L_k$ of all words in which the first $k$ letters are the same as the last $k$ letters, reversed. This language has $m = \Theta(4^k)$ equivalence classes, contains all large enough palindromes, and has density $1/2^k = \Theta(1/\sqrt{m})$. This suggests the following vague question:

  What is the minimal density of a regular language having $m$ equivalence classes and containing all palindromes or all squares?


How does the Sutherland-Hodgman Algorithm work?

As written in book:

  Let edge $E$, determined by endpoints $A$ and $B$, be any edge of the positively oriented, convex clipping polygon.

It means, that first of all you need orient your red rectangle counter-clockwise:

  We clip edge of the polygon in turn against the edge E of the clipping polygon, forming a new polygon. ... The algorithm proceeds in stages by passing each clipped polygon to the next edge of the windows and clipping

I.e.:

Clip green polygon by $\overline{WX}$ (polygon will stay the same);
Clip polygon from step 1 by $\overline{XY}$ (still the same polygon);
Clip polygon from step 2 by $\overline{YZ}$ (yellow part will be cut off, and result of this step will be polygon $ABCKLE$);
Clip polygon from step 3 by $\overline{ZW}$ (blue part will be cut off, and result of this step will be polygon $ABCKLMN$);

Here we can answer on your (1) question - yes, $\overline{AB}$ will be tested against all edges of clipping windows. And answer for question (4): $\overline{DE}$ will not be in resulting polygon, but $\overline{LM}$ (everything that lefts from $\overline{DE}$) will belong to result.

To address question (2) - we need to have a look at this quote (definition when point is on the left side or on the right side):

  Let $A(x_1,y_1)$ and $B(x_2,y_2)$ be the endpoints of a directed line segment. A point $P(x, y)$ will be to the left of line segment if the expression $C=(x_2-x_1)(y-y_1)-(y_2-y_1)(x-x_1)$ is positive.

$\overline{WX}$ is directed line segment and points $A$ and $B$ is on the left side, then whole $\overline{AB}$ edge is to the left of the line segment (cliping edge) $\overline{WX}$.

Question (3): again due to edge of clipping windows is directed $\overline{BC}$ really on the left side of $\overline{XY}$, $\overline{ZW}$ (also it's to the left of $\overline{YZ}$ and $\overline{WX}$).

I think, the cause of the questions that you forget to orient clipping rectangle.


Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution

You should show that at each step, both algorithms select an edge with the same probability distribution. For example, the first edge that is contracted by Karger's algorithm is a uniformly random edge. Similarly, if you choose the weights at random, the first edge that is chosen in Kruskal's algorithm is a uniformly random edge.

What about the next edge? Karger's algorithm selects another uniformly random edge. After removing the first edge, the remaining edges are ordered completely at random. Hence the next edge chosen by Kruskal's algorithm is also uniformly at random.

From the third edge hence, some edge choices would be bad – will close a cycle. However, by design it doesn't happen in both algorithms, and otherwise the chosen edge is uniformly random.

This is the idea of the proof, and it remains to make it formal. That's your task.


How can a user process even try to access a memory location its not allowed to when it doesn't have access to page table?

Yes, this typically happens on modern operating systems such as Linux and Windows because they implement demand-paging. That is, whenever a process requests from the OS to allocate a chunk of memory, the OS by default only allocates virtual pages that are not actually mapped to physical pages. The OS satisfies the allocation request by simply modifying its internal data structures to remember that those virtual pages have been allocated and it's OK for the process to access them. This enables the OS to distinguish between virtual pages that have been allocated and those that have not. The OS does not update the corresponding page table entry and leave it invalid.

When an allocated virtual page is accessed for the first time, the CPU sees that the page table entry that describes that virtual page does not map to a physical page and so it will raise an exception known as a page fault. The OS handles the exception by allocating a physical page and updating the page table entry. Then it lets the CPU re-execute the instruction that attempted to access the page and caused the fault. When the instruction is executed again, it will be able to successfully access the page since it's now backed by physical main memory.

The alternative to demand-paging is anticipatory paging where the OS allocates a physical page and updates the page table immediately whenever it allocates a virtual page.


Searching for an item over a non-uniform query distribution

The Optimal Binary Search Tree is exactly what you need.

Welcome to the site!


Let $A$ be a randomized procedure which outputs $h_p$ with success probability larger than $1/2$.

Consider the following code, with input $x$:

Let $y$ be the machine corresponding to machine $x$ running on itself as input.
If $A(y) = 1$, go into an infinite loop, otherwise halt.

Denote this program by $B$.
What happens if we run $B$ on itself? Let us consider two cases. In both cases, let $y$ be the machine corresponding to $B$ running on itself.

Case 1: $B$ halts on $B$ with probability at least $1/2$. In this case, $h_p(y) = 1$, and so with probability more than $1/2$, $A(y) = 1$. Therefore $B$ goes into an infinite loop with probability more than $1/2$, contradiction.

Case 2: $B$ halts on $B$ with probability smaller than $1/2$. In this case, $h_p(y) = 0$, and so with probability more than $1/2$, $A(y) = 0$. Therefore $B$ halts with probability more than $1/2$, contradiction.

(This generalizes the usual proof of uncomputability of the halting problem via diagonalization.)


Fastest algorithm for finding the number of primes in a range

Using the Sieve of Eratosthenes this takes $O((M-N) + M^{1/2}) \log \log M)$. This will be the fastest unless M is quite large and / or N is quite close to M.

If you had a case like $M = 10^{100}$, $N = 10^{100} - 10^{10}$ you would likely start with a sieve to throw out all of the 10 billion candidates that have a small divisor, leaving you with say $10^9$ candidates. Then you'd use Fermat's primality test to find all probable primes. Then you'd either say "that's good enough", or you follow it by a deterministic primality test for the remaining 43.4 million or so probable primes.

If you do a deterministic primality test then you would run Fermat's test with fewer individual tests since you don't mind a few "probable primes" that are composite. If you don't do a deterministic primality test then you would run Fermat's test for a bit longer. In practice the question would be: What is the chance that there is a "probable prime" that is really composite, vs. what is the chance that a number is reported incorrectly as prime / non-prime because of a hardware problem.


Algorithm for queue with multiple repeated different interval events

Use an efficient implementation of priority queues, such as binary heaps. Then, your algorithm would look like this:

proc triggerEvents(events : Array[(String, Integer)]) {
  q = new MinHeap()
  for ( i=0; i<events.size; i++ ) {
    // use event index as key, interval as priority
    q.add(i, events[i][2])
  }

  while ( true ) {
    (i, p) = q.popMin()
    trigger(events[i][1])
    q.add(i, p + events[i][2])
  }
}

With $n$ the number of events, this will take time $\Theta(n \log n)$ for the initialisation¹ and then $O(\log n)$ time for each iteration of the while loop plus whatever trigger does.

In practice, be mindful of overflows.

You can not be asymoptotically faster than that; otherwise we could sort² in time $o(n \log n)$ which is not possible (for unrestricted inputs).

Can be sped up to $O(n)$; see e.g. here.
Add one event per element with its value as time interval. Drop the re-adding from the algorithm and execute $n$ iterations of the while-loop. Trigger just prints the element.


Partitioning a set based on binary predicate

There is no deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$.  One can prove this with an adversarial argument.

Consider running the algorithm on the following input:

Input #1: $F(x_i,x_i)=1$, and $F(x_i,x_j)=0$ if $i \ne j$.

Keep track of the sequence of pairs $(x_i,x_j)$ of objects that $F$ is evaluated on before it terminates.  If the running time of the algorithm is is $o(N^2)$, then for some sufficiently large $N$ the algorithm must make strictly fewer than $N^2-N$ queries to $F$, so there must be some pair of objects that it doesn't evaluate $F$ on, say $F(x_3,x_7)$.  But then consider running the algorithm on the following input:

Input #2: Same as input #1, except that $F(x_3,x_7)=1$.

Since the algorithm does not evaluate $F(x_3,x_7)$, the algorithm cannot distinguish these two inputs, and must produce the same output on Input #1 and Input #2.  However, the correct answer is different for these two inputs.  This means that the algorithm's output will be incorrect for at least one of these two inputs.

Therefore, any deterministic algorithm whose worst-case running time is asymptotically better than $O(N^2)$ is not correct on all inputs.


My question was answered by email after I posted it here.

The answer is that the priorities of the elements can't be chosen completely randomly when an element is inserted into the treap that represents the set. The priorities need to be given by a hash function. That way, the same elements are always associated with the same priorities and the union algorithm, which always picks the element with the highest priority, doesn't return a biased treap.


How can I analyze the time complexity of this Dynamic Time Warping algorithm implemented in MATLAB?

Look at the main double for loop that does all the work. It loops for m from 2 to M and then inside that for n from 2 to N. This is O(MN) like you expected.


Creating arrays of object of abstract class in statically-typed object-oriented languages

In statically-typed object oriented languages (like Java), you can not create an object of an abstract class.  Abstract classes are (usually) not completely defined, so creating such an object wouldn't make any sense.

What you can create is a reference to an object instance of an abstract class.  A reference is just a pointer to an object, not the object itself.

myclass1 arr[] = new myclass1[10];

Creates an array of 10 null references to objects of class myclass1.

Similarly

myclass1 x = null;

Creates a copy of the null reference and casts it to a reference to a myclass1.

You can always assign an object of a (non-abstract) subclass of myclass1 to a reference to myclass1.  So for example:

x = new ConcreteClass();

(where ConcreteClass is a subclass of myclass1).

Any element of arr is also a reference to myclass1.  So:

arr[7] = new ConcreteClass();


Why does the experience propagation rule for checkers work in Tom Mitchell's book?

Sutton's book on reinforcement learning explains it but probably in more detail than what you're looking for, so I'll try to explain it more briefly and clearly.

Start by thinking about the last position before the end of the game. The winning player can win in one move from that position, so that position is almost certainly good for that player and bad for the other player. Now Think about the second to last position: that's only one move away from the last position which we've just established is probably a good position for the player that won in the end. The same logic applies to the third-last, fourth-last, etc.

See also: Wikipedia's page on mathematical induction, which works in a similar way.


Why do we need to convert binary numbers into hexadecimal, octal and decimal?

You got it in one. Hex is easier for humans to read but also trivial to convert to and from binary. The computer itself only uses binary, in the sense that every wire is either on or off. But, at the same time, you can look at the pattern of ons and offs on four adjacent wires and call that a hex digit.


Worst-case input for median-of-medians with groups of size 3

Whether or not the median-of-medians algorithm with groups of size 3 runs in linear time is an open problem as said in [1] (while they proposed a variant running in linear time). I checked some follow-up papers and no one has a progress on showing the complexity of this algorithm. I believe it still remains open now.

[1] Chen, K., & Dumitrescu, A. (2015, August). Select with groups of 3 or 4. In Workshop on Algorithms and Data Structures (pp. 189-199). Springer, Cham.


Imagine we build the DFA from top to bottom to recognize palindromes of length $2k$. As usual, we'll use the states to "remember" the input seen so far. The DFA will consist of three parts:

The states needed to represent the $2^k$ possible choices for the first $k$ characters. This will be a complete binary tree of depth $k$ with $2^k$ leaves and so will need $2^{k+1}-1$ nodes in total.
The states needed to process the remaining $k$ inputs. This will consist of $k-1$ layers, each of which contains $2^k$ nodes for a total of $(k-1)2^k$ nodes. For example, suppose we had $k=3$ and after part (1) we were in state $q_{011}$, i.e., having seen input $\mathtt{011}$. Then on input $\mathtt{0}$ we would transition to the fail state, since $\mathtt{0110}$ could not be part of a 6-character palindrome. If, on the other hand, we saw $\mathtt{1}$ we would change to a state on the next level, since the current input $\mathtt{0111}$ could be part of a palindrome.
Finally, we add an accept state and a reject state, with the appropriate transitions from the accept state to the reject state on either 0 or 1 and similarly from the reject state to itself on a 0 or a 1.

We will have $2^{k+1}-1$ states in stage (1), $(k-1)2^k$ states in stage (2) and the two states in stage (3) for a total of $(2^{k+1}-1)+(k-1)2^k+2=(k+1)2^k+1$ states.

It's not hard to use a Myhill-Nerode argument to show that the states are pairwise distinguishable and so this DFA is minimal.


Test cases for graph embeddability problem

No finite set of test cases can prove correctness of an algorithm, if we have no information about the form or structure of the algorithm and if the set of possible inputs is infinite.

For any finite set of test cases you might have in mind, I can come up with an algorithm that works correctly on all of those test cases, but is incorrect (works incorrectly on another input, or on infinitely many inputs).  For instance, if your test cases are the inputs $t_1,\dots,t_k$, and the correct answers are $y_1,\dots,y_k$, then my algorithm can be:

Algorithm FooledYou(x):
1. If $x=t_i$ for some $i$, then output $y_i$.  Otherwise, output 42.

This algorithm has polynomial time and works correctly on those $k$ test cases, but is not a correct solution to the problem.

This is a fundamental limitation of using testing to check program correctness.  Testing cannot prove a program is correct; it can only prove the program is incorrect.

Now, suppose you want to test your program in practice.  Here is a heuristic that will likely be effective.  You link to a paper that shows that 1-embeddability is strongly NP-complete, by showing a polynomial-time reduction from 3SAT to 1-embeddability.  There are standard ways of generating hard instances of 3SAT.  So, use that polynomial-time reduction to convert them into (hard) instances of 1-embeddability, and test whether your algorithm gives a correct answer and solves the corresponding 3SAT problem.  Odds are, this will reveal a problem of some sort somewhere.

For instance, one standard way to generate hard 3SAT instances is by using the reduction from Factoring to 3SAT: generate a random 2048-bit RSA modulus (product of two 1024-bit primes), then ask what its factors are.  For more details, see Fast Reduction from RSA to SAT and Generating 3SAT circuit for Integer factorization example.


What's the highest 'order' data structure

Perhaps this is an interesting question with explicit answers, but you probably really have a problem with "exactly how to define this".

A list does not directly corresponds to a unique data structure, nor does a tree. A singly linked list corresponds to a (sufficiently unique) data structure, as does a binary tree. When you say multi graph, you probably want to refer to a quiver, i.e. a directed multigraph (edges with own identity). A binary or ternary quiver would again correspond to a (sufficiently unique) data structure.

However, any sufficiently canonical (and efficient) realization of a (n-ary) quiver as a data structure would probably not match well with the way datatypes are handled in "common" programming languages, where the size of an object with a certain datatype shouldn't depend on the actual content of that object. Therefore, this would be the point at which I would stop to look for a higher order data structure (than a quiver, looking for function like data structures and continuations certainly is useful). My reason for this is that I don't see the practical usefulness of a higher order data structure if it cannot be realized efficiently within "common" programming languages.


Turing reduction problem, intersection is equal to an empty set

Assume $L_c$ is decidable. We will reduce $A_{TM} =\{x\mid M_x \text{ halts on } x\}$ (the Halting problem language) to $L_c$. On input $x $ create a TM $M'$ which halts on only $x$. Then $L(M') = \{x\}$ and $M_x$ halts on $x$ iff $L(M_x) \cap L(M') = \{x\} \neq \emptyset$ iff $\left(\langle M_x \rangle, \langle M' \rangle \right) \notin L_c$. Thus, to check if $M_x$ halts on $x$ we check if $\left(\langle M_x \rangle, \langle M' \rangle \right) \notin L_c$.


Here is a hint. Given a word in $L_{a\gt b}$, if you remove $ab$ or $ba$ from it repeatedly until you cannot any more, what kind of word will you end up with?

Here is an almost complete answer.

   The language $L_{a\gt b}$ is similar to the language where the number of "a"s is equal to the number of "b"s, except there can be arbitrary number of extra "a"s at any position and there must be at least one extra "a" somewhere.

 Here is its context-free grammar:
 $\quad S \to TaT$
 $\quad T \to TT|bTa|aTb|aT|\epsilon$

 As a part of a proof that the above grammar generates $L_{a\gt b}$, let us show that $T$ stands for a word that has no less "a"s than "b"s. $T$ can only generate such kind of word, since whenever a "b" is included, an "a" is included. Now suppose $Z$ is such a word that is not empty. There are two cases.

 If $Z$ starts with a "b", let us walk through the symbols in $Z$ from its beginning, counting how many "a"s and how many "b"s along the way. So initially we have zero "a" and one "b". At some point of this walk, we will count an equal number of "a"s and "b"s since $Z$ has no less "a"s than "b"s. That means $Z=bXaY$ for some words $X$ and $Y$, where $bXa$ has the same number of "a"s and "b"s and where $Y$, the remaining part, must have no less "a"s than "b"s. Note that both $X$ and $Y$ are shorter than $Z$.

 The other case is when $Z$ starts with an "a", that is, $Z=aW$ for some word $W$. If $W$ has no less than "a"s than "b"s, we are in good condition since $W$ is shorter than $Z$. Otherwise, $W$ has (exactly one) less "a"s than "b"s. There are two subcases. If $W$ ends with a "b", then $Z=aUb$, where $U$ has no less "a"s than "b"s and $U$ is shorter than $Z$. Otherwise, $W$ ends with an "a". Now let us walking through symbols of $W$ from its end, counting the number of "a"s and the number of "b"s along the way. At some point of our walk, we will count an equal number of "a"s and "b"s. That means $W=UV$ for some word $V$ that has the same number of "a"s and "b"s. So $Z=aUV$, where $aU$ must have no less "a"s than "b"s. Note that both $U$ and $V$ are shorter than $Z$.

 The preceding two paragraphs shows that $Z$ must comes from two or one shorter word that also has no less "a"s than "b"s by the production rule of $T$.  Since $T$ can be replaced by the empty word $\epsilon$, we see that $T$ can generate all words that has no less "a"s than "b"s.

Exercise
Is the language $L_{a\gt b\gt c} = \{w\in \{a,b,c\}^* \vert \#_a(w)  > \#_b(w) > \#_c(w)\}$ context free?


Negligible functions in definitions of statistical closeness and computational indistinguishability

Statistical distance between $X_n$ and $Y_n$ can be defined as the maximum, over all functions $D$, of
$$ |P(D(X_n) = 1) - P(D(Y_n) = 1)|. $$

In particular, if the statistical distance between two sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ is negligible (eventually smaller than $1/p(n)$ for any polynomial $n$) then they are computationally indistinguishable.
The other direction is not true, and this is what drives all of cryptography.

I leave it an exercise to show that if two sequences distributions have zero statistical distance (i.e., they are copies of the same random variables) then they are computationally indistinguishable.


Suppose $L\in \mathsf{UP}$, and let $M(x,y)$ be a polynomial deterministic Turing machine such that:

$x\in L \Rightarrow \exists !y : M(x,y)$
$x\notin L\Rightarrow \forall y : \neg M(x,y)$

Consider the language $L'$ consisting of words in $L$ along with a prefix of a witness:

$L'=\left\{(x,w)\big|\exists w' : M(x,ww')\right\}$

Clearly $L'\in\mathsf{UP}$. Given an oracle for $L'$, one can find the witness for words in $L$ in polynomial time. If $\mathsf{UP\subseteq BPP}$, then $L'\in\mathsf{BPP}$, so you don't actually have an oracle for $L'$, but you have an oracle which is right with high probability.

Now, given $x$, execute the machine for finding a witness for $x$ with an $L'$ oracle, only that now you replace oracle calls with executions of the $\mathsf{BPP}$ machine (after some amplification, I leave the details for you). If the execution resulted in a valid witness $w$ for $x$, i.e. $M(x,w)$ outputs $1$, then output "yes", otherwise output "no". Clearly this solution can only be wrong for positive instances, which makes it a good candidate for an RP machine for $L$. I leave it to you to choose the right success probability to make everything work.

Essentially, the above solution uses the property of self reducibility, and in that sense the same proof as that for $SAT$, or any other self reducible problem in $\mathsf{NP}$.


Largest subset such that for every two elements one of them divides the other

You can do it in $O(N^2)$ like that:

First, sort your array $L$ in increasing order.

Then, for $i \in \{0,\ldots,N-1\}$, let $M[i]$ denote the cardinality of the largest valid subset $S$ such that $L[i]$ is the largest element of $S$.

We can compute $M[i]$ in a dynamic programming fashion:
$$ M[0] = 1$$
$$\forall i \;\; s.t.\;\; 0<i<N-1:
M[i] = 1 + \max_{0\leq j < i\\L[j]\ |\ L[i]}\{M[j]\}$$
(where the max is taken to be equal to $0$ if no $L[j]$ divides $L[i]$)

To see that, notice that it is clear that $M[i] \leq 1 + \max_{0\leq j < i\\L[j]\ |\ L[i]}\{M[j]\}$ as the second largest element in the corresponding subset must divide $L[i]$. Moreover, the fact that the second largest element $L[j]$ divides $L[i]$ and that the subset without $L[i]$ is valid is enough to guarantee that the subset with $L[i]$ is valid, as all elements in the subset are compatible between them and all divide $L[j]$ and thus divide $L[i]$. Thus the dynamic programming formulation is correct.

Then, the value you are looking for is simply the maximum over all $M[i]$'s.

This leads directly to a $O(N^2)$ algorithm as the sorting can be done in $O(N\log(N))$, and finding the maximum in $M$ is done in $O(N)$.


Find the set of all edges which there is a cycle such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$

Suppose $E_{i}$ be the set of all edges that have weight $i$. Now, we want to check if any of these edges are part of the solution or not. Note that, we can simply delete all the edges from the graph of the weight strictly greater than $i$ since they should not come in a cycle containing $e \in E_{i}$. Let $G_{i}$ be the new graph after deletion of these edges. Now, we just have to solve the following new problem:
Updated Problem: Find all the edges in $E_{i}$ that form a cycle in $G_{i}$
Try solving this new problem on your own. In case, you need any help, check this link for the solution to this problem in $O(|V|+|E|)$ time.
Since there are only $10$ such graphs $G_{i}$. The overall time would remain $O(|E|+|V|)$.


What is the number of expressions containing n pairs of matching brackets with nesting limit?

Okay. I think I may have figured it out myself. I invite everyone to check my answer to see if it makes sense. So the first bracket must be a left bracket and there must be some right bracket later on that corresponds to this first bracket. Inside these two brackets there is a valid bracket expression $A$ with depth at most $l-1$ and outside these two brackets there is another valid expression $B$ with depth at most $l$ (since it is not already contained in a pair of brackets like $A$). Also, just like the definition of Catalan numbers, if $n=0$ then the number of valid expressions is $1$. If $n\neq 0$ and $l=0$ then the number of valid expressions is $0$ (since if $n\neq 0$ then we must have at least one pair of brackets, but $l=0$ means that we cannot have more than $0$ open bracket at any time, meaning that there is no way we can construct any valid bracket expressions). So the recurrence relation I got is:
\begin{align}
C(i, j)= \begin{cases}
1 & i=0 \\
0 & i\neq 0, j=0 \\
\sum\limits_{k=0}^{i-1} C(k, j-1)\cdot C(i-k-1, j) & \text{otherwise.}
\end{cases}
\end{align}


If I understood well the problem:

$S = \{ (a_1, m-a_1), (a_2, m-a_2), ..., (a_n, m-a_n),\; m>2 $

$\sum_{a_i \in C} a_i > \sum_{a_i \in C} (m - a_i)$ and $\sum_{a_j \in D} a_j > \sum_{a_j \in D} (m - a_j)$ is equivalent to

$\sum_{a_i \in C} a_i > m * |C| - \sum_{a_i \in C} a_i$ and $\sum_{a_j \in D} a_j > m * |D| - \sum_{a_j \in D} a_j$  is equivalent to

$2 * \sum_{a_i \in C} a_i > m * |C|$ and $2 * \sum_{a_j \in D} a_j > m * |D|$  is equivalent to

$2 * \sum_{a_i \in C} a_i > m * |S| / 2$ and $2 * \sum_{a_j \in D} a_j > m * |S| / 2$  is equivalent to

$4 * \sum_{a_i \in C} a_i > m * |S|$ and $4 * \sum_{a_j \in D} a_j > m * |S|$

Then given an instance of the PARTITION problem $\Pi$, $S = \{ a_1, ..., a_n \}, \sum a_i = 2k$

Add two equal big integers $z >> k$ such that $z = t * (|S|+2) - k + 1$;
the equivalent partition problem $\Pi'$ is $S' = S \cup \{a_{n+1}=z, a_{n+2}=z\}$, $\sum = 2(k+z)$ i.e. the sum of the elements of the two equal partitions must be equal to $k+z$

Now you can set $m = 4*((k+z)-1)/|S'|$ which is an integer: $m  = 4 * ( k + t*|S'| - k + 1 - 1)/|S'| = 4 * (t - 1) * |S'|$ and your problem inequalities become:

$\sum_{a_i \in C} a_i > k+z-1$ and $\sum_{a_j \in D} a_j >  k + z - 1$

And it have a solution if and only if $\Pi'$ has a solution.


If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$

It follows immediately from the definition of a mapping reduction that a reduction $f$ from $A$ to $B$ is also a reduction from $\overline{A}$ to $\overline{B}$. Indeed, if $f$ is a reduction from $A$ to $B$, then, in particular, $x\in A$ iff $f(x)\in B$, which is equivalent to $x\notin A$ iff $f(x)\notin B$, which is equivalent to $x\in \overline{A}$ iff $f(x) \in \overline{B}$. (I only used the fact that $x \to y$ is equivalent to $\neg y \to \neg x$).

This follows form the reduction theorem: if $A \leq _m B$, then $B \in RE \to A\in RE$. Try to prove it. Hint: use a machine that computes the reduction, and a machine that recognizes $B$ in order to define a machine that recognizes $A$.

To deduce that $A \in R$, they've used the fact that $R \supseteq RE\cap coRE$ (In fact, equality holds). Hint:  If $M_{A}$ and $M_{\overline{A}}$ are machines that recognize $A$ and $\overline{A}$, respectively, then you know that for every word $w$, at least one of $M_{A}$ and $M_{\overline{A}}$ halts on $w$.


Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases

A partition of a graph into independent set is the same as graph coloring. Therefore we can reformulate your question as follows:

Can we bound the chromatic number of a graph in terms of its maximum degree?

If every vertex has at most $c$ different neighbors, then the chromatic number is at most $c+1$, and this can be achieved using a greedy approach: scan the vertices in an arbitrary order, and color each vertex in a color different from all its already colored neighbors (this will always succeed since there are $c+1$ possible colors and only $c$ potential already colored neighbors).
There are graphs with maximum degree $c$ which have chromatic number $c+1$, for example the clique $K_{c+1}$ on $c+1$ vertices, so this bound is tight.


In the loop, $i$ is repeatedly squared so it will take the values
$$
2, 2^2=4, 4^2=16, 16^2=258, \dotsc
$$
In other words, $i$ will be
$$
2^1, 2^2, 2^4, 2^8, \dots,2^{2^k}
$$
so the loop will iterate $k$ times, until $2^{2^k}\ge n$. Taking the log of this inequality twice we'll have $k\ge \log \log n$ for our running time.


Space complexity of a variant of st-connectivity

The usual proof that STCON is in NL works as follows: you guess a path from $u$ to $v$, and verify it step by step.
A very similar proof works for 2STCON: you guess two paths from $u$ to $v$, and verify them step by step. As you verify them, you also verify that they are different: either the length is different, or the $i$-th vertex is different, for some $i$.


Do regular languages belong to Space(1)?

A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the original NFA), but that is irrelevant. The amount of time this transformation takes is independent from the size of the input, and is thus $O(1)$.

Similarly, the size of this DFA is also independent from the size of the input, so storing it takes $O(1)$ space. No further space is needed other than the DFA, and thus a recognizer for a regular expression can run in $O(1)$ space.


Confused in calculating the shortest-path using Dijkstra's Algorithm

Assuming that you only want to know the distance from A to a certain point, your first calculations are right.
However A to H should be 37. Check that again.
Also, there are shorter paths from A to I and A to J. Just have a look again - the other values are correct.


What is wrong with this seeming contradiction with a paper about AND-compression of SAT?

The confusion arises from a misunderstanding of what being polynomial in the size of the largest instance means.  It does not mean that polynomial growth of the compressor's output is allowed as the number of instances ($t$) increases.  Rather it means the compressor's output is allowed to grow only as the maximum instance size grows, independent of $t$, and then only within a fixed polynomial of that value.

Your compressor concatenates the CNF instances, converts them to circuits, and then converts the circuits back to CNF.  Its output grows linearly with the number of instances ($t$) independent of the instance sizes and is therefore bound to exceed any polynomial function of the maximum instance size.  Because of this, indeed because it does not do any compression at all, your compressor does not cause any hierarchy collapse.

There also seems to be a misunderstanding as to what the AND-compressor function is supposed to do.  It does not have to output an instance that preserves all satisfying assignments for all the input instances, nor does there need to be a parsimonious counting reduction from the input instances to the output instance.  A conforming implementation could at the extreme output an empty instance if all the input instances are satisfiable and a single empty clause otherwise.

A more plausible AND-compressor might adapt standard data compression techniques such as the use of a dictionary.  A table of unsatisfiable subformulas could be precomputed and used to search against the input SAT instances.  A match would imply a forbidden variable assignment, which when instantiated as a learned clause might subsume (eliminate) several other clauses.

Another technique involves taking advantage the different sizes of the input instances.  If the input instances are of different sizes, the larger instances could be searched for subformulas equivalent to one of the smaller instances.  Such a match implies the existence of a variable assignment that could produce the subformula, and therefore the larger instance is satisfiable if the smaller instance is satisfiable.  If the smaller instance is unsatisfiable, the larger instance might still be satisfiable but it doesn't matter because compressor output should still produce an unsatisfiable formula.  So the output instance is effectively decoupled from the satisfiability of the larger instance and thus the larger instance no longer has to be represented in the output at all, eliminating a large number of clauses.

There are many other techniques.  The theorem in the paper suggests that efficiently achieving high levels of compression is unlikely given the implied partial collapse of the polynomial hierarchy.


Yes, and you can even use the Floyd–Warshall algorithm as a black box, together with a post-processing step to achieve this.
First, compute the shortest path between every pair of vertices using the Floyd–Warshall algorithm. Then, for each pair of vertices u and v and every special vertex w, compute the sum of the two shortest paths, the one from u to w and the one from w to v. The constrained shortest path from u to v is realized by the special vertex w that minimizes the sum of the u-w path's length and the w-v path's length.
Since the number of special vertices is obviously at most n, the computational complexity of the post-processing step is O(n^3). Because the computational complexity of the Floyd–Warshall algorithm is O(n^3) as well, the total computational complexity of this algorithm is O(n^3).
(credit to snakile)


Must a deadlock necessarily occur if the four conditions exist?

If you have a set of processes that wait for each other in a circular way, than you have a deadlock in this particular moment. This means that there is no situation where the four conditions are satisfied and there is no deadlock.

It may happen that a process stops waiting, for example due to some timeout mechanism realized by the developer. This breaks the circular wait relationship and the system continues to work.

The confusion often comes from the fact that conditions 1-3 are prerequisites for condition 4:

Without mutual exclusion in the resource access, there is no reason for the processes to wait on anything, so the circle is never created.
Without hold and wait, you have either only outgoing or only incoming connections for all the nodes (processes) in the dependency structure. Given that, you cannot form a circle.
With preemption in place, you can always break the circle by taking a resource your are waiting for away from another process. Given that, you never end up in a waiting circle.

This shows that conditions 1-3 are system design properties, while condition 4 is a run-time situation. There is programming language research that tries to ge rid of the three design conditions, so that condition 4 becomes impossible by default.


Determining time complexity of this function in python

Let $T(x)$ denote the running time of the algorithm. The following recurrence captures the running time of the algorithm:

  $T(x)=T(\frac{x}{2})+c,\ x\geq3,\ c \in O(1)$
  where $T(0) = T(1) = a \in O(1)$

Solving this we get, $T(n) \in O(log_2 x)$


Whether assigning of single precision IEEE754 float to double is reversible?

Maybe this will help. This is not full answer - just information to think.

  5.3 Floating-Point Format Conversions
  It shall be possible to convert floating-point numbers between all supported formats. If the conversion is to a narrower
  precision, the result shall be rounded as specified in Section 4. Conversion to a wider precision is exact.

IEEE Std 754-1985


Is summing over all possible $k$-combinations NP-hard?

You can compute the coefficient of $x^k$ in
$$ \prod_{i=1}^n (1+xa_i). $$
Alternatively, you can think of this as a dynamic programming algorithm. Let $b(m,\ell)$ be the sum of $\ell$-combinations of $a_1,\ldots,a_m$. We have
$$ b(m,\ell) = b(m-1,\ell) + a_m b(m-1,\ell-1), $$
where $b(m,-1) = 0$, $b(0,0) = 1$, and $b(0,\ell) = 0$ for $\ell \neq 0$. What you want is $b(n,k)$.

In both cases, there is an optimization that only keeps track of $\ell$-combinations for $\ell \leq k$. In the polynomial representation, it is enough to keep the monomials up to $x^k$. In the dynamic programming approach, we only compute the table up to $b(m,k)$.


Consider the textbook (from my undergrad years, many years ago):

Bazaraa, M. S.; Jarvis, J. J.; and Sherali, H. D. (1990). Linear Programming and Network Flows. 2nd Edition. New York: John Wiley.

Consider the recent edition of the textbook too.


Maximum flow with edge demands: can't understand the example of transition to transformed graph in the lecture notes

Those are just typos, as you can confirm by reading the general construction on the previous page ("Intuitively, we construct $G'$ by ...") and applying it to the flow network on the left.  Yes, there are multiple off-by-one errors.  It happens. Pobody's nerfect.

Incidentally, you might want to read the latest version of his notes, available from http://web.engr.illinois.edu/~jeffe/teaching/algorithms/, rather than the 2009 version you're reading right now (though this particular typo is still present).


Linear programming restricted to rational coefficients

In order to consider the computational complexity of linear programming, we need a way of encoding an instance of linear programming as a string. In particular, we need to fix an encoding of the coefficients, noting that arbitrary real coefficients cannot be encoded in a finite manner. The simplest and most canonical possibility is to ask for all coefficients to be integers or, equivalently, rational. In practice this encoding is usually good enough, so there is no reason to look any further. In principle, however, it is perfectly possible to consider more complicated coefficients. Indeed, any field which supports efficient linear algebra would do.

A feasible linear program always has a basic feasible solution, which is obtained by taking $n$ linearly independent inequalities (where $n$ is the number of variables), and replacing them with equations. The solution of this linear system will always be rational, and furthermore will be polynomially bounded.

Later on you might learn about semidefinite programs (SDPs). In the case of SDPs, we are no longer guaranteed that there exist an optimal solution over the rationals, but there is always an algebraic solution with bounded algebraic degree over the rationals. This fine point has recently been a cause for worry, see Ryan O'Donnell's SOS is not obviously automatizable, even approximately.


This is not a context-free language, as an immediate consequence of Parikh's theorem.

In terms of pushdown automata, there is no way for a PDA to keep track of the number of $b$'s in the string in a way it can access repeatedly while reading (or popping) the $a$ part of the string. This is an essential feature of context-free languages; it is the same reason why languages such as $\{a^n b^n c^n d^n | n > 0\}$ are not context-free.

For more examples, check out our reference question on proving languages are not context-free.


Here is a solution for two couples, $m_1,w_1$ and $m_2,w_2$. The edges are $(m_1,w_2),(w_1,w_2)$. The degrees are $1,1,0,2$ (in the order $m_1,w_1,m_2,w_2$).

Here is a solution for three couples, $m_1,w_1,m_2,w_2,m_3,w_3$. The edges are $(m_1,w_2),(w_1,w_2),(m_1,w_3),(w_1,w_3),(m_2,w_3),(w_2,w_3)$. The degrees are $2,2,1,3,0,4$.

Hopefully you can generalize this construction to an arbitrary number of couples. If not, you can always try running the Havel–Hakimi algorithm, trying to avoid connecting a husband to his wife.


How to prove equivalence relation in this case?

I will only prove reflexivity $A=A$. We proceed by induction on the structure of $A$.

If $A\equiv x$, then $x=x$ follows from rule 1.

If $A\equiv \lambda x. M$, then by induction hypothesis we can assume $M=M$ is provable. Now, take any $y$ not free in $M$. We have $M \equiv [y:=x][x:=y]M$ by construction. Let $N \equiv [x:=y]M$. Rule two states

$$
\dfrac{
  x\# N, y\# M \vdash M=[y:=x]N
}{
\vdash \lambda x.M = \lambda y.N
}
$$

We indeed have $x\# N$, since the $x$ variable was renamed as $y$ in $N \equiv [x:=y]N$. We also have $y\# M$ by our choice of $y$. Induction hypothesis states $M=M$, which is $M=[y:=x]N$. Hence, the conclusion of the rule holds, which is $\lambda x. M = \lambda y. [x:=y]M$. If terms are identified up-to $\alpha$, then this equality is the same as $\lambda x.M = \lambda x.M$.

If $A=MN$, the induction hypotheses and rule 3 suffice.


Theorem 1. For every polygon with edge length sequence $a_1,\ldots,a_m$, there exist a convex polygon with same edge length sequence.

Proof. Here.

Definition. $a_1,\ldots,a_n$ be $n$ non-negative reals. It satisfies (strict) $n$-gon inequality if $2a_j < \sum_{i=1}^n a_i$ for all $j$.
Theorem 2. The sequence $a_1,\ldots,a_n$ is a sequence of edge length for a polygon iff it satisfies $n$-gon inequality.

Proof. Here. (note the proof here requires advanced math and also proves Theorem 1)
The problem reduce to:

Given a sequence of $n$ non-negative reals, find a $k$ element subsequence that satisfies $k$-gon inequality.

An simple algorithm: Check if $a_i,\ldots,a_{i+k-1}$ is a solution for every $1 \leq i\leq n-k+1$. If none of them work, then there is no solution.
Proof. If we have any solution $a_{i_1},\ldots,a_{i_k}$, find the largest $j$, such that $a_{i_{j+1}}-a_{i_j}>1$, (i.e. there is a gap). If there is no such gap then we are done. If there is one, then $a_{i_2},\ldots,a_{i_{j}},a_{i_{j+1}-1},a_{i_{j+1}},\ldots,a_{i_k}$ is also a solution. (intuitively, we used the largest element in the gap and removed the smallest element). We can repeat this step (at most $k-1$ times) and fill in all the gaps. Eventually we produced a solution of the form $a_{i_k}-k+1,a_{i_k}-k,\ldots,a_{i_k}-1,a_{i_k}$ for some $i$.
The algorithm can be done naively in $O(kn)$ time. Maybe there is a smarter way to do it.
A interesting follow up question:

Given a sequence of $n$ non-negative reals, find the longest subsequence $S$, such that every $k$ element subsequence of $S$ satisfies $k$-gon inequality.


Are there things an analog computer can do that digital computing cannot do?

Digital computers are also analog if you get down all the abstraction levels until you reach electrical circuits. The only difference is that we choose to "cut" as with some sort of grid in what levels of detectable analog shifts in signal we create another new abstraction level that we call a bit or a byte.

Anything an analog computer computes, like for example the output signal of an analog filter or the amount of millimeters that a mass in a spring and damper system moves, will also eventually reach a maximum resolution. This is because of for example noise in detectors, error in measuring equipment, and maybe quantum phenomena though I'm not so sure as how that would work. If you define a bit as that very small quantum of information you'll get a digital abstraction for the output of your analog computer.

In other words, if you use a formal abstraction of a digital computer where you can achieve enough resolution for your computations, you'll be able to compute the same than an equivalent real-world analog computer for that problem will compute.

The same problem occurs when digitizing time. For example if you look into analog and digital filter equivalencies, there is always an error that is introduced when digitizing an analog filter. That error tends to 0 as the time step used for the discretizing of the continuous system gets smaller.


Maximum set packing and minimum set cover duality

There is no contradiction. The strong duality theorem applies to the fractional linear programming formulations of the problems, where one is allowed to set fractional values for the variables, but these formulations are only relaxations of the two original problems. Strong duality does not apply to the integer linear programming formulations (as your example indeed shows).


Bisimulations: Proof that the following LTS are not bisimilar

The left diagram has a b and the right diagram has a c.  Thus, the pair $(2,4')$ does not satisfy the conditions required to be a bisimulation.  In particular, the book is correct that those two systems are not bisimilar.


How can I improve my algorithm for finding optimally balanced P-way partitioning of array

Binary search is a general strategy that can often be applied to problems that seeks a single optimized number as an answer.

Let $A=[a_1, \cdots, a_N]$ be the given array of weights. Assume $1\lt P\lt N$; otherwise, the problem becomes trivial.

Given a weight $w$ such that $1\le w\le\sum a_i$, we can associate a partition $\mathcal P(w)$, $A = P_1\,P_2\,\cdots P_m$ such that

Subarray $P_1$ is as long as possible such that the sum of all weights in it is no more than $w$.
Then subarray $P_2$ is as long as possible such that the sum of all weights in it is no more than $w$.
Then subarray $P_3$ is as long as possible such that the sum of all weights in it is no more than $w$.
And so on.
Finally, we are left with non-empty subarray $P_m$, the sum of all weights in which is no more than $w$.

Note that $m=\#\mathcal P(w)$ is the minimum number of subarrays in a partition where the sum of all weights in every subarray is at most $w$. We want to find $w$ such that $\#\mathcal P(w)=P$ and $\#\mathcal P(w+1)<P$. Since the map from $w$ to $\mathcal P(w)$ is decreasing, we can use binary search to find it.

Here is the outline of an algorithm that finds the largest $w$ such that $\mathcal P(w)=P$. Assume the given weights are integers; otherwise, we need to tweak the algorithm a bit. .

Let $ma=\max\{a_i\}$. If $P\ge \#\mathcal P(ma)$, the least maximum sum is $ma$. Deal with this easy case and return.
Let $low=ma$ and $high=\sum a_i$.
If $low\lt high-1$, $ mid = (low + high)//2$ and compute $m= \#\mathcal P(mid)$.

If $m\le P$, lower $high$ to $mid$.
If $m\gt P$, raise $low$ to $mid$.

Go back to the start of this step.
Let $H$ be the partition $\mathcal P(high)$. If $\#H\not= P$, divide some subarrays of $H$ into smaller subarrays so as to increase the number of subarrays by $P-\#(P)$. Return $H$.

The loop invariant for step 3 is $\#\mathcal P(low)>P$, $\#\mathcal P(high)\le P$ and $low\le high-1$. When the loop ends, i.e., when $low==high-1$, we must still have  $\#\mathcal P(low)>P$ and $\#\mathcal P(high)\le P$. That means, $high$ is the minimum of the maximum sum of weights of any subarray in a partition of size no more than $P$, which explains largely why this algorithm is correct.

This algorithm runs in $O(N\log(\sum a_i))$ time, since the most of time is spent on computing $\mathcal P(w)$ and it takes $O(N)$ time to compute $\mathcal P(w)$ for any given weight $w$.

Exercise (the dual problem). Given an array of $N$ positive integer weights $w_i$ and an integer $P$,  divide the array into $P$ parts such that the parts are optimally balanced, i.e. that minimum sum of weights of any part is as large as possible.


Iterate over each cell of a grid through whose interior a given line segment passes

Use a line drawing algorithm, such as Bresenham's.


Context Free Grammar $L=\{a^ib^{2i}c^{2i} | i>1\}$

Your language is not context-free. You can see this by applying the inverse of the homomorphism which sends $a$ to $a$, $b$ to $bb$ and $c$ to $cc$; this results in the language $\{a^ib^ic^i : i > 1\}$, which differs from a well-known non-context-free language by just a finite number of words.


From a quick look at your problem, it seems that it can be solved in $O(nk)$ time using dynamic programming.

Let $[a_1, \dots, a_n]$ be your input array and define $\delta(i,j)$ as the minimum sum of the differences between the first and last element of each segment in an optimal subdivision of $[a_1, \dots, a_i]$  into at most $j$ segments. If no feasible subdivision exists then let $\delta(i,j) = +\infty$.

Then:

$\delta(0,j)=0$ for any $j \ge 0$;
$\delta(i,0)=+\infty$ for $i>0$; and
$\delta(i,j) = \min_{\substack{h = 1, \dots, i \\ a_i - a_h < 125}} \big\{ \delta(h-1, j-1)  + a_i - a_h \big\}$, for $i,j>0$ (where the minimum over an empty set is $+\infty$).

The value of the optimal solution is $\delta(n, k)$ and, since computing each $\delta(i,j)$ requires $O(1)$ time, the overall time required is $O(nk)$. The optimal solution can be reconstructed using standard techniques (e.g., by retracing the optimal choices backwards, or by storing -for each $\delta(i,j)$- the optimal value of $h$ in the minimum).

There isn't much different between the above description an the pseudocode of the algorithm:

Let A[1],...,A[n] be the elements of the input array.
Let delta be a (n+1)x(k+1) matrix of integers, whose entries are indexed from 0 and initialized with -1 (representing +infinity);

for j=0,...,k:
    delta[0][j]=0;

for i=1,...,n:
    for j=1,...,k:
        for h=i,i-1,...,1:
            if A[i] - A[h]>=125: break;
            if delta[h-1][j-1]!=-1 and (delta[i][j]==-1 or delta[h-1][j-1] + A[i] - A[h] < delta[i][j]):
                delta[i][j] = delta[h-1][j-1] + A[i] - A[h];

return delta[n][k];


Is this variant of set cover NP-complete?

As quicksort comments, you can convert any set cover instance to your special case by adding dummy elements. Take a large enough pool of dummy elements, and put all of it into a new set $S_1$. Then add subsets of $S_1$ to the other sets to satisfy your cardinality condition, taking care to leave some of them out. Every solution has to take $S_1$, and otherwise it just has to be a solution to the original problem.

This is of course not a formal reduction - this is left to the reader.


Equivalence of minimum cost circulation problem and minimum cost max flow problem

Does that mean the minimum circulation problem has zero flow on every edge of the original network?

No, it does not means that, unless the lower bound capacity of every edge is equal to zero.

You need to remove the lower bound capacity. You can use the transformation done in Ahuja, page 39.