Does a do-while loop suffice for Turing-completeness? I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need unbounded memory and certain operators...). The gist of my question is: does a do-while loop have the same computational power as a while-do loop? In other words, can a language be Turing-complete if it's impossible to skip instructions entirely.

I realise that some of the semantics here could be a bit ambiguous, so let me phrase the actual question with a specific example:

Brainfuck (BF) is a Turing tarpit where the only control flow is a while-do loop, denoted as [...] (there is a complete language spec at the bottom of the question, in case you're not familiar with Brainfuck). Let's define a new language BF*, where ,.+-<> have the same semantics as in BF, but instead of [] we have {} which denotes a do-while loop. That is, the only difference to BF is that every loop is executed at least once before further iterations can be skipped.

Is BF* Turing-complete? If it is, I'd be interested in how I could translate BF to BF*. If it isn't, how do I prove that?

Some observations of my own:

Not every BF program can be translated into BF*. For instance, it's impossible to write a program in BF* which may or may not read or print a value - if the program potentially prints one or more values, it will always print at least one. However, there might be a Turing-complete subset of BF which can be translated to BF*.
We cannot simply translate [f] (where f is some arbitrary, Brainfuck program consisting only of +-[]<>) to f-1{f} (in an attempt to cancel the effect of the first iteration), because a) not every computable function has a computable inverse and b) even if it did, f-1 wouldn't necessarily have fewer loops than f so applying this step recursively isn't guaranteed to terminate in the first place.

Here is a quick overview over the Brainfuck language. Brainfuck operates on an infinite tape where each cell contains a byte values, initially zero. Overflows wrap around, so incrementing 255 gives 0 and vice versa. The language consists of 8 instructions:

+   Increment the current cell.
-   Decrement the current cell.
>   Move tape head to the right.
<   Move tape head to the left.
,   Input a character from STDIN into the current cell.
.   Output the current cell as a character to STDOUT.
[   If the current cell is zero, jump past the matching ].
]   If the current cell is non-zero, jump back to just behind the matching [.

I don't know Brainfuck so you'll have to do some translation from my pseudocode.  But, assuming that Brainfuck behaves sensibly (ha!), everything below should apply.

do-while is equivalent to while-do.  do X while Y is equivalent to X; while Y do X and, assuming you have conditionals, while Y do X is equivalent to if Y then (do X while Y).

Life is a bit harder if you don't have conditionals.  If you have while-do, you can simulate if Y then X using something like this:

B := true
while (Y and B) do
    X
    B := false
endwhile

But what if you only have do-while?  I claim that the following simulates if Y then X, assuming that X terminates given the current value of the variables.  (This isn't guaranteed: the program if y=0 then loopforever terminates if y != 0, even though X loops for any value of the variables).  Let V1, ..., Vn be the variables modified by X and let X' be X modified so that it uses Vi' instead of Vi for each of those variables. swap(A,B) denotes the obvious code that swaps the variables A and B.

V1' := V1; ...; Vn' := Vn
V1'' := V1; ...; Vn'' := Vn
C := 0
do
    X'
    swap (V1',V1''); ...; swap (Vn',Vn'')
    C := C+1
while Y and C<2
V1 := V1'; ...; Vn := Vn'

The idea is the following. First, suppose that Y is false.  We simulate doing X once, and store the results in V1'', ..., Vn''; V1', ..., Vn' hold the original values of V1, ..., Vn. Then, we assign V1 := V1'; ...; Vn := Vn', which does nothing. So, if Y is false, we've done nothing.  Now, suppose that Y is true.  We'll now simulate X twice, storing the results in both the "primed" and "double-primed" variables. So, now, the assignments at the end of the loop have the effect that X was computed once. Note that Y only depends on the "unprimed" variables, so its value is not affected by running the loop repeatedly.

OK, so what if X might not terminate for the current value of the variables? (Thanks to Martin Ender for pointing out this possibility.)
In that case, we need to simulate X instruction-by-instruction, using similar ideas to those above. Each instruction definitely terminates so we can use the if simulation above to do instruction decoding, along the lines of "If the opcode is foo, do this; if it's bar, do that; ...". So, now, we use a loop to iterate through the instructions of X, using an instruction pointer and so on so that we know which instruction to execute next. At the end of each iteration of the loop, check Y and check whether X has halted yet. If Y is false, the swapping technique allows us to undo the effects of X's first instruction.


$\mathbf{NC}$ is closed under logspace reductions I am trying to solve the question 6.12 in Arora-Barak (Computational Complexity: A modern approach). The question asks you to show that the
$\mathsf{PATH}$ problem (decide whether a graph $G$ has a path from a given node $s$ to another given node $t$) which is complete for $\mathbf{NL}$ is also contained in $\mathbf{NC}$ (this is easy). The question then also makes a remark that this implies that $\mathbf{NL} \subseteq \mathbf{NC}$ which is not obvious to me.

I think in order to show this, one has to show that $\mathbf{NC}$ is closed under logspace reductions, i.e

$$(1): B \in \mathbf{NC} \hbox{ and } A \le_l B \Longrightarrow A \in \mathbf{NC}$$

where $\le_l$ is the logspace reduction defined as

$$A \le_l B :\Longleftrightarrow (\exists M \hbox{ TM}, \forall x)[x \in A \Longleftrightarrow M(x) \in B]$$

($M$ is a TM which runs in logarithmic space).

I would appreciate if someone could give a tip for proving the statement $(1)$.

Given any language $L$ in NL decided by some machine $T$, you can decide whether $x \in L$ by considering the configuration graph of $T$ when run on $x$. This is why PATH is NL-complete. Given any length $n$ of the input, the configuration graph is a fixed polynomial-size graph which doesn't depend on $x$. Only the starting vertex depends on $x$. We can arrange that the starting configuration corresponding to an input $x$ is configuration (vertex) number $x$. This implies that $L$ is in NC.

If we are careful we can do better and show that $L$ is in fact in uniform NC (under various definitions of uniform). The idea now is that given two configurations $\sigma_1,\sigma_2$, it is easy to decide whether $\sigma_1$ can reach $\sigma_2$ in one step. According to the complexity zoo, this way we can show that PATH is NL-complete under first order reductions (uniform AC0 reductions). Since uniform NC is closed under first order reductions, this implies that NL is in uniform NC.


The number of maximal independent sets An independent set is a set of vertices in a graph, no two of which are adjacent.
A maximal independent set is an independent set that you can not add any vertex.
I want to know if the number of all maximal independent set is an exponential number.

Yes, consider the graph that consists of vertices $v_1,\ldots,v_{2n}$ and edges $(v_1,v_2),(v_3,v_4),\ldots,(v_{2n-1},v_{2n})$. This graph has exactly $2^n$ maximal independent sets, because for each $0\leq i\leq n-1$, we can either choose the vertex $v_{2i}$ or $v_{2i+1}$.


What is "Containment order"? Could I get a friendly explanation? Reading the Wikipedia page was a little dense for me. Can anyone offer a friendly explanation of what this means? It sounds like it saying that if you have two ordered collections, if they are "ordered by containment" then they will be in roughly the same order with each other?

I'll try a down to earth definition \ example:

When speaking of a set $X$, lets say $X=\{1,...,100\}$,
denote the subset $X_i = \{1,...,i\}$

It holds that $X_1\subseteq X_2\subseteq...\subseteq X_{100}$

So you could say there is a containment order over these subsets, because each subset contains the other in an order that I stated. This order came from, and connected to (and isomorphic to) the partial order of $1 \leq 2 \leq ... \leq 100$ or if you prefer more fomally, that $(X,\leq )$ is a poset.


Algorithm for projection of polytope Let a convex bounded polytope be given by an intersection of half planes: $Ax \leq b$. Let $z=Cx$ be a vector (in my case $z$ is 2-dimensional, while $x$ has a higher dimension). How can I  compute $D$ and $e$ such that $Dz \leq e$ is a projection of $Ax \leq b$ into the $z$-space.

Theorem 3 in this paper gives you the algorithm for your case (projection onto a plane). For general dimension the problem is NP-hard.


reducing a decision problem to a local search problem Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states:

  If a PLS problem is NP-hard then NP = P

So assuming L is a PLS problem (polynomial local search problem) that is NP-hard, then every NP problem can be reduced to L.

Usually if  $P_1$ is reducible to $P_2$ (being two decision problems) then there is a polynomial time function $f$ such that:

$I_1$ is a positive instance of $P_1$ $\qquad$ if and only if  $\qquad$ $f(I_1)$ is a positive instance of $P_2$

However I'm not completely sure how would a reduction from a decision problem to a local search problem be.

I guess my question is: if $P$ is a decision problem which is reducible to the problem $L$, mentioned above, with the polynomial time function (or procedure) $g$ then complete the sentence:

$I$ is a positive instance of $P$ $\qquad$ if and only if $\qquad$ $g(I)$ is ....................

To compare search problems, polytime many-one reductions work as follows: $A$ is reducible to $B$ if there are polynomial-time computable functions $f$, $g$ such that for any $A$-instance $x$, if $y$ is a $B$-solution to $g(x)$, then $f(x,y)$ is an $A$-solution to $x$.

We can view decision problems as special cases of search problems with unique binary answers, but note that the reduction notions disagree. In particular, we cannot really see the difference between yes and no instances in the search problem view.


Constructing a new graph. G'. What does it mean v ∈ S_{i+1}? John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his  errands where he visits each of k different shop in order. However, each store have more than one location in his city. More particularly, for each 1 ≤ i ≤ k there is a set $S_{i}$ of vertices at which a branch of the $i^{th}$ shop is located (you can assume that the $S_{i}$ are disjoint). Construct a new graph G' as following:

  Create a new graph G' whose nodes are given by both a node of G,
  representing John’s current location, and a number 0 ≤ i ≤ k, giving the number of stops that John has successfully made. In particular, the vertices of G' are exactly given by (v, i) with v ∈ Node and i ∈ {0, 1,..., k}.  Edges in G' are between (u, i) and (v, i) if (u, v) is an edge of G, or between (u, i) and (v, i + 1) if (u, v) is an edge of G and v ∈ $S_{i+1}$.

What does it really mean by "between (u,i) and (v,i+1) if (u,v) is an edge of G and V v ∈ $S_{i+1}$"?

Let's say we have simple graph G as below:

Here is my attempt of constructing the new graph G'.

How many new nodes do we need to make, 3  or 4 copies? I only make 3 so far since there are only 3 errands. Please let me know if my G' is correct. Thank you.

The vertices of $G'$ are exactly given by $(v, i)$ with $v\in Nodes$ and $i \in \{0, 1,\cdots, k\}$.  Edges in $G'$ are between $(u, i)$ and $(v, i)$ if $(u, v)$ is an edge of $G$, or between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S_{i+1}.$

We know $Nodes$ are 6 nodes, i.e., $H, B1, B2, Bus, P, M$ and $k=3$ as there are three kinds of shops, i.e., bank, post office and movie where $S_1$ is the set of banks, $S_2$ post offices and $S_3$ movies.

There are 24 vertices of $G'$
$$\begin{align}
(H,0),(B1,0), (B2,0), (Bus,0), (P,0), (M,0), \\
(H,1),(B1,1), (B2,1), (Bus,1), (P,1), (M,1), \\
(H,2),(B1,2), (B2,2), (Bus,2), (P,2), (M,2), \\
(H,3),(B1,3), (B2,3), (Bus,3), (P,3), (M,3). \\
\end{align}$$

The edges are
$$\begin{align}
&(H,0)(B1,0), (B1,0)(Bus,0), (Bus,0)(P,0), (P,0)(M,0), (H,0)(B2,0) \\
&(H,1)(B1,1), (B1,1)(Bus,1), (Bus,1)(P,1), (P,1)(M,1), (H,1)(B2,1) \\
&(H,2)(B1,2), (B1,2)(Bus,2), (Bus,2)(P,2), (P,2)(M,2), (H,2)(B2,2) \\
&(H,3)(B1,3), (B1,3)(Bus,3), (Bus,3)(P,3), (P,3)(M,3), (H,3)(B2,3) \\
&(H,0)(B1,1), (Bus,0)(B1,1), (H,0)(B2,1) \\
&(Bus,1)(P,2), (M,1)(P,2)\\
&(P,2)(M,3)\\
\end{align}$$

  What does it really mean "between $(u, i)$ and $(v, i + 1)$ if $(u, v)$ is an edge of $G$ and $v\in S_{i+1}$" ?

It means exactly what it means.

For $i=0$, $v$ must be one of two nodes in $S_{0+1}=S_1$, i.e., $B1$ and $B2$.

If $v$ is $B1$, $u$ must be either $H$ or $Bus$ since all edges in $G$ whose endpoints include $B1$ are $HB1$ and $BusB1$. So $(H,0)(B1,1)$ and $(Bus,0)(B1,1)$ are edges in $G'$.
If $v$ is $B2$, $u$ must be $H$ since the only edge in $G$ whose endpoints include $B2$ is $HB2$. So $(H,0)(B2,1)$ is an edge of $G'$.

It should be clear now what should happen if $i=1$ or $i=2$. Note $i$ cannot be 3 since there is no $S_{3+1}.$

  How many new nodes do need to make, 3 or 4 copies ? I only make 3 so far since there are only 3 errands.

Yes, besides the $G$ itself, we should make 3 copies of $G$, one copy of $G$ for each shop John should visit. There should be 4 copies of $G$ with 6 extra (red) edges.


Finding the number of children of the predecessor node of a given node in a Binary Search Tree(BST) I have some propositions regarding BSTs , please can someone confirm whether they are true or false:

Question :

  1.Suppose we have a node $n_1$ with a value $val_1$ i.e $n_1(val_1)$

  2.We wish to find the number of children of the predecessor node of $n_1$ , with respect to inline traversal (That is the number of
  children of node $n_2(val_2)$ with $val_2$ being the greatest number
  $val_2 < val_1$)

  3.Assume for simplicity that the BST dosen't have any repetition

Proposition 1: Let $n_1$ have two children .Then $n_2$ has atmost one child i.e the number of children of $n_2$ can't be two

Proposition 2: Let $n_1$ have only one child and $n_1$ is not root ,then also $n_2$ has atmost one child.

Please ascertain whether these propositions are true , but if false can someone provide a counter example ?

The Q is not clear enough for me, an in-order traversal will get u "n2" as the predecessor of "n1" so  what is exactly required???

Regarding ur prepositions:

-P1:         if n1 has 2 children, or just a left child, then n2 is the rightmost leaf of n1's left child

So  Proposition 1 is  correct

-P2:
-As stated above, if n1 only child is a left child, n2  have atmost only left child.
(meaning not just at most 1, but it must be left)

-if n1 has only a right child, then reverse the argument; i.e., n2 is the node n1 is her left child of a right child (search upward for a node smaller than n1.. its parent if it is a right child does not make a difference if its parent has another left child or not, parent of parent,....)

For the bold case inside the brackets, ur second proposition is wrong.

I'll try to find an example picture, u may search any data structure text book for a complete tree to exhaust all different cases by ur self

Check the example in the second pic in this Q (My mobile is subject to a Denial of Service attack that prevents attaching it here again)

Ambiguity with the Top View of a binary tree

It is clear that 10 precedes 11, 11 has one right child while 10 has two


Pumping Lemma,regular languages Lets say that we have the  language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ }
What is the way that i should  follow to prove
that the language is not regular?

Assume that the language is regular.
So,there is a string $w\in L$  such that $w = xyz$ , $|xy|\leq n, y\neqε  $, n is the pumping length

Lets say that the string that i choose( w string)  is $w = a^nb^mc^{m+n}$
Is this choice correct ?
Can someone explain me the best choice of $y$ ?
Should be $y = a^{n-r} $  and $x = a^n $ ?  Because  of $|xy|\leq n$ ?
Thank you and sorry for my english.

Pumping Lemma for regular languages (by Wikipedia):
Let $\displaystyle L$ be a regular language. Then there exists an integer $\displaystyle p\geq 1$ depending only on $\displaystyle $ such that every string $\displaystyle w$ in $\displaystyle L$ of length at least $\displaystyle p$ ($\displaystyle p$ is called the "pumping length") can be written as $\displaystyle w=xyz$ (i.e., $\displaystyle w$ can be divided into three substrings), satisfying the following conditions:

$\displaystyle |y|\geq 1$
$\displaystyle |xy|\leq p$
$\displaystyle (\forall k\geq 0)(xy^{k}z\in L)$

Task
The given Language is $L = \{a^nb^mc^{n+m}|m,n\geq 0\}$. We want to show that L is not regular through proof by contradiction using the pumping lemma.
First we assume that $L$ is regular as you wrote. This implies the existence of the pumping length $p$. You called the pumping length $n$ which might lead to confusion cause $n$ appears in the definition of the language; so I called it $p$. Since we make a proof by contradiction we need to choose a word $|w| \geq p, w\in L$ and show for every possible partition into $w = xyz, |xy|\leq p, |y|\geq 1$ that there is a $k$ such that $xy^kz\notin L$.
Now what $w$ could you choose? I think $a^pb^pc^{2p}$ is a good choice.
Because $w = xyz = a^pb^pc^{2p}, |xy|\leq p, |y| \geq 1$ implies that $x = a^{i}, y = a^j, i+j \leq p, j\geq1$ thus $xy^pz \notin L$ because the the string would look like $a^{i+p\cdot j}b^pc^{2\cdot p}$ and $i+p\cdot j + p \neq 2p$, so the property of the language is violated. That's how proof using the pumping lemma usually looks like.


per-record timeline consistency vs. monotonic writes It seems to me that the per-record timeline consistency as defined by Cooper et al. in "PNUTS: Yahoo!’s Hosted Data Serving Platform" mimics the (older?) definition of monotonic writes. From the paper:

  per-record timeline consistency: all replicas of a given record apply
  all updates to the record in the same order.

This is quite similar to a definition for monotonic writes:

  A write operation by a process on data item x is completed before any
  successive write operation on x by the same process.

Can I conclude that those things are the same, or is there a difference that I misunderstand? Note that the link above also mentions possible copies of data item x, so monotonic write includes replicas.

I'm not sure these two concepts are really comparable.

monotonic writes is a client based consistency model. It defines what a process sees.

per-record timeline consistency strikes me as a memory based model. It doesn't even mention what a client sees or does.

So I would say they are not same or even comparable.


Why is the complexity of BFS & DFS frequently written as O(V+E) vs. O(max(V,E)) Why is the complexity of BFS & DFS frequently written as O(V+E) vs. O(max(V,E)) when the 2 are equivalent?

I feel like the latter conveys more meaning and is more simplified, and we can more easily see that the time grows as a function of the number of vertices OR edges, whichever is greater, whereas the latter reads "the time grows as a function of the number of vertices AND edges"

While they are equivalent from a big-$O$ perspective, I think that the former is preferable as it directly connects with how the algorithms are implemented. To see this, let's consider fully connected graphs vs. graphs with multiple components, including vertices which are completely disconnected.

In order to cover the former, $O(E)$ is completely sufficient. $O(V)$ is not, as every edge must be traversed. For the latter case, one must also consider all the disconnected vertices, so one has an additional complexity of $O(V)$. Thus, together we have $O(V+E)$.

From an informative standpoint it's clearer that we need to process all edges and vertices. By taking $\max$ it would seem to imply that it's sufficient to look at just edges or vertices. This is often why when we have algorithms dealing with multiple parameters they're all explicitly spelled out - $O(m+n)$ vs $O(m + log n)$ for example, even if $m > n$, because this matters; how does the algorithm behave if I change one of the parameters and leave the other untouched.


Example of non extensible functions ( $f(x) \notin EXT $) for reduction This is the definition of $EXT = \{x\ | \varphi_x\ can\ be\ extended\ to\ a\ total\ computable\ function \}$. I'm trying to proof that $\overline{K} \le_{rec} EXP$ and I can't think of an example of a function that can't be extended

Every total uncomputable function cannot be extended to a total computable function. More generally, let $g$ be an uncomputable function, and let $h$ be a total computable one-to-one function, for example $h(x) = 2x$. Define a partial function $f$ by $f(h(x)) = g(x)$ (so $f$ is defined only on the range of $h$). The function $f$ cannot be extended to a total computable function.


Travelling Salesman: Big O Complexity when starting city is fixed We are studying the Travelling Salesman problem in my high school class, and I am wondering what the Big O complexity of the TSP is when you MUST start and end at the same city. For example, given 4 cities labelled A,B,C,D and you MUST start and end at A, what is the big O notation for this? Is ((n-1)!)/2 for both symmetrical and asymmetric cases?

Thanks

The start city makes no difference. You're constructing a tour through all the cities, so it doesn't matter if you do ABCDEA or CDEABC.

Held–Karp solves TSP in time $O(n^22^n)$, which is much faster than $\Theta(n!)$.


How to select a binary tree node uniformly at random The exercise I'm trying to solve is

  You are implementing a binary search tree class from scratch, which, in addition, to insert, find and delete, has a method getRandomNode() which returns a random node from the tree. All nodes should be equally likely to be chosen. Design and implement an algorithm for getRandomNode(), and explain how you would implement the rest of the methods.

The answer from the book is:

 1  class TreeNode {
 2    private int data;
 3    public TreeNode left;
 4    public TreeNode right;
 5    private int size = 0;
 ...
12    public TreeNode getRandomNode() {
13      int leftSize = left == null ? 0 : left.size();
14      Random random = new Random();
15      int index = random.nextInt(size);
16      if (index < leftSize) {
17        return left.getRandomNode();
18      } else if (index == leftSize) {
19        return this;
20      } else {
21        return right.getRandomNode();
22      }
23    }
...
55  }

But here is the problem. With this algorithm, I don't see how nodes are equally likely to be chosen. In line 16, it says if leftsize > index, where index is a number from 0 to size, then the algorithm will continue with the left node, otherwise the right node. It only works when the tree has a depth of 2. When the tree is taller, the probability of each node being chosen will not be equal.

Am I wrong? Does this algorithm work?

The algorithm works just fine.

Note that each node's size field tells you the total number of nodes in the subtree rooted at that node. Throughout this answer, I'm just going to assume that a child's size is zero if the child is null.  Thus, for any node in the tree, we have

this.size == left.size + 1 + right.size

Consider the root of the tree.  If we choose a node of the tree uniformly at random, then it should be in the left subtree with probability left.size/size, it should be the root node with probability 1/size and it should be in the right subtree with probability right.size/size.  By the equation above, these three probabilities add up to 1.  If you look at lines 15–22, the algorithm implements exactly this probability distribution.  It generates a uniform random integer in the range 0 .. size-1.  If this number is in the range 0 .. left.size-1, the algorithm picks a random node from the left subtree; if it's equal to left.size, it picks the root and, otherwise, it picks a random node from the right subtree.

And the argument I gave doesn't depend on the node you consider being the root, so the recursive calls behave as they should.  The algorithm doesn't care about the depth of the nodes: it just recurses down the subtree and chooses subtrees with the correct probability.


Why there is light source? In ray tracing if we are tracing a ray from camera to the object, then why there is need for light source as in this image and also rays are going towards the light source instead of outgoing from the light source?

Recursive ray tracing associates an entire tree of rays with each image location.
Image from: Physically Based Rendering: From Theory to Implementation
by Matt Pharr, Greg Humphreys, 2010

There are two questions that you're asking here.

The first is why there is a light source. That's the easy part. Think what happens in the real world: if there's no light source, everything is dark and you can't see anything. That's an uninteresting case in computer graphics, so we usually don't consider it.

The second question is why rays are pointing to the light source instead of away from it. Physically, photons are emitted by light sources, and scatter around the physical environment, before hitting the imaging device (e.g. eye, camera).

It's possible to produce an image this way, like this for example:

Richard Keene produced this image in 1991. It was produced by tracing almost 30 billion photons from the light sources, which scattered around the scene until they hit the virtual camera lens. This took a month of compute time on 100 SPARCstations, each with 10MHz CPUs, and it's still quite noisy.

Keene repeated the experiment in 2004, this time using volunteers around the Internet donating computer time. I can't recall how long this one took, but 382 billion photons were traced in total:

The important thing here is that this technique is highly impractical. If you need to render an 85 minute movie at 24 frames per second, and allow a year of compute time, this turns out to be less than 5 minutes per frame. Clearly you can't spend 100 CPU-months on each image.

The problem is that if you trace photons from light sources, most photons don't hit the camera lens most of the time. If you continue scattering until they do hit the camera lens, they're usually so attenuated by that point that they contribute very little to the final image.

Ray tracing fixes this problem by tracing from the camera lens instead. Mathematically, a ray is the adjoint of a photon. This ensures that every trace contributes to the final image. However, you do then have the opposite problem. If you trace a photon from a light source, there's no guarantee that it will end up in the camera lens, but if you trace a ray from the camera, there's no guarantee that it will end up at a light source.

For this reason, most modern rendering algorithms (well, the ones that attempt to solve Kajiya's rendering equation) actually work in both directions. Photon mapping, bidirectional path tracing, and the Metropolis light transport algorithm (to pick but three) use information both from the camera and the light sources to try to spend most of the computer time on light paths which contribute to the final image.

If you're reading the book that I think you're reading, you'll get to all this in time.

EDIT Richard Keene himself chimed in, but unfortunately doesn't have enough rep yet to post comments on questions. So here's the link to his Photon Soup paper.

Richard, welcome to cs.se!


How to prove NP-hardness from scratch? I am working on a problem of whose complexity is unknown.
By the nature of the problem, I cannot use long edges as I please, so 3SAT and variants are almost impossible to use.

Finally, I have decided to go for the most primitive method -- Turing Machines.

Oddly enough, I could not find any example of NP-hardness reduction done directly by modeling the problem as a language, and showing that a deterministic Turing Machine cannot decide whether a given instance belongs to that language (I might've messed up with the terminology here).

So, assuming that there are no problems to perform an NP-hardness reduction, how does one prove that a problem is NP-hard? Are there any publications that does this?

I also want to add that I know how to perform an NP-hardness reduction. However, the problem that I am tackling is a "localized" geometric problem, that it does not allow me to model any given instance of 3SAT, 3-coloring, vertex cover, etc.

The immediate question comes to mind: "what if the problem is polynomial time solvable?"
Well, that is also a possibility, but I want to exhaust everything before I move onto designing an algorithm.

The only two methods I've seen are (a) a reduction or (b) direct proof (as in the proof of the Cook-Levin theorem).  It is almost universally the case that a reduction is easier than a direct proof.  Therefore, I suggest you keep trying to find a reduction, and consider other reduction partners.  There are lots and lots of problems known to be NP-complete; perhaps you can find one that is a more suitable partner than 3SAT.

Possibly useful: How do I construct reductions between problems to prove a problem is NP-complete?.


Are results after performing operations on AVL trees ambiguous? After performing operations (e.g. insertion/deletion of a node - rotations) on an AVL tree, is the result fully determined by the order of insertion on the initial tree, or do multiple solutions exists that satisfy all AVL properties?

In standard way the order of operations determines the tree shape - there are no ambiguous choices during insertion / deletion or rebalancing so it is unique.

There are more possible trees if you consider some additional operations that do not violate AVL properties like introducing stricter balance or rotating -1 to +1, please remember that this operations are non-standard and changing -1 to +1 serves only one purpose - to show different existing trees with AVL properties.


Algorithm for decomposing a complex (self-intersecting) polygon into simple polygons I've been attempting to write a Bentley-Ottmann sweepline algorithm to transform a self-intersecting (complex) into a set of simple polygons.

There are some instructions on this page (see the heading entitled "Decompose into Simple Pieces") however my current implementation is falling short (see img below).

While I'm able to find all the self-intersecting points I'm not able to construct the desired outputs when there are multiple self-intersections on a single segment.

Here is what I'd expect to get

I'm struggling to find any other papers which describe the process or required data structures in any more detail. The blog post references a linked list which could mean a Doubly Connected Edge List although I'm not 100% sure, the other challenge with that is that I don't think there is a suitable js implementation of that data structure.

Any advice on how I might reconstruct the desired output would be appreciated

Here is a thesis on exactly this topic:

  Subramaniam, Lavanya. "Partition of a Non-simple Polygon Into Simple Polygons." Master's
  thesis, University of South Alabama, 2003.
  PDF download.

Fig.10f, p.23.


What is responsible for the 1-1 correspondence between characters and binary? Could someone explain to me what component(s) are responsible for translating binary into ASCII/UNICODE? For example, is it an assembly program that sets up a 1-1 correspondence between characters and their binary equivalents, which is then loaded into ROM during manufacturing?

Internally, everything is binary and only binary. The only places that characters exist are places where you can literally see them with your eyes. For your benefit, and your benefit only, the system contains code that associates pictures such as a or 6 with those binary values and displays those pictures on the screen or on printer paper.


Calculating cache memory based on LRU algorithm Assuming i have 4 blocks of cache memory, Using the LRU (Least Recently Used)
replacement algorithm on this following sequence of access to memory blocks: 1 2 3 4 5 2 5 4 1 5 2 3 :

1   2   3   4   5   2   5   4   1   5   2   3

1   1   1   1   5   5   5   5   5   5   5   5
    2   2   2   2   2   2   2   2   2   2   2
        3   3   3   3   3   3   1   1   1   1
            4   4   4   4   4   4   4   4   3

So in the end, the cache memory will contains this memory blocks : "5 2 1 3"

But the correct answer is "1 5 2 3"

Please tell me what am I doing wrong here!

Least recently used cache do the following things:
we add the numbers to the top(front) representing that it is the "most recent" and thus the end of this will be the number which is least recent.

If the cache is not full,
1 a). add to the cache if the entry is not in the cache.
1 b). If the entry is in cache we make that most recent and continue.
If the cache is full,
2 a) If the value is already in the cache we just move it up(front) so that it represent most recent after this.
2 b) If the value is not in the cache we remove the least recent one and add the current value to the top(front)to represent that as the most recent.

Now let me explain you the sample which you have provided.

**Input**                     **cache**(front represent most recent and end represent least recent

1   2   3   4   5   2   5   4   1   5   2   3  --> inputs

1   2   3   4   5   2   5   4   1   5   2   3  --->(this is our cache) **top represent most recent**
-   1   2   3   4   5   2   5   4   1   5   2
-   -   1   2   3   4   4   2   5   4   1   5
-   -   -   1   2   3   3   3   2   2   4   1  ----> **end represent the least recent**

So we have our answer as,(from most recent to least recent) = 3,2,5,1

hope this helps you.Sorry for my bad editing.


Space Complexity of Bottom-Up Merge Sort What is the space complexity of Bottom-up merge sort?
It uses iteration rather than recursion so it will not use stack. But will an auxiliary array be used for the merge operation?
Please explain.
Thank you.

Yes, an auxiliary array is required for the merge operation.  The space complexity would be $\Theta(n)$, where $n$ is the size of the input.

The merge subroutine can create a temporary array to store the result of the merge operation and its contents can then be copied into the input array.  Or, an array having the same size as input can be created in the beginning and passed as an extra argument to the merge subroutine.


Complexity of bitwise AND operation on bit string regular expressions Given two regular expressions of bit strings $B_1$ and $B_2$ of the same length (stated mathematically, $B_1,B_2 \in \{0,1\}^m$) that use only grouping and repetition, what is the optimal running time of performing a bitwise AND operation on $B_1$ and $B_2$?

For example, given two regular expressions, $B_1 = ((10)^2(01)^2)^2$ and $B_2 = (01)^8$, the resulting pattern $R$ of the AND operation would be $R = ((0^4(01)^2)^2$.

Does there exist an algorithm that will run in polynomial time (with respect to the lengths of the regular expressions)? Note, you can pair every possible combination of groups in $O(n^2)$ time, where $n$ = $\max(|B_1|,|B_2|)$, and $|B_i|$ is the length of regex $B_i$.  However, that still does not give you the resulting bit string regular expression $R$.

The exponent $k$ of a given substring can be stored in binary form, so it only adds $\log(k)$ bits to the representation.  Furthermore, note that given any two groups of size $m$ and $n$, there are at most $\max(m,n)$ bit patterns of length $\min(m,n)$ that can result.  In addition, if there are $g_1$ groups in $B_1$ and $g_2$ groups in $B_2$, then there can only be $g_1 g_2$ unique pairs of groups.  Therefore, I think it can be concluded that the space required is at most $O(g_1 g_2 \max(|group_{i,B_1}|,|group_{j,B_2}|)^2)$, which is polynomial in $n$.  However, I am still missing the proof that the resulting regular expression can be found in polynomial time.

For slightly easier problem, you can assume that every repetition is a power of two.  However, that does not necessarily mean that groups are power of two in size.  For an even further simplification you, could assume the groups are also a power of two in size.

Now that I think of it, I will include this idea which I just came up with.  You can represent the offsets of the 1s every group as set of linear integer equations.  Then you may be able to find solutions to pairs of integer equations with constraints somehow?  Or am I over complicating it?

Another possibility is, as Yuval Filmus suggests, convert to NFA.  However, I am not clear why an NFA would be needed since these are fixed sequences (that is, the number of repetitions is fixed).  Furthermore, I am not sure how one would apply the AND operation after they are in NFA form.

Formalism

Let me formalize your problem as follow.  Define a gegular expression as an expression that follows the following grammar:

$$E ::= 0 | 1 | E_1 E_2 | E^k,$$

where $k$ ranges over positive integers and $E_1,E_2$ range over gegular expressions.  Note that these are not regular expressions, as Yuval Filmus explains, even though they are related.

Obviously, each gegular expression codes for a single binary string.  If $E$ is a gegular expression, let $[E]$ be the binary string is codes for.  Also let $\text{len}(E)=\text{len}([E])$ denote the length of the binary string $[E]$.  Of course, these can be easily computed recursively: e.g., $\text{len}(E_1 E_2) = \text{len}(E_1) + \text{len}(E_2)$ and $\text{len}(E^k) = k \times \text{len}(E)$.

Given two gegular expressions $E_1,E_2$, the ultimate goal is to find a third gegular expression $E_3$ such that

$$[E_3] = [E_1] \land [E_2],$$

i.e., that represents the bitwise-AND of the bit strings that $E_1,E_2$ code for.  If this holds, we will write $E_3 = E_1 \land E_2$.  ($E_3$ may not be unique -- there may be multiple acceptable $E_3$ -- but we won't let this bother us.)

Helpful tools

Here are some little lemmas that are helpful.

First, if $E$ is a gegular expression and $\ell$ is a positive integer, we can compute a new gegular expression that codes for the first $\ell$ bits of $[E]$.  Define $\text{prefix}_\ell(E)$ to be this gegular expression.  We can compute $\text{prefix}_\ell(E)$ recursively using the following relations:

$$\text{prefix}_\ell(E_1 E_2) =
\begin{cases}
\text{prefix}_\ell(E_1) &\text{if $\ell < \text{len}(E_1)$}\\
E_1 &\text{if $\ell = \text{len}(E_1)$}\\
E_1 \; \text{prefix}_{\ell-\text{len}(E_1)}(E_2) &\text{otherwise.}
\end{cases}$$

$$\text{prefix}_\ell(E^k) = E^{\lfloor \ell / \text{len}(E) \rfloor} \; \text{prefix}_{\ell \bmod \text{len}(E)}(E).$$

You might notice that this does not increase the size of the gegular expression too much (at most a quadratic blowup, and usually much less).

Also, there are some special cases where your problem is easy.  For instance.

$$E_1^k \land E_2^k = (E_1 \land E_2)^k$$

if $\text{len}(E_1)=\text{len}(E_2)$.

If the exponents are not identical, we can reduce to the above case.  Let $E_1,E_2$ be two gegular expressions of lengths $\ell_1,\ell_2$, respectively (i.e., $\ell_i = \text{len}(E_i)$).  Let $m = \text{lcm}(\ell_1,\ell_2)$ be the least common multiple of their lengths.  Then

$$E^k = (E E \cdots E)^{\lfloor k/m \rfloor} E E \cdots E$$

holds for all $E,k,m$, where the first $E E \cdots E$ represents $m$ concatenations of $E$ and the second $E E \cdots E$ represents $k \bmod m$ concatenations.  Thus we have

$$E_1^{k_1} \land E_2^{k_2} =
(E_1 E_1 \cdots E_1 \land E_2 E_2 \cdots E_2)^{k_3} \;
\big( \text{prefix}_{\ell'_1}(E_1^{k_1}) \land \text{prefix}_{\ell'_2}(E_2^{k_2}) \big),$$

Also, if $\text{len}(E_1) = \text{len}(E'_1)$, then

$$(E_1 E_2) \land (E'_1 E'_2) = (E_1 \land E'_1) (E_2 \land E'_2).$$

If they are not of the same length, say $E_1,E'_1$ have lengths $\ell_1,\ell_2$ where $\ell_1<\ell_2$, then we can express their bitwise-AND as

$$(E_1 E_2) \land (E'_1 E'_2) = (E_1 \land \text{prefix}_{\ell_1}(E'_1)) (\text{prefix}_{\ell_2-\ell_1}(E_2) \land \text{tail}_{\ell_2-\ell_1}(E'_1)) (\text{tail}_{\text{len}(E'_2)}(E_2) \land E'_2).$$

(Here $\text{tail}()$ is defined analogously to $\text{prefix}()$, except it relates to the end of a string rather than the beginning.)

I think from these special cases, you should be able to build a recursive algorithm that computes the bitwise-AND of any two gegular expressions.


Heuristic for Finding Multiple Goals in Graph - e.g. using Kruskals Algorithm I'm a none-computer-science-student and get some knowledge on AI by taking the CS188.1x Course (Artificial Intelligence) on www.edx.org .

Currently, I am working on the "Search in Pacman" Project; the sources can be found online at Berkley CS188 . I have problems finding an good solution for "Finding All the Corners", so I need a good Multiple Goal Heuristic.

I allready tried the simple approach described in here. I used the minimum of all manhattan distances to all goals. This works, but is considered a rather poor heuistic, because my A-Star Algorithm expands 2606 nodes for the given maze. Using the same with euclidean distance expands even 103081 nodes. A good heuristic should expand 1600 nodes or less. A very good one 1200 nodes, an excellent one even 800 or less.

I got a hint by other students who use minimum spanning trees created with Kruskal's Algorithm. I wanted to investigate into that direction, but I am somehow confused how the Kruskal Algorithm can be used to get a Heuristic?
As far as I understood, this Algorithm returns a minimum spanning tree (MST) which is a path, right? So it is a solution to the Traveling Salesman Problem (TSP); it returns a sequence of nodes. But I need a heuristic, so a cost function which can be applied to this problem and called by an Algorithm (like A*).

Can anyone of you give me a hint on how to proceed? Every help is highly appreciated!

MST is actually a tree, not a path (generally). Therefore, it is not a solution to TSP. (Although, MST can help you to find a solution that is not more than twice as long as the optimal solution, if you solve this in a metric space on a complete graph. That's unrelated story.)

Now, I must admit that I do not see a way spanning trees can help you if the maze contains loops. And in the case that the maze does not contain loops, it is somehow weird to talk about MST, because the graph of the maze is a tree.

However, maybe you can start to think about this: in a tree, for any two nodes, there is exactly one path that connects them. That's a trivial, but quite a nice property, isn't it? Length of this unique path is an easy lower bound that is more precise than Manhattan distance.

If you build MST over a graph with loops, this would probably not make an admissible heuristic, because the path using only MST edges can be longer than some path over edges you haven't choose to the spanning tree.

"Minimality" of MST is somehow a local property -- it's not like all the shortest paths are preserved. This is why I would never think about solving your problem with MST.


Deamortizing a Las-Vegas randomized algorithm Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound.

For example, assuming you need to find the median of an array once every $n$ operations of type $X$ (which does not change the array).

You could take a specific algorithm, such as the median of medians selection algorithm, which takes at most $c\cdot n$ time, and perform $c$ of its operations every time $X$ is performed.
This guarantees that the worst case run time of finding the median in each $X$ call is constant.

But now assume we'd like to use a randomized Las-Vegas algorithm (always correct, runtime is computed in expectation), such as computing the median by selection with random pivot.

Now we know that the algorithm is expected to take $c'\cdot n$ operations, but it might take more, or less.

How do you determine how many of the iterations you run every time $X$ is performed?
Can we say that by performing, say, $2c'$ operations every time we will finish computing the median with high probability?
Can we adaptively select how many operations of the selection algorithms to perform at each of $X_1,X_2\ldots X_n$ calls such that we will finish computing the median with probability $1$, but so that with high probability, the number of operations in each $X$ call is constant?

If the expected running time of the algorithm is $c'n$, then Markov's inequality shows that for all $A$, the probability that the algorithm takes more than $Ac'n$ operations is at most $1/A$. If you run $Ac'$ operations each time then you will finish computing with probability $1-1/A$, and if you run $Ac'$ operations each time until the last step, at which you let the algorithm loose, then the number of operations will be at most $Ac'$ with probability $1-1/A$.

In some cases you know more about the distribution of the running time of the algorithm – say its variance. In that case you can get better bounds using (for example) Chebyshev's inequality.

Another trick to try is to run several instances of the algorithm in parallel with fresh coins. For example, suppose that we run $B$ independent instances of the algorithm, each for $(A/B)c'$ operations at each step. The probability that none of them finishes is at most $(B/A)^B$, compared to $1/A$ we had before. Choosing $B \approx A/e$, this improves the failure probability from $1/A$ to roughly $e^{-A/e}$.


Is it possible to copy data in a linear type system? I'm having a little problem with the abstraction layers in linear types. If every variable is used exactly once, there is no way to copy data, since you have to read each datum twice in order to write it twice to two different locations.

However, you could argue that once a variable is loaded into a register, you may do whatever you want with it, so a -> (a,a) is a possible function. I'm simply not sure where the line is drawn, or why.

Linear types in programming allows a compiler to build efficient pipelines of data transformation. Single-use variables allows in-place mutations in pure functional languages, and/or a memory-efficient implementation without using a garbage collector. Copying a value might make this process a lot more difficult, if not impossible, but I'm not sure.

Is it possible to copy data in a linear type system? Why?
Are there any (big) programming languages that implement linear types with/without copying?

I don't know why you bring up registers at all, but the answer to your first question is "sure".  You (potentially) are able to copy data, you just aren't able to do it freely.  For example, an operation $\mathtt{dup}_A : A \multimap A\otimes A$ may be provided, but only for certain types $A$.  Most commonly there are "exponentials", written $!A$ for which $\mathtt{dup}_{!A}$ is definable or given.  The opposite operation is often called $\mathtt{kill}_A : A \multimap 1$ or $\mathtt{discard}_A$. You may start to see how this leads to a kind of functional manual memory management.

For programming languages, the exponential modality is usually the opposite of what we want as it allows the defining an operation of type $!A \multimap A$ via a rule called "dereliction".  If we think of $!A$ as a type that may have multiple references, then a linear type $A$ means that references to $A$ will not be duplicated, not that it hasn't already been duplicated.  A different modality leading to uniqueness logic gives the more commonly desired sense of a variable of type $A$ has not been multiply referenced (and thus we are free to mutate it, for example).

The main "serious", general purpose languages I'm aware of using substructural types are: Rust, Clean, and Pony. Rust and Pony allow freely "copying" primitive types but put restrictions on reference types.


Maximum minimal set coverage Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq \bigcup_{e\in F}e$. Consider the following max-cost set covering problem:

$\text{argmax}_{E\subseteq F} |E|$

s.t. $U\subseteq \bigcup_{e\in E}e$ and $U\not\subseteq \bigcup_{e\in E'}e,\forall E'\varsubsetneqq E$

I failed to find any literature addressing this. I was just wondering if I could have some references with regard to this problem. Thank you!

Hardness

Your problem might be called "maximum minimal set cover".  In particular, your problem feels like it might be related to minimum maximal matching, which is NP-hard.  If you wanted to try to prove NP-hardness, you might try to see if you can find a reduction from minimum maximal matching.

Algorithms

Your problem can be expressed as an instance of SAT, and then you could apply an off-the-shelf SAT solver.  In particular, we formulate the decision problem variant, where we are given $F$ and an integer $k$, and we ask whether there exists a maximal cover $E$ such that $|E|=k$.   To express this decision problem in SAT, we introduce constraints to capture two different aspects of the problem:

The requirement that $E$ be a cover of size $k$:  We introduce boolean variables $x_f$ (one for each $f \in F$), with the intent that $E=\{f \in F : x_f = \text{true}\}$.  It is easy to write down boolean constraints on the $x_f$'s to express the requirement that $E$ be a cover (i.e., for each $u \in U$, you have a clause $\lor_{u \in f} \; x_f$) and that $|E|=k$ (see this answer for several ways to express the latter in SAT).
The requirement that no subset of $E$ be a cover: We introduce the boolean variables $y_g$ (one for each $g \in F$), with the intent that $y_g$ is true if and only $E\setminus\{g\}$ is a cover.    It is straightforward to write down boolean constraints to ensure that each $y_g$ has the appropriate value (i.e., $y_g = \land_{u \in U} \lor_{u \in f, f \ne g} \; x_f$; now apply the Tseitin transform).  Then, we can add the clause $\neg x_g \lor \neg y_g$ for each $g \in F$.

Now there exists a maximal cover $E$ of size $k$ if and only if there is some satisfying assignment for this SAT instance.  So, run an off-the-shelf SAT solver on this, and do binary search over $k$ to find the largest such cover, and you are done.

Alternatively, you can express your problem as an instance of integer linear programming, and then apply an off-the-shelf ILP solver.  This might provide reasonable approximations to the optimum in practice, as many ILP solvers have heuristics to try to find an approximate optimum (i.e., a valuation to the variables that makes the objective function as large as they're able to).

One approach to formulate this as an ILP instance is similar to that for SAT:

The requirement that $E$ be a cover of size $k$: We introduce an integer variable $k$.  Also, we introduce integer variables $x_f$ (one for each $f \in F$) that are constrained to be zero or one.  Zero plays the role of false, one the role of true.  Thus, the intent is that $E=\{f \in F : x_f=1\}$.  It is easy to write down linear constraints to express the requirement that $E$ be a cover (i.e., for each $u \in U$, we have the inequality $\sum_{u \in f} x_f \ge 1$) and that $E$ have size $k$ (i.e., $\sum_f x_f = k$).
The requirement that no subset of $E$ be a cover: We introduce linear constraints to express the requirement that if $x_f=1$, then $E\setminus \{g\}$ is not a cover, for all $g \in F$.  This can be done using the methods described here: Express boolean logic operations in zero-one integer linear programming (ILP).

In particular, here's what it looks like.  Introduce zero-or-one integer variables $y_{g,u}$ for each $g \in F$ and each $u \in U$, where $y_{g,u}=1$ is intended to represent that $E \setminus \{g\}$ does not cover $u$.  In particular, for each $u \in U$ and each $g \in F$, add the inequality

$$\sum_{u \in f,f \ne g} x_f \le K - K y_{g,u},$$

where $K$ is a sufficiently large constant ($K=|U|$ will suffice).

Also, for each $g \in F$, add the inequality

$$\sum_{u \in U} y_{g,u} \ge 1.$$

This ensures that, for each $g \in F$, $E\setminus\{g\}$ is not a cover (since there exists $u \in U$ such that $E\setminus\{g\}$ does not cover $u$).
Maximize $k$: You want to maximize $k$.  So, your integer linear program is: maximize $k$, subject to the linear inequalities mentioned above.

Now you can apply an off-the-shelf ILP solver to this ILP instance.


What is the result of a reduction operation called? Is there a commonly used term for the result of a reduction operation?

"reductant" does not quite sound right...

In the context of reducing one language to another, I have only ever seen this referred to using phrases such as "the problem being reduced to", "the target of the reduction", etc. I don't think there is a single word for it—certainly not one that would be universally understood.


Are there variations of the regular runtimes of the Big-O-Notation? There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically incorrect.

Or would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$? I can't and don't need to figure out runtimes yet and I do not need to improve anything, but I'd need to know if this how you describe your functions in reality.

I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log (n^2))$, or if those are mathematically incorrect.

Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations.

However, you will see them rarely if you would see them at all, especially in the end results. The reason is that $O(2n^2)$ is $O(n^2)$. Similarly, $O(\log (n^2))$ is $O(\log n)$. That might be surprising to beginners. However, those equalities are more or less the very reason why big $O$-notations were introduced, to hide a multiplicative constant factor that is often hard to pin down and relatively insignificant.

  Would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$?

It is not an improvement at all if the time-complexity of an algorithm is changed from $O(5n^2)$ to a $O(3n^2)$ or from $\Omega(5n^2)$ to $\Omega(3n^2)$, because $O(5n^2)$ is $O(3n^2)$ while $\Omega(5n^2)$ is $\Omega(3n^2)$. So it is incorrect to say the time-complexity is improved from $O(5n^2)$ to $O(3n^2)$. It is correct to say the time-complexity of an algorithm is improved from $5n^2$ to $3n^2$, of course.

Exercise 1. Show that $O(5n^2)=O(3n^2)=O(n^2)$.

Exercise 2. Show that $O(\log n)=O(\log (n^2))$.

Exercise 3. Show that $\Omega(n^2+n)=\Omega(n^2)$.


Why the given statement can't be expressed using predicates and quantifiers in the way described in details? Suppose there is a statement -

  Some students in this class has visited Mexico.

Solution given is: considering the universe of discourse for the variable $x$ consists of all the people. Our solution becomes $\exists{x}[S(x)\land{M(X)}]$ where the predicate $S(x)$ tells $x$ is a student in the class and $M(x)$ tells $x$ has visited Mexico.

The solution also tells $\exists{x}[S(x)\implies{M(X)}]$ is wrong because this expression is true when there is not someone in the class. So the statement can't be described in this way.

My questions is that only - What's wrong in giving true when there is not someone in the class (or true even when the someone is not student) ? Why exactly can't the statement be expressed using implication?

Rephrasing that second version back into English:

  There exists a person $x$, such that if $x$ is a student, then $x$ has gone to Mexico.

If there exists anyone who's not a student, this ends up being true. "If false then [anything]" is always true, so when "$x$ is a student" is false, "if $x$ is a student, then $x$ has gone to Mexico" is true—whether or not $x$ has gone to Mexico.

What you want is:

  There exists a person $x$, such that $x$ is a student, and $x$ has gone to Mexico.

That is indeed what the first given solution means.


How to calculate the number of weights for a CNN? Can somebody help me with the formula needed to calculate the number of weights for a CNN, using the following sample question as the basis for it?

Suppose we have a convolutional neural network with a 5x5x1 input
volume, followed by one convolutional layer with 5 filters that have a
2x2x1 receptive field, followed by one fully connected output layer
with 5 neurons.  How many weights does the network have in total?

Any help appreciated because I keep getting the wrong answer. I think the first part is:
5 * (5 * 5 * 1) + 5
And this gives 130, it might be completely wrong anyway I am doing:
filters * (5 x 5 x 1) + filters
For the second part (2 * 2 * 1) with five filters I get:
filters * ( 2 * 2 * 1) + filters = 25
So now I have a total value of 155 and after this I am unsure how to factor in the output neurons and arrive at the answer (which I know is 430).

Each receptive field of a filter has a weight. Furthermore, the whole filter has a single bias.
This gives for a single filter:
2*2*1+1 = 5 weights per filter.
5 filters * 5 weights = 25 weights for all filters.
The conv layer produces shape (4, 4, 5) if we assume the stride is 1.
The fully connected output layer (dense layer) has 5 neurons. Each of them is connected to the output of the conv layer.
So it's (4*4*5) * 5 neurons = 400 connections. Each of these connections has a weight. Each neuron in the dense layer also has a bias, so there are 5 more weights.
To sum up: 25 parameters for conv layer, 405 parameters for dense layer. 430 in total.


Is it reasonable to consider a book's table of contents as a hierarchical collection? if yes, what does the root node represent? this book "Fundamentals of Python: Data Structures 1st Edition" says

  data items in hierarchical collections are ordered in a structure
  resembling an upside-down tree. Each data item except the one at the
  top has just one predecessor
  ...
  A file directory system, a company's organizational tree, and a book's
  table of contents are examples of hierarchical collections

each hierarchical collection has a root node, is it reasonable to consider a book's table of contents as a hierarchical collection? if yes, what does the root node (one at the top) represent?

The root node is the entire book.
Its children are chapters.
Their children are sections. And so on.

This is reflected in the standard numbering system, in which chapters are labeled by numbers, sections are labeled by numbers within chapters, and so on.

As an example, we can take the table of contents of the book you mention. The root has 15 children: an introduction, 12 chapters, an appendix, and the index. The first child (introduction) is a leaf. The second child has 9 children, which are the various sections: basic program elements, control statements, and so on. The first child (basic program elements) has 19 children, all leaves: programs and modules, an example python program, and so on.


Count unique increasing subsequences of length 3 in $O(n\log n)$ Problem: Given an array of $n$ integers, $A[1 \dots n]$, such that any integer occurs at most 2 times in the array, we have to find the number of unique increasing subsequences of length 3 (duplicate subsequences must be counted only once). In other words, we have to count the number of unique integers $A[i], A[j], A[k]$ such that $A[i] < A[j] < A[k]$ with $i < j < k$.

I have been stuck on this for quite a while now. I did look up this question which tests for the existence of such a triplet. But I think my question is different because it needs the count, and because it needs unique triplets (upto 1 repetition of any number is allowed).

Idea: $O(n^2)$ algorithm. For each number, we can scan the remaining array and find out how many unique numbers are greater than it and occur after it. This can be done in $O(n^2)$ by naive brute force. For every pair of numbers ($O(n^2)$), we now have the number of possible triplets that can be formed by using the pair as the first two numbers of the triplet (since we know how many are greater than the second number).

Unfortunately, $O(n^2)$ is too slow, and I need a faster solution - $O(n\log n)$ or $O(n)$. Space complexity also has to be sub-quadratic. I was thinking along the lines of sorting a copy of the array to find out the relative rank of each element, but could not go any further. Any help or hints are greatly appreciated!

Here is an algorithm to count distinct subsequences of length $3$ in time $O(n \log n)$, regardless of how many times any value $a$ occurs in $A[j]$.

First, create a binary search tree $T$ containing all possible values $a = A[j]$, storing at each node how many times it occurs in $A$, and how many nodes there are which follow it in the tree (are further to the right) representing larger values $A[k]$. Note that with each insertion (and later, removals), the tally of further-right values will become out of date for many of the nodes. However, we can maintain these values for each node lazily, by maintaining at each parent node a count of the pending counter updates for its left and right subtrees. (When we later traverse to a child node, its own counter of larger elements, and its pending-update counters for its children can be adjusted by the amount indicated by its parent.) Similarly, any insertions or removals in the right subtree of a node leads to a pending update for the left subtree. This should also be implementable for balanced trees as well, such as AVL trees or red-black trees. We will henceforth suppose that as we traverse any particular node that its counter is thereby kept up-to-date, though it may become out of date in between visitations.  Constructing $T$ takes time $O(n \log n)$.

We traverse $A$ once more, creating a tree $F$ which also contains values $a = A[j]$ and the number of nodes to the left of each node, similarly to $T$. (We also maintain a separate counter at each node of $F$ of how many nodes have been added to its left since the last time we look up the node in the tree; this uses a similar update method as the total-counter, though because we would clear this counter each time the node is visited, in practise we just use the pending-update value for its parent node.) At the same time we will be disassembling the tree $T$, and counting distinct increasing subsequences in $A$ of length 3 by considering, using $F$ and $T$, how many different values of $a'$ and $a''$ can serve as the first and respectively third value in an ordered triple $(a',A[j],a'')$. We do this as follows.

Set $N := 0$. For each $1 \leqslant j \leqslant n$ in order, do the following:

Let $a := A[j]$. Decrement the occurance counter of $a$ in $T$. This takes time $O(\log n)$.
Search for $a$ in $F$. If it is not present, insert it, and set
$$\text{incr} := \#(\text{nodes left of $a$ in $F$}) \cdot \#(\text{nodes right of $a$ in $L$}).$$
Otherwise, if $a$ is already present, set
$$\text{incr} := \#(\mathop{*}\text{newly added}\mathop{*} \text{ nodes left of $a$ in $F$}) \cdot \#(\text{nodes right of $a$ in $L$}).$$
This takes time $O(\log n)$ as well.
Add $\text{incr}$ to $N$.
If the occurances counter of $a$ in $T$ has dropped to $0$, remove $a$ from $T$. This takes time $O(\log n)$.

[Edited to add: as Peter Shor notes in the comments, rather than storing in $T$ the number of times $a$ occurs in $A$, we can simply store the last index $1 \leqslant j \leqslant n$ such that $a = A[j]$ for the purposes of this algorithm. Then, rather than actually removing $a$ from $T$, we can just perform the decrement of the further-right tallies for all of the nodes to its left. The decrease in arithmetic and tree-modification operations would give rise to some modest savings in run-time.]

The total run-time of this algorithm is $O(n \log n)$. In each iteration of the loop above, we only count the number of ways in which elements smaller than $a$ which haven't been used yet as a subsequence starter can be combined with elements larger than $a$ which still have at least one occurance later in the list, with $a$ itself in the middle. Thus, we count the number of "newly possible" subsequences there are for each $A[j]$ as new first elements are made available for each remaining available third element, and accumulating them for  $1 \leqslant j \leqslant n$.


Proof for TM accepting any PDA-language How do you suggest I go about proving this:

Give a short, basic outline of a proof that Turing machines can accept all languages accepted by PDAs. You are allowed to use a non-standard Turing machine.

The best I can come up with is that since TMs are equivalent to computers, where as PDAs are not. A TM accepting any PDA-accepted language is understandable. (Church-Turing thesis)

BTW, I know PDAs accept CFLs, but is that all they accept?

Simple, I don't know if you want the full answer but here is my proof:

We know that
"A language is CF iff a PDA recognized it", and you know that this proof has two directions, I won't prove it here either.
We can answer your question if we proof: "Any PDA has an equivalent TM".

IDEA:

Let state a TM M and a PDA P.

We know that any operation in P has the following format:
a, b -> c, where a is the item you have at the input, b is at the top of the stack and c the symbol I want to put at the top of the stack.
We can simulate all the possible operations of P on M and the stack on the tape.

How? P will be simulated on two tapes: one for reading the input and the other for simulating the stack ( we still can simulate on a single-tape TM, since any k-tape TM can be turned on a single one tape TM.) by adding elements to the tape and erasing them as we need. The blank symbol will now be allowed as part of the input symbols $\Sigma$ (so that we can "use" the pop instruction of a PDA).

(I won't go through this but if you want me to, I can rewrite it later).

PROOF:

We know by definition that P has the formal description:

"P is a 6-tuple(Q, $\Sigma ,\Gamma,\delta, qo, F$) where:

Q is a set of states,

$\Sigma$ is a finite set called the input set,

$\Gamma$ is a finite set called the stack set,

$\delta$ is a finite subset of $Q \times  (\Sigma \cup\{\varepsilon\})  \times \Gamma \times Q \times \Gamma^* $, the transition relation.

q0 E Q  is the start state,

F $\subseteq$ Q is the set of accepting states.

"

Great, now we'll make a transition algorithm that any TM can be turned into an AP, simply put:

Given an TM M, we'll create the formal transition to make an equivalent PDA:

1st step: We add the state "idle" on M, which is simply move to the left, do nothing, move to the right, do something.

2nd step:
For every transition of P (a, b -> c), we'll create an equivalent in M $\delta$.

3rd step: The accept state will only happen if we erase the initial symbol of $\Sigma$ and the reject state if the input ends.

I think you'll get the idea, sorry for my english mistakes, if you want to make improvements, you are free to do so.


If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$ I found the following question with an answer here, but I can't understand the steps of the solution.

Show that if a language $A$ is in RE and $A \leq_m \overline{A}$, then $A$ is recursive.
Solution.  Since $A \leq_m \overline{A}$, it follows that $\overline{A} \leq_m A$, and since $A$ is in RE, it follows that $\overline{A}$ is also in RE. Since both $A$ and $\overline{A}$ are in RE, it follows that $A$ is in R (this follows from a theorem you learned in class).

Here $\le_m$ demotes mapping reducibility.
Actually I can't understand most of the answer. In particular:

Why does $A \leq_m \overline{A}$ imply $\overline{A} \leq_m A$?
I understand the following step (why $\overline{A}$ is in RE).
Which theorem is used to deduce that $A$ is in R? (I'm not a student in this class)

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

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

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


What does "monotonicity" mean in the context of mutability I'm reading The Rust Programming Language and found the following passage:

  Remember that writing to a struct is not an atomic operation, and many
  functions like vec.push() can reallocate internally and cause unsafe
  behavior, so even monotonicity may not be enough to justify
  UnsafeCell

It just popped out of nowhere in the book and I've had a hard time online trying to find what it exactly means in this context. Too much information is about the concept of "monotonicity" of mathematical functions, which I already knew but is apparently not very helpful.

I only seemed to find this article that talks about it.

  Now, in addition to respecting equality in the obvious way, I also include the stipulation that a functional program must respect the monotonicity of observations. What do I mean by this? It must be that once you have observed something at a point in time, then that will not cease to be evident in the future. This is analogous to the monotonicity property in Kripke or Beth semantics.

However this is also quite abstract and I'm not sure it talks about the same thing either.

The author appears to be using the same (general) concept of "monotonicity" as in pure mathematics.

Using the example of a vector, if the size of some particular instance of vector is monotonic, then it would seem reasonable to assume that the memory location of any previously pushed element will not be subsequently modified, and thus that it is safe to directly change the value of that element without having to synchronize with the vector's subsequent push operations.

This assumption seems reasonable for much the same reason why it seems reasonable to assume that the memory location of an element previously pushed onto a (non-circular, array-based, unbounded) stack whose size is strictly increasing will not be affected by a future push operation.  This stands in contrast to a stack on which both push and pop operations are being invoked, and so the memory location of a previously pushed element may be "removed" by a pop operation, and thus available to be assigned to once again (i.e. modified) by a subsequent push operation.

The author's point is that this assumption is not correct, since even in a data structure whose size is strictly increasing, future insertions may affect previously inserted elements by triggering an internal reallocation of some sort that is distinct from the "logical" effect of the insertion.


How do I find if a programming language is infinite or finite? I know that in an infinite language there are infinite number of strings.  I want to know what type of the languages are C, C++ and JAVA? I can have infinite number of variables in all these languages, so I think all these languages are infinite. Please correct me if I am wrong.

An infinite number of potential identifiers results in an infinite language, but this is a "boring" feature with this consequence, because you can do without. We know that two variables are sufficient to compute any Turing computable function, so this is not the crucial part; I'll assume we use only finitely many variables.

Even then, ignoring real-world constraints such as finite memory, programming languages are -- of course -- infinite languages. Consider the following class of programs:

def m(x) {
  x++
  x++
  ...
  x++
  return x
}

It is clear that you can have as many statements as you want (never mind that, depending on the semantics, it might be that only finitely many of them run without error).

Why do I say "of course"? Well, usually programming languages are supposed to be Turing complete (again, assuming infinite memory). There are infinitely many functions that are Turing computable -- consider only $f_i(x) = i$ for $i \in \mathbb{N}$ -- so we must have infinitely many programs.

It is even so that typical programming languages have infinitely many programs for any single (computable) function! Consider, for instance, $f_1$ and all implementations of the form

def f1(x) {
  x++
  x++
  ...
  x++
  return 1
}

If you think about it, you can do stuff like that -- inserting "meaningless" statements -- in any program written in any language.


Converting NFA to DFA I've converted an NFA to a DFA.  But even after checking over it a few times, it still doesn't feel right.  I'm sure this is trivial, but I'd like someone to give me an idea where I went totally wrong on this.

NFA:

DFA:

Well, of course you have to merge the two empty states and there should be two transitions $(\{q_5\}, a, \emptyset)$ and $(\{q_5\}, b, \emptyset)$ if you want a complete automaton, but otherwise, it looks right and I agree with Subhayan: both automata accept $ab^+ \cup ab^+a$.


What does it mean that B-tree leaves carry no information? According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.".
What does it mean that they carry no information?
Does that mean that there are no more pointers to children nodes? (kinda redundant to say that as they are the leaves no?)
In the more literal meaning I understand from it that there is actually no information there (AKA the nodes values vs. the key which is used to search) but that doesn't make sense as each  key in a B-tree appear only at one node and thus must have a value associated to it or at least a pointer to the data.
Please notice that I'm not referring to a B+ tree where indeed there is an extra layer just for the data/values/information and the keys are indeed duplicated between nodes levels.

So according to CLRS (quotations):

Any "satellite information" associated with a key is stored in the same node as the key
Leaf nodes have no children, so their ci fields [pointers to child nodes, added for clarification] are undefined
A common variant on a B-tree, known as a B+-tree, stores all the satellite information in the leaves and stores only keys and child pointers in the internal nodes

There was no mention about leaf nodes carrying no keys/information/etc...
So basically leaf nodes do carry keys in order to actually get the data you search for (just like all the other nodes), they just don't carry pointers to child nodes.
And why Donald Knuth wrote (according to Wikipedia and other sources) that leaf nodes "carry no information" is beyond me, maybe he was referring to a different variant of B-tree... I honestly don't know.


Converting PDA to CFG I am trying to understand this example of converting PDA to CFG but I am not getting the idea quite right. I do have the general understanding of theorem that if $p,q\ \epsilon\ Q $ and $X \varepsilon\ \Gamma$ for $[pXq]$ we have include the sequence of derivations which would pop X
from the stack.
I partially understand what is going on but I cannot seem to understand how do I unroll the productions to form strings so I can understand it clearly. Take the production (5) in the example for instance. From what I understand it we are in state p we want to pop A and in the end we should be in state p with empty stack. As we are reading 0 we have zero in the production followed by $[pAq][qAp]$, this is the thing which I am not understanding because if we look at the PDA there is no way of going to q on reading 0. I would like to know what really is going on.
A related question is answered here
but I cannot understand it how to clear my confusion.

You have the basic intuition right.
The variable $[p,A,q]$ represents the set of (strings accepted by) computations from state $p$ to state $q$ that will pop the topmost symbol $A$ from the stack.

Technicaly the relation between grammar $G$ and pda $M$ is given on the top of the slide you show.
Then the construction follows recursion. If the pda pops $A$ but pushes $B_1B_2B3$ the grammar will replace the computation on $A$ starting in $p$ and ending in $q$ into three separate computations $[q_1,B_1,q_2][q_2,B_1,q_3][q_3,B_1,q]$. Here the intermediate states $q_2,q_3$ are unknown and are guessed by the grammar. Only $q_1$ is known, as it is the state where the pda instruction moves to.

Your observation is right. This standard construction might introduce triplets $[p,A,q]$ that will be useless. In your example there will be no computations from $q$ to $p$ so a triplet $[q,A,p]$ is never used in a succesful derivation. That is not problamatic. The construction just produces all possibilities, and variables that turn out to be useless can be removed afterwards if one really wants.
Note. The other question you link to uses a different Sipser style automaton model! There stack symbols are pushed one by one without popping at the same time. To add to the confusion the answer given at that question perfectly matches the construction from your slide!


how is the set of undecidable programs related to the set of non-halting programs? Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting?

Thanks!

The notion of an "undecidable program" doesn't make sense, for the same reasons I gave in response to your last question.  It makes sense to talk about whether a language is decidable or undecidable.  It doesn't make sense to talk about whether a program is decidable or undecidable.  If you check the formal definition of decidable, you'll see that decidability is only defined for languages.

Undecidable is not the same as non-halting.  Check the definition.


Studying Programming Language Theory I have recently become extremely interested in understanding and proving aspects of (functional) programming languages.

However as I dive deeper in, things like $\lambda$ calculus, category theory, and denotational semantics are a little difficult to grok without proper explanation.

I read SICP (quite an enlightening book) but I'm looking to dive deeper into the theory of functional programming. Are there any books/blogs/sites/you-name-it that would discuss the theory of functional programming languages from the ground up?

It is not easy to come by books that consider the denotational semantics of $\lambda$-calculus. One possibility is:

Roberto M. Amadio and Pierre-Louis Curien: Domains and Lambda-Calculi

Type-theoretic accounts are easier to get hold of:

Bob Harper, Practical Foundations of Programming Languages (there is also a printed version).
Benjamin Pierce, Types and Programming Languages.
Frank Pfenning's course on Computation and Deduction, I think he also published a book with the same title.


Algorithm: turining a fraction into a decimal expansion string I already asked this question over on Mathematics and got the suggestion to ask it here.

So I'm basically implementing a number type that can represent all fractions and was working on an algorithm to compute the decimal expansion for said fractions.

Let's say we have the reduced fraction $\frac{n}{m}$. For converting it into its decimal expansion I now have two algorithms.

The first algorithm is simply long division to calculate the decimal expansion up to a given number of decimal places.

The second is:

Let $a \in \{1,2,\ldots\}$ be a specifier for accuracy.

Calculate:
$$
\begin{align}
p &= \lceil \log_{10}(m) \rceil + a \\\\
f &= \lfloor \frac{10^p}{m} \rfloor \\\\
v &= n \cdot f
\end{align}
$$
Then in $v$ insert the decimal comma at the correct place or add 0. with leading zeros.

Which works well but it is hard to control the accuracy with $a$.
For example if I have the fraction $\dfrac{884279719003555}{281474976710656} \approx \pi$ then I get:

 a | dec. exp.
---|--------------------------------
     v acc 0
 1 | 3.0949790165124425
       v acc 1
 2 | 3.13919300246262025
        v acc 1
 3 | 3.14096156190062736
             v acc 7
 8 | 3.14159264580768862709685
              v acc 8
 9 | 3.14159265288192637912529
                  v acc 12
10 | 3.141592653589350154328134
                  v acc 12
11 | 3.141592653589350154328134
                  v acc 12
12 | 3.141592653589350154328134
                     v acc 15
f  = 3.1415926535897931159979634...

pi = 3.1415926535897932384626433...

So its seems I can control with $a$ that at least $a-1$ decimal places are correct.

But I'm not sure if this will always be the case.

Also, I benchmarked both algorithms, and the second is more than 5 times faster. So I really want it to be controllable.

| Method |       Mean |    Error |   StdDev |
|--------|-----------:|---------:|---------:|
|  first | 4,929.2 ns | 24.34 ns | 20.33 ns |
| second |   848.8 ns |  4.00 ns |  3.54 ns |

So my question basically is: does anybody have suggestions on improving the algorithm or maybe another algorithm that does the job even better (a.i. fast)?

All we need is a function $f$ that gives the whole part of a fraction. One can define this one using integer division:

$$f(a, b) = \lfloor a / b\rfloor$$

Finally let's assume we have routine $g(a, b)$ that reduces a fraction to its simplest form. This can be done with the Euclidean algorithm.

Let's first take the integer part of a fraction out using $f$, and reduce our fraction using $g$, giving us $\frac{a}{b} < 1$. Then we can repeatedly ask for the next decimal $d$ and continue with $10\cdot \frac{a}{b} - d$:

$d := f(10a, b)$
$a, b := g(10a - b\cdot d, b)$

This algorithm will perfectly give you all digits ad infinitum, and $g$ makes sure the numbers stay small and manageable.


Eliminating ambiguity when referring to complexity in cases of multiple parameters and/or multiple results When looking through a few questions at StackOverflow¹ that all ask for algorithms to select k distinct random numbers out of N, I've become confused about how to compare the answers in terms of time and space complexity.

each algorithm has two parameters, N and k
and returns k elements

In terms of Big O notation, all the algorithms worth speaking of are O(N) overall.

But there are still major differences between them:

Some require ~k steps while others ~N
Some can return elements one by one while others only return them all at the end.
Most require all the k (or even N) elements to be present in memory at once, but some are able to return each one in sequence and discard it.

Now to unambiguously put these distinctions when describing each algorithm's complexity? More specifically, I'm interested in the standard way it is done in formal papers so as not to reinvent the wheel.

¹https://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1/16097246, https://stackoverflow.com/questions/158716/how-do-you-efficiently-generate-a-list-of-k-non-repeating-integers-between-0-and-n, https://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values, https://stackoverflow.com/questions/54059/efficiently-selecting-a-set-of-random-elements-from-a-linked-list

You can report:

The running time (e.g., $O(k)$ vs $O(n)$),
The space requirements (e.g., $O(1)$, $O(k)$, etc.), and
Whether the algorithm is a streaming (online) algorithm or a batch algorithm.   A batch algorithm returns the entire answer at once.  A streaming or online algorithm returns numbers one at a time.  You might also be interested in the notion of "delay"; for instance, a $O(\log n)$ delay algorithm returns algorithms one at a time, taking at most $O(\log n)$ steps (running time) to output each number.

Since there are two variables here, $n$ and $k$, if you report a running time like $O(k)$, it may be helpful to mention explicitly that the constant is independent of $n$.

Formal papers aren't always as formal as you might think.  They'll use standard notation and terminology where they exist, but if standard notions don't cover it, they'll just use the English language to describe the situation, or they may introduce some new terminology and provide a definition for it.  That's the great thing about human language: it provides a way to express arbitrary new concepts, even ones we don't already have a pre-existing standard name for.


Sublinear query time for the $i$th element of an array after some additions? We are given an array $A[1..n]$ of integers, and an array of 3-tuples known as queries. The query tuples $(i,j,v)$ denote additions of an integer $v$ to the subarray of $A[i..j]$. I'm interested in the query time of $A[k]$ for $1 \leq k \leq n$ between the queries.

For example, let $A = [1,2,3,4]$, and let the queries be $Q = [[1,2,5],[2,3,6],[1,3,10]]$. After the second query has been processed, say I want to find the value of $A[3]$, which would be $3+5+6=14$. Does an algorithm exists to do this in less than linear time?

Yes, there are good data structures for this.  The running time to handle  $q$ queries and $\ell$ lookups will be $O((q+\ell) \lg n)$ time in total, or in other words, $O(\lg n)$ time per query and $O(\lg n)$ time per lookup.  This can be much faster than linear time in general.

Let $A_\text{orig}[1..n]$ denote the original value of the array $A$.  We're going to build a data structure to represent the array $\Delta[1..n]$ of integers, where $\Delta[i]$ holds the amount that $A[i]$ has been increased by (given the queries so far).  Thus, to compute $A[i]$, it suffices to look up $A_\text{orig}[i]$ and $\Delta[i]$ and return their sum.

The question is, how do we maintain the $\Delta[]$ array in a way that we can efficiently look up $\Delta[i]$ at any index $i$, and that we can efficiently update $\Delta$ in response to a particular query?

If we represent $\Delta$ as an array, then lookups take $O(1)$ time, but updates (handling a query) may take $\Theta(n)$ time, which is no good.

A better solution is to represent $\Delta$ using an interval tree.  With the proper data structures, each lookup will take $O(\lg n)$ time, and each update (processing each query) will take $O(\lg n)$ time.  This should give an efficient algorithm.

An interval tree holds a set of non-overlapping intervals.  In our case, the intervals will be consecutive ranges of array indices for which $\Delta$ holds the same value.  We will augment the data structure to hold the value of $\Delta$ for each such interval.

For example, initially the interval tree could be represented as $[1,n] \mapsto 0$, to represent that all indices in the interval $[1,n]$ yield the value 0; so $\Delta[i]=0$ for all $i$.  If we now receive the query $(1,2,5)$, then $\Delta$ is updated to the interval tree $[1,2] \mapsto 5, [3,n] \mapsto 0$.  If we then receive the query $(2,5,6)$, then the interval tree should be updated to $[1,1] \mapsto 5, [2,2] \mapsto 11, [3,5] \mapsto 6, [6,n] \mapsto 0$.

We can store the interval tree using a binary search tree.  If we have $m$ intervals, then there will be at most $2m$ unique endpoints of the intervals.  We store these endpoints in a binary search tree.  Each leaf node represents a single endpoint.  We will augment the nodes with a value: if a node represents the integer $a$ (an array index) and the next-largest integer endpoint is $b$, then the value $v$ at the node for $a$ means that the interval tree contains $[a,b-1] \mapsto v$.

Note that each query can be processed in $O(\lg n)$ time.  That's because a query might possibly split two existing intervals in the tree into two sub-intervals.  Each split operation can be handled in $O(\lg n)$ time by inserting one node into the  binary search tree.

Similarly, lookups can be handled in $O(\lg n)$ time, by traversing the binary search tree to find the largest node that is less than or equal to the index you're looking up.

This provides a sub-linear time solution to your problem.  Processing $q$ queries and $\ell$ lookups to the array takes $O((q+\ell) \lg n)$ time in total.


Describing the asymtotic complexity of processing two-dimensional data structures Consider the following Python function:

def count_chars(list_of_strings):
  chars = 0
  for s in list_of_strings:
    for c in s:  # intentionally avoiding len() here for the sake of example
      chars += 1;
  return chars

Clearly this is a linear operation, since we iterate over every element/character once. But I've often seen the Big-O of this function as $O(n*k)$ where $n$ is the length of the list, and $k$ is the length of the longest string. In a sense, that's polynomial or quadratic (at a minimum, I've heard people refer to this type of algorithm as such).

What is the appropriate way to refer to this type of function? Is there an intuitive way to understand this is linear, despite multiple variables?  In particular, how can we discuss that this is worse than a solution that uses len() (which is $O(1)$) without getting hung up on the fact that, in practice, both are linear?

Context: I'm posing an interview question that, while more complex than this example, involves identifying and eliminating $k$.  I've had candidates struggle to see that and it's felt like a communication issue more than a understanding problem.

I'm looking for ways to help guide a discussion, and to recognize that while this is linear, it is still asymptotically worse than an operation that avoids hitting each character individually.

The solution is that you shouldn't just ask whether it is "linear" -- ask what variable it is "linear" in.

Your example code has running time that is linear in the total length of the input strings.  There's a long history of characterizing the running time of an algorithm as a function of the length of the input to the algorithm, and that's an entirely valid thing to do.

It's also true that its running time is $O(nk)$ where $n$ is the number of strings and $k$ is the length of the longest string.  This might be a looser bound.

Both statements are true, and don't contradict each other.  It's just a matter of identifying which upper bound on the running time is more useful.


What is the computer science interpretation of a qubit? I am a CS major trying to decipher quantum computing. I have done some elementary study on qubits and I always seem to get lost at the "infinitely many" states that the qubit can have. And I really want to understand what it actually means. My understanding is as follows and please correct me if I am wrong,
A classical bit has two states 0 and 1, which means n bits can represent 2^n different states, though each state is individually expressed. A Qubit could have "infinitely many" states between 0 and 1. This means that n qubits can represent m^n states, Where 'm' is the base and m > 2. This would mean we can represent larger numbers using fewer qubits when compared to the classical bit. If this is so, how does this lead to an increase in computation speeds?
If I am completely off track, what is the actual interpretation of a qubit?

A qubit is a vector in a 2-state complex space. Its vector form is something like Qubit = $ax + by$, which by convention in Dirac notation is $|Q\rangle = a|0\rangle + b|1\rangle$, where $|0\rangle$ and $|1\rangle$ represent linearly independent basis vectors and the coefficients $a,b$ are complex numbers. $a^2$ and $b^2$ represent the probability of measuring 0 or 1, and they can take on any complex value as long as $|a|^2 + |b|^2 = 1$ (which must be true because we only have one qubit).
In this framework, the qubit acts like a vector pointing from the origin which  naturally evolves or rotates around the infinitely many surface points of a ‘Bloch Sphere’ except when it’s measured it only ever tells you 0 or 1 (which represent the north and south poles of the sphere).
In short, a qubit is a vector.
The ‘infinitely many’ language comes from the ability of $a,b$ to take on any complex value so long as their squares equal 1. Measuring a qubit (meaning when you read it, touch it, look at it, record its value etc) only gives you 0 or 1, not both and not a decimal in between.
If you also think of the qubit as a wave, then the goal of quantum computing is to take a superposition of all possible results of a qubit string (000, 001, 010, 011 etc), weight the components appropriately to constructively and destructively interfere with one another, so that at the very end you’re biased to get the right result... with a nonzero probability that you will get the wrong answer even if you do everything right.
Incidentally a string of three qubits, you’ll notice, is the tensor product of three qubit vectors. This creates a complex space with $2^3 = 8$ basis vectors which our 3-string qubit can happily explore.


Weighted Online Matching - randomized algorithms Let's consider the edge weighted online matching problem.
The Vertices arrive online and reveal all their current edges and edge-weights $w_e>0$. The goal is to maximize the matchings weight. An edge can only be added once and irrevocably to the matching. As so often, we consider basically consider the setting from KVV.
It is obvious, that any deterministic algorithm can't be competitive against an oblivious adversary. Since any new edge could have arbitrary large weight.
Can a randomized algorithm improve upon this result?

A randomized algorithm cannot be constant-competitive in worst-case order.
A proof using Yao's principle can be found here.


Are there any proofs of exponential lower bound time complexity I'm trying to understand what are the techniques to prove an exponential time lower bound.

For some problems, we can prove that the size of the output is exponential is the size of the input, thus it takes an exponential number of steps just to write the output. For example for some generalized board games, if the input is the size of the board and the output is the sequence of winning steps.

But what about decision problems, where $|output|=1$ ? Are there any decision problems in $EXPTIME$ with known exponential lower-bounds ?

I don't see how we can prove such a lower bound. Like if we take again the generalized board game and ask the question if there is a winning strategy, we can prove that evaluating all strategies will take (in the worst case) exponential time, but how can we prove that evaluating all strategies is the only way to answer the question ?

Or if I take another example, if my input is a number $x$ and the output is $1$ iff there exist a permutation $p$ such as shuffling the bits of $x$ makes it prime, i.e. $p(x)$ is prime. Exhaustively exploring all permutations and running a primality test will probably be exponential in $|x|$, but what if there is a smart way to answer just by looking at $x$ (in sub-exponential time) ?

I hope that looking at an example of such a proof will help me grasp the principles involved.

The Time Hierarchy Theorem states that for any (reasonable) function $f$, there exists a problem that cannot be solved in time substantially faster than $f(n)$. The proof of this is similar to the proof of the undecidability of the Halting problem: we construct the decision problem "given a description of a Turing machine, does it halt in time at most $f(n)$ and then show that it cannot be decided substantially faster than $f(n)$, in a very similar way to showing that "does this Turing machine halt in finite time" cannot be decided (in finite time).

In the case of generalized board games (e.g., Chess), these are often $EXPTIME$-complete. This means any problem in $EXPTIME$ can be reduced in polynomial time to it. Since (by the Time Hierarchy Theorem) there are problems in $EXPTIME$ that cannot be solved in subexponential time, neither can Chess (or any other $EXPTIME$-complete problem).

Your other example (shuffling bits to get a prime number) probably doesn't require exponential time. The chance that a random permutation of the bits results in a prime is quite high, and only a polynomial number of guesses would be required to find a prime. The problem is in $NP$, so a proof that it requires exponential time would be a somewhat significant breakthrough.


Exact runtime of median of median algorithm Consider median of median algorithm. If I make to group of size $7$ instead of $5$ then the recurrence equation will be
$$T(n)=T(n/7)+T(5/7\cdot n+4)+O(n),$$
which can be proven by induction equal to $O(n)$.
Assume it takes around $14$ steps to sort group of $7$ elements. How do I find exact runtime if I want to find $k$th smallest element in sequence, by exact run time I mean a solution for above recurrence.
My idea was that since $T(n)=O(n)$ then $T(n)=an+b$ ,where $a $ or $b$ might be depend on value of $k$. How can I find value of $a$ and $b$ or it is impossible to find value of $b$, as value of $a$ can be found but I am not sure how.

"since $T(n)=O(n)$ then $T(n)=an+b$" it's wrong assumption, because big-$O$ gives only upper bound. For example $n^\alpha \in O(n)$ for $\alpha \in (0,1))$, $\log n \in O(n)$ etc., so you cannot reduce situation for only linear functions.
For exact estimation you need to elaborate $O(n)$ in recurrence relation.