The name for this genetic algorithm variant

Most EAs may be divided into generational algorithms, which update the entire population once per iteration, and steady-state algorithms, which update the sample a few candidate solutions at a time.

Steady-state GAs (popularized by the Darrell Whitley and Joan Kauth's GENITOR system) iteratively breed a new child or two, assess their fitness and then reintroduce them directly into the population, thus killing some preexisting individuals to make room (take a look at Essential Metaheuristics by Sean Luke for further details).

So a steady-state GA fits part of the description ("death comes after random period of time").

Other characteristics ("the better phenotype is (fitness function) the bigger is chance to have (more) children") are shared with generational algorithms.

Gender-specific selection / crossover operators / GAs fit the last part of the description ("phenotypes have sex (man or woman)"):

  instead of selecting individuals from a single group for mating, a gender genetic algorithm create two groups and permits mating only between opposite groups; the selection from two groups helps to increase diversity.

Anyway many GA variants based on a more natural governing framework are possible:

delayed reproduction / breeding age (most life forms aren't able to  breed during  the early  stages of  their life);
life span for individuals (no  matter how poor the fitness is, it
would still stay in the population for a length of time) / predetermined death age;
progressive ageing (Individual Aging in Genetic Algorithms by Ashish
Ghosh, Shigeyoshi Tsutsui and Hideo Tanaka);
Age-Layered Population Structure (ALPS) evolutionary algorithms (The Age-Layered Population Structure by Gregory S. Hornby)
...


Are genetic algorithms an effective way to train neural networks?

There have been hundreds of papers published over the years on training neural networks with GAs. Here's a starting point Neuroevolution.

The basic problem though is that stochastic gradient descent works really well in vastly less computation time.


How P2P search engines prevent corruption of distributed index by malicious peers?

When tackling such problems, think in general terms. Researchers have studied the impact of malicious peers in numerous papers. Most of these systems should work.

However, define your problem clearly. Ex: What are the malicious peers trying to do in this case? do you want to:

protect your system from unwanted outsiders (security),
protect your data from faulty peers (fault tolerance),
protect your data from greedy peers (greedy peers),
or others?

Also note that Kademlia is very similar to Chord, SkipNet, Pastry and others (some researchers call these networks "common prefix networks - I can't remember", others: ring-based p2p networks, etc ... Some solutions may be designed specifically for these networks.  However, I don't see why a solution made for a structured P2P networks would not work for your architecture.


How to bridge theory and implementation for while loops?

So I managed to solve this issue today. The code for my while loop:

while (condition: ~>bool) (body: ~>void) => void {
    if condition {
        body;
        while condition body;
    };
}

When I go to build this into CIL (a stack based runtime, important for the psuedocode, not important for the answer) it looks like:

ldarg 0
<build closure from { body; while condition body; }>
call if

The important thing I was missing is that in the while code, the conditional was the thing in tail position. From the compiler's perspective, the block and the while function are two separate functions, with two separate "tails". Each of those are easily evaluated for tail position, making the optimization viable despite the lack of built-in conditionals.


Given a directed acyclic graph (DAG) - what can you say about each case?

A. Let's prove that $v$ will be a vertex which can be reached by every node (it is the mother vertex of the transpose of the graph) by contradiction. Suppose that there is a node $u$ such that $v$ is unreachable by it. Consider every node in the DAG reachable by $u$. There must be at least one node in this set that has no leaving edges. (Otherwise you could start from $u$ and always follow a leaving edge from the current node so after at most $|V| - 1$ steps you would visit an already visited node. But this implies a cycle which isn't allowd in a DAG.) So no other node is reachable by $u$ and $u$ could be last in a topological cue instead of $v$ and we reached a contradiction. As a result $v$ is reachable by every node. This is equivalent with (A)'s statement as a node being reachable by every node can appear only last in any topological cue.

Also $v$ is a sink because if it wasn't there would be at least one edge leaving it so it couldn't be at the end of any topological cue. (A)'s statement implies that $v$ is a sink but the reverse doesn't always hold.

B. $v$ is a mother vertex (every node is reachable by it). The proof is similar.


Anagrams solver based on transitions probability

There's a better way to list all anagrams.

Given a word, compute its "canonical form" by sorting the individual letters into alphabetical order.  For instance, BASEBALL becomes AABBELLS.  Do this for each word in the dictionary, and build a data structure that maps from a canonical form to the list of words with that canonical form (e.g., from AABBELLS to BASEBALL) -- for instance, you might use a hashtable or a sorted list.

Now, given one English word, if you want to find all anagrams of it, you can rapidly compute all anagrams by computing its canonical form and then looking that up in your data structure.

This doesn't require n-grams, transition probabilities, Viterbi algorithm, or anything fancy like that -- just sorting and simple data structures.  Thus, it can be coded up quickly and elegantly; and it will be very efficient.


Exercise: Sliding window protocol: Bits for sequence number

Assuming SWS(sender window size) = RWS(receiver window size)

In this case Assume a scenario where SWS = RWS = 3 so MaxSeqNum = SWS - 1 = 2

LAF(Last Acknowledged frame)
LFS(Last Frame Sent)

Sender = { [ 0, 1, 2 ], 0, 1, 2, 0, 1, 2}

Note:
Sequence of packets waiting on the queue.
Square bracket represent the window

Receiver = {0, 1, 2, [0, 1, 2], 0, 1, 2}

Here the packets 0, 1, 2 are obtained and window is moved further acks sent by the receiver.

but acks are lost in traffic.

So the sender didnt got the acks thinks that the packets have lost and sends the
first window packets with sequence numbers 0, 1, 2. In this case the packets received are actually not distinguished by the receiver.


This is exactly the edge cover problem, which can be solved in polynomial time by finding a maximum matching.  Then, for each unmatched vertex, add an arbitrary edge containing that vertex.

In fact, if all you want to know is whether there's an edge cover of size at most $k$, you don't need to construct the cover: the size of a minimum edge cover is $M + n - 2M = n-M$, where $n$ is the number of vertices in the graph and $M$ is the number of edges in a maximum matching.  (The reasoning here is that the cover is the $M$ edges of the matching plus one more edge for each unmatched vertex, and there are $n-2M$ unmatched vertices.)


Decidability problem solved by an alogrithm step by step difference between Decision and decidable problem

A decision problem is a problem of the form "Is my input in this set?", with a yes/no answer. A decidable problem is a decision problem that can be solved by a Turing machine.


Why do Shaefer's and Mahaney's Theorems not imply P = NP?

Schaefer's theorem applies only to a specific type of languages, those of the form $\mathrm{SAT}(S)$ for a finite set of relations over the Boolean domain or $\mathrm{CSP}(\Gamma)$ for a finite constraint language over the Boolean domain (the two notations are equivalent; see the Wikipedia page for a description). Any other language is not covered by the theorem, and the theorem has nothing to say about it. In particular, Schaefer's theorem doesn't say anything about your language $L$.


How does the use of oracle Turing machines not lead to contradictions?

There's a number of ways to look at this.

One is that in proofs, implication is kind of like a function, that takes as input a proof of something, and outputs a proof of something else.

We can write functions that operate on values that we don't have.

For example, let's consider the halting number $h$, which is not computable. I can write the function

$haltingPlusOne : \{h \} \rightarrow \mathbb{N}$

$haltingPlusOne(x) = x + 1$.

This function takes as input the Halting number, and returns the Halting number plus one. Clearly this is a well defined function: if we give it the right input, it gives the right output. The fact that we can't find the right input doesn't make it any less valid of a transformation.

I see proofs with oracles as similar. They're basically functions which say, give me a Turing machine that solves problem $X$, and I'll give as output a proof of some theorem.

It's also important to realize that when we say something like "There is no Turing Machine that can decide the halting problem,"  that is saying that, there's no TM matching the standard definition of a TM that decides the halting problem.

An oracle is basically saying "Assume we have a TM that matches the normal definition except also assuming we can solve some problem". So there's no contradiction, since we're not assuming there's a normal TM accepting the problem, we're assuming there's a special TM accepting the problem.

In a very informal analogy, think of it like this. If I can prove to you that no humans without superpowers can fly, there's no contradiction saying that there's a superhero that can fly.

These oracles are purely logical objects. We don't know how to build physical machines that emulate them, the way we can with Turing machines, but as far as we know, there's no inherent contradiction between their definitions and our basic axioms.
As logical objects, these oracles do exist. We know they're not standard Turing Machines or Lambda-Calculus terms or Partial-recursive functions. The Church-Turing thesis says that there's no more powerful model, but it's not a theorem, it's just a conjecture, and is too informal to ever really be proved.


With a halting oracle, can tell whether something will have finite output?

It's not clear what specific computational model you use.
If you're using Turing Machines, then having a finite output is equivalent to having a finite number of distinct configurations (assuming that you're not allowed to "erase" the tape).

So we're considering the language of all TMs $M$ such that $M$ has a finite number of configurations when run on the empty input.
Clearly this is Turing recognizable - simulate the machine and accept if it halts or repeats a configuration. Thus, the problem is in RE.

It's also very simple to show that it's not in coRE by a reduction from $A_{TM}$. So we conclude that the problem is in RE\coRE.

Now, given a halting-problem oracle, the problem is decidable: Given a TM $M$, modify it to a machine $M'$ such that $M'$ simulates $M$ and records the configurations, and if a configuration is repeated,or if $M$ halts, then $M'$ halts. Now simply run the oracle on $M'$.


Circle Intersection with Sweep Line Algorithm

You're definitely on the right track. The big question is: when you insert a circle, which other circles do you check for intersection? How do you perform this check?

In the line segment intersection case, the line segments at any given x coordinate are totally ordered. (You can list them from lowest to highest Y coordinate). Thus, you can maintain the line segments in a binary search tree, and when you add a new segment, you only need to find out where it belongs in the binary search tree, and check its neighbors for intersection events.

In the circles case, its not immediately clear which circles to check. If your answer is "all of them" then your algorithm needs some work.

Can you figure out a way to represent the circles so that they are totally ordered, like the line segments are?

   Try representing the circles as two half-circles. Each insert event is actually two events: insert top half, and insert bottom half.


Time complexity of recurrence function with if statement

Let us prove by induction the following formula:

  $T(n)$ is the number of 0s in the binary representation of $n$, plus twice the number of 1s.

This certainly holds for $n = 0$. If $n$ is even, then $T(n) = T(n/2) + 1$, and indeed the binary representation of $n/2$ differs from that of $n$ by having one less 0. If $n$ is odd, then $T(n) = T(n-1) + 1$, and indeed the binary representation of $n-1$ differs from that of $n$ by having one 1 replaced by 0.

This shows that $T(n) = O(\log n)$. It is not clear what you mean by average case, but the formula above should let you work that out. For example, let us consider the $2^{m-1}$ numbers of length exactly $m$. Each of them has a leading 1, and the other $n-1$ bits are half 0, half 1 (considering all numbers in the range). Hence the average value of $T$ for $2^{m-1} \leq n < 2^m$ is $m + 1 + \frac{m-1}{2} = \frac{3m+1}{2}$. Using this, we can compute the average value of $T$ for $0 \leq n < 2^m$ to be
$$
\frac{T(0)}{2^m} + \sum_{\ell=1}^m 2^{\ell-1-m}\frac{T(2^{\ell-1}) + \cdots + T(2^\ell-1)}{2^{\ell-1}} =
\frac{1}{2^m} + \sum_{\ell=1}^m 2^{\ell-1-m} \frac{3\ell+1}{2} = \frac{3}{2}m - 1 + \frac{1}{2^{m-1}}.
$$


How to do pixel array rotation whose angle not a multiple of 90 degree?

Choose an origin for your coordinate system. A corner or the middle of the image is typical.
For each pixel, compute its (x, y) coordinates relative to the origin.
For each pixel, compute its new coordinates when keeping its distance from the origin the same and adjusting its angle by the desired rotation.
In a temporary buffer, copy pixels from the original image using the new coordinates.
Go over the temporary buffer, and for each pixel that wasn't assigned a color, interpolate the colors from surrounding pixels.

There are some details glossed over there, but the basic idea is sound. Coordinate transformations can be accomplished using basic trigonometry.


Find the smallest summed distances by uniquely pairing elements of one set to elements of another set

This is the problem of finding the maximum matching in a weighted bipartite graph.  There are efficient algorithms that solve this problem in polynomial time.

Basically, you have a complete bipartite graph with $2m$ vertices.  $S$ forms one set of vertices; $T$ forms the other set of vertices.  For each $i,j$, create an edge from $s_i$ to $t_j$ whose weight is equal to $-d(s_i,t_j)$, the negation of the distance between $s_i$ and $t_j$.

Now, you want to find a matching whose weight is as large as possible.  This corresponds to a set of pairs $(s_i,t_j)$ whose total distance is as small as possible.  From there, you can use existing algorithms on this graph to find the maximum-weight matching.


Is this a good way of generating diverse solutions to a problem using a genetic algorithm?

The success (or otherwise) of your proposed scheme may well be highly problem dependant, so I would urge you to consider diversity-promoting methods such as 'niching' or 'island models' that have proved useful across a wide-range of problems.

Island models, for example involve partitioned populations that are evolved separately, with only occasional gene transfer.

More details on diversification methods can be found in the (freely downloadable) 'Essentials of Metaheuristics'


Is there a non-brute force algorithm for Eulerization of graphs?

Consider the Chinese Postman Problem on undirected graphs: Given an undirected graph $G$, find the shortest circuit of the graph that travels every edge atleast once. Now, if $G$ is Eulerian, then the Euler circuit is the shortest such circuit. If not, some edges will be traveled more than once. In other words, some edges will be duplicated, and the circuit will be Eulerian on the graph with these extra edges.

Now, for obtaining the shortest circuit, the edge duplication has to be minimized. This is the same as your problem. You need to find a new graph $H$ which has all the edges of $G$, and a few extra parallel edges - as few extra edges as possible - so that $H$ is Eulerian. Each extra edge in $H$ corresponds to the fact that its corresponding parallel edge in $G$ is visited again in a shortest complete circuit of $G$. In other words, the optimum (minimal) "eulerization" is equivalent to the Chinese Postman problem. For a better expressed explanation of this, refer to Section 4 (Chinese Postman Problem) and Definition 11 (Eulerization, Minimal Eulerization) of these notes. Fortunately, this is solvable in polynomial time for undirected graphs.

For the Chinese Postman problem, Wikipedia has one solution. I describe another algorithm from Steven Skiena's The Algorithm Design Manual [1]:

Find the shortest paths between each pair of odd-degree vertices in $G$: $O(n^3)$.
Finding the best set of shortest paths to add to $G$ reduces to identifying the minimum-weight perfect matching in a special graph $G' = (V', E')$. The vertices $V'$ of $G'$ correspond the odd-degree vertices of $G$, with the weight of the edge $(i, j) \in E'$ defined to be the length of the shortest path from $i$ to $j$ in $G$. Note that a matching is a set of pairwise non-adjacent edges. Thus, each edge in the matching connects two vertices, and no vertex is part of two matching (a matched vertex is matched with exactly one other vertex). A perfect matching is a matching where each vertex has been matched. Now, for each matching edge obtained, you can consider the two end vertices to be paired up. The constraint of "minimum-weight" when obtaining the matching ensures that the total weight of each edge in the matching is as small as possible. Since the weight of each edge is the distance between its end points in $G$, which in turn is the number of edges that need to be duplicated when the end points are paired up - this condition ensures that globally, the total number of edge duplication is minimized. Obtaining such a matching is described in [2], and is based on the Blossom algorithm. An efficient implementation is described by Kolmogorov [3] (preprint copy) with an implementation here. The implementation is an improvement over the ideas and review presented by Cook and Rohe in [4]. This can be done $O(n^3)$.
Once the matching is obtained, each odd vertex is paired with another odd vertex. This is the pairing that you want.

Thus, you can obtain the optimal "Eulerization" in time polynomial (cubic) in the number of odd-vertices. This is based on a paper by Edmonds and Johnson [2] which solves the Chinese postman problem.

References:

Steven S. Skiena. The Algorithm Design Manual. ISBN: 978-1-84800-069-8 e-ISBN: 978-1-84800-070-4 and DOI: 10.1007/978-1-84800-070-4
J. Edmonds and E. Johnson. Matching, Euler tours, and the Chinese postman.
Mathematical Programming, 5:88–124, 1973.
Vladimir Kolmogorov. Blossom V: A new implementation of a minimum cost perfect matching algorithm. In Mathematical Programming Computation (MPC), July 2009, 1(1):43-67.
W. Cook and A. Rohe. Computing minimum-weight perfect matchings. INFORMS Journal on Computing, 11(2):138–148, February 1999.


If $j − 1 < \log k < j$. Why is $j = O(\log k)$?

You solved your own question. Quite literally the bounds you gave (with $c=1$ or $c=2$) should suffice


Show this language is non-regular using pumping lemma: B = {ww | w ∈ {a,b,c,...,z)*}

Your proof using the pumping lemma is wrong. You choose a pumping lemma constant $p=4$ but what happens if $p=5$ works? The pumping lemma tell us that there exists a constant $p$. Now you have to try all the remaining possible values of $p$.

I recommend you to study carefully the pumping lemma first. It is a bad idea to try using it without understanding it. After that if you want to assimilate it more you can check this answer: https://cs.stackexchange.com/a/50618/31129 where I explain some common mistakes.


If the path has to be simple reduce the HamiltonPath problem to this to show that's NP-complete, otherwise (not necessarily simple paths) take the $k$-th power of the adjacency matrix, whose entry corresponding to $u$ and $v$ not only contains whether there is such a path, but also the number of such paths.


What does it mean that a core supports 2 threads?

See Wikipedia on Computer Multitasking and Time-sharing, which have an explanation of how operating systems allow this.  Basically, they switch between multiple threads.

Read also about hardware multithreading.  This allows a single core to execute multiple threads concurrently, without switching between them.


How to understand the probablistic analysis of skiplist?

The first sum is obviously equal to $\lfloor\log n\rfloor\leq\log n$.

For the second sum, assuming that logs are base-$2$ and using $r>\lfloor\log n\rfloor$,

$$2^r = 2^{\lfloor\log n\rfloor+1}2^{r-\lfloor\log n\rfloor-1} \geq n2^{r-\lfloor\log n\rfloor-1}\,,$$

and the result follows.  If the logs aren't base-$2$, then there'll be a scaling factor but the second sum will still be $\Theta(1)$.


Finite state automaton's reaction to simultaneous events

Finite-state automata take a sequence of events as input. There is a single event in the input sequence at any given position. What if there are two different values at position 3 in the sequence $ababcaccab$? There aren't, that's just how the mathematical object is constructed.

The input to a FSA is not necessarily a sequence of events that happen one after the other. For example, when an FSA is used for string parsing, there's no concept of time. But let's assume that you're using an FSA as part of a model of something that reacts to events over time. Note that this is no longer just about automata theory, but also about what you're modeling. What if you want to express that two events are simultaneous? Then you'll need to use a more sophisticated mathematical tool.

The core of the mathematical tool can still be a finite state automata, but instead of taking a sequence of events as input, you'd take a sequence of sets of events. The thing is, in practice, this is rarely useful, because in practice, things do not happen simultaneously. At most, they happen simultaneously up to measurement error. Given that measurement error is, by definition, variable, the same physical process may or may not be observed as simultaneous if you try it again several times. Therefore it is not useful to consider simultaneity in the model: it brings extra complexity to the math without providing any extra insights regarding the physical process.

Simultaneity is a useful concept regarding events that have a duration: event A may end after event B starts, in which case events A and B overlap. But if you're interested in that, then you can't model A and B as single events, you need to distinguish separate events “A starts, B starts, A ends, B ends”. These start/end events happen sequentially.

There is one world where things do happen sequentially, which is the world of discrete time. Discrete time is used to model digital circuits (because it corresponds to how they work). Two events may happen during the same clock cycle; that's the definition of simultaneous here. A digital circuit is modeled as a finite state automaton in a straightforward way, but then each element in the input sequence is not an individual event such as “input 42 switches from 0 to 1”, but a collective event made of the state of all the states of all the inputs.


Use nonlinear regression: https://en.wikipedia.org/wiki/Nonlinear_regression.  Write down a model, e.g., $f(x) = \sin(\alpha x + \beta)$, and then try to find parameters $\alpha,\beta$ that minimize the regression error (the sum of the squared error at each point; i.e., square of difference between model's prediction and observed value).  You can use gradient descent or other forms of mathematical optimization for that.  If a sin function isn't the right model, you can write down some other model (with some parameters) and use optimization to find the best values for the parameters.


Conditions for maximum period of quadratic congruential method (PRNG)

What's exactly "trial and error method" applied in this situation?

$\newcommand{\mymod}{\operatorname{modulo}}$As I understand, "trial and error method" here means checking all cases from a few simple natural or known perspectives until we have found a satisfactory solution or proof. It is useful and efficient in this situation because the number of cases $\mymod 2$ or $\mymod 4$ or $\mymod 9$ is very small.

What you have done seems pretty good.

  Why does $dx^2+ax+c\equiv d(x+a_1)^2 + c_1(\mymod{p^e})$ hold when $d \not\equiv 0\,(\mymod{p})$ ?

Prime $p\not=2$ since it has been assumed $p\ge5$. Since $d \not\equiv 0\,(\mymod p)$, $2d$ and $p^e$ are relatively prime, which implies $2d$ is invertible $\mymod p^e$. Let $(2d)d'\equiv1\,(\mymod p^e)$ fro some $d'$. Then

$$\begin{aligned}
dx^2+ax+c
&\equiv dx^2+2dd'ax + c\\
&\equiv d(x+d'a)^2 -d(d'a)^2+c\ (\mymod p^e)\\
\end{aligned}$$

Letting $a_1=d'a$ and $c_1=-d(d'a)^2+c$, we are done.


Particular function communication complexity computation

There is a cheap lower bound of $\Omega(r)$ obtained by reduction. Suppose for simplicity that the $r$ dIstinguished coordinates are the first $r$. Let $g(x_1,\ldots,x_r) = f(x_1,\ldots,x_r,0,\ldots,0)$. Your condition on $f$ implies that $g$ satisfies Jukna's condition on $g$, so $g$ has communication complexity $\Omega(r)$. Any protocol for $f$ also works for $g$, so we get a lower bound of $\Omega(r)$ for $f$.


What are drawbacks of Tree Sort algorithm (with balanced tree) vs Tree Sort (with unbalanced tree)?

The advantages of unbalanced trees over balanced trees in practical situations are little to none. A large number of predefined algorithms/ data structures that many programming languages use implement a variety of the Tree Sort algorithm in order to keep time complexity of emplacement and retrieval of data to a minimum (keeping in mind that space complexity stays the same). Such varieties are AVL trees and Red-Black trees.

For instance, in STL (Standard Template Library in C++), structures such as map/ multimap, set/ multiset implement a BST as to keep the time factor to a minimum value.

An example of usage of an unordered tree (although not a binary tree) is a tree used to represent TRIE structures. You can find more about these from Wikipedia or Geeksforgeeks.

Hope this was helpful!


Why update weights and biases after training a Neural Network on whole set of training samples

You are right.  While you could backpropagate for all samples and then update the weights, you don't have to.  Alternatively, you can iterate through the samples and, for each sample, backpropagate for just that sample and then update the weights.

The latter turns out to be more effective (empirically).  It is called stochastic gradient descent.  Today, most neural networks are trained using stochastic gradient descent, because it reaches convergence faster than the alternative.  This makes neural networks faster to train.

Anyway, you could do it either way.  Both ways are valid.  The stochastic gradient descent approach seems to be faster in practice, but neither one is wrong.

Why did the book describe it this way?  That's a pedagogical choice.  The author might have considered it more natural or easier to explain this way.


An algorithm to find highest lines in at least one point

If the lines are unlimited (as they seem to be) then the way to go seems to divide the lines by their slope.

Preprocessing:

Sort all the lines lexicographically by their slope and constant term. This allows to remove each line which is parallel to some higher-placed line. The ordering is also used to split the lines into subroups depending on their slope later on.

Recursion:

Divide the lines into lines with positive and negative slope. For each group call recursion. From each recursion we get two lists, a list of top-lines (ordered as they appear on top from left to right) and a list of top-intersections of the top-lines (ordered by x-coordinate) corresponding to the points where one line takes over the previous one.

Now we only need to combine the two results we got from recursion. The algorithm passes through the intersection-point lists in parallel, going through positive-slope lines from right to left, and through negative-lines from left to right until the x-coordinates of the intersections meet. To do this properly, we need always make the step on the side with higher y-coordinate.

(I strongly suggest to draw it, it's easier to see in a picture. Imagine bunch of lines forming a "U"-shape and the algorithm descends with equal vertical speed on both sides until it reaches the lowest point of the "U"-shape.)

In this way we found a "middle" point where one positive- and one negative-slope top-line meet in a new top-intersection. From the list of lines we know which lines meet there and we can compute the intersection point they share (the lowest point of the "U"-shape).

We can now construct the total list of intersections of top-lines (all the point we went through + the new intersection point we found in the middle) and the list of the corresponding top lines.

Note that it might happen that all the positive-slope intersection might be too much to the left (so we do not get a "U"-shape). In that case we only get one positive- and one negative-slope line as a result, intersecting in an "V"-shape.

Now, how to split the groups in the recursion? Well, simply realize that by tilting (by less than 90 degrees) what the algorithm understands us "horizontal" none of the necessary properties is violated (within the subgroup). Thus the algorithm can again split the groups into smaller groups, while the left-right orderings remain consistent. So in fact we don't want to split lines into positive and negative slope, but simply split by the median slope each time. (splitting by the horizontal direction just makes it easier to understand)

Complexity:

Each level of recursion is linear-time in respect to the number of lines (going through lists in parallel, concatenation of lists, etc.). Since the lines are already ordered by their slope (from preprocessing), we can always split by the mean slope in linear time. So the total time is O(nlogn).

Hope the description is somewhat clear. I did not go into details as that would be lengthy.


need of error control in transport layer

There are many types of error controls. The link layer error control that you are referring to is probably to do with ensuring that no bits were flipped in transit i.e. safe guarding against data corruption.

The error control in the transport layer usually refers to the guaranteed delivery mechanism with TCP, which attempts to safe guard against frames/packets getting lost entirely.


A simple and efficient algorithm would be (correct me if I'm wrong):

1) Find the biggest valued coin just below that particular amount
2) Do the same thing with amount - coin_chosen
3) Repeat until convergence

Does this solve your problem?

e.g   Available coins: 1p,2p,5p,10p,20p,50p,£1 ...
47p -> -20p -> 27p -> -20p -> 17p -> -10p -> 7p -> -5p -> 2p -> -2p -> 0p

There are other less efficient ways to do this like maybe using genetic algorithms but I guess this would be the quickest ...


Are the No Free Lunch theorems useful for anything?

A practical implication is that there is no silver bullet: we shouldn't expect any single optimization method to be perfect for all problems.  Rather, we should try to design optimization methods that are tailored to the problem we're trying to solve.

For instance, if you want to use local search, you'll probably need to define a neighborhood relation (a set of moves that makes "small" changes to the current solution) that is informed by the problem domain.  See, e.g., https://cs.stackexchange.com/a/88016/755 for a recent example of this here on this site.

A practical implication is that machine learning won't work if there is no structure at all on the space of possible models/hypotheses.  Instead, we need some kind of prior that makes some models more likely than others.

Often, we assume a prior that assume "simpler" models are more likely than complex one's (Occam's razor: all else being equal, the simpler explanation is more likely to be true).  This leads to use of regularization in machine learning, as it effectively applies Occam's razor to candidate models.  So, you can think of the NFL theorems as providing some kind of theoretical justification for regularization or theoretical understanding that helps us see what the role of regularization is and provides some partial explanation for the empirical observation that it seems to often be effective.

You could characterize these as "NFL theorems tell us some directions that won't work", which arguably has value as it helps us avoid wasting time on something that won't work and helps point us towards directions that are more likely to work.


What is the result of multiplying O(n) and Ω(n)?

Basically, without further information you know nothing about the asymptotic growth of $f \cdot g$.

Let's unfold the definitions:

$\qquad f \in \Omega(n) \implies f(n) \leq cn$ and

$\qquad g \in O(n)      \implies g(n) \geq dn$

for some $c,d \in \mathbb{N}$ and $n$ greater than some constant.

Now it's clear that you get no bound on $g \cdot f$; you have no upper bound for one factor and no lower for the other. In fact, you can get arbitrarily slowly and fast growing results:

For $f : n \mapsto n$ and $g_k : n \mapsto n^{-k}$, we get $f \cdot g_k : n \mapsto n^{-k+1}$. Note that the induced sequence of functions is properly decreasing in terms of asymptotic growth.
For $f_k : n \mapsto n^k$ and $g : n \mapsto n$, we get $f_k \cdot g : n \mapsto n^{k+1}$. Note that the induced sequence of functions is properly increasing in terms of asymptotic growth.

If you restrict yourself to (eventually) non-decreasing functions -- that is $f,g \in \Omega(1)$ -- you get one of the missing bounds and thus $f \cdot g \in \Omega(n)$.


Definition of "idempotence" of a function?

There are two related concepts called "idempotence" in programming. One is the mathematical one that quicksort and Raphael talk about. Namely, given a mathematical function $f$, $f$ is idempotent if $f(f(x))=f(x)$. Or more algebraically, $f\circ f = f$.

The other notion that's common in practice and particularly for distributed computations is if an identical "request" is made multiple times, the system will behave as if it was made once. For example, an HTTP PUT is supposed to be an idempotent request so that it can be transparently repeated in case it's suspected that an earlier request was lost. This sense of idempotence is important in distributed computing because it turns at-least-once semantics into effectively exactly-once semantics.

The second notion cast into the context of an imperative language would correspond to the property of a procedure or method that calling it once is the same as calling it arbitrarily many times with the same arguments (assuming no intervening related procedures/methods are called).

The second notion can be related to the mathematical notion by viewing the request/procedure/method as performing a function on the state of the system (taken broadly). An idempotent request/procedure/method, corresponds to an idempotent function on the system state.

Arguably, the response to an idempotent request should be the same on every request. In practice, the responses tend to be informational and so potentially non-deterministic (often due to the concurrency inherent in distributed computing), that you have no real guarantee of any response. For example, the MDN page I linked discusses the case of HTTP DELETE. A HTTP DELETE may return a 200 status code after successfully deleting a resource and then a 404 for future HTTP DELETE requests. But the non-determinism of networking means that making two identical DELETE requests could produce any of two 200 responses, two 404 response, a 200 response followed by a 404, or a 404 followed by a 200 response. (And, of course, many other possibilities such as a 503 response or no response.) The upshot is that your DELETE request could get a 404 response even when you expected a 200 response for a variety of reasons and thus, since the 404 response means the resource wasn't there at the time the request was processed*, you should treat that as just as good as having gotten a 200 response.

If the semantics of your procedure/method are: "on these arguments, do this, then non-deterministically return one of this set of responses", then the procedure/method is free to return different responses (from that set of responses) even when called multiple times with the same arguments. I would consider such a procedure idempotent assuming the "do this" part was idempotent. On the other hand, if the semantics of your procedure/method are: "on these arguments, do this, then if it is the first time this procedure was called return X else return Y", then I would not consider the procedure/method idempotent.

* Of course, someone could have added it back between the time the 404 was generated and the time you received it.


An accepted definition of Third Normal Form is that any non-trivial dependency with a single attribute on the right part must have a superkey as left part, or the right part must be constituted by a prime attribute.

In other words, if you have a dependency with a prime attribute on the right part, that dependency does not violates the 3NF.

For your second question, a relation is in BCNF if any non-trivial dependency has a superkey as left part. If a relation does not have partial dependencies, and all the attributes are prime, this means that no dependency exists with attributes that are not a full key or that are not constituted by non-prime attributes. So, the answer is yes, that relation is in BCNF.


Finding the private key in BB84 quantum cryptography

The first stage of the BB84 protocol involves throwing away any measurements where the measurements were performed with a different basis.  After throwing those away, we are left with the following binary sequence:

$$11 10 0 0 01 10 01.$$

However, in the BB84 protocol as it was originally published, this is not the final key.  There are several subsequent steps that are performed after this.

In the second stage, Alice and Bob check whether they both got approximately the same sequence, by comparing a randomly chosen subset of this sequence.  If there are too many errors (differences between Alice's string and Bob's string) in those randomly selected positions, then they declare it a failure and go back to the beginning and start over.

In the third stage, a privacy amplification protocol is applied to the remaining bits, to derive a key that Alice and Bob can use.

Consequently, in the real BB84 protocol, the final key is not $111000011101$.  That's just the output of the first stage.  The final key is the output of the third stage.

However, I don't know what they taught you in your class.  I'd hope that they taught you all three stages, but if they only taught you the first stage, then you'd get a different answer than if they taught you the full protocol.  Therefore, we can't really tell what the right answer to your exam might have been.  If you want to know about that, I suggest you contact your instructor.


Are there hardware lock implementations without test-and-set or swap?

Yes, you can implement mutual exclusion with only memory load and store instructions.  There is a long tradition of devising successively simpler solutions to this problem.

The earliest version that I know of, called "Dekker's solution", was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., Programming Languages: NATO Advanced Study Institute, pp. 43-112, Academic Press, 1968.  There have been dozens of solutions since then.  I will discuss only a few of the more notable ones.

Lamport, Leslie; "A New Solution of Dijkstra's Concurrent Programming Problem", Comm ACM 17(8):453-455, 1974 introduces the "Bakery algorithm" (because it is based on the analogy of people taking numbers to determine the order in which they will be served at the bakery shop).  One of the particularly notable features of this algorithm is that it demonstrates that no hardware atomicity at all is required to solve the mutual exclusion problem.  Reads that overlap writes to the same location can return any value and the algorithm still works.  Lamport discusses this a bit in the description of the paper on his home page.

Peterson's solution, Peterson, G.L.; "Myths about the mutual exclusion problem," Inf. Proc. Lett., 12(3): 115-116, 1981, is one that is specifically designed to be easy to understand, and reason about.
Finally, a particular favorite of mine is Lamport, Leslie; "A Fast Mutual Exclusion Algorithm," ACM Trans. Comp. Sys., 5(1):1-11, 1987.  In this paper Lamport was trying to optimize a solution to the mutual exclusion problem in the (common) case that there is little contention for the critical section.  It guarantees mutual exclusion and deadlock freedom, but not fairness.  It is (I believe) the first mutual exclusion algorithm using only normal reads and writes that can synchronize N processors in O(1) time when there is no contention.  (When there is contention, it falls back on an O(N) test.)  He gives an informal demonstration that the best you can do in the contention free case is seven memory accesses.  (Dekker and Peterson both do it with 4, but they can only handle 2 processors, when you extend their algorithms to N they have to add an extra O(N) accesses.)

Apparently people who work on the problem of solving mutual exclusion using just memory reads and writes get frustrated by other people's (lack of) understanding of the problem and its solutions.  This is demonstrated partly by the title of Peterson's paper ("Myths about the mutual exclusion problem") and partly by a short note that Lamport published in 1991: Lamport, Leslie; "The Mutual Exclusion Problem Has Been Solved", Comm ACM 34(1):110, 1991, which Lamport describes somewhat bitterly on his homepage.

So to answer your second question: No.  There are many more than three categories of hardware level solutions to the critical section problem (using just loads and stores is one, others involve compare-and-swap instructions, load-linked/store-conditional instructions (using the cache coherence protocol to test for atomicity), and fetch-and-add instructions.)  In another sense there's really just one category of solutions: those that involve getting a bunch of asynchronous processes to agree on a global order of events.

(Note that this answer is an (extensive) edit of an earlier answer I gave for a very different question.)


Greedy sequential/parallel task scheduling

I have a pretty messy proof. I'm sure this can be cleaned up with a bit of work. Let me know if you need me to simplify the proof.
For the sake of the proof, lets rearrange all the terms such that
$a_1 \geq a_2 \geq a_3 \ldots$. Let $f(1), f(2), \ldots, f(N)$ be some schedule. The total time spent for any schedule $f$ is given by the following.
$$T(f) = \max \{m_{f(1)} + a_{f(1)}, m_{f(1)} + m_{f(2)} + a_{f(2)},\ldots, \sum_{i = 1}^N m_{f(i)} + a_{f(N)} \}$$.
For the sake of contradiction, suppose that your greedy method is not the optimal solution. There exists some schedule $\phi$ such that $T(Id) > T(\phi)$ (here $Id$ is the identity). Choose $k$ such that $\sum_{i = 1}^k m_{i} + a_k = T(Id)$. Let $h$ be the smallest number such that $\{1,\ldots, k\} \subset \{\phi(1), \ldots, \phi(h)\}$. Note that $\phi(h) \leq k$.
Because $\{1,\ldots, k\} \subset \{\phi(1), \ldots, \phi(h)\}$, $\sum_{i = 1}^h m_{\phi(i)} \geq \sum_{i = 1}^k m_i$. Because $a_1 \geq a_2 \geq \ldots$, we know that $a_{\phi(h)} \geq a_k$. This means that
$$\sum_{i = 1}^k m_i + a_k \leq\sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)}$$
But $T(Id) = \sum_{i = 1}^k m_i + a_k \leq \sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)} \leq  T(\phi)$. This is a contradiction.


Runtime of weighted interval scheduling dynamic programming algorithm

If I understand your concern correctly, you are right in that many $p(j)$ may give the same $i$. But that means that other $i$s don't get many $p(j)$s (the total of them is $n$).


How is this problem related to the study of algorithms and big O notation?

You need to be more patient. This problem is hinting at the repeated squaring algorithm for powering. The more general question is: How long does it take to compute $x^n$? Naively, you might think that it takes $n$ multiplications, but the repeated squaring algorithm can do it using $O(\log n)$ multiplications.

Repeated squaring is very important for cryptographic applications. Many cryptographic algorithms rely on computing modular powers: $x^p \pmod{n}$, where in general $p$ and $n$ could be very large (say roughly $2^{1024}$). It makes a huge difference whether you do it in $O(p)$ or in $O(\log p)$ time.


Let me give you a real-world example, that's very similar to something I wrote once.

Let's say you're implementing a library catalogue system. A library catalogue is conceptually a collection of documents (perhaps in MARC format). A user of this system might enter a query, as in any search engine, and get a set of documents in return. The user would like to be able to sort the result set by some field (e.g. title or author), and display the result set a screenful at a time.

Sorting is a well-understood problem. However, suppose this is a big library, and a search returns 100,000 relevant documents. Clearly the user is not going to look through all of them! In fact, the user might only look at the first couple of screens of results (say, 50-100 documents) and realise that their query was too broad, and so refine it further.

Moreover, accessing the sort key for a document requires parsing the document. True, you could extract the possible sort keys into a form where you didn't require parsing MARC (or, even worse, SGML/XML), although that would duplicate data. And besides, these are strings we're talking about. They are variable length, which makes memory and disk management difficult.

So you could try a fixed-size format. You could take, say, the first K characters from every title for some predetermined K, and store it in an array on disk, indexed by document number. Then you could first sort the documents by those string prefixes (i.e. something like a bucket/radix sort), and any documents which fall in the same bucket could then be sorted by extracting the "real" sort key from the documents.

The nice thing about this is you don't need to fully sort the result set. Because the user is paging through the set, you only have to completely sort the first few screenfuls, and just retain enough bucket information to sort the others if the user decides to page through that far.

So that's an improvement, but how do you set K? A lot of titles start with the letters "The ", and that's using 32 bits of information for very little discriminatory power. In fact, you'd probably be surprised how many periodicals are called "The International Journal of X", or similar boilerplate, and some searches are likely to return a lot of documents with similar titles just like that.

One possible solution is to use an order-preserving code. Compress all titles using that code, and store first 64 bits (or some other fixed amount) of the compressed title in an on-disk array. This has quite a few practical advantages: parts of the title which have very little discriminatory power get very short code words (so you don't waste space on irrelevant detail), you can sort by it because it's order-preserving, and the keys are fixed-length (so they're easy to manage in an efficient way).


Is Rectilinear Steiner Tree still NP-complete when points have integral coordinates?

Yes.

I suspect that you have not read the paper The Rectilinear
Steiner Tree Problem is NP-complete, by M. R. Garey and D. S. Johnson, SIAM Journal on Applied Mathematics, Vol. 32 (1977), pp. 826-834. Well, if you have, I am sorry. Well, if you have, please indicate that critical information in your question. In fact, whenever your question is based on one big theorem/one paper, it is always a good idea to inform readers here whether you have no access to or have read or are familiar with a proof or proofs of the theorem/that paper. People, or at least I, will then be able to exchange ideas with you more efficiently in a way that suit you better.

I just browsed through the proof by Garey and Johnson. It is clear that, in fact, they build their proof on the rectilinear stree problem with integral coordinates within a square of side length $n^{O(1)}$, where $n$ denotes the number of points.


First note that $eps$ is not necessarily the same on every machine, it depends on architecture and precision. Also, the definition of $eps$ is not unique in literature. Often it is defined as the difference between $1$ and the next greater number that can be represented exactly, sometimes it is half of this difference (as it is the maximal relative error). In general, if you look at a machine number with base $b$, mantissa $m$ (and exponent $e$), you can define $$eps := \frac{b^{1-m}}{2}.$$

To your example: You would probably represent $4$ normalized as $(0.10000000)_2 \cdot 2^3$. The next number $4+ \frac{1}{32}$ is then represented as $(0.10000001)_2 \cdot 2^3$, i.e. you have $m = 8$ and thus $eps = 2^{-8}$.


Identify the function call statement in the following snippet

Are you writing an interview test right now ?

__name__ is not a function. Is a special keyword used by Python and its value is ‘__main__’ if the script is run directly from terminal.
So if another script.py imports the one in the photo, the code inside the if statement won’t execute.

sys.argv

Is a list of the arguments of the script, if given any from the terminal. The reason of sys.argv[1:] is to exclude the first argument which is the file name of the script.

So you are right. The only function call statement is the main(...)

As far as for why the notorious

if __name__ == ‘__main__:’

is used, I would say for testing purposes. Imagine having a lot of .py files which import other .py files. You need to test each one separately from the other.


Can I change the input of my reductionduring the proof?

No, you may not modify $I_1$. By the time you get to Step 3, everything is determined and you might not change your instances. Say $f$ is the polytime transformation from Step 2. Then you need to show

$I_1$ is a yes-instance of $\Pi_1$ if and only if $f(I_1) = I_2$ is a yes-instance of $\Pi_2$.

If after arriving at Step 3 you notice that your $I_2$ instance does not allow you to prove the statement, then you might want to change $f$ in your Step 2, and redo Step 3.


Can we define a program by means of a walk of a graph induced by the category of types?

Consider the simply-typed $\lambda$ calculus: this is one of the simplest functional languages you can define.

It is very common to interpret it in a Cartesian closed category (CCC). Indeed, CCCs are the "ideal" categorical setting where to interpret simple types.

CCCs, being categories, admit morphisms composition and identity. Taking your definition of "walk" loosely, as a rough idea rather than a rigorous concept, I think you covered this aspect of CCCs.

However, they also allow products, which are not considered by "walking". Given $f:A\to B$ and $g:A\to C$ there is a unique morphism $\langle f,g \rangle: A\to B\times C$ satisfying a certain universal property. This is a way to craft new morphisms from old ones that "walking" does not consider.

There's even more. The main, fundamental property of CCCs is the "currying" adjunction. That is, there's a natural bijection between the set of morphisms $A\times B\to C$ and $A\to C^B$ (where $C^B$ corresponds to the functional type $B\to C$). So, given a morphism in one of this set, we can take the corresponding one in the other set. Doing this is important to interpret $\lambda x. \ldots$, and without that, we do not have a "lambda" calculus.

So, even in the simplest setting, interpreting a functional program is much more than "composing morphisms", or the proposed definition of "walking".


How to convert 010111 to decimal using only odd numbered positions while still applying the correct positional exponent?

I'm assuming positions are counted from $1$ starting from the least significant bit.

In this case you're using the exponents as if the number was 0111.
The question is asking to use the same exponents you would use for the odd-position digits of the number 010111.

To break it down, from the least to the most significant bit, the contribution to the final decimal value of each digit is:

First digit: $1 \cdot 2^0 = 1$.
Second digit: would be $1 \cdot 2^1 = 2$ but it is 0 since digits in even position are ignored.
Third digit: $1 \cdot 2^2 = 4$.
Fourth digit: ignored.
Fifth digit: $1 \cdot 2^4 = 16$.
Sixth digit: ignored.

The final result is: $16+4+1 = 21$.

Edit: Since you added that the answer should be $2$ this tells us that positions are either numbered starting from $0$, from the least to the most significant bit, or starting from $1$ from the most to the least significant bit.

In either case you would select the bits $001$ whose contribution would be $1 \cdot 2 + 0 \cdot 2^2 + 0 \cdot 2^4 = 2$.


Is there a difference between pure binary and binary?

I'm guessing here for lack of context, but I think the following distinction is reasonable.

A binary encoding is anything that maps stuff to bit strings. There are many, including two's complement, IEEE float, ASCII, and so on.

Pure binary probably refers to bland natural numbers written in base two, i.e.
if $n_{(2)} = a_k\dots a_0$ then

$\qquad\displaystyle n = \sum_{i=0}^{k} 2^ia_i$.


Find the shortest OPEN path connecting a set of 2D points (special case)

Your paths are varieties of what are often called angle-restricted paths in the literature, and exploring the literature may help with your
particular situation:

Fekete, Woeginger, 1997, "Angle-Restricted Tours in the plane."
Dumitrescu, Pach, Tóth, 2009, "Drawing Hamiltonian cycles with no large angles."
Bárány, Pór, and Valtr, 2009, "Paths with No Small Angles"

The general angle-restricted TSP (Traveling Salesman Path) problem is NP-hard, as
established in the 1997 paper, "The Angular-Metric Traveling Salesman Problem."


Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters?

Assume you have the alphabet $\{A,B,C\}$ and you want to form words of length 4.

For the first letter you have 3 choices, $A, B$ or $C$. For the second letter you have again 3 choices, $A,B$ or $C$ and so on. In total: $ 3 \cdot 3 \cdot 3 \cdot 3 = 3 ^ 4 = 81 $ possibilities.


Lower complexity bounds without mutation

See the section labelled "Negative result: you cannot avoid some slowdown, for some data structures" of https://cs.stackexchange.com/a/18266/755 for examples of problems whose solution in a functional language is inherently a bit slower than a solution in an imperative language with mutation.  One example is an array data structure; with mutation, you can achieve $O(1)$ worst-case time for both mutation and lookup, but with a functional language (with persistent data structures), you cannot.


simple question about epsilon and estimation turing machines

Suppose there exists $k>0$ such that $\lim_{n\to\infty} \left(3-\frac7n\right)=3-k$.

By the definition of a limit,
$$\lim_{n\to\infty} f(n)=L\Leftrightarrow \forall\epsilon>0,\exists N>0,n>N\implies |f(n)-L|<\epsilon$$

Here, we need to check:
$$\lim_{n\to\infty} \left(3-\frac7n\right)=3-k\Leftrightarrow \forall\epsilon>0,\exists N>0,n>N\implies \left|k-\frac7n\right|<\epsilon$$

Now, disproving this just requires a suitable choice of $\epsilon$. Consider $\epsilon=\frac k2$. We have for all $n>\frac{14}{k}$, $\left|k-\frac7n\right|>\frac k2$. So, there does not exist any $N>0$ satisfying the condition, and as  a result, no such $k>0$ can exist.


Here is the hint or outline of a proof.

Show that by mathematical induction, that $2x^2< 2^x$ for $x>7$.
Show that $\dfrac12\cdot2^x< 2^x-x^2$ for $x>7$


Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular?

The first step is figuring out the language of first thirds of $S$. Let us denote this language by $L$. A good starting point is to consider the language $P$ of prefixes of $S$, since clearly $L \subseteq P$. The language $P$ is easy to find: it is
$$
a^*ba^*ba^* + a^*ba^* + a^*.
$$
With some work, you can show that $L$ and $P$ are rather close to each other, and so $L$ is regular. Details left to you.

More generally, if $S$ is any regular language, then the language $L$ of all first thirds of words in $S$ is always regular. The easiest proof of this is via NFAs. You can take it as a challenge, or look up material on the very similar operation of taking the first half of all words in a regular language.


Doubt in the correctness of decision tree models for constructing a lower bound

The bound you're describing is that the depth of the decision tree is at least the logarithm of the number of distinct answers. This bound always holds, but is not always tight. In the case of searching an element in a list, it is tight when the list is sorted, and not tight if we don't assume anything on the list. The reason for this discrepancy is that the bound doesn't distinguish between the two cases — it is too general.

I challenge you to come up with another argument showing that the depth of a decision tree for finding an element in a list is at least $n$ (or even $n+1$, depending on how depth is defined).


Why can't we say that a Neural Network is a NP problem solver?

SGD is an algorithm, not a problem.  It is not NP-complete or NP-hard.  SGD is one approach to an optimization problem.  Some optimization problems are NP-hard; some are not.
All of your deductions start from that one incorrect assumption, so they don't actually follow.
"Neural Networks" don't have a computational complexity; they aren't a problem.


Is every algorithm on bounded resources O(1)

By definition, every algorithm (that always halts) on a finite domain has $O(1)$ running-time: pick $n_0 > \max \{ |x| \mid x \in D\}$ with $D$ the input domain of the algorithm.

However, that fact is utterly uninteresting. Asymptotics are designed to help make statements for "large n", expressed through a limit process; they are simply meaningless if the domain is bounded, or the inputs you see in practise are "small".

As a consequence, if you are concerned with finite domains you'll have to use different mathematical notions, and potentially different machine models.


What is the difference between "strict schedule" and "cascadeless schedule"?

On a cascadeless schedule a transaction $T_2$ cannot read a value $a$ if a transaction $T_1$ wrote $a$ before that and didn't commit. On a strict schedule $T_2$ also wouldn't be able to write $a$ after $T_1$ wrote it (even if it read $a$ before $T_1$ wrote it).

If you read carefully, the definition of strict says "not read or overwritten". That's the difference.

I reproduce here an example of cascadeless but not strict schedule, from the Wikipedia page on the subject:


Check for balanced parentheses in an expression in log-space

The Dyck language on any fixed number of symbols can be recognised by a marking automaton, which is a two-way finite automaton that can mark a fixed number of input tape squares.
The automaton simply uses a different mark for each type of parenthesis.
Since a marking automaton is easily implemented by a Turing machine with a fixed number of logarithmic-sized regions of the worktape forming pointers into the input, Dyck languages can be parsed in logspace.

R. W. Ritchie and F. N. Springsteel, Language Recognition by Marking Automata, Information and Control 20, 313–330, 1972.
doi:10.1016/S0019-9958(72)90205-7


lambda-calc program which halts on only one input

Well nevermind this has an easy answer.

Let $r_n = \lambda x_1 ... x_n . \lambda p . p \: x_1 ... x_n$

Note that for $m < n$, $r_n\: A_1 ... A_m$ normalizes for any normal $A_1 ... A_m$.

Then for any $f$, let $n$ be larger than the number of subterms in $f$.

$f \:r_n$ normalizes, so therefore no $f$ exists which only normalizes for a specific input.


Relationship between Kleene Star of a subset of regular language and the regular language

Of course not: Consider R1='a', R2='a|b', R3='a|b|c', for instance.


How do we make sure in Paxos that we don't propose a different value if a majority has formed?

$P2^c\implies P2^b$ since $P2^c\iff (a)\lor (b)$ and the logical statement $(a)\lor(b) \implies P2^b$ is equivalent to $(a)\implies P2^b\land (b)\implies P2^b$.

Let's consider $(a)$. If no acceptor in $S$ has accepted anything below $n$, then $P2^b$ is trivially satisfied (the implication predicate is false).

Otherwise, assume $(b)$. Then there exists a highest-numbered accepted value $(v, n)$ for some acceptor within $S$, which the proposer will decide to send as an accept request. Thus $v$ must have been chosen already, since an acceptor had it.


The middle transition fertig is the shared action so this must be ran parallel, but after this there are 2 transitions which dont have to run parallel, one is kochen and the other is essen.

Assume, we are now in the point where fertig is done by both processes and now we have 2 options, kochen and essen. We do both one after another as options: if i do kochen then the option essen is left, if i do essen, then kochen is left. I also have to do what is left to do.

So, let's say, I choose essen then go to USER back, but if I do kochen first, then I have to do essen which is the second essen in this case.


The problem is that you won't be able to verify if the certificate is legitimate as you are making certificate with assignment of variables clause by clause. To check it is legitimate you would have to traverse back on certificate tape which you won't be able to. For example let $\phi = \{ (x_1 \vee x_2 \vee x_3) \wedge (\overline{x_1} \vee x_4 \vee x_5) $. And say your certificate is {(True,False,False),(True,False,False)}. In this case you would declare that assignment makes $\phi$ True but that's not the case as $x_1$ and $\overline{x_1}$ can't both be True and to check all assignments are valid you will have to traverse back and forth on certificate tape which you can't do. Thus your approach is not correct.


Why is $A_{TM}$ reducible to $HALT_{TM}$?

Step one, don't try to argue why this TM can not work: under the assumption it does work. But then, since everything else $S$ does is possible (you have to accept that separately), the existence of $R$ certainly is "the problem".

As for understanding, the proof, there are two facts you have to check (under the assumption that $R$ exists):

$S$ is a Turing machine (i.e. its function is computable)
$S$ decides $A_{TM}$.

Arguably, 1) is clear; simulating other TMs given their indices/encodings is something TMs can do (thanks to the existence of a universal TM, which you should have seen a proof of already) and $S$ does little more. This is as close to a proof as you'll get with this form of "definition" of $S$; it's more of an idea, really.

For the second, note that $S$ always halts because $R$ always halts and

$\qquad\begin{align*}
  S\langle M,w \rangle) = 1 &\iff R(M,W) = 1 \land M(w) = 1 \\
             &\iff M(w)\downarrow \land M(w) = 1 \\
             &\iff w \in L_M \\
             &\iff \langle M,w \rangle \in A_{TM} \;.
\end{align*}$

By definition, that means that $S$ decides $A_{TM}$.

Similar arguments usually works for this kind of proof; check our reference questions and other questions tagged computability+reductions.


Given a r.e. (recursively enumerable) language, L, how many Turing machines semi-decide L?

You are correct.

One can always add redundant states to obtain different Turing machines deciding (or semi deciding) the same language. This yields countably infinite Turing machines deciding $L$ (for any decidable $L\subseteq \Sigma^*)$.


Decidability algorithm, whether substring belongs to L

On the contrary, it can be arbitrarily hard to decide if a word is in a language. Not only are there undecidable languages (such as the halting language), but there is an infinite hierarchy of undecidable languages, each one even harder than the previous one!

It also seems unlikely that an algorithm for deciding membership in a language would be easily modified to decide if every string in a language has some particular property. That's a completely different problem, requiring completely different analysis.


How do we derive the runtime cost of Karatsuba's algorithm?

"Karatsuba's basic step works for any base B and any m, but the recursive algorithm is most efficient when m is equal to n/2, rounded up."

I understood this to mean that for integers with n digits, m is the ceiling of half n (m being the exponent applied to the Base in the algorithm).  This can be seen if you simply look at the definition of the algorithm.

"In particular, if n is $2^k$, for some integer k, and the recursion stops only when n is 1, then the number of single-digit multiplications is $3^k$, which is nc where c = ${\log3}$"

I took this to mean, given n is some power of 2 (2, 4, 8, ...), the number of single digit multiplications performed is 3 * (exponent of 2).  I worked out how this conclusion was reached by writing out the tree and finding that each sub-problem involves 3 multiplications, and at the base of the recursive tree, you should have $3^{m - 1}$ sub-problems for that bottom level.  However, the -1 can be ignored as, using the properties of exponents, you can factor that out into a constant, which Big-O doesn't consider.  Therefore, if we are looking for the exponent of 2, we can get that exponent of 3 as a log relative to n, thus $3^{\log n}$, which by a law of logarithms turns into $n^{\log 3}$.  Since the computational complexity of each sub-problem by itself is a constant 7 (4 additions and 3 multiplications) independent of the number of digits in the number representation, the computation itself can be ignored in the efficiency analysis, giving us $O(n^{log 3})$


Approximation with imperfect dichotomy oracle

I found thanks to @YuvalFilmus 's advice! (if you want me to remove this answer and post it yourself, feel free to ask)
1. We find a factor 4 approximation
If we know a value r s.t. O(r/2) = True and O(r) = False, then we know that x is in [r/2, 2*r[.
And for any starting point y, while O(y) = True we multiply y by 2 until we have O(y) = False, and conversely for O(y) = False to find such a value.
By the properties of the oracle, this terminates. We have a logarithmic complexity. But when evaluating $O(y \times 2^k)$ for an integer k, we know that there is an index that separates the True values from the False. Thus we can apply binary search on this logarithmic scale to have a $\log(\log(x))$ number of evaluations of the oracle.
2. We transform a $2^{1+\frac{1}{k}}$ approximation in a $2^{1+\frac{1}{2k}}$ approximation
Suppose you know $x\in[a, b[$ with $\frac{b}{a} = 2^{1+\frac{1}{k}}$.
Take $c = a * 2^\frac{1}{2k}$.
We know that if $x \in [a, c[$, then $O(c)$ is false, and that if $x \in [2c, b[$, then $O(c)$ is true.
Thus we can eliminate one interval of ratio $2^\frac{1}{2k}$, and the remaining interval is of ratio $2^{1+\frac{1}{k}-\frac{1}{2k}}$ = $2^{1+\frac{1}{2k}}$.
3. Complexity
We make $\log(\log(x))$ calls to the oracle in the first stage, and then $i$ to get a $2^{1+\frac{1}{2^i}}$ approximation factor.
For example, if you work with integers, the stop condition is $ x * (2^{1 + \frac{1}{2^i}} - 2) < 1 $. A Taylor expansion gives us $i > \log(x) + 1$ with the first term, so $i > \log(x) + 2$ should be fine.
4. Other strategies
Like shown below, more evaluations per step could get us immediately better approximation factors than 2.
However, it requires too much evaluations, with no improvement in the worst case when the oracle is a threshold function.
Let $x_1, x_2 = \frac{r}{2}, x_3, x_4=b, x_5, x_6=2r$ be numbers in geometric progression of ratio $\sqrt2$ with $r$ found after the first stage.
We know $O(x_2) = T, O(x_4) = F, O(x_6) = F$, and we know $x \in [x_2, x_6[$. We split this interval in 4 and look at the values of $O(x_1), O(x_3), O(x_5)$. We note $?$ when a value can be True or False.
For $x\in[x_2,x_3[$, the possible values are $?, F, F$.
For $x\in[x_3,x_4[$, the possible values are $T, ?, F$.
For $x\in[x_4,x_5[$, the possible values are $T, ?, F$.
For $x\in[x_5,x_6[$, the possible values are $T, T, ?$.
If we get $O(x_1) = F$ or $O(x_5) = T$, we know a $\sqrt2$ factor approximation of x. Else, the value of $x_3 = c$ allows us to eliminate either the leftmost or the rightmost interval, which is exactly the first step of the second stage of our general strategy to transform a $4 = 2^{1 + \frac{1}{1}}$ approximation into a $2\sqrt2 = 2^{1 + \frac{1}{2}}$ approximation.


Hint: $S_l - S_r$ is the sum of $2n$ independent variables $X_1,\ldots,X_{2n}$, with $\Pr[X_i = 1] = \Pr[X_i = -1] = 1/2$.


How to make efficient path minimum queries in a tree?

You can preprocess your tree in time $O(n \log n)$ so to obtain a data that uses $O(n)$ space that can answer path-minimum queries in constant time. See "Bottleneck Edge Queries" in this paper which shows how to answer queries that ask for the edge of minimum weight in the unique path between two given vertices in a tree.
You can easily reduce your problem by splitting each edge into two edges and then setting the weight of each edge incident to a vertex $v$ of the original tree to the weight of $w$ itself.
If you are find with a solution that is easier to implement but requires $O(n \log n)$ space and preprocessing time (rather than the $O(n)$ space of the paper I liked above), and supports $O(\log n)$-time queries, then you can do  the following:
Start by constructing a LCA oracle for $T$. To do so consider an Euler tour $E = \langle u_1, u_2, \dots u_{m}\rangle$ of your tree and construct an array $A[1 \dots m]$ where $A[i]$ contains the depth of $u_i$. Here $m=2m-2$. Then construct a range minimum query (RMQ) oracle on $A$, so that the LCA $u_k$ between $u_i$ and $v_j$  with $i<j$ is such that $k$ is the index of the minimum $A[k]$ in $A[i], \dots, A[j]$.
A simple RMQ oracle is the following: for each index $i$ of $A$, and for each $j=0, 1, \dots, \lfloor \log m \rfloor$, store in $B[i, j]$ the index $k$ of the minimum $A[k]$ between $A[i], \dots, A[i+2^j-1]$. All the entries of $B$ can be found in $O(n \log n)$ time since, for $j>0$, $B[i,j]$ is either $B[i, j-1]$ or $B[i + 2^{j-1}, j-1]$.
The answer to a RMQ query $(i,j)$ is then the index of $A$ with the minimum value among the two indices $B[i, \Delta]$ and $B[j- \Delta, \Delta]$, where $\Delta=\lfloor j-i+1 \rfloor$.
We are now able to find the LCA $w$ of two vertices $u$ and $v$ in constant time. Then your problem reduces to the one of finding the vertex of minimum weight in two ancestor-descendant paths, namely those between (i) $w$ and $u$, and (ii) $w$ and $v$.
This can be done using a trick similar to the previous one: For each vertex $z$ at depth $d$ maintain $\delta = \lfloor \log d \rfloor$ values $M[z, 0], \dots, M[z, \delta]$, where $M[z, j]$ is the minimum among the weights of the vertices $z= z_1, z_2, \dots, z_{2^j}$ encountered by walking from $v$ towards the root for $2^j - 1$ steps. Moreover, for each vertex $v$, we explicitly store the $O(\log n)$ vertices $z_{2^j}$.
As before, all the values $M[z,j]$ can be found in $O(n \log n)$ time and a path query on an ancestor-descendant path of length $L \ge 2$ can be answered by letting $\ell = \lfloor \log L \lfloor$ and selecting the minimum among $M[z, \ell]$ and a recursive query for the path of length $L - 2^\ell$ that ends with $z_{2^\ell}$.
The query time can actually be improved to $O(1)$ if you additionally compute a long-path decomposition of your tree. The long path decomposition is defined recursively and is obtained by selecting the longest root-to-leaf path $P$, deleting (the edges and vertices of) $P$ from the tree and returning the union of $P$ with all the long-path decompositions of the trees in the resulting forest.
This decomposition can be found in $O(n)$ time and has the following property: given a vertex $v$, the (unique) path $P_v$ that contains $v$ has a lenght |P_v| not smaller than the height of the subtree rooted in $v$.
Let $P_1, P_2, \dots$ be the paths of the decomposition and for each $P_i$ construct an array $P'_i$ by extending $P_i$ by $|P_i|$ edges towards the root, and writing down the vertex weights along this extended path.
Build a RMQ oracle on each of the obtained arrays and, for each $v$, keep a reference to the position of $v$ in the (unique) array associated with the path $P'_v$ such that $v$ is contained in $P_v$.
The total size of the arrays is $O(n)$ and hence the total size of the  RMQ oracles is $O(n \log n)$.
A query on an ancestor-descendant path can now be answered in $O(1)$ time by first looking at $M[v, j]$ and a then querying the oracle associated with $P'_{z'}$, where $z'=z_{2^\ell}$.
This is because $L-2^\ell < 2^\ell$ (by the choice of $\ell$), showing that $P_{z'}$ has length at least $2^\ell-1$, and hence all the remaining $L-2^\ell$ proper ancestors of $z'$ (that were not already considered in $M[v, j]$) must be in $P'_{z'}$.
There is a great paper explaining this technique that combines the lookup table $M$ with this extended path-decomposition.
With some additional work you can even get rid of the $O(\log n)$ factor in the space complexity.


Introductory explanation of the Big-Oh properties

Let's start by considering the positive numbers. There is a notion of order:
$$ x \leq y. $$
We can add and multiply numbers, and the order relation respect these operations:
$$
x \leq y, z \leq w \Longrightarrow x + z \leq y + w, xz \leq yw.
$$
Big O notation is very similar. We consider, for simplicity, functions which accept a natural number as input, and output a positive real. We define an order relation:
$$
f = O(g) \text{ iff there exists } C > 0 \text{ such that } f(n) \leq Cg(n) \text{ for all } n.
$$
(The funny notation $f = O(g)$ is just a notation for an order relation. Sometimes $f \ll g$ is used instead, but this is not common in computer science.)
This is similar to what we had above, with two important differences:

Since we have a function rather than a single value, we need the inequality to hold for all inputs.

We put in the extra constant $C$. This has the effect of identifying functions which differ only by a constant factor.
In more details, if $Af(n) \leq g(n) \leq Bf(n)$ for all $n$ then $g$ is "equivalent" to $f$ in the sense that $f = O(h)$ iff $g = O(h)$ and $h = O(f)$ iff $h = O(g)$.

The big O order relation also respects addition and multiplication:
$$
f = O(g), h = O(k) \Longrightarrow f + h = O(g + k), fh = O(gk).
$$

For positive numbers, we have not only $\leq$ but also $\geq$. These are related by
$$ y \geq x \text{ iff } x \leq y. $$
The relation corresponding to $\geq$ for functions is $g = \Omega(f)$, defined by
$$
y = \Omega(x) \text{ iff } x = O(y).
$$
This order relation also respects addition and multiplication.

What happens if $f = O(g)$ and $f = \Omega(g)$? When this sort of situation happens in the universe of numbers, that is when $x \leq y$ and $x \geq y$, then the two numbers are equal: $x = y$. In the case of functions, we don't get equality, but rather the notion of equivalence that was mentioned above: $Af(n) \leq g(n) \leq Bf(n)$ for some positive $A,B$. In this case we write $f = \Theta(g)$.
You can think of $f = \Theta(g)$ as an analog of equality. Indeed, it is possible to quotient by this equivalence relation and work with functions "up to constant factors", but there is no need to understand this point of view when working with asymptotic notation. It suffices to understand that if $f = \Theta(g)$ then, for the most part, $f$ and $g$ are interchangeable.
(They are not interchangeable when appearing in the exponent: for example, $n^2$ and $n^3$ don't have the same asymptotic rate of growth, although $2 = \Theta(3)$. They are also not interchangeable if appearing at the base of a non-constant exponent: $2^n$ and $3^n$ have different rates of growth.)
An important special case is $Cf = \Theta(f)$ (for $C > 0$). That is, in most cases $f$ and $Cf$ are interchangeable. In other words, asymptotic notation hides constant factors. This is one of the advantages of big O notation.

Big O notation satisfies the following peculiar property:
$$
f + g = \Theta(\max(f,g)).
$$
This useful property allows us to simplify expressions: for example, $n^2 + n = \Theta(n^2)$. Generalizing this, if $f$ is a degree $d$ polynomial, then $f = \Theta(n^d)$.


Show this function is partially computable

Since $B$ is a computable predicate, there is one procedure that computes it. We can call this procedure in any point of our program.

K <- k
i <- 0
LOOP
    RESULT <- B(i)
    IF RESULT != 0 GOTO TRUE
        GOTO ELSE
        TRUE
        K<-K-1
    ELSE
    IF K != 0 GOTO KEEP_GOING
        GOTO BREAK
    KEEP_GOING
    i <- i+1
GOTO LOOP

BREAK
RETURN 1

You will need to substitute the instruction K <- K-1 by an appropriate procedure.

To understand what is going on, we are looping through every natural number and checking whether it satisfies the predicate $B$, keeping a counter that diminishes every time we find one such number. So when the counter K reaches zero we know that the function should return 1, and we proceed to do exactly that.


Examples for lower bounds proof except sorting

Here are some examples:

Finding an element in a sorted list takes time $\Omega(\log n)$ in the RAM model.
Implementing a disjoint sets data structure requires an amortized $\Omega(\alpha(n))$ operations in the cell probe model.
Determining whether the input string is a palindrome requires $\Omega(n^2)$ operations on a single tape Turing machine.

There are many others.


That website uses a different notation than what you assumed. This would be the correct input:

S -> A S | b.
A -> S A | a.

You entered AS (and SA) which it does not recognize as A followed by S, but as a single nonterminal named AS.

With that input it correctly says that the language is not $\text{LL}(1)$.


$c=\frac{1}{2}$ is enough for large enough $n$.

Indeed, there are positive integers $n_1$ and $n_2$ such that

$$\begin{eqnarray*}
n &\ge& n_1 \implies -\frac{1}{2} < \log_2 \left ( 1 - \frac{1}{n} \right ) \\
n &\ge& n_2 \implies -\frac{1}{2} < -\frac{1}{n} \log_2 (n - 1).
\end{eqnarray*}$$

Rewriting $$cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$$

as

$$
cn \left [ \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c} \right ],
$$

we have

$$n \ge \max(n_1, n_2) \implies -2 + \frac{1}{c} < \log_2 \left ( 1 - \frac{1}{n} \right ) - \frac{1}{n} \log_2(n-1) + \frac{1}{n} - 1 + \frac{1}{c}.$$

But $-2 + \frac{1}{c} \ge 0 \iff c \le \frac{1}{2}$.


$p(n)$ is just a polynomial that indicates the length of the output of the function $g$, as a function of the length of the input.  Imagine that it's something like $27n$ or $2n^2$, and then read through the proof and you'll see how it works.

I didn't see any requirement to compute an inverse of $p(\cdot)$ in that proof.  I'm not sure where you got that from.  But anyway, if you wanted to invert it, any such polynomial is monotonic and can be easily inverted, e.g., by using binary search or using Newton's method.


Why do ACLs (access control lists) have better persistence than capabilities?

There's a lot of confusion and regrettable writing out there surrounding the comparison between ACLs and capabilities.  Often, when books make a comparison, they are referring to one particular type of ACL system vs one particular type of capability system, but the difference isn't always fundamental.  So, if you see some comparison like this, I wouldn't worry about it too much.

In particular, capabilities can certainly have equal persistence to ACLs.  As an extreme example: If you have a persistent store and all applications are persistent (so that when the machine reboots, all applications are relaunched with the same state as before the crash), then capabilities will be persistent.  You can achieve the same level of persistence.  Historically, people who have built capability systems in the past might not have built them that way (usually), but that isn't always a guide to what is or isn't fundamental.

So, I would take issue with the book's claim that ACLs have better persistence than capabilities.  That's not necessarily true; it'll depend on specifically how the ACLs and capabilities are implemented by the system and used by applications.

(Also note that so-called "POSIX capabilities" are a bit of a misnomer and it's not clear we should really call them capabilities.)

I do realize that this might or might not help you if you're taking a course, as depending on the instructor, the instructor might expect you to go by what the book says and might not appreciate other perspectives (or, more benignly, want you to understand things from the textbook's perspective before taking a broader view).


Why Convolutional codes is easy to factor/handle the uncertainty of a bit being a 0 or a 1 into the decoding?

An important idea with convolutional codes is that the output sequences of bits (of the convolutional coder) consists of sequences of bits that are correlated with one another, i.e., not independent. Hence, in the receiver side, you know that, given what the convolutional coder is, the sequence of bits can only be some sequences, out of the big set of possibilities. Imagine a big space (say, it may be easier to imagine in 2 or 3 dimensions, then just imagine it gets extended to more dimensions), that has many points in it with integer coordinates, e.g., (1,0,1,1,0), but only only a few of these are allowed possibilities. So you look for the maximum likelihood sequence, which you could think of as the allowed point with the highest probability of having been the input to the convolutional coder.

Having soft-decision decoding, helps when you get to the stage of decoding the sequence of bits, as now, you have the probabilities of each bit being 1 or 0 (by itself, apart from the sequence), which can be fed into the computation of the likelihood of each sequence in the maximum likelihood sequence detection.

A simple example to illustrate: imagine if there are two allowed sequences coming out of the convolutional code: 10 and 01. Now, the receiver gets a sequence that it thinks is 11, but the first 1 only with high certainty (a very likely 1, let's say) whereas the second 1 only with low certainty (maybe 1, if we have to decide between 0 and 1, we say 1). This information helps to decide that the sequence was probably 10 rather than 01. Whereas, with hard decisions, you have 11 and both 10 and 01 are equally likely (e.g., same Hamming distance).

Why is it easy to handle the uncertainty of the bit by bit decisions? This is merely a statement that the decoding algorithms like the Viterbi algorithm, are fundamentally designed to accept the uncertainty values (probabilities) of the bit by bit decisions, as inputs. You could imagine some other algorithms where this is not true. But it is very natural and easy with such maximum likelihood sequence detection algorithms like the Viterbi algorithm.


What is context free grammer of $L = \{w: n_c(w) \ne n_a(w) + n_b(w)\}$

$\Sigma = \{a,b,c\}$. Consider the two cases:

$n_c(w) > n_a(w) + n_b(w)$: The idea is to create one more $c$ for each $a$ or $b$ produce in the word:
\begin{align}
             S_c \rightarrow aS_cS_c | bS_cS_c | c
    \end{align}
$n_c(w) < n_a(w) + n_b(w)$: In this case, we can produce as many $c$'s as $a$ and $b$ combined + 1.
\begin{align}
             S_{ab} \rightarrow aS_{ab} | bS_{ab} | cS_{ab}S_{ab}|a|b
    \end{align}

The grammar for the required language would be : $S \rightarrow S_c | S_{ab}$.


What is the purpose of erasing a type application to a term-application in parametric polymorphism?

Q1

Is the purpose of "erase a type abstraction to a term-abstraction" to prevent the body of a type abstraction from being evaluated?

Yes.

  We can repair this discrepancy by introducing a new form of erasure appropriate for call-by-value evaluation, in which we erase a type abstraction to a term-abstraction

Q2

What is the purpose of erasing a type application to a term-application by adding dummyv?

The erasure introduces a term-abstraction into a type-abstraction:

eraseᵥ(λX. t₂) = λ_. eraseᵥ(t₂)

So the erasure needs a term-application instead of a type-application. An argument of the term-application can be any untyped value because it will be discarded, so for example unit.

Q3

What is the evaluation rule for an application when the argument is unit?  (I can't find it in the section for type Unit.)

The unit value unit is a value. Therefore we can use (E-APPABS) for an application.

(λx:T₁₁. t₁₂) v₂ ⟶ [x ↦ v₂] t₁₂    (E-APPABS)


Your problem, NAE-HORN-SAT is $NP$-complete. Monotone NAE-SAT is $NP$-complete and it is a special case of your NAE-HORN-SAT. Literals in monotone SAT formula are either all positive or all negative.

Take any instance of Monotone NAE-SAT problem (all its literals are negative) then this formula is an instance of NAE-HORN-SAT problem.


Yes.  Both bounds are valid.  There's not much difference between the two bounds.

There are certainly at most $mn$ items in the queue at any time, as there are only $mn$ possible items.  Consequently, the running time is at most $O(mn \log(mn))$.

By analyzing how BFS visits nodes and the size of the "fringe", one can show that the size of the fringe is most $m+n$.  In particular, the fringe is a path that goes from somewhere on the top of the matrix to somewhere on the left of the matrix, by going only down, left, or diagonally down-and-left (but never right or up).  Thus the fringe can include at most $m+n$ cells.  This means that at every stage, the size of the heap is at most $m+n$, so $O(mn\log(m+n))$ is also a valid upper bound on the running time.

These two bounds are pretty close, so either is a reasonable upper bound on the running time.

Caveat: there are multiple heap data structures, with different running times for the heap operations.  This answer assumes you are using a heap data structure where inserting into a heap containing $k$ items can be done in $O(\log k)$ time.


If the edges in the graph only represent valid moves between certain positions, using Dijkstra's would work just fine. However as the graph is unweighted it would be overkill. A simple breadth-first-search will give the optimal answer.


see this link:

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

It first picks variable "O" and then tests "O" with all of it's legal values "i" to see the number of reductions on "O"'s neighbors "N". It adds all of them. and picks an "i" that causes less reductions:

   sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
   For i from 0 to 9:
     plug "o=i" into the constraint formulas
     For each neighbor "N" of "o" in the constraint graph:
       sums[i] += the number of values remaining for "N"

It picks "i" so that:

sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}

I hope This can help you find your answer!


Does polynomial time reduction from CNFFAL to CNFSAT is also polynomial time reduction from CNFSAT to CNFFAL?

No, $CNFFAL\le_P CNFSAT$ doesn't appear to imply $CNFSAT\le_P CNFFAL$, as far as we know.

As you say, we know that $CNFFAL\le_P CNFSAT$ is true.  However, $CNFSAT\le_P CNFFAL$ is true if and only if $P = NP$.

Consequently, the claim $CNFFAL\le_PCNFSAT\implies CNFSAT\le_PCNFFAL$ is logically equivalent to the claim that $P=NP$.  There is no known proof that $P=NP$ (and many would consider it surprising if that is true).

I didn't understand why you think the implication does hold.  I couldn't quite follow your reasoning.  The notation $\beta$ is never explained clearly (I don't know what you mean by "the boolean formulated generated by a NTM"; NTMs don't generate boolean formulas, so that would need to be defined more clearly). It's hard to know what you might be thinking, but if I were forced to speculated, I'd guess that the flaw in your reasoning might have something to do with the situation where $\alpha$ is both satisfiable and falsifiable.  Then it's true that $NTM_{CNFFAL}$ has both an accept path and a reject route, but so what?  It's not clear why that would imply anything interesting.


Describing the language formed by a particular grammar

There doesn't appear to be a simple description for the language generated by this grammar, but here's what happens.

From $E$ we have the productions $E\rightarrow E(E)\mid\epsilon$. The first few strings generated from $E$ are:
$$\begin{align}
\epsilon &\quad E\Rightarrow\epsilon\\
(\:) &\quad E\Rightarrow E(E)\stackrel{*}{\Rightarrow}(\:)\\
(\:)(\:) &\quad E\Rightarrow E(E)\Rightarrow E(E)(E)\stackrel{*}{\Rightarrow}(\:)(\:)\\
(\:(\:)\:) &\quad E\Rightarrow E(E)\Rightarrow E(E(E))\stackrel{*}{\Rightarrow}(\:(\:)\:)
\end{align}$$
It's not too hard to show inductively that $E$ generates all and only the strings of balanced parentheses, i.e., the strings over $\{(\;,\, )\}$ that could appear in a legal arithmetic expression. Let $\mathcal{B}$ denote this language.
From the production $B\rightarrow (E)$ we see that $B\stackrel{*}{\Rightarrow}(\mathcal{B})$, namely any string of balanced parentheses enclosed in $(\,)$.
From the productions $L\rightarrow LE\mid L\:(\:\mid\epsilon$. It's not too hard to see that $L$ generates all strings over $\{E,\,\,(\,\}$. Call this language $\mathcal{L}$. In simple terms, $L$ generates all strings of balanced parentheses interleaved with an arbitrary number of left parens.
From $N\rightarrow\,(\,L\,]$ we see that, similarly to step (2), we have $N\stackrel{*}{\Rightarrow}(\,\mathcal{L}\,]$
Finally, it's not too hard to see that from the productions $G\rightarrow GB\mid GN\mid\epsilon$, that $G$ generates all strings over $\{B,N\}$, so we have that the language of this grammar will generate all strings made from the concatenation of terms of the form $(\mathcal{B})$ and $\:(\mathcal{L}\:]$ in any order.

For example, a string generated by the grammar is $((\:)(\:)((\:]\,(((\:)(\:)))$, where I've separated the $N$ and $B$ substrings for clarity.

As I said at the start, not pretty.


It is trivial that $P$ is contained in $BPP$ and that $P$ is contained in BPP. There are of course, many consequences of resolving both of these questions (they wouldn't be major open problems if that weren't the case).  There is an important relationship between resolving 1 and resolving 2: From the Sipser-Lautemann theorem https://en.wikipedia.org/wiki/Sipser%E2%80%93Lautemann_theorem it follows that if $P = NP$, then $P=BPP$.  Of course, we strongly believe that $P \neq NP$, and that $P = BPP$, so this isn't a direction of reasoning that is likely to be actually useful by itself.


Your approach will work.  There are no hard and fast rules in micro-op scheduling.  The number of micro-ops that can be executed in parallel depends on the internal organization of the CPU. Clearly, we cannot reload the program counter (PC) until we save its contents, but there is nothing stopping us from saving its contents on the leading of the clock signal and loading new contents on the trailing edge.


If I understand your description correctly, you are looking for a dominating set.


The idea of the reduction you give in your question is the following:

I) If $\langle M,w\rangle \in A_{tm}$, then $L(M')=\Sigma^*$.
II) If $\langle M,w\rangle \notin A_{tm}$, then $L(M')=\{10\}$.

thus, for any $w$, $\langle M,w\rangle \in A_{tm}$ iff $\langle M',w\rangle \in S_{tm}$.
In case (I), for any $w\in L(M')$ also $w^R\in L(M')$ hence $\langle M',w \rangle S_{TM}$ for any $w$. For case (II), there is no $w\in L(M')$ such that $w^R\in L(M')$ as well, thus for any $w$, $\langle M',w \rangle S_{TM}$.

Now for your question about accepting "10" no matter what: Assume we avoid this step. Then, in case (II), $L(M')=\emptyset$, hence $\langle M',w\rangle \in S_{tm}$ for any $w$, since the condition on $w,w^R$ vacuously holds. Now the mapping cannot map inputs  $\langle M,w\rangle \notin A_{tm}$ to inputs outside $S_{TM}$ (since none exists).

The value "10" is arbitrary. Any other non-palindromic string will do.


Removing $\epsilon$ transitions in a NPDA

This effect I would not consider this a "halting problem" but there is a point here. A pushdown automaton can end its computation in an unbounded sequence of $\varepsilon$-moves. This behaviour can be avoided for general PDA, indeed. For each PDA there is an equivalent PDA without $\varepsilon$-moves. This is equivalent to Greibach Normal Form for grammars.

For deterministic PDA, DPDA, the situation is different. We would like to avoid this unbounded behaviour, in particular for the construction of the complement of the language of the DPDA. As you might know DPDA are closed under complement. Quite involved constructions can avoid infinite computations, but we cannot avoid $\varepsilon$-moves.

The language $\{ a^mb^nc^n \mid m,n\ge 1\} \cup \{ a^mb^nd^m \mid m,n\ge 1\}$ can be accepted by a DPDA but it has to use  $\varepsilon$-moves.


How to convert $(0.11001100...)_2$ to a decimal number

Classical formula for proper fraction is
$$(0.a_{-1}a_{-2}a_{-3}\cdots)_2 = \left(\sum\limits_{k=1}^{\infty}\frac{a_{-k}}{2^k}\right)_{10}$$
Where for $a_{-k}$ we have $k \in \mathbb{N}$ and $a_{-k}\in \{ 0,1\}$.  As you see for indexing is taken negative numbers.
In your example
$$(0.11001100...)_2 =\left( \frac{1}{2^1}+\frac{1}{2^2}+\frac{1}{2^5}+\frac{1}{2^6}+ \cdots\right)_{10}$$


Definition of deterministic pushdown automaton

Yes, this is an example of an informal explanation that is not quite true.

A PDA is deterministic if (at any moment) it can make at most one legal computational step. This is a local property, a condition on a single step, and not on a computation.

The statement "If only one computation exists for all accepted strings" is a global property, a statement on all computations on a given string.

Let me give an example where the two concepts differ. The language of all (even length) palindromes over $\{a,b\}$ is context-free. It is accepted by a PDA in the obvious way. Start copying the input to the stack, guess the middle, then check whether the rest of the input matches the first part read (in reverse), finally accept on the empty stack. This automaton has only one accepting computation on each palindrome, but certainly is not deterministic.

But here I have argued that "only one accepting computation" is not the correct statement, where Wikipedia does only insist on a single computation (without the condition of acceptance). So is Wikipedia right after all? Unfortunately, no. The problem is in the $\varepsilon$-transitions. It is quite legal for a deterministic PDA to have the possibility of making several $\varepsilon$-moves before and after acceptance, it may even loop. That means many accepting computations on a fine deterministic PDA. It is also the reason that some proofs on PDA need just some extra care.

You may now edit Wikipedia to correct this mistake!


Closed-form solution to recurrence equation

Define
$$
\begin{align*}
A(x) &= \frac{1}{x^2} + 1 + x + x^3, \\
B(x) &= \frac{x^3}{1-x^2} + \frac{x^2}{(1-x^2)^2} - \frac{1}{x^2} - 1 - 2x^2 \\ &=
-\frac{1}{x^2} -1 - x^2 + \sum_{m=0}^\infty x^{3+2m} + \sum_{m=0}^\infty (2+m) x^{4+2m}.
\end{align*}
$$
Then the generating series $F(x) = \sum_{n=0}^\infty f(n) x^n$ satisfies the identity
$$ F(x) = A(x) F(x^2) + B(x), $$
and so in some sense is given by the "formula"
$$
F(x) = B(x) + A(x) B(x^2) + A(x) A(x^2) B(x^4) + A(x) A(x^2) A(x^4) B(x^8) + \cdots.
$$
Unfortunately, this formula holds only in the sense of analytic continuation.

If we use Dirichlet series instead of ordinary generating series, we can probably compute the asymptotics of the sequence, along the lines described here. We leave that as an exercise to the reader.


Must you work with all qubits in a circuit when applying a gate?

You can apply a quantum gate on any subset of the qubits, not affecting the rest.

This can be formalized as evolving certain qubits via $U$ while the other qubits evolve via $I$, thus the joint unitary is $U \otimes I$.


Determining if given languages are regular or recursively enumerable

Your intuition is entirely correct; this solution is nonsense. $L_1$ isn't a regular language; it's not even a decidable language, by Rice's Theorem, and also not recognizable (aka recursively enumerable).

$L_2$ is in fact recognizable. The following algorithm recognizes it:

  Take an encoded Turing machine $M$ as input. First simulate it on every input of length ≤ 1 for 1 step, then on every input of length ≤ 2 for 2 steps, and so on. Keep track of how many distinct inputs it's ever accepted. If this number ever exceeds 2016, return True.

But as it turns out, none of this matters to the actual problem. Note that (C) is taking the union of a language with its complement, and the union of any language with its complement is $\Sigma^*$. This language is regular, thus decidable, thus recognizable. So the correct answer is (C).

EDIT: Of course, the intersection of a language with its complement is $\varnothing$, which is also regular, thus decidable, thus recognizable. So (B) is also true.


Disjoint paths of length at most L and the number of nodes to remove to vanish this property - Inequality

Hint: Suppose that $P_1,\ldots,P_t$ are internally disjoint $(s,t)$-paths of length at most $L$. Show that you have to remove at least one vertex from each path to make the distance from $s$ to $t$ larger than $L$.

When $L = |G|$, the classical Menger's theorem states that equality holds.


Find all intervals that overlap with a given interval

I believe that interval trees offer a solution to your problem.  Basically, you store your intervals in the interval tree data structure; then, to find all intervals that overlap with $[t_0,t_1]$, you do a query into the interval tree.  This should solve your problem and run faster than $O(n)$ time.