Is there a concept of probabilistic quantum computers? Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial.
Accordingly a Quora answer

Quantum computation is fully deterministic. A given computation applied to a given starting state will always produce the same final state, every time. What is potentially non-deterministic is extracting the output in classical terms.

So, it looks like it makes sense to introduce probabilistic quantum computation (as opposed to "fully deterministic"). Does it make sense? Does such thing as probabilistic quantum computation exist in physics?
So maybe, for probabilistic quantum computation there is no known proof that there are computable functions of (probabilistic) quantum time complexity strictly above polynomial, is there?

It is true that unitary gates used in quantum algorithms (and indeed any unitary evolution in quantum mechanics generally) is deterministic and measurements are the only non-deterministic elements in a quantum algorithm (and indeed in quantum mechanics generally). However, it is not true that measurement is always the final step in a quantum algorithm, see for example my answer to this question for a few prominent instances of the use of intermediate measurements. The misconception might originate in the principle of deferred measurement which says that any quantum algorithm with intermediate measurements is equivalent to one where all measurements are moved to the final step. In particular, the principle enables us to replace classical control of quantum gates based on results of intermediate measurements with quantum controlled gates.
Returning to the question of probabilistic quantum computation, note that any probabilistic quantum algorithm (understood here as one that chooses gates to apply based on random bits) can be simulated by a quantum algorithm with intermediate measurements. This follows from the fact that measurement of the state $|+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}$ in the computational basis generates a random bit which can subsequently be used to make random choices about which quantum gates to apply. By the principle of deferred measurement we can turn such a probabilistic quantum algorithm into a quantum algorithm where all measurements are terminal. In conclusion, probabilistic quantum computing is subsumed by regular quantum computing. This is why no distinction is generally made between probabilistic and deterministic quantum algorithms.


What computational model supports arbitrarily sized integers? I want to do some research, but I don't think it's important the number of bits it takes to represent the integer input and arithmetic on the abstract machine.  So what is the model that addresses this?

Specifically, I want to prove that integer factorization is not in P.  If the above is a bad idea, then what model should I be using?  Clearly, I would be needing add, sub, mul, and divide instructions.

Or, should something else be used such as algebraic complexity theory?

I suspect you're looking for either the RAM model or the transdichotomous model.  They differ primarily in how they take into account the size of integers and their effect on the time of various operations.  See What's the difference between transdichotomous model and RAM?.

If you want your results to have any applicability at all, the main thing is to pick a model that avoids treating the time to do arithmetic on exponential-length integers as polynomial, otherwise you can end up with absurd results.  If you count each arithmetic operation as $O(1)$ time, no matter how large the numbers are, then you end up with absurd results like polynomial-time algorithms for factoring and indeed all of #PSPACE.  See https://cs.stackexchange.com/a/53885/755.

Note that proving a problem is in P is not the same as proving it runs in polynomial time on some strange model of computation.  P is defined as problems that have an algorithm that run in polynomial time on a Turing machine.  As mentioned in the previous paragraph, if you change "on a Turing machine" to some other model of computation, that statement might no longer hold.

It's a famous open problem with factorization is in P or not. The problem is likely to be very difficult, with our current state of understanding.  I would not recommend taking on such an ambitious goal.


How are CPU architecture and word size related? I did lot of research on internet but couldn't get my answer. I want to know what is the difference between the word size and CPU architecture?

For eg.- I read that CPU of 32-bit architecture can address 2^32 memory locations. Now if we consider that one address points to a single byte, then it means we can have memory size of 2^32 Bytes. We can call it byte addressable memory.
Now, I also read that word size is the size of register in a CPU, i.e., it is the minimum no. of bits on which a CPU works upon.

So, help me understand here what is the word size of this computer organization? Is it 32-bit or 1 Byte (as memory is byte addressable)?

What if one address could point 2 Bytes of data instead of 1 Byte? What would be word size then?

Consider the following link.

GATE CS Questions on computer organisation

Question no. 3 from this link is as follows-

  A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is

Now, the very first line of the solution says-

  As machine has 32-bit architecture, therefore, 1 word = 32 bits = instruction size

How can we say that since CPU is 32-bit, word size is also 32 bit. Doesn't 32-bit architecture just mean that the no. of addresses in the physical memory is 2^32? And also doesn't the word size mean the size of memory each  of those 2^32 addresses would point to?

It's simple - 32 bit word size, or 32 bit architecture, mean exactly what the person using the expression means. No more, no less. You can't draw any conclusions from it.

For example, there's an Intel 32 bit architecture that can address 64 GB of physical RAM, and no Intel 64 bit architecture that can address anything near 2^64 bytes of physical or virtual memory, while 32 bit PowerPC supported 2^53 bytes of virtual memory.

64 bit POWER has 32 bit instructions. 32 bit Intel has instructions from 8 bit to over 100 bit.

32 bit ARM is what it is, and 64 bit ARM is what it is. Some with 32 and 64 bit x86, except they are different. And so on. Don't make any assumptions, they will all be somewhere between wrong and not quite right.

If you want to pass an exam, learn the answers that the exam expects (sad but true).


An algorithm that find the max X/Y in a polygon in O(log n) I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$.

The polygon is represented by an array of its vertices where each vertex is represented by its coordinates $(X,Y)$.
We also know that the first vertex in the array has the smallest $X$ coordinate and after that, all the other coordinates are set in the array clockwise and also that all of them are different (all the $X$'s and all the $Y$'s are different)

I have the general idea.. using binary search but I'm not sure how to fully apply it.

How should move in the array while checking coordinates and yet keeping it in $O(\log n)$ complexity?

Assume the polygon is a convex polygon; otherwise there might not be an $O(\log n)$ algorithm to find the maximum of X-coordinates or Y-coordinates.

First, let us handle the case of X-coordinate.

Let $x_1, x_2, \cdots, x_n$ be the X-coordinate of the points. Since $x_1$ is the minimum X-coordinate, that sequence is a bitonic sequence. Here are two nice answers to how to sort a bitonic sequence.

Next, let us solve the case of Y-coordinate, which is mildly more complicated.

Let $y_1, y_2, \cdots, y_n, y_{n+1}=y_1$ be the Y-coordinate of the points. We can drill down into the following cases by comparing $y_1$ against $y_2$ and against $y_n$.

$C_{\lt, \lt}$ when $y_1\lt y_2$ and $y_1\lt y_n$. Here $y_1$ is the minimum.
$C_{\gt, \gt}$ when $y_1\gt y_2$ and $y_1\gt y_n$. Here $y_1$ is the maximum.
$C_{\lt, \gt}$ when $y_1\lt y_2$ and $y_1\gt y_n$. Here Y-coordinates goes up from $y_1$ to the maximum, then goes down to the minimum, then goes up to $y_1$.
$C_{\gt, \lt}$ when $y_1\gt y_2$ and $y_1\lt y_n$. Here Y-coordinates goes down from $y_1$ to the minimum, then goes up to the maximum, then goes down to $y_1$.

The first two cases are bitonic sequences, which can be treated as before.

Let us check the case of $C_{\lt, \gt}$; the case $C_{\gt, \lt}$ can be handled similarly.

Let $y_M$ is the maximum and $y_m$ is the minimum, where $M<m$. Given an index $1<i<n$, we can compare $i$ to $m$ and $M$ as follows:

If $y[i-1] < y[i] < y[i+1]$ and $y[i] > y_1$, then $i < M$.
If $y[i-1] < y[i] > y[i+1]$, then $i = M$.
If $y[i-1] > y[i] > y[i+1]$, then $M < i < m$.
If $y[i-1] > y[i] < y[i+1]$, then $i = m$.
If $y[i-1] < y[i] < y[i+1]$ and $y[i] < y_1$, then $i > m$.

The above result enables us to cut the search intervals in half each time with 2 or 3 comparisons, thus ensuring an algorithm with $O(\log n)$ time-complexity.

Exercise. What about the case when we have a sequence of $n$ distinct numbers, in which there are $t$ local maximums and $t+1$ local minimums?


Should i work with tree representation as an array of nodes and an array of edges Here is the problem, i have a graphical component that displays a tree. It takes as input an array of nodes and array of edges(eg:an edge has a source and target).
I will be performing complex tasks, such as building the tree dynamically from user input, removing nodes adding nodes, hiding a node's children, i would need to traverse certain paths and collect information, and all things of tree such as getting children of a node or get all leafs etc.
I have two solutions: either manipulate directly both arrays i already tried with hiding a node's children and it was fine.
Or map the two array into a tree structure and manipulate the tree to do what i want since there will lots of ready algorithms then map it back to the two arrays.
The first solution sounds better and easier at first, however if  things get more complex i will implement each function i need (such getting leafs etc) and the diffculty is manupilating a tree in a non tree representstion.
The second solution is better since its a tree there are a lot of algorithms but there is more work on mapping back and forth on each addition or deletion.
What do you think is better? (A compromise between being it easier fof me and performance)

In the unforgettable words of Donald Knuth

Premature optimization is the root of all evil.

Your best option is as follows.  Do what is simplest for you, while maintaining a good abstraction with good encapsulation.  A good abstraction (a well-defined and thought out API) will make it easy for you to change and improve the underlying implementation in the future while not having to change the rest of the application.
When (or really if) you discover that the application is too slow, then you start changing the underlying implementation, but only after a proper complexity analysis.
It is very difficult (if not impossible) to say in advance what will be the bottleneck of the application, so it's best to leave this decision until you actually know.


Role of the MMU in a Page Fault Swap When a virtual memory address outside the range of loaded into physical RAM is referenced and a page fault occurs, does the Memory Management Unit rely on DMA (Direct Memory Access) to swap the referenced page into RAM, or is an interrupt routine that uses the CPU to copy in the memory in some more mundane way occur?

Please assume the x86 architecture.

For x86 if the hardware page table walker tries to load a page table entry from a speculative access (or hinted by a prefetch instruction) and the Present Bit is zero, then a page-fault exception is generated (Intel® 64 and IA-32 Architectures Software Developer’s Manual, Vol. 3A, 4.7 PAGE-FAULT EXCEPTIONS).

The OS then handles this exception by using OS-specific structures to find where the page is stored and return it to memory. (An OS can choose to mark a page as not present even though it is still in memory. This could be used to give the page a brief last chance before being victimized with potentially less overhead in the common case of the page not being reused before another free page is required.)

A transfer from a hard drive is almost certain to use DMA as such is more efficient. (Network storage using something like ISCSI or a network file system would typically have more processor involvement since such protocols are not typically implemented as part of the networking hardware interface.)

Other ISAs with hardware page table walkers would behave similarly. (An ISA whose hardware page table walker uses hashed page tables like Power Servers and Itanium [which also has the option of using linear page tables] can have a page table miss from a conflict in the hash table. Such page tables are sometimes used as "software TLBs" in that software fills the page table and like a TLB the page table can suffer a miss, which is different than a hit with the page table entry marked invalid/not-present.)

With a software page table walker (e.g., older MIPS, Itanium using linear page tables when the virtual address associated with the location of the PTE is a TLB miss), the software would typically check to ensure the page table entry was marked as valid/present before inserting it into the TLB (loading an invalid PTE usually only makes sense for a sectored TLB entry where multiple PTEs are cached with a single virtual address tag). This avoids an additional exception.


How can any non-primitive-recursive function like the Ackermann function be implemented on hardware? If for-loops and function calls both boil down to jump instructions when implemented on a real machine, then how is "The Ackermann function isn't implementable with for-loops" a meaningful phrase?

Real machines have access to a stack, and so can implement recursion. This is all that is needed to implement the Ackermann function.

However, the Ackermann function grows very fast, so you would only be able to calculate a few of its values given realistic time and space constraints.


Raptor algorithm: find next best paths I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). What are the ways to find next best paths (path is a sequence of trips and transfers from source to destination)?
I have few ideas about it:

Find best path, then exclude trips (from path) from transportation network
and rerun algorithm. (It's not clear for me how to choose new departure time).
Find best path P, then rerun algorithm with adjusted departure
    time so it's not possible to use P. (I think some good paths may be missed here)

What is the way to find next best paths?

There are standard algorithms for finding the $k$ shortest paths in a graph: you provide $k$, and it returns the shortest path, second-shortest path, ..., up to the $k$th shortest path.  See https://en.wikipedia.org/wiki/K_shortest_path_routing.  I'd suggest that as a natural place to start.


Plow a 2D polygonal area I have a problem that is similar to this that I am trying to solve:
"Given a randomly-shaped field, what is the best (fastest I guess) way to plow it? Every part of the field must be plowed, plowing outside the area is not a problem, and turning around is slower than going straight."
Basically, I'm in the situation of a farmer that wants to plow as fast as possible a weirdly-shaped field with no obstacle.

As far as I can tell, this is a covering problem for a simply-connected 2D space, but with some special restrictions.

It seems like it should be a common enough problem, but I can't seem to be able to find anything. I guess most fields have a shape similar enough to a rectangle and thus it is not an issue.
Is there any algorithm or numerical method that allows to solve this problem?

Thanks.

You'll find plenty of literature on this widely-studied problem, which is called complete coverage path planning. Many techniques have been applied with more or less success (genetic algorithms, etc.) but in the end the only viable technique is some variant/improvement on the boustrophedon decomposition algorithm, which is in the class of Morse decompositions.

Choset's paper is the founding document, but I found Xin Yu's PHD dissertation to be the best practical description. The problem is that Boustrophedon decompositions find only a single 'best' ploughing angle for all trapezoids, when some may certainly be better ploughed at some other angle.

Bochkarev and Smith recently described a way to minimize turns by exploiting the minimum altitudes of the polygons, but I found it difficult to grasp with my limited high-school maths.

I am currrently trying out an alternative approach, by taking a Boustrophedon decomposition at all the angles of the polygon and then layering all the resultant trapezoids sorted by a score based on area and minimum altitude. If it works out I'll try and remember to come back here to post the results.

Citations

Choset, Howie. "Coverage of Known Spaces: The Boustrophedon Cellular Dercomposition" Autonomous Robots 9, 247-253, 2000.

Xin, Yu. "Optimization Approaches for a Dubins Vehicle in Coverage Planning problem and Traveling Salesman Problems" PhD Dissertation, Auburn, Alabama, 2015.

Bochkarev, Stanislav and Smith, Stephen L. "On Minimizing Turns in Robot Coverage Path Planning" Automation Science and Engineering, 2016


Recursive algorithm - a^(2^n) The a^n was pretty easy:

function powN(a, n) {
    if(n == 0) return 1;
    return a * powN(a, n - 1);
};

But somehow I got stuck on a^(2^n), any suggestions or even a hint?

I need a recursive algorithm that solves: a^(2^n).

Let's look at how many multiplications are necessary to perform $a^{16}$ by your recursive method:

$$a \xrightarrow{SQR} a^2 \xrightarrow{MUL} a^3  \xrightarrow{MUL} \ldots  \xrightarrow{MUL} a^{14}  \xrightarrow{MUL} a^{15}  \xrightarrow{MUL} a^{16}$$

Where:

$SQR$ = Squares a number

$MUL$ = Usual Multiplication

So as Yuval pointed out in the comments, even a small power of $2$ would require $\Theta(n)$ multiplications, which means this would be too slow for practical use.

However, you can the same thing using only $SQR$ with $\Theta(\log{n})$ operations. That is:

$$a \xrightarrow{SQR} a^2 \xrightarrow{SQR} a^4 \xrightarrow{SQR} a^8 \xrightarrow{SQR} a^{16}$$

Of course, since $16$ is a power of $2$ we only need to use $SQR$. But you can alternate between $SQR$ and $MUL$. This is the principle behind Exponentiation by Squaring.

Example:Computing $a^{19}$.

$$a \xrightarrow{SQR} a^2 \xrightarrow{SQR} a^4 \xrightarrow{SQR} a^8 \xrightarrow{MUL} a^{9} \xrightarrow{SQR} a^{18} \xrightarrow{MUL} a^{19} $$


Mathematical model for a webpage layout? Getting layout right (even if only a structure is considered) with HTML5/CSS3 is still more like an art or black magic.

On the other hand, there are other GUI systems (like wxWindows and Tcl/Tk) and some GUI research (like The Auckland Layout Model, ALM, and other methods), which hint at the possibility of formalization for the layout managers (geometry managers).

Are there any comprehensible formal models for HTML5/CSS, which provide ultracompact (abstract) way to describe structure, "physics" and "geometry" of resizeable webpages, using language of blocks? Also html/css can be generated from it, which works more or less as described in standard browsers. Also, a model can be derived given HTML/CSS (browsers do it by their algorithms, so this seems to be theoretically possible).

By "ultracompact" and abstract it is understood: much more compact than HTML/CSS and also more domain-oriented, "speaking" the language of webpage's dynamics in response to resizing or changed content, that is, higher level than HTML/CSS constructs.

For an analogy, it is possible to write a program to make a textual search, based on some complex rules, but the same task can be performed by a much more compact regular expression. So, is there similar compact language for HTML/CSS layout?

The goals of such a model could be:

to verify existing design (model checking)
to build robust design given higher level specifications
to check whether a set of requirements is consistent with HTML5/CSS3 engine (e.g., does not require writing javascript to make an adjustment too complex for the declarative languages)
to be a solid platform for even higher level research on qualities ("to check the harmony with algebra.")

Also it could be a language to use for certain GUI-related abstractions, like is usual in programming language domain, where we do not need to use concrete syntax to express an idea of for-loop and we do have all kinds of nice, proven results about main concepts of algorithmic constructions.

Of course, web-browsers possess algorithmic model for rendering, e.g. popular and simplified description can be found here, but as pointed above it does not have the properties listed above.

At the time of writing, I am not aware of any formal (or at least formalized enough) models for layouts in HTML. All the examples (ALM, etc) indicate, that usually the model is created to guide layout manager's creation. In the case of HTML and web-browsers the development is evolutional and while each web engine contains some sort of algorithmic models to be able to render HTML, nobody (I know of) published underlying math, and nobody "reverse engineered" program code to extract the model.

It should also be noted, that the model could have grown very complex, so any effort to build one retrospectively may be quite costly.

Even though it is not done yet, it does not mean it is impossible. As more rigorous approaches are being applied to web programming (e.g., recent release of Ur/Web - typesafe approach spanning from database to client-side interactions), modelling HTML5 layout management may be on the horizon, especially, as we witness more formal approach in the recommendations for new HTML5/CSS features (for example, http://www.w3.org/TR/css3-flexbox/), because having formal model may help proving consistency of the additions (analogously to formal grammar, which greatly facilitates making additions to the programming language syntax).


what is the relevance of computability when applying diagonallization? When thinking about diagonalization, I've always glossed over whether or not the enumeration, or the diagonal is computable or not. When does it matter?
Say for example, that have an enumeration of the rational numbers in an uncomputable order, then we would have to assume that either an uncomputable enumeration of the rationals doesn't exist, or the diagonal gives an uncomputable number?
Or suppose that we had an enumeration of a countable but non-recursive set. Would diagonalization produce an uncomputable number?
Or if we assume that we have a computable enumeration of the computable real numbers, and we do diagonalization on it, then we would have to assume that the number on the diagonal is uncomputable? Something seems wrong here.
In general, what are the catches when doing diagonalization pertaining to computability?

There are no catches. Diagonalization is a very general proof technique that works in classical, constructive and computable setting. It is used to prove:

that there is no surjection from a set to its powerset
that the real numbers cannot be enumerated
that the computable real numbers cannot be computably enumerated
that the Halting oracle does not exist
etc.

In its most general form it is known as Lawvere's fixed-point theorem.
You ask what happens if you diagonalize against the rational numbers. You did not specify in what form the rationals are given, I am assuming you mean their decimal expansions. The diagonalization will produce a real number which is not a member of the enumeration (this real may be rational or irrational, depending on what enumeration you started with). If you start with a non-computable enumeration, the result may be non-computable. If you start with a computable enumeration, you will get a computable result, because diagonalization preserves computability.
Likewise, if you take a computable enumeration of computable real numbers (given as infinite sequences of digits), the result of diagonalization will be a computable real number which is not a member of the starting enumeration.


Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I am having trouble finding algorithms which perform well on a massively parallel architecture where there is no shared memory between CPU and GPU.

However, on the wikipedia page for the $\mathsf{NC}$ complexity class states that the determinant (and inverse) of matrices lies within this class, which makes me believe that there do exist algorithms which perform well on massively parallel architecture.

Can anyone provide me with a reference to such an algorithm, or is it just proved that the determinant and inverse of a matrix lies within $\mathsf{NC}$ without a current algorithm having been developed.

The class NC is the class of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. Is your problem to decide - or actually compute the Determinant of a Matrix? Chistov's algorithm solves for the determinant in the class NC with $(log$ $n)^2$ processors, and is the best(?) so far for the class NC(Reference:  Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic. A. L. Chistov ). As an aside, the question whether the class  P is equivalent to NC is still open.


How much data could I store on a Rubik's Cube? Google tells me that a standard 3x3x3 Rubik's Cube has 43,252,003,274,489,856,000 permutations. If I wanted to store data on that Rubik's Cube, how much could I store?

The only way I see to store data on a Rubik's Cube is to assign an integer to each permutation, then convert that integer into binary. It would take 66 bits to store an integer of that size, so the Cube could theoretically hold 65 bits of information by my calculations.

Is there any way to eke out more than 65 bits of storage from a Rubik's Cube?

If you consider the cube as living in a physical space, then you can get an extra factor of 24 from its orientation: assume it's sitting on a table and note the uppermost face (six options) and the face that's facing north (four more options). That gives you $\lfloor \log_2 (24\times 43\ 252\,...)\rfloor = 69\,\text{bits}$, and you could get even more by considering more fine-grained notions of orientation, at the risk of losing information by somebody jostling the cube.


Some slight confusion with the UNTIL operator in CTL (e.g. a U b) I've sketched a very small transition system in paint that I'll use as an example.

I want to see if $A(aUb)$ holds for this transition system. From my understanding, this CTL formula is asking if ALL paths satisfy $aUb$. The only path we can take in this example is S0S1S0S1S0S1S0S1...

This path produces the output (1) $aaaaaaaaaaaaaaaaa...$ or (2) $aaaaaaaaaaaaaaab...$

(2) definitely holds - however it's (1) that I'm unsure about. Am I correct in saying that $aUb$ doesn't hold for (1)? Since we can continue looping over a infinitely without eventually reaching b (and because (1) doesn't satisfy the formula, $A(aUb)$  doesn't hold for this transition system).

Have I understood this correctly? I guess the main confusion for me is that there is 1 path but more than 1 possible output.

Any help is much appreciated.

edit: This is the transition system I'm referring to in the comments below

You have some misconception regarding transition systems:
The alphabet of the system is $2^P$ for some set $P$, and paths induce words over $2^P$. In the first system, there is a single path: $(S_0,S_1)^\omega$, and it induces a single word: $(\{a\},\{a,b\})^\omega$.

Now, this word satisfies $aUb$, since $a$ holds until the secod letter, in which $b$ holds.

The $\forall$ quantifier here is somewhat useless, since there is a single path.

The second system is problematic, since there is nowhere to go to from $S_2$...


Iterative vertex removal algorithm Let $G=(V,E)$ be a graph, where $|V|=n$,$|E|=m$,$k=m/n$.

We consider the following algorithm:

  while (there exists $u ∈ V (G)$ such that $d_G(u) < k$) do

  $\quad G ← G − u$;

Prove that the resulting $G$ isn't null.

Implementing the algorithm is easy, but I can't find a way to prove it rigorously.
k doesn't change over time.

After removing the first vertex, the new graph has $n' := n-1$ vertices and $m' := m-d_G(u) > m-k$ edges. Therefore
$$
\frac{m'}{n'} > \frac{m-k}{n-1} = k.
$$
Continuing in this way, we see that at any point in time, the ratio between edges and vertices is always at least $k$. Any graph on $\ell$ vertices has a ratio of at most $\binom{\ell}{2}/\ell = \frac{\ell-1}{2}$, so the number of vertices always satisfies $\ell \geq 2k+1$. In other words, when the algorithm terminates, there will be at least $2k+1$ vertices left.


How does DNS work if there is no recursive querying? Suppose I type in the website  www.youtube.com. The computer first asks a local domain name server (DNS) what the IP address of this website is. If it can't find it, it then asks the root server, etc. This is recursive querying.

How does DNS work if there is no recursive querying? Is the root server the only one that is used to find the IP address of the website?

If a resolver tries to send its recursive DNS queries to a server that refuses those queries, or the queries time out, then the resolver was originally supposed to try to do an iterative query itself: ask the roots, follow referrals until an error is detected or an answer is seen.  However, nearly all resolvers are stub resolvers and simply choke at this point: they rely on being pointed to a short list of DNS servers where they can send recursive queries, and don't support doing iterative queries.  Moreover, some networks only allow DNS queries to go to a small list of approved DNS servers providing recursive service.  In this case iterative resolution wouldn't help.

(As Martin Berger points out, if the DNS server where a recursive query is sent happens to have the answer in its cache, and it is prepared to handle the recursive query, then it will supply the answer from its cache.  Presumably your phrase "if there is no recursive querying" rules this out.)

The root servers answer recursive queries with referrals to other servers.  This usually does not answer the query, and further queries are required.

If the DNS servers to which the resolver sends queries are not reachable, a DHCP lease refresh may provide a new list of servers and fix the problem.

A packet capture tool like Wireshark can show the DNS queries generated by your machine and the answers it receives.

For completeness, this is how the DNS works.

Usually the resolver is set up as a stub resolver, to send all DNS queries to a server.  This is often done by including the IP address of this server in the DHCP negotiation when connecting to the network.  The server's IP address can also be in /etc/resolv.conf or some equivalent configuration entry.  When a DNS server sees a recursive query, and it is willing to provide an answer to that recursive query, then it usually does iterative resolution.

Iterative resolution works by sending the query to the servers for the root domain.  This is a list of servers that changes infrequently; the latest one is available by FTP.

Queries to the servers for the root domain result in a referral, giving a list of name servers that are more likely to be able to answer.  The resolver picks one of these, and sends the query there.  This continues until it receives an answer, or something goes wrong: a loop occurs, a server responds with "NXDOMAIN" (no such entry exists in the DNS), or the query times out.

Name servers also keep a cache of previously seen name servers.  When a DNS server is started, the first query works as above, but subsequent iterative queries will use the cache to short-circuit the process and will be sent directly to the best server, if one is known.

Instead of the term "recursive server", it is more correct to refer to a DNS server being prepared to answer recursive queries.  Many DNS servers are prepared to answer recursive queries for some "trusted" clients but not for the Internet as a whole.


Construct a loop program for equality I want to construct a loop-computable program for this construction:

IF x1 = c THEN P ELSE P'

I know how to transform if else construction in loop , but I can't understand how to check the equality.I have idea for x1 >= c , but how can I check if the both numbers are equal ?

Do you have idea how to check $x_1 \leq c$ as well? Then just check $(x_1 \leq c) \wedge (x_1 \geq c)$ which implies $x_1 = c$.


Shortest-depth routing algorithm This problem came up in a graph network routing context, it can be expressed as follows:

  Let $n, m > 0$ be integers. Find any smallest list of positive integers $\langle a_1, \cdots, a_k \rangle$ such that:

  $$1 + \sum_{i = 1}^k \prod_{j = 1}^i a_j = n$$

  With the added condition that $a_i \leq m$ for all $1 \leq i \leq k$.

  (for a challenge, add the constraint "with the least number of $1$'s", but the above would suffice)

Graphically, if you picture a tree of depth $k$ (with a single root) with branching factors $a_i$ at each level, the algorithm asks for the shortest such tree containing exactly $n$ nodes in it, with each branching factor at most $m$. For instance, taking $n = 12$ and $m = 5$ as an example, we see that $\langle 1, 1, 3, 2 \rangle$ is a solution, since:

$$1 + (1) + (1 \cdot 1) + (1 \cdot 1 \cdot 3) + (1 \cdot 1 \cdot 3 \cdot 2) = 1 + 1 + 1 + 3 + 6 = 12$$

Which corresponds to the tree with branching factors $1, 1, 3, 2$ shown below:

But there is a shorter solution, given by $\langle 1, 2, 4 \rangle$, as illustrated by the tree:

And there is no shorter solution with $m = 5$, in fact the only other solution of length $3$ is $\langle 1, 5, 1 \rangle$. Note the solutions need not start with $1$, e.g. $\langle 4, 3, 1 \rangle$ for $n = 29$ (the order is clearly very important).

We are talking $n \approx 10^8$, $m \approx 10^4$ in my case (but asymptotic algorithms are welcome!)

I solved it quickly using a brute force approach, which is pretty inefficient, running in exponential time. Is there an easy lower/upper bound on the length of the smallest solution in terms of both $n$ and $m$, and an efficient algorithm to find one such solution? My first thought was a backtracking algorithm, but it doesn't seem to help since you usually get stuck at the leaves of the tree where you realize you can't find a branching factor that will make it add up to $n$, perhaps there is a clever number-theoretic algorithm to select good branching factors as you go?

One optimization I came up with is that if you are at depth $i$ in the tree, then you can calculate the number of nodes you've already added as $x$, then the branching factor for the next tree level must necessarily divide $n - x$, so it might be efficient to go for branching factors that lead to prime values of $n - x$, then we can build a set of optimal solutions for small primes and look them up as needed to complete the tree (going for primes with shorter solutions first). But that doesn't appear to guarantee a shortest solution...

Well, it does reduce the number of $a_i$ candidates to explore down to $O(\log(n))$, but in the absence of a better bound or a procedure to not have to explore fully the tree of possibilities for $a_{i + 1}, a_{i + 2}, \cdots$, this does not make for an efficient algorithm, even if the length of the shortest solution is (probably) upper-bounded by $O(\log(n))$.

Thanks!

PS: I wasn't totally sure what to tag this, so I filed it under combinatorics - please retag if there is a better category for this kind of problem!

Problem statement

Define the function $f$ by

$$f(a_1,\dots,a_k) = \sum_{i=0}^k \prod_{j=1}^i a_i.$$

In other words,

$$f(a_1,\dots,a_k) = 1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \dots + a_1 \cdots a_k.$$

Given $n$, you are looking for $a_1,\dots,a_k$ that form a solution to the equation

$$f(a_1,\dots,a_k) = n.$$

A useful lemma

Let me point out a useful property of the function $f$:

$$f(a_1,a_2,\dots,a_k) = 1 + a_1 f(a_2,\dots,a_k).$$

This follows immediately from the identity

$$1 + a_1 + a_1 a_2 + a_1 a_2 a_3 + \dots + a_1 \cdots a_k = 1 + a_1 (1 + a_2 + a_2 a_3 + \dots + a_2 \cdots a_k).$$

An algorithm for your problem

Now we get a reasonable algorithm for your problem, using dynamic programming.

Each subproblem is indexed by $(i,n')$, and records the best sequence $a_i,a_{i+1},\dots,a_k$ such that $f(a_i,a_{i+1},\dots,a_k)=n'$.  Now we can find the best solution to the original problem by enumerating all possible values for $a_1$, then looking for a solution to the $(2,(n-1)/a_1)$-subproblem.  And, we can solve the $(i,n')$-subproblem by enumerating possible values of $a_i$ and looking for a solution to the $(i+1,(n'-1)/a_i)$-subproblem.  Of course, as a straightforward optimization, we can limit our search to only values of $a_i$ that are a divisor of $n'-1$.

How many subproblems are there, in all?  A simple bound is that there are at most $kn$ subproblems, so the running time of this algorithm is at most $O(kn^2)$.  Using the optimization, I expect the running time will be much less in practice, as most values of $n'$ have only a limited number of divisors.  (See also this question for a math question that is related to the efficiency of this dynamic programming algorithm.)

Another optimization

Here is one more optimization you could apply.  You could use modular arithmetic to quickly filter out subproblems that have no solution.

Suppose we have a small prime $p$, and we have fixed values of $k,n$.  Then if there exists a solution to $f(a_1,\dots,a_k) = n$, then there exists a solution $f(a_1,\dots,a_k) \equiv n \pmod p$; conversely, if there is no solution to $f(a_1,\dots,a_k) \equiv n \pmod p$, then there is no solution to $f(a_1,\dots,a_k) = n$.

So, we could pick a small prime $p$, and then tabulate for which values of $(i,n')$ the $(i,n')$-subproblem has a solution.  Note that we only care about the value of $n'$ modulo $p$, so there are only $kp$ such subproblems, and we can enumerate which ones have a solution in $O(kp^2)$ time using dynamic programming.  (We cannot use the divisibility optimization any longer.)

So, we could precompute a table of size $kp$ and use it to filter out subproblems.  Before trying to solve the $(i,n')$-subproblem, we first look up $(i,n' \bmod p)$ in our table to see whether it has a solution modulo $p$.  If it doesn't have a solution modulo $p$, we don't try to explore that subproblem (we don't try to look for a solution in the integers; we know it'll fail).

We can build a table for each of a handful of small primes, say $p=2,3,5,\dots,17$, and check against each of these tables before exploring a subproblem.  This might reduce the number of subproblems that have to be explored, and thus improve efficiency.

Can we use this idea plus the Chinese remainder theorem to solve the original problem?  Unfortunately not: the requirement that $a_i \le m$ does not behave well under modulo arithmetic.  Thus, if all we wanted to know is whether there exists some sequence of positive integers $a_1,\dots,a_k$ satisfying $f(a_1,\dots,a_k)=n$, then we could solve that in $\text{poly} \log (n)$ time by looking for a solution modulo a set of small primes whose product exceeds $n^k$, then applying the Chinese remainder theorem.  However, your question asks whether there exists a sequence $a_1,\dots,a_k$ satisfying $f(a_1,\dots,a_k)=n$ such that $a_i \le m$ for each $i$, and that cannot be solved efficiently in such a way.  If you were willing to drop the requirement that $a_i \le m$, then your problem could be solved a lot more efficiently.


Solving Unary Constraint Satisfaction Problem other than branch and bound I am solving a problem of planning a meal, where I need to fulfill requests such as "create a two-dish meal that MUST have at most 2g of fat, the first dish MUST have 400kcal and SHOULD have at least 10g of protein, and the second dish MUST have 100kcal" by returning a list of dishes from a predefined list. In other words, it takes soft/hard constraints on a meal as a whole and sets of soft/hard constraint on each dish slot as an input, and outputs an assigment of dishes to dish slots.

I modelled it as a Constraint Satisfaction Problem with all dish constraints being unary constraints and meal constraints being used for accepting/rejecting a solution as well as ranking. I wrote Depth-First Branch and Bound roughly following [1] (shortly, it constructs depth-first a tree of all possible assignments and prunes branches with a dish violating its constraints) and it works pretty well.(*)

The problem is, I need another algorithm for solving that problem and - for reasons I can't change - it needs to be fully deterministic. Which is problematic, since:

the whole meal planning research focuses on using various flavours of artificial intelligence,
the few research papers that don't use AI, use onthologies and rule-based reasoning, but offer no details and constructing such is outside of my time budget and capabilites,
all other algorithms I could find for solving Constraint Satisfaction Problem focus on the ones with binary constraints.

I have tried to find such algorithm for about two weeks, but found nothing. I feel like I'm missing an obvious solution, but I can't quite put my finger on it.

(*) Of course, I plan to improve it by appriopriately integrating meal constraints into the search.

[1] Sundmark, Niclas. "Design and implementation of a constraint satisfaction algorithm for meal planning." (2005).

A pragmatic approach will be to formulate this as an instance of integer linear programming, and feed the system to an off-the-shelf ILP solver.  The details of exactly how to do that will depend on the specific kinds of constraints you have.  There are many tutorials on integer linear programming, so you might start there.

If you need the solution to be deterministic (so solving the same problem multiple times is guaranteed to give the answer), and if you're not sure whether your ILP solver is deterministic, you can define an ordering on solutions (e.g., lexicographic search) and then use binary search to find the "first" valid solution out of all optimal solutions.


Designing a CFG that produces as many c's as the difference of numbers of a's and b's The question is to design a CFG for the language of words that have as many c's as the difference of numbers of a's and b's, that is

$\qquad\displaystyle L = \{(a^l)(b^m)(c^n) \mid l, m \in \mathbb{N}; n = |l-m|\}$.

I have so far go to create the cfg for $(a^l)(b^m)$ but don't know how to do the one for $(c^n)$. It looks complicated as to find the value of n, we need to take the abs value for the difference between l and m. Can someone help?

And, here is the cfg I got so far for $(a^l)(b^m)$.

$S \to aS \mid bT|\epsilon $

$T \to bT \mid \epsilon$

I hope this is correct.

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

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

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

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

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

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

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

The arguments for the second proposed grammar are similar.


Scaling down a set of points into a smaller area A visibility graph $G(P) = (V,E)$ of a set $P = \{p_1, \dots, p_n\}$ of points is defined as follows.

Each vertex $u \in V$ corresponds to a point $p_u \in P$.
There exists an edge $uv \in E$ if, and only if the line segment $\overline{p_up_v}$ does not contain any other points in $P$.

Assume that the coordinates of every $p_i \in P$ has $O(n^c)$ digits, where $c$ is a constant.
My aim is to scale the point set, without changing the relative positions, into a smaller area.
For the sake of simplicity, assume that the area is a circle of raduis 1.
Consider three points: $p_1(100, 340)$, $p_2(500,150)$, $p_3(240, -600)$.
The new coordinates after scaling would be $p'_1(0.1, 0.34)$, $p'_2(0.5, 0.15)$, $p'_3(0.24, -0.6)$, and the relative positions stay the same, as well as the visibility relations.
My question is two folded:

In the very simple example above, the coordiantes are divided by $100$, and it is pretty easy to find that number. But what is the algorithm to find this number for any given point set?
Assuming that the coordinates are of $O(n^c)$ length, can there be a coordinate of $O(d^n)$ (exponential) length?

Regarding Discrete lizard's comment,
$100$ is an integer, which can be represented using $O(\log n)$ bits.
However, instead of $100$, the number was say $1998.12341234123422335$, then (i) it is not trivial to determine the number, and (ii) the division itself requires exponentially many digits.

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


Extracting the Root of a Leftist Tree A leftist tree is a variant of a binary heap, where the height of the left side of the tree is usually greater than the right side. Can a leftist tree's height ever increase after extracting the root? I am pretty sure it is impossible. How can a tree's height increase after taking away a node?

When extracting the root, the subtrees of the root remain and have to merged. Merging two leftist trees is done by "zipping" the trees along their rightmost paths. Two short paths together might be rather long. Try some examples.


what does it mean to extend an assignment? For a constraint satisfaction problem, what does it mean for  an assignment x to extend an assignment  a?

Sorry if this is super trivial,  I did not find an answer

e.g here:  No Small Linear Program Approximates Vertex Cover Within a Factor 2 − $ \epsilon $  pg 16 x does not extend \alpha

It means that you have a partial solution, and you extend that partial solution by assigning at least one more variable to some value, thus producing either a new partial solution or a solution where every variable is assigned a value.

Put differently, if $x$ extends an assignment $a$, it holds that $x$ does precisely the same assignments as $a$ and assigns any number of other variables in addition.


Finding a lower bound for the expression $\log(n!)$ Problem:
Is $\log(n!) \in$ $\Omega( n^n )$?
Answer:
Since $n! > n^n$ for all $n > 1$ we can conclude that: $\log(n!) \in$ $O( n^n )$.
Let us look at the special case where $n = 4$.
\begin{align*}
n! &= 4(3)(2) = 24 \\
n^n &= 4^4 = 256
\end{align*}
Let us look at the special case where $n = 5$.
\begin{align*}
n! &= 5(4)(3)(2) = 5(24) = 120 \\
n^n &= 5^5 = 3125
\end{align*}
Let us look at the special case where $n = 8$.
\begin{align*}
n! &= 8! = 40320 \\
n^n &= 8^8 = 16777216
\end{align*}
It looks to me that $n^n$ is growing faster but that is not a proof. To prove it, I need to
show that there exists an $M > 0$ and $n_o > 0$ such that the following statement is true for
all $n \geq n_0$:
$$ n! \leq M n^n $$
I select $n_0 = 4$ and $M = 1$. Hence the expression reduces to:
$$ n! \leq n^n $$
We have already shown that this expression is true for the special case of $n = 4$. Now, if we
add $1$ to $n$ we have:
$$ (n+1)! \leq (n+1)^{(n+1)} $$
This must be true because the left hand side increased by a factor
of $n+1$ and the right hand side increased by more than a factor of $n+1$. Now we add $1$ to $n$
again. The left hand side increases by a factor of $n+2$ and the right hand side increases by more
than a factor of $n+2$. Hence the right side increases more. We can repeat this process for ever. Therefore, I conclude the statement is true.
Do I have this right?

$\log n! \le \log n^n = n \log n = o(n^n)$.


Implementing a Compiler with Macros I've been thinking about embedded languages (domain-specific or otherwise), and in particular the approach where we define a datatype to represent terms of the embedded language, e.g. (in Haskell):

data Expr = Numeral Int
          | Apply Expr Expr
          | Lambda String Expr
          | Var String
          | ...

We then provide a library of functions which allow us to write programs, like plus 10 5, but when "run" they don't actually produce the 'answer' (15), they instead produce a representation of that program in the embedded language, like Apply (Apply (Var "plus") (Numeral 10)) (Numeral 5).

My question is: can we implement a general-purpose, high-level programming language, like Haskell, such that the "compiler" is actually a set of library functions, "compiling" is just interpreting our program, and the resulting value is machine code (or Javascript, or whatever our compilation target is).

Another way to think about this: in Lisp-like languages, we can create new language constructs using macros, which get "expanded" into other macro calls and eventually down to "special forms" implemented with an interpreter/compiler. From this perspective, my question would be: is it possible to make a Lisp where the only special forms are (representations of) machine code, and the whole "user-facing" language (function definition, calling, branching, etc.) is just a set of macros? In such a system, macro-expanding a program would result in a compiled binary. I'm willing to ignore the "dynamic"/reflection/etc. features found in "real" Lisps.

Another way to think about this: assembly languages get macro-expanded into machine code; are there any any assemblers which do/could provide "high-level" features, like higher-order functions, pattern-matching, garbage collection or linear types, etc.?

Is there some insurmountable difficulty with this (e.g. linking?)? Is it something that's been done? Things which seem related, but slightly different:

Forth seems to 'bootstrap' itself in a similar way when executed, but doesn't (in my limited experience) seem to "compile down" to a 'self-contained binary'; rather, it either runs "dynamically" (i.e. the code we write gets executed 'as is'), or it gets compiled into a form with an embedded interpreter.
The IO approach of Haskell, Idris, etc. is similar, in that Haskell can be seen as a macro language for constructing "IO programs", but it's not quite the same: our Haskell code isn't "fully expanded" by the compiler: we can write pure functions which only get executed at runtime, and even when things do get inlined/fused/etc. it's because of 'compiler magic' rather than the language's semantics.
The Nix language is purely functional and turing complete, and its programs evaluate to give "derivations", containing an environment and build script for some 'package'. Derivations can, optionally, be sent to the nix-build tool for execution. Could we make a similar language which evaluates to give a "machine code" (or "unlinked assembly") value, which we can subsequently pass to an assembler/linker/etc.?

In such a system, our program would be instructions for the "compiler" (the interpreter we run to get the resulting binary), hence we could implement things like instrumentation, optimisation, cross-compiling, etc. as library functions, rather than having to update some separate, monolithic program like GHC.

Yes and no.

Yes, you could structure a compiler this way, but most of the benefits you are hoping for would not materialize. There may be some benefits, such as a powerful compile-time meta-language. There are also costs like a complete loss of the ability to make meaningful guarantees about code that isn't completely self-contained (e.g. takes in objects or higher-order functions as parameters).

Felleisen defines a notion of "macro expressiveness" in his 1991 paper On the expressive power of programming languages. Basically, a programming language feature that is macro-expressible is one that can be expressed by a localized and delimited syntactic transformation. With this notion you can partially compare the "expressive power" of different language features: a language feature is at least as expressive as another feature if the second feature is macro-expressible in a language with the first feature (relative to a common base language).

If a feature is not macro expressible relative some language, that means to implement it requires non-local (often global) transformations. This may be done in a brute-force way as a transformation of the whole program, but it also could be done by having a bunch of smaller macros that coordinate to maintain invariants. Either way, the point is if I want to extend your language with a macro of my own creation that operates at the "base" level (machine code in your idea), then my macros need to maintain all the invariants your macros rely upon or else I'll break the "high-level language". It's possible that these invariants are too constraining for what I want to do. If I proceed anyway, rewriting parts of the language so its compatible with my new macros, the end result is that I haven't extended your language at all, I've made a new, incompatible language. It's quite likely that I will either not be able to use your language's existing standard library or that I will need to reimplement it so that it takes advantage of the new features. Even if I can make something that's compatible with the old language, if what I'm doing is not macro-expressible in terms of the "high-level language" (which presumably it isn't or else I wouldn't be accessing the base language) then my macros are going to have their own invariants that need to be maintained across usages and/or will be making assumptions about the low-level details. Now imagine I'm not making an application but a library. Now imagine you want to use my library and another library that has its own set of macros and invariants but don't know about each other.

I've discussed this quite extensively at LtU. See this comment thread and the comment threads it references. I even briefly touch on the thought experiment of assembly + macros in this comment (from 2006). This comment (a bit into one of the threads referenced by the first comment) may be a relatively coherent explanation with examples.

In a nutshell, separately adding two features which are not macro-expressible to a common language will typically produce two incompatible languages. The less expressive the common language is, the more often this will occur.


Does a graph always have a minimum spanning tree that is binary? I have a graph and I need to find a minimum spanning tree to a given graph. What is to be done so that the output obtained is a binary tree?

There is nothing to be done: for instance, let $S_k$ denote the star graph with $k$ leaves. The graph $S_k$ has a unique spanning tree (which is $S_k$ itself), and it has a vertex with degree exactly $k$.

In fact, the general problem of finding a degree-constrained minimum spanning tree is NP-complete.


Can Floyd-Warshall algorithm be used in an undirected graph with negative edges? So i know that it cannot be used if the directed graph has negative cycle, but what about the undirected graphs with negative edges?

is it going to always work, or sometimes or never?

Floyd–Warshall can be used to detect the presence of negative cycles in directed graphs. This aspect has been widely used in the scheduling community in the form of detecting consistency of a simple temporal network. To answer your question, the values output by Floyd–Warshall will be correct even in the presence of negative edges as long as there are no negative cycles.


How Do Common Pathfinding Algorithms Compare To Human Process This might border on computational cognitive science, but I am curious as to how the process followed by common pathfinding algorithms (such as A*) compares to the process humans use in different pathfinding situations (given the same information). Are these processes similar?

Humans tend to choose not strictly optimal, but close to shortest solutions. So you'll need to look at fuzzy (approximate) algorithms, not at A*.

The closest algorithm to human thinking I've aware of is a Contaction hierarchies on par with a Reach pruning algorithm. When I need to find a path between A and B on the map, I do a quick overview, taking into account if there is crossing river or something else and looking for some general ways and then adding details that could shorten path.


Assuming NP $\neq$ P, are there NPI languages only P languages reduce to? let $L_c$ be the class of all languages that have a polynomial reduction to some language L, for example if $L=SAT$ then $SAT_c=NP$.

Assuming know that $NP\neq P$ we know that there exist languages that are not NP-hard and not in P, i.e. those in NPI. My question is there a language L in NPI such that $L_c \setminus \{L\}=P$?

I don't think such a language $L$ can exist, because it suffices to slightly modify it to get a language $L'\in L_c$ and not in $P$.
For instance let $u$ be a word of minimal length which is not in $L$, and take $L'=L\cup\{u\}$. It is clear that $L'$ polynomially reduces to $L$: check if the input word is $u$, and if it's not use your oracle for $L$. Since $u$ is of constant size, this algorithm runs in polynomial time. So $L'\in L_c$.
But you also have the inverse reduction: $L$ polynomially reduces to $L'$. This implies that $L'\notin P$, because otherwise $L$ would also be in $P$.


Why do some authors not include summation in the $\pi$-Calculus? In Robin Milner's book "Communicating and Mobile Systems: the $\pi$-Calculus", on page 87, the set of expressions of the $\pi$-Calculus is defined as

$$P ::= \sum_{i\in I} \pi_i.P_i\ {\huge|}\ P_1|P_2 \ {\huge|}\ \operatorname{new} a P\ {\huge|}\ !P$$

So in Milner's formulation, the summation of processes is included, just as in CCS. However, some authors do not include it: in Mathew Hennessy's book, "A Distributed $\pi$-Calculus", summation is not used (section 2.1 deals with the language, and summation isn't there).

The Wikipedia article on $\pi$-Calculus also doesn't include summation.

Why is summation not included in these descriptions? Was it somehow abandoned because it can be expressed using the other primitives? If so, how would it be done?

To answer this question, it's best to reflect on the meaning of sums in process calculi. Essentially sums express a lack of knowledge. The process $P + Q$ means something along the lines of "either $P$ or $Q$ is active, but I have absolutely no information which". Note that this is related to, but different from a probabilistic sum like
$P +_{0.5} Q$ which also expresses uncertainty about which process is active, but quantifies the uncertainty by stating that both outcomes are equally likely. So $P+Q$ expresses less information than $P +_{0.5} Q$.

A specific case of using sums to express uncertainty is the input process

$$
   x(v).P
$$

Cleary an process waiting on an input on channel $x$ is uncertain what input will be received, for otherwise there would not be a need to input something. Hence
input can be seen as a sum over all possible inputs, e.g. if we expect to get a natural $n$, then $
   x(v).P
$ really is the sum:

$$
   \Sigma_{n \in \mathbb{N}} xn.P\{n/v\}
$$

Here $xn.P$ is the process that inputs the number $n$ (seen as a constant) on $x$ and becomes $P$.

With this understanding of sums as an expression of uncertainty, the question
whether to include sums, and what kind of sum
 depends what you use the $\pi$-calculus for. There are two main uses.

If you use it as an idealised programming language, then you don't need sums other than the input prefix  $x(v).P$  (and possibly its replicated variant). Indeed what computation would $P+Q$ express?

If you use it to specify program behaviour, then you typically don't want to specify everything and instead express uncertainty by using sums of processes, e.g. $P + Q$. Typically you don't know exactly what the environment of a process is going to do, and use non-determinism to formalise this lack of knowledge.


Transitions needed for dividing two fixed integers Let $Q$ be the set of states of the Turing Machine, $\Sigma$ be the alphabet, and $\{L,R,S\}$ be the left shift, right shift, and stay respectively.

A transition is an element of $Q \times \Sigma \times Q \times \Sigma \times \{L,R,S\}$ which can be read as current state, current symbol, next state, next symbol, movement direction.

For a Turing Machine I'm looking to understand how many transitions, or states since they are linearly related, are needed so that when I give integer $i \ge 0$ on the tape it outputs the $i^\text{th}$ digit after the decimal point(zero indexed) of $\frac{p}{q}$ for which $p$,$q$ are coprime. Assume it is in base $c$ and you only have the characters $0,1,\dots,c-1$ and blank. I imagine this is possible to do in $O(c\log q)$ states, but my best attempts(outlined below) only give me $O(cq)$. An example where $c=2$ and $\frac{p}{q}=\frac{1}{3}$ would be I want a binary Turing machine such that when given $10$ on the tape would output the $3^\text{rd}$ digit after the decimal point of $\frac{1}{3}$ which is $0$ and when given $110111$ would output the $56^\text{th}$ digit which is $1$.

Here is my way of doing it. For the purpose of this $\text{nt}(c,q)$ is the length of the non-terminating portion length of $\frac{p}{q}$ in base $c$, this is easily verified to be the same for all coprime $p$,$q$. Also define $\text{per}(c,q)$ as the length of the periodic portion of $\frac{p}{q}$ in base $c$

My basic idea was you check if it is less than $\text{nt}(c,q)$ and if so output that digit and halt, this takes $O(c\,\text{nt}(c,q))$ transitions. If it's not smaller subtract out $\text{nt}(c,q)$ which takes $O(c\lfloor \log \text{nt}(c,q) \rfloor)$ transitions. Then test for what the result is modulo $\text{per}(c,q)$ and output the appropriate digit. This takes $O(c\,\text{per}(c,q))$ transitions. Now remember that the worst case of $\text{per}(c,q)+\text{nt}(c,q)$ is $q-1$. Therefore the final transition complexity is $O(cq)$

A second idea I had was Newton's algorithm which I think would take $O(c\log q)$ transitions. The basic idea would be to output $p$,$q$,$.1$ to the tape in base $c$, convert to unary which takes $O(c)$ transitions then do multiplication and subtraction in unary which takes $O(1)$ transitions. Would this work?

Using a Turing machine compiler I wrote I devised a program to do this in $O(c\log(q))$ transitions assuming $0 \le p < q$. More precisely it does it in $2 \lfloor \log_2(q) \rfloor +\lfloor \log_2(p) \rfloor + C$ states for some value $C$. I'm sure the value I found(~$409$) wasn't optimal.

The actual program itself is too long to include here(totaling $3584+18\lfloor\log_2(q)\rfloor + 9\lfloor \log_2(p) \rfloor$ lines) Here is the program in my pseudo language for approximating 5/9, it can be compiled with the program found here. The syntax for the language is also found there.

xn=1,4
while i decr {
    xnH=xn
    a=xnH
    a=a,0
    t=0,1
    while xnH decr {
        p=9,4
        while p decr {
            incr(a)
        }
        incr(t)
    }
    two=a
    two=two,2
    two=two,0
    first(two)
    while a decr {
        decr(two)
    }
    xnH=xn
    b=two
    b=b,0
    while xnH pop {
        b=b,1
        xn=xn,1
        incr(t)
    }
    pop(b)
    xn=xn,1
    while xn decr {
        p=two
        while p decr {
            incr(b)
        }
        incr(t)
    }
    xn=b
    incr(t)
}
xnH=xn
xnH=xnH,0
while xn decr {
    p=5,3
    while p decr {
        incr(xnH)
    }
    incr(p)
}
incr(xn)

xnH holds the final value(the whole thing is assumed to be after the decimal point). It shouldn't be too hard to extract out a single digit from it(in $O(1)$ states). Also as a note even for small values of i this program takes quite a long time to execute.


BFS for transforming one word to another I'm having a hard time understand the reasoning in the solution of 18.7 in Elements of programming interviews (EPI):

Let $s$ and $t$ be stings and $D$ a dictionary, i.e., a set of strings. Define $s$ to produce $t$ if there exists a sequence of strings from the dictionary $P = \langle s_0,s_1,\ldots,s_{n-1} \rangle$ such that the first string is $s$, the last string is $t$, and adjacent strings have the same length and differ in exactly one character. The sequence $P$ is called a production sequence. For example, if the dictionary is {bat,cot,dog,dag,dot,cat}, then ⟨cat,cot,dot,dog⟩ is a valid production sequence.
Given a dictionary $D$ and two strings $s$ and $t$, write a program to determine if $s$ produces $t$. Assume that all characters are lowercase alphabets. If $s$ does produce $t$, output the length of a shortest production sequence; otherwise, output -1.
Hint: Treat strings as vertices in an undirected graph, with an edge between $u$ and $v$ if and only if the corresponding strings differ in one character.

Here is the solution:

The number of vertices is $d$, the number of words in the dictionary. The number of edges is, in the worst-case $O(d^2)$. The time complexity is that of BFS, namely $O(d+d^2) = O(d^2)$. If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$, implying an $O(nd)$ bound.

So I agree with number of vertices being $d$, and the  worst case number of edges is $d^2$. We know that the complexity of BFS is $O(V+E)$, hence $O(d+d^2) = O(d^2)$, though if we used a set to record visited vertices (or removed a vertex once we visited it from the graph), that should reduce BFS's complexity to $O(d)$. But then things get funky.

If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$.

don't agree with this. Imagine we have 5 words in our dictionary $\{ab, ac, ad, ae, af\}$, so $d=5$ and $n=2$. All these vertices are connected and you can see that each vertex has 4 edges leaving it... which is more than $O(n)$. You can have $26^n$ possible edges leaving the vertex, but you only have $d$ vertices in the graph, so the number of edges leaving a single vertex should be $O(d)$.
I ultimately agree that the final complexity of the algorithm is $O(nd)$, but I calculated that simply given that we can visit up to $d$ vertices (we use a visited set to prevent cycles) and for each vertex visited one we iterate over the string of length $n$ as we look for differences in the alphabet of lower characters $O(26nd) = O(nd$).
Interested to hear what people think,
Thanks :)

The maximum degree of a vertex is $25n$, since this is the number of words which can be obtained by changing a single character. I'm not sure how you get to $26^n$.

You are writing "$4$ is more than $O(n)$" (where $n=2$). This is completely meaningless, since $O(n)$ stands for a function bounded by $Cn$ for some unknown constant $C$. If you don't know the value of $C$ (in this case, $C=25$) then you cannot possibly determine that $4 > Cn$.


Find a collection of sets where each number from a given list is contained in a different set I have a set of numbers S of cardinality N, and a collection of sets each containing some subset of S.  The cardinality of each of these sets can be anywhere from 1 to N.  The number of sets is variable, but is necessarily at least N.

e.g.

$S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$

Sets:

$\{3, 6\}$
$\{1, 2, 5\}$
$\{5\}$
$\{2, 6\}$
$\{2, 5\}$
$\{7, 8\}$
$\{1, 3, 5\}$
$\{7, 9\}$
$\{4, 8, 9\}$
$\{4, 5\}$

I'm looking for an algorithm that will let me determine if there is a group of N sets, where each element of S is contained in a different set (the other elements in the set are irrelevant).  Note that every element of S will always be represented at least once in the collection of sets (otherwise it is obvious that no solution is possible).

For this example, a possible solution is:

$\{\mathbf{1}, 2, 5\}$
$\{\mathbf{2}, 5\}$
$\{1, \mathbf{3}, 5\}$
$\{\mathbf{4}, 5\}$
$\{\mathbf{5}\}$
$\{2, \mathbf{6}\}$
$\{\mathbf{7}, 9\}$
$\{7, \mathbf{8}\}$
$\{4, 8, \mathbf{9}\}$

(bold numbers indicate the element of S for which each set was selected)

But if we were to exclude the set $\{4, 5\}$ from the pool of available sets, there would be no possible solution, despite every number being represented at least once in the available sets, and the number of sets still being at least N.

My N will not be more than 100, and the number of sets could be up to 100,000.  The frequency of numbers in the sets will likely be very unevenly distributed, so, for example, there might be 95% of the sets that contain a 1, but only <1% of sets that contain a 3.

Obviously the best performance is desirable, but I would appreciate any algorithm that is better than a brute-force search of every possible combination of sets.

You are looking for a perfect matching. Consider the bipartite graph in which the left side consists of $N$ vertices corresponding to the numbers in $S$, and the right side contains a vertex for each set. Connect $x$ on the left to $y$ on the right if $x \in y$. Your problem is solvable if there is a matching that matches all of the left side. This is the classical problem of unweighted maximum matching in bipartite graphs, which has many efficient algorithms.


In "multi hop" network, is computer => computer 0 hop or 1 hop? Would this here, a computer sending information directly to another computer, count as 0 hops or 1 hop?

As stated on this site:

  A hop is a computer networking term that refers to the number of routers that a packet (a portion of data) passes through from its source to its destination. Sometimes a hop is counted when a packet passes through other hardware on a network, like switches, access points, and repeaters. This isn't always the case and it depends on what role those devices are playing on the network and how they're configured.

So as there are no routers showed between the two workstations, I'd say this is a point-to-point connection (layer 2 link with only two devices) with no hops in between.


Difference between DPDA and NPDA? What are the major differences between Deterministic Push Down Automata and Non-deterministic Push Down Automata? Which one is faster and how? Also what are the drawbacks of DPDA with respect to NPDA.
Can anyone quote an example and explain these concepts.

The main (and only) difference between DPDA and NPDA is that DPDAs are deterministic, whereas NPDAs are non-deterministic. With some abuse of notation, we can say that NPDAs are a generalization of DPDAs: every DPDA can be simulated by an NPDA, but the converse doesn't hold (there are context-free languages which cannot be accepted by a DPDA).

The main advantage of DPDAs is that we can simulate them much more easily with our deterministic computers (real hardware is always deterministic). In fact, simulating general DPDAs is not fast enough for most purposes, and so when parsing code we usually use LALR grammars which are weaker than DPDAs.


How to implement conditional probability distribution on set-valued Random Variables I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing for me. In the usual scenario, for some pair of discrete RVs, $X,Y$, we can compute the conditional probability of two "punctual" events by using the Bayes theorem:
$$P(Y=y|X=x)=\frac{P(X=x|Y=y)P(Y=y)}{\sum_{y'\in\mathcal{Y}}P(X=x|Y=y')P(Y=y')}=\frac{f(x,y)}{\sum_{y'\in\mathcal{Y}}f(x,y')},$$
where $f(x,y)=\sum_{(x',y')\in (\mathcal{X},\mathcal{Y})}\chi(x'=x,y'=y)$ is an accumulator function giving the total number of times the specific joint event $x,y$ is observed in the sample space (i.e. the indicator function $\chi(x'=x,y'=y)$ equals one when $x'=x,y'=y$ holds). I'd like to compute such probability when events drawn by $X,Y$ are sets $\boldsymbol{x},\boldsymbol{y}$, respectively. So, how to define the corresponding $f(\boldsymbol{x},\boldsymbol{y})$?
I've tried with two main options:
$$(1)\hspace{10mm}f(\boldsymbol{x},\boldsymbol{y})=\sum_{(\boldsymbol{x}',\boldsymbol{y}')\in(\mathcal{X},\mathcal{Y})}|(\boldsymbol{x}\cap\boldsymbol{y})\cap(\boldsymbol{x}'\cap\boldsymbol{y}')|,$$
and
$$(2)\hspace{10mm}f(\boldsymbol{x},\boldsymbol{y})=\sum_{(\boldsymbol{x}',\boldsymbol{y}')\in(\mathcal{X},\mathcal{Y})}|(\boldsymbol{x}\cap\boldsymbol{y})\cap \boldsymbol{x}'\cup(\boldsymbol{x}\cap\boldsymbol{y})\cap \boldsymbol{y}'|,$$
On the one hand, the motivation behind $(1)$ is that $\boldsymbol{x}\cap\boldsymbol{y}$ provides a measure of how the attributes of both sets should be observed jointly (such as any intersection event). In turn intersecting this intersection event against other intersection events $\boldsymbol{x}'\cap\boldsymbol{y}'$ should provide the measure of how much the joint attributes are observed through the sample space. On the other hand, the motivation behind $(2)$ is that in order to compute $f(\boldsymbol{x},\boldsymbol{y})$ we need to look for $\boldsymbol{x}\cap\boldsymbol{y}$'s attributes in each event of the sample space, without building new events.
However, I'm not sure which one of these analogies is correct (or none at all) with respect to the usual notion of observing the joint event in a sample space. Please, some one can help me to clarify/fix/prove this?
Thank you in advance

Your understanding of the basic situation (without sets) has some caveats.  It seems that you are defining
$$f(x,y) =  \Pr[X=x \land Y=y] \times |\mathcal{X}| \times |\mathcal{Y}|.$$
You seems to be assuming that $X,Y$ are independently and uniformly distributed over the sample space $\mathcal{X} \times \mathcal{Y}$.  Note that this is a big assumption -- it typically won't hold, and if it doesn't hold, your formula is not correct.
You don't need a fancy accumulator function. There is a simpler expression for $f$, namely, $f(x,y) = 1$ if $x \in \mathcal{X},y \in \mathcal{Y}$ (and $f(x,y) = 0$ otherwise, if you allow that to happen).  Again, this is only valid if $X,Y$ are uniformly distributed on $\mathcal{X} \times \mathcal{Y}$.
When $X,Y$ are sets, the exact same formula holds... under the same assumptions.  No changes needed at all.
Your proposed formulas (1), (2) are not correct.
In practice, usually $X,Y$ are typically not independently and uniformly distributed.  Therefore, these formulas are usually not useful in practice.  Instead, you need to work directly with the probabilities; counts and $f$ probably won't be useful in that case.


Term for number of edges in a graph Is there a single-word term for "the number of edges in a graph"?  Something along the lines of "arity" for function parameters.

I don't believe there is a single word term for this. Edge count seems to be the closest thing to what you are after. Mathematically it can be expressed as E(g).

http://mathworld.wolfram.com/EdgeCount.html


Proving algorithm for removing nodes from a complete graph with two kinds of edges Lets say $G$ is complete undirected graph with a set of edges coloured either black or red. The problem is to find an algorithm answering if it is possible to remove a subset of nodes from $G$ in a way such that all black edges are gone, but for any two nodes in the set of removed nodes there was no red edge between them.

I think I found a solution: If the graph has more than one black strongly connected components, then the answer is "no", because then there are two black edges $E_1$ and $E_2$ with no common nodes, and for every black edge at least one of its nodes should be removed to remove that edge from graph, and for any pair of nodes of $E_1$ and $E_2$ we choose to remove, there is a red edge between them, so we fail. Otherwise, we can sort all nodes by the number of linked black edges in descending order and then iterate this list node by node removing them from graph. If for current node there is a linked red edge, then mark the node on other end as "dangerous", and if we come across such node before all black edges are gone, then answer is "no". Otherwise, when there is no black edges, stop and answer "yes".

But now I want to prove this algorithm is correct. I think the case of more than one black SCCs is simple and doesn't require anything more rigorous, but the other case is more complicated and I'm not even entirely sure it's correct. Currently this is where I got:

Lets say the strategy of always removing a node with more linked black edges first is incorrect. Then it means, such strategy can make algorithm answer "no" when there was an other way to choose nodes which would make algorithm answer "yes". Then there is a step where some max-black-edges node $X$ is improperly chosen. Lets take a look at set of its black-adjacent nodes $S$. If all of them have the same number of linked black edges as $X$, then all other choices are symmetric and we will fail anyway, otherwise, there are nodes with less linked black edges than $X$ which means there are at least two nodes in $S$ which have a red edge between them. And to remove all black edges that make nodes in $S$ black-adjacent to $X$, we should remove all these nodes, so we will remove two with that red edge, so such strategies are incorrect and max-black-edges nodes should always be removed first.

I think this proof is somewhat naive and vague (especially in the end) and maybe even incorrect, so I'm seeking suggestions to make a better one. Not necessarily super-formal, but at least something which is sufficiently strict and believable.

A complete graph with red and black edges is just an unnecessarily complicated way of describing an arbitrary graph (where black edges correspond to neighbors and red edges to non-neighbors).

Effectively, given a graph $G$ you are looking for a subset of the vertices that is both a clique and a vertex cover.

Restating the problem like this, it is easier to see that your arguments are correct: in a graph with no isolated vertices, if there is more than one connected component (in an undirected graph every connected component is also strongly connected so stating "strongly connected" is redundant) then clearly there is no clique that covers both components.

Let $\Delta$ be the maximum degree of the graph $G=(V,E)$ and let $v$ be a degree-$\Delta$ vertex. Suppose there is a valid solution $S\subseteq V$ that does not contain $v$, then this solution must contain all of $v$'s neighbors. Suppose $S$ can not be extended to a valid solution by adding $v$, then $S$ contains some vertex not adjacent to $v$, thus the graph restricted to $S$ is a clique of size least $\Delta+1$ in which all vertices have degree at least $\Delta$. However, then the graph restricted to $S\cup{v}$ has a vertex of degree at least $\Delta+1$, contradicting that $\Delta$ is the maximum degree. Thus if a valid solution exists then this solution remains valid when adding a maximum-degree vertex.

So the algorithm can be restated in much simpler terms: take all maximum-degree vertices, and check that they are a valid solution.


Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$ $\mathrm{NP}$ has not been separated from constant-depth circuits consisting of solely $\mathrm{Mod}_6$ gates. So, the question is whether current techniques are enough to deduce interestingly unintuitive consequences of that bizarre claim.

Even a weaker claim that $\mathrm{DLogTime}$-$\mathrm{uniform}\:\mathrm{AC_2^0}=\mathrm{L}$ readily implies $\mathrm{NP}= \mathrm{PSPACE}$

First, $\mathrm{NP} = \mathrm{EXP}$-$\mathrm{AC_2^0}$ by using a similar argument in this answer. Here, I mean constant-depth $\mathrm{AC}^0$ circuit of depth at most $2$. And, $\mathrm{PSPACE} = \mathrm{EXP}$-$\mathrm{L}$, if you are willing to abuse the notation.

Second, since the mentioned above answer does not describe in details the uniformity of the first-order reduction. I move on to prove the $\mathrm{\mathrm{DLogTime}}$-$\mathrm{uniformity}$ of the standard Cook proof.

That is we need to establish a $\mathrm{DLogTime}$ constructor that constructs a constant-depth circuit, for each input length. And the constructed constant-depth circuits then receives arbitrary input (of given length) and always output correctly.

Indeed, Cook proves completeness of $\mathrm{SAT}$ by using a big tableau.

From the second row of the tableau on, every cell can be computed by a constant-size formula of "nearby" cells of previous row. So, these can be printed as constant output node of the constructed constant-depth circuit. This can be called hard-coded. So, almost all of the constructed constant-depth circuit are merely constant output nodes.

We only need to deal with the first row. This part of the constructed circuit needs to take the actual input bits as its own designated input gates. So, it requires some more indexing work of the constructor. It is worthy mentioning that these actual input bits does not contribute to the variable of the formula output by our constructed circuit (the circuit is a constant-depth reduction, not a decider). This very first part of the constructed circuit can be constructed by the $\mathrm{DLogTime}$ constructor easily. What really makes it into variables of the formulae that will be reduced to by our constructed circuit are the nondeterministic guess bits (also called the witness if you prefer the verifier-style definition of $\mathrm{NP}$). This witness part can also be printed out as constant output gates of the constructed circuit.

Back to your question, we can easily adapt the above argument to deduce that the strange consequence of $\mathrm{DLogTime}$-$\mathrm{uniform}$ $\mathrm{Mod}_6^0 = \mathrm{NP}$ is that $\mathrm{Mod}_6PH = NEXP$. If someone can prove that $\mathrm{Mod}_6P$ is low for itself like $\oplus P$ then the consequence can be strengthened to $\mathrm{Mod}_6P = NEXP$


Existence of graph spanners An (unweighted) $k$-spanner of a graph $G$ is a subset of edges $S$ such that the distance between any two vertices of $G$ when using only edges in $S$ is at most $k$ times the distance in graph $G$. The goal is to find a small set $S$ that satisfies this constraint.

Recently, I've looked at some algorithms for this problem such as A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Interestingly, all of them seem to compute a $(2k-1)$-spanner that have at most $O(k n^{1+1/k})$ edges, for integers $k\ge 1$.

This made me wonder about the following:

  Is it impossible to construct a $k$-spanner for even $k$, e.g., $k=2,4$, in general graphs?

Strictly speaking it is possible to construct $2k$ spanners but, under some assumptions (see below), their size will never be asymptotically better than the size of the best $2k-1$ spanner.

Indeed, assuming Erdős Girth Conjecture, there are graphs $G=(V,E)$ with girth (length of the shortest cycle) $2k+2$ and $\Omega(n^{1+\frac{1}{k}})$ edges.

A $2k$ spanner $S$ of $G$ cannot exclude any edge $(u,v) \in E$. Indeed, if $(u,v)  \in E \setminus S$, either $u$ and $v$ are disconnected in $(V, S)$, or their distance in $(V, S)$ is at least $2k+1$. This is a contradiction.

This means that any $2k$ spanner of $G$ must have at least $\Omega(n^{1+\frac{1}{k}})$ edges. However, $O(n^{1+\frac{1}{k}})$ edges are already enough to guarantee the existence of $2k-1$ spanners in any graph, as you point out.


Solving $UCYCLE$ in logspace - two possible approaches ? Why can't we one of them use to solve connectivity? $$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$
There are two possible approaches to this exercise:
Solving cycle in undirected graph in log space?

https://stackoverflow.com/questions/29640543/solving-cycle-in-undirected-graph-in-log-space

These two solutions are different. The instresting solution is second one (on stackoverflow). In this case we generally implement DFS in logspace.  I can see that it does work (using DFS). However the question is:
Why we can't use this DFS algorithm to solve USTCON problem ?

However, I can see that we can't easily use this DFS to solve bipartity problem. It is not easy to count number of nodes in cycle.

Edit
Modified algorithm from stackoverflow (mentioned link) which should solve ustcon problem:

    for v_j in neighbours(s)
        current, prev = v_j, s
        repeat
            idx = neighbours(current).index(v_j)
            idx = (idx + 1) % len(neighbours(current))
            current, prev = neighbours(current)[idx], current
            if current = t then return connection between s and t
        until current adjacent to s
return no_connection between s and t

Your algorithm is from the paper Problems complete for deterministic logspace by Cook and McKenzie, where it is used to perform DFS on trees, as well as for related problems such as cycle detection. Presumably it doesn't work on graphs with cycles.


What is the best you can do with a noisy message? You play a TV game in which you have to open one door out of $n$. Behind each door, there is a treasure with probability 1/2, independent of the other doors, so your apriori chance of winning is 1/2.

In order to increase your chances, you can coordinate with a friend. You do the coordination before the game starts. Then, the friend can see what's behind all the doors, and send you a single integer number between 1 and $n$.

You receive your friend's number, but, in addition to that number, you receive $k-1$ more numbers between 1 and $n$, which are selected at random without replacement between 1 and $n$. You don't know which of the $k$ numbers is the real message and which is fake.

What strategy can you and your friend can coordinate, such that your probability of finding a treasure is maximized?

EXAMPLE: suppose $k=2$. Then, one possible strategy is that the friend just selects a door with a treasure behind it, and sends its number to you. You receive your friend's number and another number, in random order. Suppose you just pick the first number that you receive and open the door with that number. If it is your friend's number then you win; if this is a fake number then you have a chance of 1/2 to win. Hence, your total chance of winning with this strategy is 3/4. Is this correct? Is there a better strategy?

Suppose that $k \ll n$. In that case, your friend can send you the index of the first door containing a treasure. Of the $k$ numbers you get, you pick the smallest one. If $k$ is small enough compared to $n$, then it is very likely that the smallest of the $k$ numbers is the one that your friend sent you.

More concretely, suppose that $k$ is constant. With probability $1-1/n$, the number that your friend sends you is at most $\log n$. The probability that the other $k-1$ numbers are more than $\log n$ is $(1-\log n/n)^{k-1} \approx 1-k\log n/n$. We conclude that this strategy fails with probability at most roughly $1/n + k\log n/n$, which tends to $0$ as $n \to \infty$.

To determine how small $k$ should be, let us be a bit more careful. Denote by $m$ the number that your friend sends you; the distribution of $m$ is geometric (we ignore for now the event in which there are no treasures at all), and so $\Pr[m] = 2^{-m}$. The probability that one of the other $k-1$ numbers is smaller than $m$ is $1-(1-(m-1)/n)^{k-1}$. Overall, this strategy fails with probability
$$
\frac{1}{2^n} + \sum_{m=1}^n 2^{-m} \left(1 - \left(1 - \frac{m-1}{n}\right)^{k-1}\right) = 1 - \sum_{m=1}^n 2^{-m} \left(1 - \frac{m-1}{n}\right)^{k-1}.
$$
We can non-rigorously estimate this as
$$
1 - \sum_{m=1}^\infty 2^{-m}e^{-(m-1)k/n} = 1 - \frac{1}{2-e^{-k/n}} = \frac{1-e^{-k/n}}{2-e^{-k/n}} \approx \frac{k}{n}.
$$
This suggests that if $k = o(n)$ then you win with probability $1-o(1)$.


Quick sort worst case complexity improvement Can the worst case time complexity of quick sort be changed from $O(n^2)$ to $O(n\log n)$ by modifying it?

The simplest way is to choose the median as pivot. Since the median can be found in linear time, the overall algorithm would satisfy the recurrence
$$ T(n) = T(\lfloor \tfrac{n-1}{2} \rfloor) + T(\lceil \tfrac{n-1}{2} \rceil) + O(n), $$
whose solution is $T(n) = O(n\log n)$.


Finding $d$ in RSA Encryption mathematically and by hand I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically.

Let's say $p=11$, $q=13$
$$N=p \cdot q=11 \cdot 13=143$$
I chose $e$ to be relatively prime to $(p-1)(q-1)$, $e=23$
So the public key is $(23,143)$

Now I want to find out $d$ and for that I've come across $2$ different methods. First is using this formula
$$23 \cdot d \equiv1 \mod120$$ where I can't seem to work out what $d$ is. I tried to solve it like a quadratic equation $$23x=1 \mod 120$$
$$x=\frac {1}{23}$$ which doesn't make sense. Then I came across this other method to find the value of $d$.

$$∃k : e \cdot d +k(p-1)(q-1) \equiv1$$
$$23 \cdot (47) + (-9)\cdot120=1$$ So the private key would be $(47,143)$ but there is no mention of how they figured out the value of $d$ and $k$. That's why I need some help to work out the value of $d$ in a way so that I can find it given any problem.

Suppose that you know $e$ and $n$, and want to find out $d$ such that $ed \equiv 1 \pmod{n}$ (this is possible if $(n,e) = 1$). An efficient way to do this is to use the extended Euclidean algorithm, which finds two integers $a,b$ such that $an + be = (n,e) = 1$. You can use $d = b \bmod{n}$, since $de \equiv be \equiv 1-an \equiv 1 \pmod{n}$.


What's beautiful in CS? I'm afraid this may be opinion-based and not apt here, but...
Mathematicians often talk about "mathematical beauty", i.e. Gauss' proof of the Fundamental Theorem of Algebra, Euler's Formula, etc.
What's beautiful in Computer Science?
Things like the Church-Turing thesis or Curry-Howard correspondence are cool, but I'm not sure they are the same kind of "beauty" as mathematicians commonly prescribe.
Is it because CS is often an engineering field (despite its theories), and doesn't share the same notion of "beauty"?

As others have said, this is very opinion based. What's the difference between "cool" and "beautiful"? I find the Curry-Howard isomorphism beautiful, you don't. Neither of us is wrong.
Ultimately, Computer Science is a science of compromise. Mathematics is concerned with what "is": logical facts, pure truth and knowledge. Computer Science is concerned with what can be computed, and thanks to undecidability, that's really not that much.
There are uncountably many undecidable sets, but only countably many decidable ones.
So the mathematicians get to write beautiful pictures and draw beautiful diagrams about what is, in the abstract. And the computer scientists get to find the heuristics, the edge cases, the conservative approximations, and the impossibility results. In some sense, ours is a science of ugliness.
That said, everyone will find something beautiful in their field. In mine (Programming Languages), there's a whole category of paper called "Pearl" papers, where the design of something complex is made particularly simple or elegant by the programming language or technique used to create it. If you google "ICFP Functional Pearl" or "JFP Functional Pearl" you'll find a ton.


Two Turing machines $M_1$ and $M_2$ with $L(M_1) \subseteq L(M_2)$ Suppose $M_1$ and $M_2$ are two Turing machines such that $L(M_1)\subseteq L(M_2)$. Which of the following is true?

(A) On every input on which $M_1$ does not halt, M2 does not halt
(B) On every input on which $M_1$ halts, $M_2$ halts too
(C) On every input which $M_1$ accepts, $M_2$ halts.
(D)On every input which $M_2$ accepts, $M_1$ halts.

I am confused between B and C. This was an online practice test question.

For (B) my claim is that when $M_1$ is able to decide the language (i.e., $M_1$ halts on every input), then, since it is given $L(M_1) \subseteq L(M_2)$, $M_2$ should also halt and be able to decide on every input.

However, option (C) also looks convincing. If for every input $M_1$ says "yes" in the language, then $M_2$ should also be able to decide for that input.

Please let me know how to approach this correctly.

EDIT:
After reading the discussion, am I correctly interpreting the problem If I imagine the figure below

SO, (B) must be the wrong choice according to this right?

"Halt" is not synonymous with "accept", although the latter implies the former. A TM can halt and reject. On the other hand, $L(M)$ stands for the set of words accepted by $M$, not the words it halts for.

Hence, alternative (C) is correct. (B) is incorrect because $M_1$ could halt on and reject a word which is accepted by $M_2$ (i.e., a word in $L(M_2) \setminus L(M_1)$), or for which $M_2$ does not halt, even.

Note the question makes little sense, if any, if we assume $M_1$ and $M_2$ to be deciders since, then, all alternatives are correct, (A) because the premise is always false (since $M_1$ always halts) and the others because the respective implications are always true.


Is the capacity of a hash table a constant value? In this paper, page 4, it is said:

"...there is always a constant expected number of elements that map to the same slot"

Assume we have a set $S$ of $n$ values, and we want to insert them into a hash table. Let's fix some parameters: let $d$ be the hash table's bin/slot capacity, i.e. the bin will get more than $d$ elements only with a negligible probability. Then, we set the hash table length, $h$.

Question 1: is it correct that the capacity of each bin is constant?

Moreover, assume we want to perform an operation on only one bin of the hash table.

Question 2: Is it correct to say the complexity of the operation is constant? because it performs the operation on a constant elements of the set $S$?

Update: Please note that the updated is inserted after the answer is given by provided by @D.W.

I am using a simple static hash table. Assume that the number of elements $n$ is known in advance. Also, for some reasons we want a bin capacity be $d$ with a high probability (e.g. $2^{40}$). Moreover, we use the equation in theorem 1, in here to calculate the number of bins (or hash table length) required. Furthermore, we want to perform a polynomial factorization, whose complexity is $O(d^{2})$, in one bin.

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

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

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


Is the union of a non-regular and a regular language regular? I am studying Automata and stuck in a question that says:
Is the following a regular set {a^p, where p is prime} U {even-length strings}?

As we see here this language consists of two sub-languages. The left side one is infinite, and by using prove by pumping lemma, we will wind up that it is not regular.
However, the  right side one is also infinite but we can build the fsa for it and the regular expression is ((0+1)(0+1))*. So, it regular language.

What I stuck in is that When we Union regular language with non-regular language what is the the final result will be????

From the OR truth table it says to return TRUE value, either of them TRUE or both.

There is no simple rule.

Consider the languages

$L_1 = \{ a^n b^n \mid n \geq 0\}$,
$L_2 = \{ b^n \mid n \geq 0 \}$, and
$L_3 = \{ a^n b^m \mid n,m \geq 0 \}$.

Clearly, $L_2$ and $L_3$ are regular while $L_1$ is not. Furthermore,

$L_1 \cup L_2$ is not regular but
$L_1 \cup L_3$ is.

Therefore, you will have to look more closely at the language at hand and maybe try to proof both claims. Our reference material can help you get started; feel free to post any specific questions about your attempts as new questions.