Resulting complexity class for allowing two passes over witness in NL? I know that when an NL Turing machine is allowed to go back and forth freely, the resulting class of problems solvable on it is NP.

But limit of two passes over the witness tape, does not seem to add much power to the NL machine, if at all.

I am stuck on this problem. What is the resulting complexity class? Is it still NL? How do I prove this?

Any finite number of passes will still give you NL. Here is why two passes give you NL — the general case is very similar. You can guess the state of the work tape after the first pass and them simulate the two passes in parallel. In the end you verify that the state of the work tape after the first pass in indeed what you guessed earlier.


Why did the concept of "write-protecting" not carry over from floppy disks to USB memsticks and especially external USB HDDs? Many times, I've wished to plug in my backup hard disks into my PC without the risk of any of the data being deleted, overwritten, or modified in any manner. Purely for "inspection" and copying over certain files from it.
But, unlike on the old floppies, there's just no hardware switch anywhere to enable "read-only" mode, or "write-protected mode". Why?
This very simple, mechanical thing was a thing back then, but later, "we" decided that it was unnecessary?

I'm not entirely sure that this question is on topic, but nonetheless, I suspect it has a simple answer.
Physical write protection mechanisms predate floppy disks. At my school holiday job in the 1980s, my desk had a drawer full of write rings for reels of 9 track tape. If the ring is in place, you can write to the tape.

There are certainly flash devices with physical write protection mechanisms. Many older USB drives have them. Memory Stick and SD both have a write protection lock. You can see it on the left-hand side of an SD card.

Micro SD cards don't have them because there's no way to effectively make them "micro". And I suspect that's the main reason why they went out of vogue. Once it became unimportant for one removable medium, many of the rest followerd.
The history of storage is about maximising speed, and minimising size and price. Adding a write protection lock adds to both size and price when devices are very small.
In addition, moving parts wear out faster than devices with no moving parts. Unlike disks or tape, flash memory has no moving parts by default. Adding a write protection lock means adding a moving part, which effectively shortens its usable life.


How can an artificial neural net change the sign of a weight? My neural net is having trouble switching the sign of a weight. The issue is that the deltas applied to the weight are proportional to that weight, so when it gets closer to zero, the deltas become smaller and are never sufficient to get it past that point. I tried adding a momentum term with 5% of the previous iteration contributing to the current iteration without success.

In my example I have a very simple neural net with one input and one output and no hidden layer. The transfer function in the neural net is a sigmoid, and the function I am trying to learn is also a sigmoid. Specifically: $y = S(10 x - 5)$ where S is the sigmoid function. The neural net gets to a point where its internal weights are essentially generating a function very close to $y = S(2x + 0)$. At this point it gets stuck because the fitted function is sometimes above and sometimes below the desired function, but the weight on $x$ needs to go up and the weight on the constant term needs to go down. I ran it for 1,000 epochs and 100,000 epochs and it stays in the same place. The initial weights were 0.6 and 0.2, so it made improvements over that.

How can a net get over this hump? Should I not be scaling the weight delta by the weight value?

Here's the reference I'm using for computing the weights for back-propagation.  I am using a learning rate of 0.05 and apply the deltas after each training example.  The x-values (input) used in training are 0.00, 0.01, 0.02, ... 0.99, 1.00.  I always play them in order.

Thanks for your help.

Note: I originally posted this on stack overflow and was directed here.

Your problem stems from the fact that the equations in the link you provide refer to linear neural networks. Your network is not linear, as it has a sigmoid activation function. So you need to include its gradient in weights correction. Wikipedia explains how to do it pretty well. Here is an example Python script, which learns your target function in 1000 epochs achieving average error of order $10^{-3}$ in exactly the same conditions as you describe. Increasing the number of epochs makes the error smaller.

Note: this is NOT a recommended implementation of a neural network - just a demonstration script written on a whim.

import math

def sigmoid(x):
    return 1.0 / (1.0 + math.exp(-x))

class Network:
    def __init__(self, w, b):
        self.w = w
        self.b = b

    def __call__(self, x):
        return sigmoid(self.w * x + self.b)

    def propagateError(self, x, error, output):
        dEdW = error * output * (1 - output) * x
        dEdB = error * output * (1 - output)

        self.w += 0.05 * dEdW
        self.b += 0.05 * dEdB

def target(x):
    return sigmoid(10 * x - 5)

n = Network(0.6, 0.2)
# Training
for it in range(1000):
    for i in range(100):
        x = 1.0 * i / 100
        output = n(x)
        t = target(x)
        error = t - output
        n.propagateError(x, error, output)
# Testing
te = 0
for i in range(100):
    x = 1.0 * i / 100
    output = n(x)
    t = target(x)
    error = t - output
    print("Desired:",t)
    print("Actual:",output)
    print("Error:",error)
    te += error
    print("---")

print("Average error:",te/100.0)

Output:

('Desired:', 0.0066928509242848554)
('Actual:', 0.012425919415559344)
('Error:', -0.005733068491274489)
---
('Desired:', 0.007391541344281971)
('Actual:', 0.013550016530277079)
('Error:', -0.006158475185995108)

...

('Desired:', 0.9918374288468401)
('Actual:', 0.9855607114050042)
('Error:', 0.006276717441835888)
---
('Desired:', 0.9926084586557181)
('Actual:', 0.9867575913715647)
('Error:', 0.005850867284153405)
---
('Average error:', -0.0013496485567271077)


Why do computers keep old cache? I cleaned up my computer and found 50GB of old cache on it and it made me wonder, why do computers keep old cache files?

The cached data might be needed again in the future and keeping it doesn't cause any particular performance problem, so you may as well keep it until you need the space for something else.


Which of the following problems can be reduced to the Hamiltonian path problem? I'm taking the Algorithms: Design and Analysis II class, one of the questions asks:

  Assume that P ≠ NP. Consider undirected graphs with nonnegative edge
  lengths. Which of the following problems can be solved in polynomial
  time?

  Hint: The Hamiltonian path problem is: given an undirected graph with
  n vertices, decide whether or not there is a (cycle-free) path with n
  - 1 edges that visits every vertex exactly once. You can use the fact that the Hamiltonian path problem is NP-complete. There are relatively
  simple reductions from the Hamiltonian path problem to 3 of the 4
  problems below.

  For a given source s and destination t, compute the length of a shortest s-t path that has exactly n - 1 edges (or +∞, if no such path
  exists). The path is allowed to contain cycles.
  Amongst all spanning trees of the graph, compute one with the smallest-possible number of leaves.
  Amongst all spanning trees of the graph, compute one with the minimum-possible maximum degree. (Recall the degree of a vertex is the
  number of incident edges.)
  For a given source s and destination t, compute the length of a shortest s-t path that has exactly n - 1 edges (or +∞, if no such path
  exists). The path is not allowed to contain cycles.

Notice that a Hamiltonian path is a spanning tree of a graph and only has two leaf nodes, and that any spanning tree of a graph with exactly two leaf nodes must be a Hamiltonian path. That means that the NP-Complete problem of determining whether a Hamiltonian path exists in a graph can be solved by finding the minimum-leaf spanning tree of the graph: the path exists if and only if the minimum-leaf spanning tree has exactly two leaves. Thus, problem 2 is NP-Complete.

Problem 3 is NP-Hard; here is a paper that proves that.

That means, between 1 and 4, one is NP-Complete, another is in P. It seems like problem 4 reduces trivially to the the Hamiltonian path problem, but I'm not able to understand how having a cycle makes it solvable?

Problem 1 can be solved in polynomial time. Here is a simple algorithm to compute it in $O(n^2 + nm)$ (it can probably be done faster).

This can be solved in a dynamic programming style. If we find the shortest length $k$ path to all nodes from source $s$, then we can easily find the shortest length $k+1$ path to all nodes from source $s$. Let $d_k(v)$ be the length of the shortest $k$-length path to node $v$ from source $s$. We have:

$$d_{k+1}(v) = \min_{u\ \in\ adj(v)} \ d_k(u) + w(u,v)$$

Where $d_0(s) = 0$ and $d_0(v) = \infty$ if $v \neq s$. Then we must simply iterate over all $k$ and compute the necessary values.

set d(s) = 0
set d(v) = infty for all v != s
for k in 1, 2, ..., n-1 do:
  for all nodes v do:
    set dp(v) = infty
    for all nodes u adjacent to v do:
      set dp(v) = min(dp(v), d(u) + w(u,v))
  set d = dp
return d(t)

Note that dp is just an intermittent variable so that $d_k$ is correctly computed on $d_{k-1}$ rather than accidentally overwriting $d_{k-1}$.

The two inner for loops take $O(n + m)$ and the outer takes $O(n)$. Overall this algorithm takes $O(n^2 + nm)$.

The reason for this speed-up is precisely what Peter said. We do not need to keep track of intermediate nodes in order to prevent cycles, we simply keep going without worry of cycles at all. If we needed to keep track of intermediate nodes then it is not necessarily the case that $d_{k+1}(v) = \min_{u\ \in\ adj(v)} \ d_k(u) + w(u,v)$. It may end up being that case that we would actually not use $d_k(u)$ to compute $d_{k+1}(v)$ because there may be a slightly longer path to $u$ that actually allows us to use edge $(u,v)$. This creates a combinatorial explosion in terms of what we must check and remember.


purpose of supercomputers Last fall I went on a tour of the Blue Waters supercomputer at the University of Illinois.  I asked whether anyone ever used the entire computer.  I was told that it was always working on multiple projects.  That made me wonder about the usefulness of supercomputers.  Perhaps Blue Waters is unusual in that it has to be shared by industry and the university - I don't know.  I assume there's some overhead in managing the processors and memory of a single supercomputer.  Would it be more cost effective to build smaller computers?  Can anyone help me to understand the value of supercomputers?  Or is it that sometimes they are dedicated to single projects?

A typical job on Blue Waters is using about 10% of the machine and consumes a total of 75 node hours.  Blue Waters has about 27500 nodes, so that means some of those "75 node hour" jobs are running in just a couple of minutes.  That allows scientists to use the machine somewhat interactively.  (You can see the moving averages here: http://xdmod.ncsa.illinois.edu/#tg_usage:group_by_Jobs_none)

Supercomputers are just large collections of smaller computers.  The main reason we collect them together in one place is that we can share the cost most efficiently that way.  You are trying to create a computer that can do a lot of work, and for which the total cost of ownership (the total cost of the computer, the power, and the maintenance), is minimized over the lifetime of the computer.

There are several factors involved in the total cost of ownership: The cost of the equipment is one.  To minimize the cost of ownership you want the equipment to be doing useful work as large a percentage of the time as possible (ideally 100% of the time, realistically somewhat less, like 95% would be considered good), until the equipment burns out or becomes obsolete.  In contrast, the computer in your laptop or your phone is probably actually in use less than 10% of the time you own it (you are asleep 33% of the time, you are eating and relaxing about half the time you are awake, and even when you are "using" the computer, the processor is idle most of the time.)

The second is the cost of power. There are several parts of this: the first is the cost of the power itself.  Part of that cost is consumed in transporting the power from the power plant to the computer.  Part of it is lost in the computer's "power supply" (which is just converting AC power into DC power).  A larger AC->DC converter can usually be made more efficient.  Additionally computers turn useful electric power into waste heat.  So you also need to pay to remove the heat.  Again, larger air conditioners can usually be made more efficient than multiple small air conditioners.

The third is the cost of maintenance.  By putting together a bunch of computers and designing them so that when one goes down the rest keep running you can amortize the cost of maintenance staff over a much larger number of computer nodes than you could if the nodes were all different and placed in different buildings (or cities).

The details: Blue Waters has 288 cabinets.  Each cabinet has 96 "nodes".  Each node is a pretty normal high-end computer.  Most nodes have 2 AMD Opeteron 6276 processors running at 2.3GHz, and 64GByte of DRAM.  About 1/6 of the nodes instead have a single AMD Opteron 6276, an NVidia K20 GPU, and 38GByte of DRAM.  If you wanted, you could buy something similar to a "node" for about \$3000 or \$4000 and put it in your living room to play video games.  Blue Waters has about 27648 nodes.  https://bluewaters.ncsa.illinois.edu/hardware-summary

Each node probably consumes a bit more than 500 Watts, and turns that power into heat.  If you had a node in your living room to play video games it wouldn't be a particularly big deal.  It would consume some electricity from the wall socket and generate about as much heat as a small personal space heater.  In the winter that would be kind of nice and cozy.  In the summer you'd have to run your air conditioner more frequently to keep your house comfortable.  If you had it running full power all day every day, your electricity bill would go up considerably, perhaps double what you are consuming now.

But when you put 27648 of them together it consumes about 15 Megawatts, and generates a correspondingly large amount of heat.  The true engineering marvel of Blue Waters, like any large data center, is the building itself.  It's an enormous refrigerated box.  The Blue Waters building is particularly interesting because it is a fantastically efficient.  About 85% of the power going into the building is actually used to run the nodes.  I believe I read somewhere (can't find it at the moment) only 15% is lost in power conversion and removing waste heat.  That's a lot better than what you'd get from the 500Watt gaming computer in your living room.  You'd probably need a 750Watt "power supply" and another couple hundred Watts to run the air conditioner.

TL; DR

Let's put it all together.  By putting together thousands of smaller computers and spreading the usage among many many people, we keep those computers running most of the time, sharing the resources in a very efficient way.  It costs a lot of money to give people computers that sit idle most of the time.  The best way to save money on computation is to have people share the computers so the computers are busy most of the time.

Blue Waters is much more than just the computers inside it.  It is specially designed to be as power efficient as possible.  Part of that involves putting it near power plants to reduce power losses in power transmission lines.  Here's a satelite picture of the part of Champaign IL containing Blue Waters to demonstrate:


Reduce Turing Machine If $T_n = \{ \langle M \rangle \mid M \mbox{ is a Turing machine and } |L(M)| = n\}$ where $n$ is $0,1,2....$

I need to show that if $n \geq 1$, $T_{n+1}$ reduces to $T_n$. I know I need to create a machine where that machine accepts $|L(M)|-1$ strings, which I could then use to verify with $T_n$. I'm just confused as how to properly do it. Can I use some kind of search algorithm to find a string in it and exclude it?

I don't want to spoil the exercise, but I'd try to play with the fact that the property

$$
p_M(n,k):\ \mbox{$M$ accepts $n$ in exactly $k$ steps}
$$

is decidable. Then, we have that $\langle M \rangle \in T_{n+1}$ iff there are exactly $n+1$ pairs $(n,k)$ satisfying $p_M$.

Try to exploit this in your reduction.

  Can I use some kind of search algorithm to find a string in it and exclude it?

This approach is unlikely to work: to search, the new TM $N$ would need to run $M$ on some given inputs, but this is risky since $M$ can diverge and "block" the whole execution of $N$. It's safer to work with decidable predicates like $p_M$.


How to simulate a bidirectional TM on a regular one with time factor four? In Computational Complexity A Modern Approach, one claim says that if $f$ is computable in time $T(n)$ by a bidirectional TM $M$, then it is computable in time $4T(n)$ by a unidirectional TM $\tilde{M}$. How to work out the constant $4$?

In my opinion, in addition to "go over the edge" operation, one transition in $M$ corresponds to one transition in $\tilde{M}$, so where does constant $4$ come from?

In the book you mentioned above you simulate a infinitely long bidirectional TM increasing the number of symbols and by "“folding” it in an arbitrary location". Thus each cell in the unidirectional TM will represent 2 symbols or a pair. So this can be x/(symbol or blank), x/y or (symbol or blank)/x. Now T(n) is the worst case scenario. Let us assume that the current state of the TM is as follows

^ symbol for blank.

e/h|l/^|l/^|o/^|!/^|?/^  (this is equivalent to h|e|l|l|o|!|? in a bidirectional TM, basically bend on the first position itself). with head pointing to ?/^, now if I want to write to the position I have to write as a pair. But I cannot read the second symbol in the pair without iterating to the left most position and then to the right again. So from the head position ?/^ we have to iterate 6 times to the left and 5 times to the right to read "^". Once we read "^" we have to return, so iterate back so 6 times to the left and then 5 times to the right. Now that we know the second symbol in the pair, we can write the new symbol for ex . "u/^". In a more generalized sense to write something in a Tape in the above state we have iterate the length of the tape(n) 4 times. So it will take 4 times more time to halt on a regular TM in the worst case, so t(n) = 4t'(n).


Can every program be parallelized infinitely and automatically? In my previous question ( Can Turing machines be converted into equivalent Lambda Calculus expressions with a systematic approach? ), I got the answer that it is indeed possible.

And as I have read before, every program written in all programming languages is convertible to a Turing Machine. And of course, since there are no side effects and no order in calculating a lambda expression, parallelization is infinitely possible, and it can break down to computing one lambda function on a separate machine.

So with having these three facts in mind, An interesting question comes to mind. Since every program written in every programming language has an equivalent Turing machine, Turing machines are convertible to Lambda Calculus expression through an algorithm, and Lambda expressions are infinitely parallelizable, can every program be parallelized automatically and infinitely?

EDIT : I think I have to clear out one thing. By infinitely parallelizing, I mean to parallelize till the point where it benefits us, so the arguments about the size of parallelizations are not valid. For example, by having five cores of cpu, one can utilize all of his\her cores by these approach.

If you're working in the strict lambda calculus, everything can be automatically parallelized. In particular, when evaluating a function application, the function and the argument can always be evaluated in parallel.

However, it cannot be infinitely parallelized. There are inherent data dependencies: the result of a function application can't be determined until both the argument and the function have been evaluated, meaning that you need to wait for your threads to both finish, then synchronize.

This is still relevant with your clarified definition of infinitely. For example, if you have 5 processors, it's possible that a particular program can only ever use 4 processors, because of the data dependencies.

Moreover, while this is automatic, it is not "performance for free." In practice, there is non-trivial overhead to creating and synchronizing threads. Moreover, it's difficult to do this in a way that scales only to the current number of processors: if you have 5 cores, the automatic parallelization might generate 6 threads, and in general, it's not possible to know at compile-time how many threads will be active at a given time.

So, you can automatically make a program that runs massively parallel, but with the current state of affairs, it will likely be slower than your original.

It's also worth mentioning that, in practice, this becomes difficult with shared access to resources and IO. For example, a real world program might write to a disk, which can cause problems if done in parallel without control. This is something that can't be modeled by the standard lambda calculus.


Passing a non-mutable argument by value or by reference? A function can generally be defined to receive parameters by value or by reference. If we want to mutate an object inside the function and have those changes reflected outside the function, then it must be passed by reference.

If we don't want to mutate the object then we can choose between passing by value or by reference. The choice, in my experience, is based on whether or not it's expensive to copy the object. If it's cheaper to copy than to deal with the reference's indirection - pass by value, else - pass by reference.

1) Are there any other considerations that should be taken into account?

2) Wouldn't a compiler be better suited to make this choice instead of the programmer? Why, or why not?

To illustrate question 2, the programmer could simply indicate whether they intend to mutate an argument or not. If an argument will be mutated then it must be passed by reference. If it won't be mutated, then the compiler can choose between passing by value or by reference - whichever is faster.

3) Do you see any pitfalls in this approach to language/compiler design?

Be careful. If I define (C type syntax for familiarity):

int var;

void f(const int x)
{
      ...
      var = ...;
      ...
      /* use */ ... x ...
      ...
}

Now go f(var). If pass by value, f uses the original value (at the call); with pass by reference, the value asigned in f. The language should specify which one. Only if the compiler can prove it makes no difference can it decide (and for that, it has to know all programs calling f, or forbid changing global variables).

I'd give one option, just for clarity of specification.


Rounding of $2-10^{20}$ in IEEE double precision How do we get the rounding of $2-10^{20}$ in IEEE double precision? The textbook says it is $-10^{20}$, but I do not know why. I think my textbook only explains the rule for rounding mantissa.

Determine the binary exponent of $10^{20}$. From that determine the value of the lowest bit of the mantissa of $10^{20}$. Then ask yourself: How large does a number x have to be at least so that round (x-$10^{20}$) is not $-10^{20}$?


A < HPL < Complement(A) What can you say about A and Complement(A)? Suppose we have the language

$ \overline L = \{x∈\{0,1\}*:x∉L\}$

And we know that

$A ≤ HPL ≤ \overline A$

where HPL is the Halting problem.

We need to state whether A is finite, countably infinite and whether $A$ and $ \overline A$ is recursive or not or re or not.

We know that A reduces to HPL and HPL is re and therefore A is re. Since HPL reduces to $\overline A$ and HPL is not recursive then $\overline A$ is not recursive. Furthermore, if we know that a language is not recursive but its complement is re then the language is not re. We know so far that $\overline A$ is not recurisve but $A$ is re then it means that $\overline A$ is not re. Furthermore if you know that a language L is not re then either $\overline L$ is not re or $\overline L$ is re but not recursive. We know that $\overline A$ is not re but A is re and therefore, we can say that A is not recursive.

Can anybody tell me if my deduction is any good? Also, how can I know if A is finite/ count infinite? Any tip would be greatly appreciated!

Your analysis appears to be correct. But some clarity may help you.
Let's analyse each case and check whether it is consistent with given information.
As $\text{HPL} \leq \overline{A}$, $\overline{A}$ cannot be finite or recursive.

\begin{array}{|l|l|}
\hline
\textbf{If A is }  & \textbf{Then }\overline{A} \textbf{ is}\\
\hline
\mbox{Finite} & \mbox{Contradiction - }\overline{A} \text{ has to be FA; Violates HPL} \leq \overline{A} \\
\hline
\mbox{Recursive} & \mbox{Contradiction - }\overline{A} \text{ has to be recursive; Violates HPL} \leq \overline{A}\\
\hline
\mbox{Recursively Enumerable} & \text{Non-Recursively Enumerable}\\
\mbox{but not Recursive} & \\
\hline
\mbox{Non-Recursively Enumerable} & \mbox{Contradiction - Violates } A \leq \text{HPL}\\
\hline
\end{array}

You can now infer countability based on this information.


Does this mean $P = NP$ I am not a formally trained guy on Complexity theory, but due to interest I am learning it. Based on different feedbacks, I have started my journey with Micheal Sipser's "Theory of Computation" (2013 edition). My question is based upon some statements from the book. My sincere apologies if the question is meaningless.

Here it goes:

On page 298, it is written as "We are unable to prove the existence of a single language in NP that is not in P". That implies all the NP languages are also in P.
Theorem 7.27 says $SAT\in P$ iff $P=NP$, and it's an implication in both directions.
From cook's theorem, $SAT$ is NP-complete. Hence, from the NP-complete definition $SAT \in NP$.
Now, from the point 3 and 1, as $SAT \in NP$ it should also be $SAT \in P$, and therefore from point 2 it should be $P=NP$.

I got stuck here, I know there is some flaw in this logical deduction (because it is not that easy to prove), but I am unable to find it. Please help me in understanding this concept, so that I can proceed further. Thanks in advance.

You are misinterpreting the statement quoted at point 1. We are unable to prove the existence of a single language in NP that is not in P, but we suspect that there are infinitely many, in fact, we suspect that all NP-complete languages are not in P.


Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP? The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in polynomial time. But is there a proof of whether or not it can be verified in polynomial time assuming P ≠ NP?

If $optTSP$ is in $NP$, then $coNP = NP$.  The latter is unresolved currently.

Proof: if $optTSP$ is in $NP$, then $coTSP$ is in $coNP$ (the certificate being whatever certificate was provided to verify a solution to $optTSP$ was minimal, and then comparing the value of that solution to the desired bound). And because $TSP$ is $NP$-complete then this implies $NP = coNP$.


Google DeepDream Elaborated I've seen a few questions on this site about Deep Dream, however none of them seem to actually speak as to what DeepDream is doing, specifically. As far as I've gathered, they seem to have changed the objective function, and also changed backpropagation so that instead of updating weights they update the input image.

I'm wondering if anyone knows exactly what Google did. They mention in one of their articles imposing Bayesian priors when they carry out their optimization, and with this I can imagine that getting the neural net to spit out an image for each label is not that difficult - we can simply set the label, and then optimize the input vector accordingly.

However, the interesting part of deep dream is that it does this per layer, and in this regard I'm not quite sure how it emphasizes the details  in a per layer way.

Certainly, feeding in an image will give you values at each neuron, but then how can we use that information to exaggerate details in the original image? I've struggled to find any detailed write-ups about this.

References:
Here vzn answered a similar question: https://cs.stackexchange.com/a/44857/49671

From that link, there is an implementation of Deepdream, here: http://auduno.com/post/125362849838/visualizing-googlenet-classes

Except it doesn't offer exaggeration of features as discussed here:http://googleresearch.blogspot.com/2015/06/inceptionism-going-deeper-into-neural.html

Where they both show the visualization of particular classes, and particular layers, and say:

  Instead of exactly prescribing which feature we want the network to
  amplify, we can also let the network make that decision. In this case
  we simply feed the network an arbitrary image or photo and let the
  network analyze the picture. We then pick a layer and ask the network
  to enhance whatever it detected.

The idea of DeepDream is this: pick some layer from the network (usually a convolutional layer), pass the starting image through the network to extract features at the chosen layer, set the gradient at that layer equal to the activations themselves, and then backpropagate to the image.

Why does it make sense? Intuitively, it amplifies the features that are maximally activated in the network. By backpropagating this gradient, we'll make an image update that will boost any of the existing activations. If there's a cat-like detector in the layer and the image contains some patch that looks a bit like a cat, DeepDream boosts this activation by updating this patch to be even more cat-like. As a result, DeepDream is trying to find cats and dogs everywhere in the image (ImageNet dataset has lots of dogs, so the network has many dog-related neurons).

If you look at the code, the key part is objective_L2 function that makes this: $dx = x$ and then backpropagates.


How could you "solve" the halting problem if, hypothetically, the busy beaver numbers were "small"? I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem.

I'm trying to figure out how you could specifically do this. One obvious possibility is to build an n-state Turing machine that looks for a solution to an undecidable problem, then simply waiting for it to pass BB(n) transitions. This should be feasible since BB(n), in this scenario, is small, and surpassing it would prove that the machine loops forever.

But this isn't a satisfactory answer because surely decidability isn't about how feasible a procedure is in practice, but whether it's decidable in theory - what if computers were powerful enough to be able to implement this in our current universe where BB(n) is very large? Shouldn't we just assume that the machine is independent of number theory instead?

To follow the strategy you outline, we need to be confident a priori that we have an upper bound on $BB(n)$. More snappily, if $f$ is any function with $f(n)\ge BB(n)$, then from $f$ we can compute the halting problem: given an $n$-state machine, run it for $f(n)$-many steps.

Since the halting problem isn't computable, this means that no such $f$ is computable; this is a "global" phenomenon. No particular value of $BB$ is too large to be used, but rather the growth rate of $BB(n)$ prevents us from having a whole sequence of upper bounds, one for each $n$. As a low-level analogy:

  There is no polynomial function which is always above $exp(n)=2^n$. Of course, this isn't because individual values of $exp$ are too big, but rather because of the overall behavior of the function across all inputs
  .


Left-Right-Rotation of AVL-Tree For AVL-Tree there exists the following Rotations for Balancing:

Left Rotation
Right Rotation
Left-Right Rotation
Right-Left Rotation

My Question is about the Naming for the Double-Rotations. Sometimes a Left-Right Rotation is defined as a Left-Rotation followed by a Right-Rotation. This is for me the logical case. Sometimes a Left-Right Rotation is defined as a Right-Rotation followed by a Left-Rotation.

Is there a reason for this different definitions? I think it is only a Exchange of the terms - but why?

I would say they are just personal preferences without any particular naming rules or standard attached. Just as you said, it is only a exchange of the terms. There is negligible if any other difference.
The logical choice for me is also letting Left-Right Rotation be the Left-Rotation followed by a Right-Rotation.
However, a few people might prefer to recognize Left-Right Rotation as primarily a Left-Rotation (the larger rotation) with a Right-Rotation before it (as a delta operation). In this way, both Left-Rotation and Left-Right-Rotation moves the (larger) right subtree to the left.
In case you might think this is the whole story, here is more naming confusion and conflict. People may even differ on which tree rotation should be called Left-Rotation and which one should be called Right-Rotation! Not only with AVL trees, but possibly also with other kinds of binary search trees that use rotations to maintain balance. Here is an excerpt from the wikipedia item for tree rotation.

In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations.
There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of rotation reflects the direction that a node is moving upon rotation (a left child rotating into its parent's location is a right rotation) while others say that the direction of rotation reflects which subtree is rotating (a left subtree rotating into its parent's location is a left rotation, the opposite of the former). This article takes the approach of the directional movement of the rotating node.

So, should we take some action to make it more consistent? Probably not necessarily. As far as I have experienced and as far as I have checked[1][2][3][4][5], the approach taken by Wikipedia, which calls the rotation in the counterclockwise direction left rotation and which calls the left rotation followed by right rotation left-right rotation is far more popular. I will stick to that approach myself. I would recommend you stick to that approach, which you are comfortable with as well.


Addition, multiplication, and apostrophe used to represent boolean algebra expressions? I'm looking at a worksheet that expresses boolean logic expressions using multiplication, addition, and apostrophes; something I've never seen before.
I can make a guess that the apostrophe is equivalent to ¬ (except it's suffixed instead of prefixed). But I'm not sure what the addition and multiplication of the variables/propositional atoms would mean. Furthermore, I don't know how a boolean logic formula can "output" something other than just a truth value...
I can't seem to piece together with certainty the meaning of this representation. Could anyone take a look at the below example and maybe make a guess as to a translation of this representation to the more traditional ^, v, and ¬ symbols?
This arose in the context of digital logic in terms of logic gates and such on a CPU, if that makes a difference.

An alleged truth table of the above two expressions (the first row is filled in as an example):

Usually $+$ means $\lor$, "multiplication" means $\land$, and $'$ means $\lnot$.


Is $P$ defined for TM which decide or accept a language? Sipser defines $TIME(t(n))$ as the set of all languages that are decidable by an $O(t(n))$ time TM and then $P = \bigcup_k TIME(n^k).$

However I see also many definitions like
$$
P = \{ L \mid \text{There is a polynomial } p(n) \text{ and a TM which accepts each string } w\in L \text{ in max. } O(p(n)) \text{ steps.} \}
$$

The first definition by Sipser requires a TM which decides the language and the second definition requires only a TM which accepts the language.

Which definition is more common? Is there a theorem which relates both?

Both definitions are the same. They just use a different wording. The difference between "decide" and "accept" is commonplace in computability theory, but in complexity theory different terminology is typically used, since we usually deal with machines that always halt.

The class $\mathsf{P}$ consists of all languages $L$ for which there exists a Turing machine $T$ such that:

$T$ runs in polynomial time. This means that there is a polynomial $p(n)$ such that $T(x)$ stops within $p(|x|)$ steps, where $|x|$ is the length of $x$.
If $x \in L$, then $T$ accepts $x$.
If $x \notin L$, then $T$ rejects $x$.

Suppose we have a machine $T$ with a different guarantee:

If $x \in L$, then $T$ halts after $p(|x|)$ steps.
If $x \notin L$, then $T$ never halts.

The language $L$ is in $\mathsf{P}$, since we can construct a different machine $T'$ which simulates $T$ for $p(|x|)$ steps, accepts the input if $T$ halts, and rejects the input if $T$ doesn't halt. Perhaps that answers your question.


If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how? Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku.

Can you treat this program as a black box and use this to solve TSP? I mean is there a way to represent TSP problem as partially filled Sudoku, so that if I give you the answer of that Sudoku, you can tell the solution for TSP in polynomial time?

If yes, how? how do you represent TSP as a partially filled Sudoku and interpret corresponding filled Sudoku for the result.

For 9x9 Sudoku, no.  It is finite so can be solved in $O(1)$ time.

But if you had a solver for $n^2 \times n^2$ Sudoku, that worked for all $n$ and all possible partial boards, and ran in polynomial time, then yes, that could be used to solve TSP in polynomial time, as completing a $n^2 \times n^2$ Sudoku is NP-complete.

The proof of NP-completeness works by reducing from some NP-complete problem R to Sudoku; then because R is NP-complete, you can reduce from TSP to R (that follows from the definition of NP-completeness); and chaining those reductions gives you a way to use the Sudoku solver to solve TSP.


What us difference between distributed computing and workgroup computing? According to the definition, distributed computing means to distributed a problem among different users while workgroup computing means to work on a problem by different users. So what's the difference between these two? Plz explain it with an example

Workgroup is Microsoft's term for peer-to-peer local area network. Computers running Microsoft operating systems in the same workgroup may share files, printers, or Internet connection.
They call small local area networks such as home or hospital as 'workgroup'. But it's performance is best with fewer number of computers. You can share resources like printers, scanner, etc,. between computers connected on workgroup. Also, it is not safe for sensitive information and there is no centralized management of the resources.

Whereas, distributed computing is the field of study in computer science.  E.g. distributed database, aircraft control systems, routing algorithms, grid computing could computing etc.,

Now, I ask you one question: Can workgroup be that part of distributed computing or vice verse or both are possible? I hope this question will help you dig out more information and learn little bit more about workgroup and distributed computing.


Time-space tradeoff for missing element problem Here is a well-known problem.

Given an array $A[1\dots n]$ of positive integers, output the smallest positive integer not in the array.

The problem can be solved in $O(n)$ space and time: read the array, keep track in $O(n)$ space whether $1,2,\dots,n+1$ occured, scan for smallest element.

I noticed you can trade space for time. If you have $O(\frac{n}{k})$ memory only, you can do it in $k$ rounds and get time $O(k n)$. In a special case, there is obviously constant-space quadratic-time algorithm.

My question is:

  Is this the optimal tradeoff, i.e. does $\operatorname{time} \cdot \operatorname{space} = \Omega(n^2)$?
  In general, how does one prove such type of bounds?

Assume RAM model, with bounded arithmetic and random access to arrays in O(1).

Inspiration for this problem: time-space tradeoff for palindromes in one-tape model (see for example, here).

This can be done in $O(n \log n)$ word operations and $O(1)$ words of memory (respectively $O(n \log^2 n)$ time and $O(\log n)$ memory in bit-level RAM model). Indeed, the solution will be based on the following observation.

Say there are $n_0$ even and $n_1$ odd numbers in range $[1, n + 1]$ (so $n_0 \approx n_1$ and $n_0 + n_1 = n + 1$). Then there is $b \in \{0, 1\}$ such that there are at most $n_b - 1$ values with parity $b$ in the input. Indeed, otherwise there are at least $n_0$ even and at least $n_1$ odd values in the input, meaning that there are at least $n_0 + n_1 = n + 1$ values in the input, contradiction (there are only $n$ of them). It means that we can continue searching for missing number only among the odd or even numbers only. The same algorithm can be applied to higher bits of binary notation as well.

So our algorithm will look like that:

Suppose that we already now that there are only $x$ values in the input with remainder modulo $2^b$ being equal to $r \in [0, 2^b)$ but there are at least $x + 1$ numbers in range $[1, n + 1]$ that have remainder $r$ modulo $2^b$ (at the start we know
that for sure for $b = 0, r = 0$).
Say there are $x_0$ values in the input with remainder $r$ modulo $2^{b + 1}$ and $x_1$ values in the input with remainder $r + 2^b$ modulo $2^{b + 1}$ (we can find these numbers in a single pass through the input). Clearly, $x_0 + x_1 = x$. Moreover, because there are at least $x + 1$ numbers in the input with remainder $r$ modulo $2^b$, at least one of the pairs $(r, b + 1), (r + 2^b, b + 1)$ satisfies the requirements of the step $1$.
We have found the missing number when $2^b \geqslant n + 1$: there is only one number in range $[1, n + 1]$ that may have remainder $r$ modulo $2^b$ ($r$ itself if it is in range), so there are at most zero values in the input that have such remainder. So $r$ is indeed missing.

Clearly, the algorithm halts in $O(\log n)$ steps, each of them needs $O(n)$ time (single pass over the input array). Moreover, only $O(1)$ words of memory are required.


Hardness of approximating 0-1 integer programs Given a $0,1$ (binary) integer program of the form:

$$
\begin{array}{lll}
\text{min} & f(x) & \\
\text{s.t.} & A x = b \\
 & x_i \ge 0 & \quad \forall i\\
 & x_i \in \{0,1\} & \quad \forall i
\end{array}
$$

Note that the size of $A$ is not fixed in either dimension.

I believe this problem has been shown to be hard to approximate (strongly ${\sf NP}$-Complete) by Garey & Johnson. If so, is this still the case when $A, b$ have binary entries and $f(x)$ is a linear function ( $f(x) = \sum_i c_i x_i$ )?

One-in-three 3SAT is NP-complete. Looking at the reduction, it inherits the APX-hardness of 3SAT. You can formulate one-in-three 3SAT as a binary integer program with binary entries, so you problem is APX-hard.


How does "do in parallel" work currently i'm preparing for an exam in a high performance computing course. In this course we discuss several common parallel algorithm patterns called "dwarfs". The first dwarfs we had was the "dense linear algebra", so basically matrix multiplication. In one of the first slides there is a example for a basic matrix multiplication:
MatrixMult PRAM(A:Matrix[n], B:Matrix[n], C:Matrix[n]) {
for i from 1 to n do in parallel
    for k from 1 to n do in parallel
        for j from 1 to n do
            C[i,k] = C[i,k] + A[i,j]∗B[j,k]
}

Nothing really fancy, just the basic matrix multiplication. But below this piece of code the slide states:

• synchronized execution of the for-j-loop;
→ in the first step:
• all processors $P_{i,k}$ simultaneously access A[i,1]
• all processors $P_{i,k}$ simultaneously access B[1,k]

I don't understand why all processors access these elements at the same time. I thought every processor has a different value for i and k, so every processor should access a different element. For example, n=3:

Time step (execute first for loop in parallel on all P):

P1 -> i = 1
P2 -> i = 2
P3 -> i = 3

Time step (execute second for loop in parallel on all P):

P1 -> k = 1
P2 -> k = 2
P3 -> k = 3

Time step (execute third for loop sequential on all P):

P1 -> j = 1, i=1, k=1 ==> A[1,1] B[1,1]
P2 -> j = 1, i=2, k=2 ==> A[2,1] B[1,2]
P3 -> j = 1, i=3, k=3 ==> A[3,1] B[1,3]

Time step:

P1 -> j = 2
P2 -> j = 2
P3 -> j = 3

etc..

So in the third time step every processor would access another element. So i'm not quite sure if i understand the "do in parallel" statement correct. I thought that every statement in this loop would be executed on every processor but with different index as Joseph JáJá defines the "pardo statement" (i think it's the same like "do in parallel") as follows:

for l $\leq$ i $\leq$ u pardo statement
The statement (which can be a sequence of statements) following the pardo depends on the index i. The statement corresponding to all the values of i between l and u are executed concurrently
(from "An Introduction to parallel algorithms", Jospeh JáJá page 27)

So the question is, why do all processors access the same element and how does the "do in parallel" statement work? I'm not sure if i understood this statement.

Two consequent parallel loops maybe joined like "product", so this code can be effectively parallelized up to $n^2$ (9 in your example) processors. Each such processor can be indexed by $i,k$ pair.

Now,

  all processors $P_{i,k}$ access simultaneously $A[i,1]$

means that all processors which have the first index equal to $i$ and second index equal to anything (to some $k$ but it does not restrict the cell), will simultaneously access $A[i,1]$. In your example, you parallelize only by $i$ (first for loop), so you have only one processor per each such cell. If you parallelize completely (by pairs $(i,k)$), you will have $n$ processors per each such cell.


Function problems and $FP \subseteq FNP$ I find it hard to find formal definitions of function complexity classes. Here are two from Wikipedia.

  A binary relation $P(x,y)$ is in FP if and only if there is a
  deterministic polynomial time algorithm that, given $x$, can find some $y$
  such that $P(x,y)$ holds.

The definition above seems to imply that for all relations in FP it holds that for every $x$ there exists at least one $y$ which its length is polynomial in the length of $x$. However, it does not seem to restrict that there exists more $y$ for that $x$ so that $P(x,y)$ holds while $y$ is exponentially longer than $x$.

  A binary relation $P(x,y)$, where $y$ is at most polynomially longer than
  $x$, is in FNP if and only if there is a deterministic polynomial time
  algorithm that can determine whether $P(x,y)$ holds given both $x$ and $y$.

This definition implies that for a relation in FNP it need not to be true that there exists at least one $y$ for every $x$ so that $P(x,y)$ holds. It implies however that if $P(x,y)$ holds, $y$ has to be at most polynomially longer than $x$.

In literature, one can read that FP $\subseteq$ FNP. As far as I do (or do not) understand, this can not be true. It is possible that for some relation $R(x,y) \in$ FP there exists a $(x,y)$ so that $R(x,y)$ holds and $y$ is exponentially longer than $x$. Because of this, this relation does not belong to FNP and therefore FP $\not\subseteq$ FNP.

Are the definitions on Wikipedia incomplete? Am I missing something?

Either way, what are some good sources to read up on function problems (I deem myself knowledgeable of decision problems)?

I found the following in Papadimitriou's book Computational Complexity which I've found satisfying.

Let $R \subseteq \Sigma^* \times \Sigma^*$ be a binary relation on strings.
$R$ is called polynomially decidable if there is a deterministic Turing Machine deciding the language $\{x;y : (x,y) \in R\}$ in polynomial time.
We say that $R$ is polynomially balanced if $(x,y) \in R$ implies $|y| \leq |x|^k$ for some $k \geq 1$.

Then Papadimitriou notes the following, which basically is another definition for NP:

Let $L \subseteq \Sigma^*$ be a language. $L \in$ NP if and only if there is a polynomially decidable and polynomially balanced relation $R$, such that $L = \{x : (x,y) \in R$ for some $y \}$.

A few dozen pages later...

The function problem associated with $L$ [$\in$ NP], denoted $FL$ [here $L$ stands for said language, not logspace], is the following computational problem:
Given $x$, find a string $y$ such that $R_L(x,y)$ if such a string exists; if no such string exists, return "no".

Then

The class of all function problems associated as above with languages in NP is called FNP. FP is the subclass resulting if we only consider function problems in FNP that can be solved in polynomial time.


Creating a priority search tree to find number of points in the range [-inf, qx] X [qy, qy'] from a set of points sorted on y-coordinates in O(n) time A priority search tree can be constructed on a set of points P in O(n log(n)) time but if the points are sorted on the y co-ordinates then it takes O(n) time. I find algorithms for constructing the tree when the points are not sorted.

I am thinking of a way to do this, which is as follows:

Construct a BST on the points.
 Since the points are sorted then it will take O(n) time.

I followed the approach given in this link for this step.
Check if all the nodes satisfy the min-heap property based on the x-coordinates

This will take O(n) time.

So total time complexity will be O(n)

Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates??

Is there a way to make PST in O(N)

The simple is answer is No. It will take a minimum $O(NlogN)$ time to construct the tree.

  Is this a valid approach to construct a Priority Search Tree in O(n) time, from a set of points sorted on the y-coordinates.

No, the algorithm you mentioned will fail when you try to maintain the min-heap property based on $x-coordinates$.When you perform the min-heapify operation, the $y-coordinates$ will move from original position and the property of BST (based on $y-coordinates$) will fail. You can't maintain BST property for $y-coordinates$ anymore. So the tree will just reduce to min-heap  based on $x-coordinates$.

Here's a thought to construct priority search tree sorted on $Y$-coordinates:

For a given set of points $S$(sorted on $X$-coordinates), create a priority search tree as follows:

If $S$ is empty, return a NULL pointer and stop.
The point $P$ in $S$ with the greatest $Y$-coordinate becomes the root $R$.
If  $S-P$ is an empty set , then $R$ is a leaf so we return it and stop.
Let $X(P)$ be a value such that half of points in $S-P$ have
$X$-coordinate lower than $X(P)$, and half having higher value. Basically $X(P)$ is median(based on $X$) of your $S-P$
Recursively create a priority search tree on the lower half of $S-P$,
let its root be the left child of $R$.
Recursively create a priority search tree on the upper half of $S-P$,
let its root be the right child of $R$.

Total time complexity will be $O(nlogn)$ as the tree will be height balanced.

Notes:

Since you have sorted points based on $X$coordinates finding median will take $O(1)$.
To find the maximum $Y$, for simplification you could also maintain a max-heap based on $Y$. Finding maximum $Y$ from it and subsequently removing from it during creation of priority search tree will take $O(logn)$.


Language with $\log\log n$ space complexity? We know that every non-regular language can be recognized with $ \Omega
 (\log\log n) $ space complexity.

I'm looking for an example of a language which is $ \Theta
 (\log\log n) $ space complexity (if such exists).

I found the answer below in lecture notes of Muli Safra.

Consider the language consisting of the following strings:
$$
\begin{align*}
& 0 \$ 1 \$ \\
& 00 \$ 01 \$ 10 \$ 11 \$ \\
& 000 \$ 001 \$ 010 \$ 011 \$
  100 \$ 101 \$ 110 \$ 111 \$ \\
&\ldots
\end{align*}
$$
This language can be recognized in space $O(\log\log n)$. For each $m$ which is smaller than the width of the first block, we check that the $m$ least significant bits form a counter modulo $m$ starting at $0$ and ending at $2^m-1$. We stop when $m$ is the width of the first block.

Since this language clearly isn't regular, it requires space $\log\log n$ (see for example these lecture notes by Hansen). We conclude that the language requires space $\Theta(\log\log n)$.


Star-free decomposition of regular language given by regular expression I was wondering: is there an algorithm to decompose any regular expression, provided it doesn't use complementation, into one or more regular expressions which don't use Kleene star (only catenation and union).

Right now I'm reading On the Decomposition of Finite Languages by A. Mateescu, A. Salomaa and S. Yu, but this paper doesn't seem to discuss this problem, but that's where I get the idea.

No.  If the regular expression encodes an infinite language, then there is no way to decompose it that way.  Without the Kleene star, regular expressions can only express finite languages.

I realize this is a rather trivial answer, and it begs the next question: what if we are promised that the language is finite?  In that case, the answer is yes.  Here are two ways to see that the answer is yes:

Approach #1: Since the language is regular, we can find a DFA that recognizes it -- let's choose the minimal DFA.  Since the language is finite, this DFA will not have any loops in it.  Now if you apply the standard algorithm for converting a DFA to a regular expression, the result is a star-free regular expression.  In fact, you get out only a single regular expression.

Approach #2: If the language is finite, then you can enumerate all of the words in the language, say $L=\{w_1,w_2,\dots,w_n\}$.  Therefore $w_1 + w_2 + \dots + w_n$ is a regular expression for $L$.

Credit: The answer for the case where the language is finite is due to @J.E. Pin.


Path in digraph passing through given set of vertices Suppose we have digraph G, set of its vertices W and two (possibly equal) vertices s and f. I'm looking for an algorithm which will solve the following problem: whether there is path from s to f passing through all vertices from W; if yes, return any of such paths. By "path" i mean path in the most general sense: repetitions of edges and vertices are allowed.

Unfortunately no information about graph is known: it needn't be connected in any sense, it might have oriented cycles, etc.

My idea was to modificate DFS somehow but i didn't manage to proceed. Any ideas and hints will be highly appreciated. Thanks in advance.

Decompose the graph into strongly connected components. You get a DAG, each vertex of which represents a strongly connected component. Let $S,F$ be the strongly connected components containing $s,f$. There is a path from $s$ to $f$ if there is a path from $S$ to $F$ in the decomposition (this includes the case $S=F$). Any such path can only pass through (genuine) vertices in the connected components that appear on the path from $S$ to $F$ in the decomposition, and conversely we can arrange it to pass through all of them (since you allow the paths not to be simple). This leads to a simple criterion for your problem – can you state it?


Is every algorithm on bounded resources O(1) Suppose that I have a restricted Turing Machine - it has finite tape and takes bounded input. Consider a program that halts on every input (which is at most $k$ bits). The set of inputs is finite, therefore the function describing running time is bounded and hence is $\mathcal O (1)$.

Therefore, when analyzing any algorithm that has been tuned to support some machine requirement (ex. input is 32 bit integer), if it halts, we may say it's $\mathcal O (1)$.

What am I missing here? What are arguments supporting/opposing this point of view?

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 a forwarding pointer? I recently came across the concept of "forwarding pointer" and have not been able to find sources of a precise definition. In my case this was mentioned and briefly (but poorly) explained during a discussion on distributed systems.
Could you elaborate on the concept, its usual context(s) and possible other names by which this is also known as?

"Forwarding pointer" is the name of a technique used in garbage
collection algorithms when data cells are being moved to a different
storage location, either because you are using a copying collection
technique such as Cheney's collector, or because you are doing a compaction phase to reduce
memory fragmentation. Compaction is usually associated with mark-and-sweep collectors, but it could be used in other contexts, though the care required by forwarding pointers may entail overhead that is more naturally acceptable with mark-and-sweep.

The forwarding pointer replaces the data cell that has been moved, so that any piece of code trying to access that cell through its old address can find the forwarding pointer to the new address. Exactly like a person moving to a new house will leave her new address on the mailbox (or at the post-office) of her old house. Of course, the code and data must be organized so that forwarding pointers may be recognized as such.

As far as I know, this was historically the first widespread use of the concept of forwarding pointer. But the idea of using forwarding pointers can be considered, and has been considered in other situations that require moving data to a different location, for example:

The concept is used in mobile computing when an agent moves to a
different location (agency) and must still receive messages sent to
its former location.
The concept is also used in data-base implementation when the organization and management
of data requires moving some part of it to another location.

Basically, forwarding pointers are a way of reorganizing incrementally
the storage structures or system organizations without disrupting (too much) on going computations,
and avoiding a complete sweep of the system space, by leaving the new address of moved constituents at their former location.

(You could have found some of that yourself by searching the web and wikipedia).


Is this language Context-Free? Is the language

$$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$

context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.

Hint:

   Yes

Solution:

   $$\{(a^n b^n)^n \mid n \geq 1 \} = \{a^{n_1} b^{n_2} \dots a^{n_{2k-1}} b^{n_{2k}}\}: k \geq 1 \land n_1 = k \land \forall i. n_i = n_{i+1} \}$$

 and therefore the complement is

 $$\{a,b\}^{\ast} \setminus \{(a^n b^n)^n \mid n \geq 1 \} = \{a^{n_1} b^{n_2} \dots a^{n_{2k-1}} b^{n_{2k}}: n_1 \neq k \lor \exists i. n_i \neq n_{i+1}\}$$

 which is context-free as you can easily write a nondeterministic PDA.


What is random logic? Why is it needed? I read now several articles about RISC and CISC architecture. Most are rather exuberant enumerating all the differences between these architecture, but not necessarily why things are the way they are.

One point that struck out to me the most was about the RISC's feature of using hard wired parts in its processor and in particular so called "Random Logic" . According to wikipedia one might best view it as a "simple" decoder from "high level logic" to hardware features like AND and OR gates.

Unfortunately I didn't find more about "Random Logic", so I am a bit at a loss of its concept, design, purpose and why it is needed.

So I hope someone could go into more detail or simply provide references to read up on that topic online.

This all deals with one of the major, and complex tasks in any processor. Namely decoding instructions. On a simple conceptual level, this may be viewed as taking the contents of the instruction register and translating this into logic commands to the various functional units of the processor to perform the desired action and then fetch the next instruction into the instruction register and repeat.

Traditionally there are two competing camps called Random Logic and Microcode.

The random logic camp tends to look at the task as a sort of huge logic problem. Given an input (the instruction set), what outputs are needed (the instruction implementation). The result tends to look like a huge array of gates, flip-flops etc arranged in a non-intuitive (looking random, but no actual randomness here).
Needless to say, for any non-trivial processor, this can be really complex.

The microcode camp on the other hand, maps each instruction to a stored program for a very simple but fast processor. Often, the microcode program is stored in very wide memory so that many program units can be simply connected to fields in the microcode with little or no additional decoding. In a sense, the microcode is implementing the random logic's output by table lookup.

These views are a gross simplification. Almost all random logic designs have small memory elements in them to simplify the state machines that are part of all processors, like the instruction fetch, operand decoding, or responding to interrupts. Likewise, almost all microcode machines employ some logic to speed up the decoding of the microcode to avoid needing insanely wide microcode memory. In addition, logic is often employed to allow the microcode to loop or branch to create more complex behaviour.

While microcode is extremely difficult to write, when an error is found, the code "simply" needs to be updated (assuming that you don't run out of microcode space, then well, problems) When a bug is found in the random logic decoder, it is not uncommon for the whole logic formulation to be affected. This can make random logic designs very hard to get right. The Z-8000 used random logic and its design was plagued by bugs in the instruction decoder. On the other hand, the simpler MC6809 also used random logic decoding and was highly successful.

The advantage of random logic is that it avoids the overhead of fetching the microcode from it's storage. In simpler processors avoiding this overhead can result in savings of silicon (that is money) and clock cycles (that is time).

RISC computers have much simpler instruction sets than CISC machines. This is a major reason why the random logic decoder is so often associated with RISC chips. CISC chips have intricate, complex instruction sets, so microcode is highly favoured for those designs.

I understand that most modern processors use a hybrid approach. Random logic for the simple and/or highly time critical stuff and microcode for the more complex behaviour and/or exception handling.


Understanding Levin's Universal Search I am having troubles understanding Levin's universal search method. In Scholarpedia, http://www.scholarpedia.org/article/Universal_search, it is claimed that “If there exists a program $p$, of length $l(p)$, that can solve the problem in time $t$, then Universal Search will solve the problem in a time $2^{l(p)+1}t$ at most.” How do they arrive at this number? Here is what I tried.

If we put all programs in a list, it looks like $e,0,1,00,01,10,11,000,001,010,011,100,101,110,111,0000,\ldots$
Generally, the first occurence of a program of length $l$ is at the $n$th position, with $n=2^l-1$.

Now, I have encountered two different dovetailing procedures in the literature. The first describes executing program 1 every second step, program 2 every second of the remaining steps, program 3 every second of the remaining steps etc. This leads to the following execution sequence of the programs $n=1,2,3,4,5,6,\ldots$:
$1213121412131215121312141213121612\ldots$
At step $i$ then $n$th program will have been run for $i/2^n$ steps. In the example above $i=34$. Thus, for $n=1,2,3,4,5,6$ we get $17,8,4,2,1,1$ (rounded) which is roughly correct.

Now, suppose there exists a program $p$ that computes a string $x$ in time $t$, whose position is $n$ in the lexicographic enumeration. This means that it will be the value of our time step $i$: $t=i/2^n=i/2^{2^{l(p)}}$. Therefore, $i=2^{2^{l(p)}}t$, which doesn't match the claim $2^{l(p)+1}t$.

In a different description, the execution is done in phases such that the first $i$ programs are run for 1 step at phase $i$. Therefore, before phase $i$, the $n$th program will have been executed $i-n$ times. We require the $n$th program to be executed $t=i-n$ times. Then, we get $i=2^{l(p)}+t$, which is the number of phases. The number of time steps to get to phase $i$ is $i^{2}/2$ (the area of the triangle). Hence we get $\left(2^{l(p)}+t\right)^{2}/2$, which is much larger than $2^{l(p)+1}t$.

Looking at the expression $2^{l(p)+1}t$ it looks like every program up to length $l(p)$ is executed for exactly $t$ time steps. But I thought, Levin search allocates execution time such that shorter programs are favoured?

Where is my mistake? Any help is greatly appreciated.

You do not need dovetailing when $t(n)$ can be quickly computed. Also, note that $l$ is an absolute CONSTANT. The only function is $t$ but the variable is the input string length $n$, hence we write $t(n)$.

So when you are given an input string $x$ of length $|x|=n$, Levin search just does as follows:

Knowing an upperbound for the fixed length of $p$ (i.e. $l$), quickly compute the upperbound for runtime $t(n)$, for each program represented by a tring $M$ of length $|M|=\leq l$, simulate $M$ on input $x$.

Here is the part that is TOTALLY missing from your post: If some $M$ outputs a result $s$, use the verifier for the language to see if $s$ is the string being searched for.

This is only possible if the language is in $NP$.


Morgenstern proof for FFT lower bound I looked at my notes from a class about fast forier transform , and the professor proved in class theorem thanks to Morgenstern , first he defined linear algorithm as a algorithm that inly uses multiplications by scalar and addtions, that he stated Morgenstern's theorem the following way

  Every linear algorithm that computes DFT (Discrete Fourier Transform) , in which the scalar are bounded in their absolute value by $C$ , takes at least $\Omega_C(n\log{n})$ addition operations.

I haven't understood his proof , if someone can give me guidlines to the proof I'll be more than happy :) [right now my proof of the theorem looks like a mess]

p.s.: In class he said we will write in each step the coeffiecents of the linear function that was just computed , then he defined a "computation advancment function" , I didn't understand his definition of this function , it was definied something like $\phi(k)=$ maximum determinant of n$\times$n matrices that were computed untill the k'th step [I probably copied wrong]

Morgenstern first defines the notion of a linear algorithm. A linear algorithm gets as input $x_1,\ldots,x_n$ and its goal is to compute some $y_1,\ldots,y_m$, each of which is a (specific) linear combination of $x_i$s. The algorithm proceeds in steps, starting with step $n+1$. At step $t$, the algorithm computes $x_t = \lambda_t x_i + \mu_t x_j$ for some $i,j < t$. At the end of the computation, for each $i$, $y_i = x_j$ for some $j$.

For example, here is an algorithm computing the unnormalized DFT on 2 variables:
$$
x_3 \gets x_1 + x_2 \\
x_4 \gets x_1 - x_2
$$
Similarly, the unnormalized two dimensional DFT on $2^2$ variables is computed by:
$$
x_5 \gets x_1 + x_2 \\
x_6 \gets x_1 - x_2 \\
x_7 \gets x_3 + x_4 \\
x_8 \gets x_3 - x_4 \\
x_9 \gets x_5 + x_7 \\
x_{10} \gets x_5 - x_7 \\
x_{11} \gets x_6 + x_8 \\
x_{12} \gets x_6 - x_8
$$

We can view each $x_t$ as an $n$-dimensional vector which gives the linear combination of $x_1,\ldots,x_n$ producing $x_t$; call this vector $v_t$. The vectors $v_1,\ldots,v_n$ are just the $n$ basis vectors.

Morgenstern defines the quantity $\Delta_t$, which is the maximum magnitude of the determinant of any square submatrix of the matrix $V_t$ whose rows are $v_1,\ldots,v_t$.

Lemma. Let $c \geq 1/2$. If $|\lambda_s|,|\mu_s| \leq c$ for all $s$ then $\Delta_{n+t} \leq (2c)^t$.

Proof. The proof is by induction on $t$. When $t = 0$, this is easy to verify directly since $V_n$ is just the identity matrix. Consider now any $t > 0$. Every square submatrix of $V_t$ is either a square submatrix of $V_{t-1}$, in which case its determinant is at most $(2c)^{t-1} \leq (2c)^t$ by induction, or it involves the new row $v_t = \lambda_t v_i + \mu_t v_j$. In the latter case, we can write the square submatrix $A$ as $A = \lambda_t B + \mu_t C$, where $B,C$ are square submatrices of $V_{t-1}$ (replace the relevant part of $v_t$ by the corresponding parts of $v_i$ and $v_j$). Since the determinant is a linear function of any of its rows, $\det(A) = \lambda_t \det(B) + \mu_t(C)$. By induction, $|\det(B)|,|\det(C)| \leq (2c)^{t-1}$, and so $$|\det(A)| \leq |\lambda_t| |\det(B)| + |\mu_t| |\det(C)| \leq c(2c)^{t-1} + c(2c)^{t-1} = (2c)^t.$$

Corollary. Computing the DFT on $n$ variables using a linear algorithm with bounded coefficients requires $\Omega(n\log n)$ steps.

Proof. The determinant of the DFT matrix is $n^{n/2}$. Hence any linear algorithm computing the DFT in $t$ steps satisfies $\Delta_t \geq n^{n/2}$. If the bound on the coefficients is $c$, then the lemma shows that $(2c)^t \geq n^{n/2}$ and so $t = \Omega(n\log n)$.

Remark.  Strassen has shown that any algebraic algorithm (algorithm involving $+,-,\cdot,/$) for computing the DFT can be transformed to a linear algorithm using the same number of steps.


How to convert statement with the existential quantifier to statement with universal quantifier? How to convert the following statement with the existential quantifier to statement with universal quantifier?

$\exists n. n>1\rightarrow x(n)\not=1$

Please give me some suggestion?

Let's give names for the atom formulas:

$n>1$ will be $\phi$ and $x(n) \neq 1$ will be $\psi$
Now what we have is:
$$\exists{n} (\phi\rightarrow\psi)$$
$$\exists{n} (\neg\phi \lor\psi)$$
$$\neg\neg \exists{n} (\neg\phi \lor\psi)$$
$$\neg\forall{n} \neg(\neg\phi \lor\psi)$$
$$\neg\forall{n} (\phi \land \neg\psi)$$
$$\neg\forall{n}((n>1) \land \neg(x(n)\neq 1))$$
$$\neg\forall{n}((n>1) \land (x(n) = 1))$$


Do Kleene star and complement commute? I am having hard time solving the following problem.

  Are there any languages for which
  $$
\overline{L^*} = (\overline{L})^*
$$

Assuming $\emptyset^* = \emptyset$, if I consider $\Sigma = \{a\}$ and L = $\Sigma^*$, I get that $L^* = L$ and that $\overline{L^*} = \emptyset$. For the right side I get $\overline{L} = \emptyset$ and $(\overline{L})^* = \emptyset$. Thus, both sides are equal.

Is it true that $\emptyset^* = \emptyset$?

Hint: The star of a language always contains the empty string. The complement of a language containing the empty string never does. With that in mind, look at the left and the right hand sides of your proposed equality.


Which types of mathematical functions are the least complex for a computer to compute ? Let's consider these four function types : Polynomial, Exponential, Logarithmic and Trigonometric.

Considering that both input and output values are floating point numbers.

How do they rank in terms of time complexity (of computing an output value for a given input value) ?

To evaluate polynomial you use Horners scheme, or if you do not know how to compute it, still straightforward naive approach works. It depends on "how big" is this polynomial...

For logarithm and exponent you could use BKM and for trigonometric functions CORDIC.
So ranking by time polynomial is the fastest, and the rest is equally time consuming.
It is hard to tell apart, as basically the same algorithm can compute all these functions.

Using floating point numbers (so inexact results are obvious) the time complexity of special functions is $O(1)$, because underneath you have constant number of rounds no matter what the input was.
Number of iterations is fixed for given precision, so it does not depend on particular input (although angle reduction is time consuming for huge input value).
Polynomial evaluation is $O(n)$ in number of given coefficients using Horner, otherwise it is $O(n^2)$.


The logic behind one's complement addition For my computer science class I need to finish a project where I desperately need to understand logic of one's complement and two's complement. I already know how to construct these and also how hardware adder works when dealing with two's complement. The thing that is bothering me and I need help with is the logic behind one's complement addition. Why do we have to add the bit we would carry over (and discard when using two's complement coding) to the sum to get the correct result? I don't understand why binary addition behaves like this when adding one's complement and why is that last adding of carry over bit so crucial. I need to understand the logic behind it. Thanks

A binary number in one's complement is represented by $\bar{N} = (2^{n} - 1) - N$.
So when you subtract N from M you get:
$$
S = M - N = M + \bar{N} = M + (2^{n} - 1 - N) = (M - N) + 2^{n} - 1
$$
And when you do the so called end-around carry operation you effectively add $-2^{n}+1$ to the intermediate result because you take away the MSB and add 1. So you get:
$$SUM = S -2^{n}+1= (M - N) + 2^{n} - 1 - 2^{n}+ 1 = M - N$$
This is correct again.

In two's complement ($2^{n} - N$) you have:
$$S = -M + N = \bar{M} + N = (2^{n} - M) + N = 2^{n} - (N - M)$$
Discarding the MSB does $- 2^{n}$
 and gives you:
$$SUM = S -2^{n} = 2^{n} - (N - M) - 2^{n} = N - M$$

Done you are.


How to calculate the basic steps in Fibonacci sequences to get nFn and n^2 I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $nF_n$ and $n^2$ were calculated. Here's the part of the book in Chapter 0 that mentions them. Functions fib1 and fib2 are written below the excerpt.

fib1, which performs about $F_n$ additions, actually uses a number of basic steps roughly proportional to $nF_n$. Likewise, the number of steps taken by fib2 is proportional to $n^2$, still polynomial in $n$ and therefore exponentially superior to fib1.

function fib1(n)
if n = 0: return 0
if n = 1: return 1
return fib1(n - 1) + fib1(n - 2)

function fib2(n)
if n = 0 return 0
create an array f[0 ... n]
f[0] = 0, f[1] = 1
for i = 2 ... n:
   f[i] = f[i - 1] + f[i - 2]
return f[n]

Let's start with the second function, fib2. If you count the number of operations, then you get only $O(n)$. So why is the running time given as $\Theta(n^2)$? The reason is that the Fibonacci numbers grow exponentially, and so addition can no longer be considered an $O(1)$ operation. The $n$-th Fibonacci number is $\Theta(n)$ bits in length, and this leads to a running time proportional to $\sum_{i=2}^n i = \Theta(n^2)$.
As for fib1, we can easily write a recurrence for the running time $T(n)$:
$$
T(n) = \begin{cases}
O(1) & \text{if } n \leq 1, \\
T(n-1) + T(n-2) + \Theta(n) & \text{if } n \geq 2.
\end{cases}
$$
For the sake of asymptotic analysis, we can replace $\Theta(n)$ with $n$ and consider $S(n) = T(n)/n$, which follows the recurrence
$$
S(n) = \begin{cases}
O(1) & \text{if } n \leq 2, \\
S(n-1) + S(n-2) + 1 & \text{if } n \geq 3.
\end{cases}
$$
Thus $R(n) = S(n) + 1$ satisfies $R(n) = R(n-1) + R(n-2)$.
Choosing appropriate initial values (which is fine, for the sake of asymptotic analysis), we find out that $R(n) = F_n$, and so $T(n) = nS(n) = n(R(n) - 1) = \Theta(nF_n)$.


Is it a sufficient condition to be in NP? Suppose the following situation.

You have a decision problem $D$.
You know that $SAT$ is $NP$-complete.
You know that $D\leq_p SAT$.

Can you conclude that $D\in NP$?
I think it's true because it means that $D$ is at least as hard as any other problem in $NP$.
As I know I am not able to post questions to answer with yes/no:
If it's true, can you give a better explanation? If it's false, can you argue why is so?
PD: it's not homework.

You can obtain a non-deterministic polynomial-time Turing machine $T$ for $D$ as follows:

Since $D \le_p SAT$, there is a polynomial-time Turing machine $T'$ that maps any instance of $D$ into an instance of $SAT$. Simulate the $T'$ on $x$, where $x$ is the input of $T$.
Use any non-deterministic polynomial-time algorithm to decide SAT (e.g., guess the value of all the variables in the SAT formula and check if the formula is satisfied). By definition of Karp reduction, $T$ will accept if and only if $x \in D$.

This shows that $D \in \mathsf{NP}$.


How to prove regular languages are closed under left quotient? $L$ is a regular language over the alphabet $\Sigma = \{a,b\}$. The left quotient of $L$ regarding $w \in \Sigma^*$ is the language
$$w^{-1} L := \{v \mid wv \in L\}$$

How can I prove that $w^{-1}L$ is regular?

Assume $M$ is a deterministic finite state machine accepting $L$. Feed the word $w$ into $M$, which will land you in some state $q$. Construct a new machine $M'$ which is the same as $M$ but has start state $q$. I claim that $M'$ accepts $w^{-1}L$.

Now prove it.


Is what the all-zeroes instruction does considered in machine instruction design? I remember using a simulated machine with with a minimal instruction set in university. In particular I remember that the instruction that consisted of all zeroes loaded was a LOAD instruction. So, if you made a mistake and began executing empty memory then it would simply keep executing until it ran out of address space.

x86 appears to perform an ADD on empty memory, so similar behaviour to the example above.

All zeros in 6502 on the other hand, corresponds to the BRK instruction which activates a software interrupt so executing empty memory quickly puts the machine in a known state.

My understanding is that 6502 was designed to be written by humans, whereas (at least modern) x86 is designed for compilers to output. Historically, when a machine instruction set is designed, how much attention has been paid to the specific representation each instruction has, given that it can have real effects? I've focused on what the all-zeroes instruction does because I expect that would be the most common instruction to be accidentally executed, but I'd be interested in considerations relating to other instruction representations as well.

In general ease of decoding and code density seem to be given more emphasis when designing an instruction encoding than catching the accidental execution of data (though the danger of nop slides is well known).

Catching the all-zeroes case is rather inexpensive and a number of ISAs specify that such will always be an illegal instruction; e.g., RISC-V (The RISC-V Instruction Set Manual, Volume I: User-Level ISA, Version 2.1: "We reserve all-zero instructions to be illegal instructions to help trap attempts to execute zero-ed or non-existent portions of the memory space. The all-zero value should not be redefined in any non-standard extension. Similarly, we reserve instructions with all bits set to 1 (corresponding to very long instructions in the RISC-V variable-length encoding scheme) as illegal to capture another common value seen in non-existent memory regions.") and Power (Power ISA, Version 2.07: "An instruction consisting entirely of binary 0s is guaranteed always to be an illegal instruction. This increases the probability that an attempt to execute data or uninitialized storage will result in the invocation of the system illegal instruction error handler.")

One might expect memory access protection mechanisms to prevent accidental execution of data, but special casing the all-zero instruction is an inexpensive means of providing a slightly deeper defense. (In addition, some embedded processors do not provide any memory protection.)

Mitch Alsup (a semi-retired computer architect) has designed a RISC-inspired ISA that has a somewhat broad range of illegal instructions meant to catch executing data. From a comp.arch post: "And in particular, opcodes near integer zero are decoded as unimplemented, and Opcodes near FP one (~10**-5 to ~10**5) are also decoded as unimplemented; in both positive and negative senses." "Thus jumping into data is highly likely to result in attempting to execute an unimplemented instruction."


Are there search algorithms that perform better on a Rope than a String? I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not apply.) This data structure is good for making incoherent edits to, but retrieving the character at a given index takes $O(\log n)$ time. All the text search algorithms I've examined so far seem to assume that accessing characters in $O(1)$ and therefore tend to use a lot of accesses. In particular, the search algorithm I've implemented is performing poorly on large files, (hundreds of thousands of characters.) Profiling reveals most of the time to be spent in retrieving the characters to be compared.

The particular algorithm I currently have implemented is the Two-way string-matching algorithm. I chose it for my first attempt mainly because it needs only $O(1)$ additional memory, and not having an additional data structure to implement seemed like it would speed up implementation.

So, I'm wondering are there any well-described search algorithms exist which are designed for use on a B-Tree, or which otherwise perform well in such an environment? I assume the algorithms I have been looking at are trying to minimize comparisons, which I suppose would tend to minimize character retrieval as well. Does it seems sensible to suppose that one would design an algorithm differently if it was to be used on a data structure with a larger than $O(1)$ indexing time?

Rooted trees, balanced or not, can be traversed in linear time via depth-first search. Actual implementations of balanced trees usually provide a way to iterate through it, taking amortized $O(1)$ for each step. So any algorithm will work without $O(\log n)$ overhead if it makes only a single pass through the string (or if it only requires a small bounded sliding window).


Argument in proving that function is not polynomial time in bit length of input seems faulty I am currently solving a question that asks which of the following functions can be calculated in polynomial time:

$$n!, \binom{n}{5}, \binom{2n}{n}, n^{\lfloor \lg n \rfloor},  \lfloor \sqrt{n} \rfloor, \text{the smallest prime factor of } n, \text{the number of prime factors less than }n.$$

In proving the first one, I thought $n! \geq n$ and the input size is $\log_2 n$ so the output cannot even be written in polynomial time. So then clearly the calculation cannot be done in polynomial time.

But then I thought I must have some misunderstanding, since by that logic even just calculating $n$ from the input (that is, the identity function) should not be polynomial time. But that's clearly not possible.

What is the problem in my thinking, and instead how should I be thinking about these?

You should measure the length of the output in the same way you measure the length of the input.

For example, when computing the identity function $f(m) = m$, an input $m$ has input length $n = \Theta(\log m)$ and output length also $n$, which is polynomial in $n$.

The factorial function, in contrast, has much too long output length. Indeed, if the input is $n$, then by Stirling's formula, the length of the output is $\Theta(n\log n)$, which is exponential in the input length $\Theta(\log n)$.


How do compilers implement symbolic (rather than textual) insertion? From a programming language designer's point of view, how is "symbolic"
insertion implemented as opposed to "textual" insertion using pre-processor
macros?

I understand the basics of how "textual" insertion works in C and C++. That is,
the pre-processor might transform:

#include "person.hpp"

class employee
{
    person p;
};

into:

#ifndef PERSON_HPP
#define PERSON_HPP

class person
{
public:
    uint32_t height_;
};

#endif // PERSON_HPP

class employee
{
    person p;
};

This is required because the size of the employee class can only be determined
if the compiler knows the size of the person class. One disadvantage of this is
slow compilation speed. A program consisting of a single source code file
main.cpp might have thousands of lines inserted into it by the pre-processor
before compilation begins. This can be avoided in some cases by forward
declaring the class and using pointers. The employee class cannot use the
person class until it is defined, (which is why the implementation file will
still include "person.h") but it does remove header file dependencies and
increases compilation speed.

class person;

class employee
{
    person* p;
};

For a language like Java, on the other hand, no textual insertion is required.
Instead, "symbolic" insertion is performed. So the file below would not be
"fleshed out" with the definitions of the dependent software modules.

import com.example.library.person;

class employee {
    private person p;
};

I can't wrap my head around how the compiler accomplishes this. I imagine that
because Java is garbage collected, it doesn't need to know the size before it
is declared, in much the same way as classes can be forward declared in C++
without including the entire file. But how does the compiler know that
p->some_function_that_does_not_exist(23) is valid?

This question was originally asked on stack overflow.

The Java compiler reads the files you listed with the import statements to see the definitions. For historical reasons C compiler doesn't do this and prefers to get everything in one file, hence the preprocessor.

In the end, there is no magic. If you want to make sure at compiletime that the functions that you're calling exist, then the compiler has to see the definitions. Dynamic languages like Python don't do this check, so they have to see less of the code.


Minimum spanning tree vs Shortest path What is the difference between minimum spanning tree algorithm and a shortest path algorithm?

In my data structures class we covered two minimum spanning tree algorithms (Prim's and Kruskal's) and one shortest path algorithm (Dijkstra's).

Minimum spanning tree is a tree in a graph that spans all the vertices and total weight of a tree is minimal. Shortest path is quite obvious, it is a shortest path from one vertex to another.

What I don't understand is since minimum spanning tree has a minimal total weight, wouldn't the paths in the tree be the shortest paths? Can anybody explain what I'm missing?

Any help is appreciated.

Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct path, but if you put all of them together you get a triangle rather than a tree. Every collection of two edges forms a minimum spanning tree in this graph, yet if (for example) you choose $\{x,y\},\{y,z\}$, then you miss the shortest path $\{x,z\}$.

In conclusion, if you put all shortest paths together, you don't necessarily get a tree.


3D intersection algorithm for cylinders The problem

The input is a list of $N$ cylinders in 3D space, and the output should be a list of $M \leq N(N-1)/2$ pairs of cylinders that intersect. ($M$ depends on the input data, obviously.)

If it matters, the cylinders are very thin (with a diameter less than 1% of the length for all cylinders), and a solution for "rounded cylinders" would work for me (it probably simplifies the geometry calculations). A "rounded cylinder" is a cylinder with half-spheres at the extremities; formally, for a starting point $S$, an endpoint $E$ and a radius $r$, the rounded cylinder $(S, E, r)$ is defined as the set $\{P \mid \exists Q \in [S,E], \|PQ\| \leq r\}$.

The obvious solution

It is easy enough to do in $O(N^2)$ time and $O(max(M, N))$ space: the pseudocode of my current implementation is (for rounded cylinders):

Ncyl = length(cylinder_list)
output = {}
for i = 1, 2, ... Ncyl:
  for j = i+1, i+2, ... Ncyl:
    (S1, E1, r1) = cylinder_list[i]
    (S2, E2, r2) = cylinder_list[j]
    find P∈[S1, E1], Q∈[S2, E2] such that ||PQ|| is minimal  # this is the costly line, says the profiler
    if ||PQ|| < r1 + r2:
      add (i, j) to output
return output

Better performance?

Any algorithm will have a (time and space) worst-case in $O(N^2)$ (at least) because the output list can itself be of that length. However, the above algorithm guarantees $O(N^2)$ time even on "friendly" data because it tests all possible intersections.

In my use case, the cylinders are fairly spread apart in space (the longest cylinder is less than one tenth of the diameter of the whole set of cylinders). Furthermore, they occupy a small fraction of space and $M\sim N$ (for values of $N$ up to 2000 or so, above that it times out). This suggests to me that there could be an improvement by some "sweeping plane" algorithm similar to Bentley-Ottmann. However, I did not find a straightforward way to do Bentley-Ottmann in 3D (in 2D after sweeping you end up ordering points on a line which is easy enough, but in 3D there is no obvious ordering for a plane).

If you could accept an approximate solution for this problem, then the following approach would help you. Your cylinders are thin, so if two of them intersect, then their axial segments almost touch each other. If you project such a pair of almost touching segments on each of coordinate planes you'll see that their projections almost always intersect.

So - project your set of segments on three coordinate planes and apply the Bentley-Ottmann (or similar) algorithm three times to find all the intersections. Select pairs of segments, which intersect on all three planes, calculate distance between them and verify the cylinders intersection.

This method can give you false negatives - for example in the case, when two cylinders are collinear with small gap between them. However, this method won't give you false positives, because you explicitly verify each suspicious pair of cylinders.


More Information about the Question Answering System called LUKE LUKE is a new state-of-art in question answering system and after googled keywords LUKE Studio Ousia NAIST and RIKEN AIP (I suppose LUKE is a colaboration between several research centers) I couldn't find any information.

LUKE is mentioned in the following pages:

https://paperswithcode.com/sota/question-answering-on-squad11.

https://sheng-z.github.io/ReCoRD-explorer/.

Is there here anyone with insider information able to explain LUKE?

Check this out. This might be the paper

https://www.researchgate.net/project/LUKE-Project

https://www.researchgate.net/publication/340461536_Global_Entity_Disambiguation_with_Pretrained_Contextualized_Embeddings_of_Words_and_Entities


Show that an NP-Complete problem exists that is contained in SPACE(n) The problem I am working on is the following:

  Show that there exists an $NP$-Complete problem in $SPACE(n)$.
  Does the existence of such a problem imply that $NP$ is contained in
  $SPACE(n)$. Why or why not?

$SAT$ is contained in $SPACE(n)$. To show that, simply store Boolean formula (takes $O(n)$ space) and try all assignments for the variables.
$NP$-Complete problem is the problem that is in $NP$ and every problem in $NP$ can be reduced to it, therefore, since $SAT$ is in $SPACE(n)$, any other problem in $NP$ would be contained in SPACE(n).

Would that be a correct solution to the problem?
Also, I have come across related question on $NP \neq SPACE(n)$

First, let me show how to prove that some NP-complete problem using linear space just given the existence of some NP-complete problem.

Suppose that $L$ is NP-complete. In particular, $L$ runs in nondeterministic time $O(n^k)$ for some $k$, and so uses $O(n^k)$ space. Construct a new language $L’ = \{(x,1^{|x|^k}) : x \in L\}$. Given an input to $L’$, we can first verify that it is of the form $(x,1^{|x|^k})$, and then run the nondeterministic algorithm for $L$, which now runs in linear time and space (since the length of the input is $|x| + |x|^k$). Conversely, $L’$ is still NP-hard, since you can easily reduce $L$ to $L’$.

The technique illustrated above is known as padding, and is very useful in computational complexity.

Second, why does this not show that all of NP can be solved in linear space? The fact that $L’$ is NP-hard means that every language $A$ in NP can be reduced to it in polynomial time. If the reduction works in time $O(n^k)$, we can use the linear space algorithms for $L’$ to solve $A$ in space $O(n^k)$, since this is the size of the input to $L’$.

It is expected that NP is not contained in $\mathsf{SPACE}(n)$, but we don’t know how to prove it. Indeed, since L is contained in $\mathsf{SPACE}(n)$, if we could prove that NP is not, then we would separate L from NP, a separation which isn’t known at the moment. See this answer. It is known, however, that NP is different from $\mathsf{SPACE}(n)$; see this answer.


Does a context-free grammar with multiple variables have a "starting" point? So lets consider the following grammar

$$
\begin{align*}
S &\to 0 \mid 0A \\
A &\to 1
\end{align*}
$$

would the string "1" be accepted by the language or must the language start with $S$?

What you have shown is technically not a grammar, only part of it. A grammar is formally defined as the tuple $(N, \Sigma, P, S)$, where:

$N$ is a set of non-terminal symbols
$\Sigma$ is a set of terminal symbols
$P$ is a set of production rules
$S$ is a start symbol

You have only provided $P$, but to have a grammar, you also need $N$, $\Sigma$ and $S$.

$N$ and $\Sigma$ are often omitted when defining a grammar, because they are clear from $P$ (like in your example, where $N = \{ S, A \}$ and $\Sigma = \{ 0, 1 \}$).

Explicitly specifying the start symbol (referred to as $S$ in the formal definition above) can be omitted when there is a clear convention for the name of the start symbol; naming it $S$ as you do in your example is a common convention.

What this all means for your example is that if you assume that $S$ is the start symbol, then $1$ is not a member of the language. If you instead assumed that $A$ is the start symbol, then $1$ would be a member of the language. Such grammar would be formally valid, but defining it like this wouldn't make sense from a human's point of view.


Show that the Laplace smoothing for bigrams is a valid probability distribution If we consider any smoothing technique like laplace or delta smoothing. Intuitively we can see that the we are stealing from sequences with non zero probablity and re distribute to sequences with zero probablity and there by it should be a probability distribution function. But how do we prove this mathematically say for example laplace smoothing?

First, let me rewrite your formula:
$$
\Pr_L[w_j|w_i] = \frac{\#(w_i,w_j)+1}{\#w_i+|\Sigma|}.
$$
The quantity $\#w_i$ should be defined so that $\sum_j \#(w_i,w_j) = \#w_i$ (so we should ignore the final character when calculating $\#w_i$). Therefore
$$
\sum_{w_i \in \Sigma} \Pr_L[w_j|w_i] = \frac{\sum_{w_i \in \Sigma} \#(w_i,w_j) + \sum_{w_i \in \Sigma} 1}{\#w_i + |\Sigma|} = \frac{\#w_i + |\Sigma|}{\#w_i + |\Sigma|} = 1.
$$


Hough transform: difference in cartesian to polar equation According to Wikipedia and most other resources on the internet, the relation between cartesian coordinate and polar coordinate parameters are described by the equation $x\cos{\theta}+y\sin{\theta}=d$.

However, the computer vision course in Udacity used $x\cos{\theta}-y\sin{\theta}=d$ instead, as shown in this short video https://youtu.be/2oGYGXJfjzw?t=4s.

What is the difference?

There's no fundamental difference.  The difference is merely one of convention, namely, where you consider the origin to be in your $(x,y)$ coordinates.  If you consider $(0,0)$ to be in the upper-left (with increasing $y$ values corresponding to going downwards), use one formula.  If you consider $(0,0)$ to be in the lower-left (with increasing $y$ values corresponding to going upwards), use the other.  Ultimately, the two are equivalent, up to a flip of the plane (reflection across the x axis).