How to answer multiple queries for a tree? I encountered an interesting  problem based on tree-data-structure.

We are given a tree which has N nodes, with 1≤N≤105.
Time starts from second 1 and it continues for q seconds.
At each second, the value of each internal node is transferred to all of its child nodes. This happens with all the nodes, except leaf nodes.
Sometimes, at a given time p (seconds), we are asked to return the current value of node x.

There is this O(logN) approach: just find the pth ancestor of the given node x, and output its value.
A harder version of the same problem

Sometimes, at a given time p (seconds), we are asked to return the current value of node x, or we are said to update the value of node x to y.

How to solve this problem for q queries (seconds) efficiently, where 1≤q≤105.
Example
Input
N=5, q=8
Edges of the tree:-
4 3
3 1
5 2
1 2

Values of nodes 1 to 5:-
1 10 4 9 4

Queries:-

1st second:- Add(1,6). Add the value 6 to node 1.
2nd second:- What is the current value of node 3? (?,3)
3rd second:- Add(3,5)
4th second:- (?,3)
5th second:- Add(2,2)
6th second:- Add(5,10)
7th second:- (?,5)
8th second:- (?,4)

Expected Output

6
0
33
25

Explanation

1st second: 6,1,1,13,14 (Values of all nodes)
2nd second: 0,6,6,14,15
3rd second: 0,0,5,20,21
4th second: 0,0,0,25,21
5th second: 0,2,0,25,21
6th second: 0,0,0,25,33
7th second: 0,0,0,25,33
8th second: 0,0,0,25,33

For this problem I recommend to solve first for trees with simpler structures that can be generalized afterwards with data structures that run on top of trees (there are plenty of them).

Let's build an idea of what are the dynamics of the problem before jumping to the answer. We have the array A = [N0, N1, N2, N3]. An let's say after each second numbers at each position moves one step to the right. And in some place one number might change (in cases of queries). The initial array after the first second will look like A = [N0, N0, N1, N2]. If we are asked to change the value at position $2$ (indexed in base $0$) with value Q0 at the end of the first step, then the array will look like A = [N0, N0, Q0, N2]. After the following step the array will look like A = [N0, N0, N0, Q0]. We should be able to answer queries of the form: What is the value of position $i$ at this moment?

If there is a value at position $i$ at time $t$ we know this value will be at position $i+\delta$ at time $t+\delta$, unless it is overridden by some update. In the case it was overridden it must be the case that it happened on a position to the right of position $i$.

Supposed we are asked for the value at position $p$ at time $t$. Turning previous equations backwards, we are looking for the right-most position to the left of $p$ (let's call it $o$ from origin) such that an update originated there at time $t_o = t - (p - o)$. We say that for all positions in the array there was a simultaneous update at the beginning with initial values. Rewrite previous equation as: $t_o - o = t - p$. Notice that the problem is simpler now, for every update in position $o$ at time $t_o$ with value $v$ we store at this position the value $(t_o - o, v)$. For every query of the form ($p$, $t$) we should ask for the right-most position to the left of $p$ such that the first element is $t - p$ and return $v$ from such pair.

After every second add always an update in the root with current value, in order to always find the answer for every query. This idea can be implemented with a 2D Segment Tree. Complexity for every query an update will be $O(log^2 N)$.

To turn this idea into the tree case, just notice that:

right becomes the sub-trees.
left becomes the ancestor.
position becomes the height.

Decompose the tree in paths using Heavy Light Decomposition (HLD) and solve the same instance of the problem. Since HLD decompose every path from node $u$ to the root in $O(log N)$ paths each update/query complexity will be $O(log^3 N)$. Overall complexity will be $O((N + Q) log^3 (N+Q))$.


Can the formalisms of category theory replace those of type theory? The subtleties of the correspondence between type theory and category theory are outside my ken. However, by my naive understanding of the relationship between the two historically convergent disciplines, the latter entirely subsumes the former. If this is so, can the language and formal/graphical descriptions used by category theorists replace those of type theorists? And should they (e.g., in pedagogy and academic publishing)?

Different formalisms can inspire novel perspectives and lay bare conceptual connections that might otherwise be obscure. However, a multiplicity of dialects probably also limits the size of a receptive audience, and, should a polyglot approach be taken, the length and complexity of exposition is compounded.

If category theory does subsume type theory, should the dialectical differences of the two disciplines be retained, and if so, why? For the sake of historical or cultural value? To retain different but salient differences of instructional or theoretical emphasis? What might these be?

My view is more or less similar to chi's. I see category theory as (roughly) being to type theory what model theory is to logic. Some of the consequences of that are, first, each can exist autonomously. Indeed, type theory predates category theory, and the creation of category theory was not motivated by these concerns. Second, many of the distinctions category theory/model theory are purposely trying to blur are of primary interest in type theory/logic.

As a very basic example, all presentations of the axioms of a group give rise to the same class of models (namely groups). From the perspective of universal algebra, a variety (in the universal algebra sense, or a finitary algebraic category from a CT perspective) forgets its presentation. Meanwhile, from the perspective of equational logic, presentation is all there is. A primary computational topic here is E-unification which operates entirely at the level of equational logic, i.e. presentation.

This is typical. We say the simply typed lambda calculus (with products) (STLC) is the internal language of Cartesian closed categories, but it is really just one presentation of the internal language and not even the most "direct" one. The Categorical Abstract Machine (CAM) is arguably a more "direct" representation. Even with the STLC, the arrows of corresponding syntactic category are $\beta\eta$-equivalence classes of lambda terms! (But see this.) So either we somehow directly describe the syntactic category as a mathematical structure whose hom-sets just happen to coincide with $\beta\eta$-equivalance classes of STLC terms and have no computational content, or we need to already understand the STLC external to category theory, or we need to talk instead of presentations of Cartesian closed categories which, taking a fairly natural approach, will lead to something CAM-like. In the last case, equality of arrows becomes something like an E-unification problem. Understanding and simplifying this process as well as placing the more ergonomic facade of the STLC in front of it, requires techniques that are the bread and butter of logic and type theory but are not particularly natural within category theory.

A massively over-simplified picture that may nevertheless give a better idea of how category theory and type theory interrelate is the following. You can imagine them as two dimensions. The tools, techniques, and notations of type theory are geared toward moving vertically between different presentations of the same object, meanwhile the tools, techniques, and notations of category theory and geared toward moving horizontally between different mathematical objects. You might even say that a category is a whole vertical line and that category theory talks about moving one vertical line to another but not how the points of the two lines correspond. In this picture, category theory is not even capable of talking about the distinctions type theory is making, but this is intentional because it means that the arbitrarily complicated mapping of points on one vertical line to points on another is just irrelevant to what category theory cares about and can be ignored.

In my blog post, Category Theory, Syntactically, I describe an approach that makes category theory look more like type theory (rather than the other way around). Unsurprisingly, what I'm really discussing there are presentations of categories. Further, you can see aspects of normalization enter the picture, e.g. in my discussion of "product theories", even though this is not a focus at all of that particular post.


Will irrational parameters make a problem not well-defined on complexity Given a set $=\{_1,⋯,_\}$ where all $_$s are rational positive numbers and $\sum_{i\in N}a_i=1$, find a subset ⊆ such that $(\sqrt{2\sum_{i\in S}a_i}-1)^2$ is minimized. Does the appearance of √ make the problem ill-defined with regrading to complexity?

The appearance of square roots does not make this an ill-defined problem.

Note that $(\sqrt{2\sum_{i\in S}a_i}-1)^2=0$ if $\sum_{i\in S}a_i = 1/2$ and $(\sqrt{2\sum_{i\in S}a_i}-1)^2>0$ otherwise. Therefore, the problem is easily seen to be NP-hard by reduction from subset sum.


Math term for Associative arrays/Maps/Dictionaries What would be the equivalent math concept for associative arrays/maps/dictionaries?

EDIT: Disregard mutability. FYI,off topic, the reason why I ask this question, is that I want to calculate the distance(or similarity) between two maps given that I have a distance function for each entity(or key) in the map.

Function ($A \to B$). If that doesn't work for you, try a set of pairs (subset of $A \times B$).

Note that something like mutable state is not common in maths, outside of computer science.


difference between lzw and huffman coding technique What is the difference between the LZW and Huffman's coding of text compression ?

I've read this and
this , but I'm not able to distinguish ?

Lempel–Ziv encoding (or rather, encodings, since there are many different variants) and Huffman coding are very different algorithms.

Huffman coding. Choose a block length, usually one byte. For each possible value of the block, we choose some bit string, so that no bit string is a prefix of another one (this is known as a prefix-free code). This choice is either fixed (like the JPEG Huffman code, which while in principle adaptive, is often fixed to some standard code) or adaptive (chosen according to the actual text being compressed). Each block is encoded by its bit string, and the results are concatenated.

The name Huffman code proper refers to the optimal choice of code given a distribution on the value of the blocks. Huffman code satisfy the following optimality property: if the source being compressed consists of i.i.d. copies of some distribution, then as the block length tends to infinity, the average number of bits used to encode one copy is the entropy of the source.

Lempel–Ziv encoding. Here the idea is to separate the input bits (instead of bits, we can choose longer blocks) into pieces, where each piece consists of an earlier piece plus an additional bit at the end. For example, the input 01011100010 can be partitioned as (0)(1)(01)(11)(00)(010). The idea is to encode each piece by referring to an earlier piece, including the additional bit. For example, if we number the pieces from 1, 0 being the empty piece, then the previous example could be encoded as (0,0)(0,1)(1,1)(2,1)(1,0)(3,0).

There are many different variants of Lempel–Ziv encoding. In particular, in practice we don't keep all earlier pieces in memory, and there is some specific encoding for the pairs (p,b) encoding the earlier piece and the new bit. Lempel–Ziv encoding is optimal for ergodic sources – the expected length of the compressed stream tends to the entropy.


Does an Operating System inject its own machine code when you open a program? I'm studying CPU's and I know how it reads a program from the memory and execute its instructions. I also understand that an OS separates programs in processes, and then alternate between each one so fast that you think that they're running at the same time, but in fact each program runs alone in the CPU. But, if the OS is also a bunch of code running in the CPU, how can it manage the processes?

I've been thinking and the only explanation I could think is: when the OS loads a program from the external memory to RAM, it adds its own instructions in the middle of the original program instructions, so then the program is executed, the program can call the OS and do some things. I believe there's an instruction that the OS will add to the program, that will allow the CPU to return to the OS code some time. And also, I believe that when the OS loads a program, it checks if there's some prohibted instructions (that would jump to forbidden adresses in the memory) and eliminates then.

Am I thinking rigth? I'm not a CS student, but in fact, a math student. If possible, I would want a good book about this, because I did not find anyone that explains how the OS can manage a process if the OS is also a bunch of code running in the CPU, and it can't run at the same time of the program. The books only tell that the OS can manage things, but now how.

No. The operating system does not mess around with the program's code injecting new code into it. That would have a number of disadvantages.

It would be time-consuming, as the OS would have to scan through the entire executable making its changes. Normally, part of the executable are only loaded as needed. Also, inserting is expensive as you have to move a load of stuff out of the way.
Because of the undecidability of the halting problem, it's impossible to know where to insert your "Jump back to the OS" instructions. For example, if the code includes something like while (true) {i++;}, you definitely need to insert a hook inside that loop but the condition on the loop (true, here) could be arbitrarily complicated so you can't decide how long it loops for. On the other hand, it would be very inefficient to insert hooks into every loop: for example, jumping back out to the OS during for (i=0; i<3; i++) {j=j+i;} would slow down the process a lot. And, for the same reason, you can't detect short loops to leave them alone.
Because of the undecidability of the halting problem, it's impossible to know if the code injections changed the meaning of the program. For example, suppose you use function pointers in your C program. Injecting new code would move the locations of the functions so, when you called one through the pointer, you'd jump to the wrong place. If the programmer was sick enough to use computed jumps, those would fail, too.
It would play merry hell with any anti-virus system, since it would change virus code, too and muck up all your checksums.

You could get around the halting-problem problem by simulating the code and inserting hooks in any loop that executes more than a certain fixed number of times. However, that would require extremely expensive simulation of the whole program before it was allowed to execute.

Actually, if you wanted to inject code, the compiler would be the natural place to do it. That way, you'd only have to do it once but it still wouldn't work for the second and third reasons given above. (And somebody could write a compiler that didn't play along.)

There are three main ways that the OS regains control from processes.

In co-operative (or non-preemptive) systems, there's a yield function that a process can call to give control back to the OS. Of course, if that's your only mechanism, you're reliant on the processes behaving nicely and a process that doesn't yield will hog the CPU until it terminates.
To avoid that problem, a timer interrupt is used. CPUs allow the OS to register callbacks for all the different types of interrupts that the CPU implements. The OS uses this mechanism to register a callback for a timer interrupt that is fired periodically, which allows it to execute its own code.
Every time a process tries to read from a file or interact with the hardware in any other way, it's asking the OS to do work for it. When the OS is asked to do something by a process, it can decide to put that process on hold and start running a different one. This might sound a bit Machiavellian but it's the right thing to do: disk I/O is slow so you may as well let process B run while process A is waiting for the spinning lumps of metal to move to the right place. Network I/O is even slower. Keyboard I/O is glacial because people are not gigahertz beings.


Time complexity of an enumeration of SUBSET SUM instances An instance of the SUBSET SUM problem (given $y$ and $A = \{x_1,...,x_n\}$ is there a non-empty subset of $A$ whose sum is $y$) can be represented on a one-tape Turing Machine with a list of comma separated numbers in binary format.
If $\Sigma = \{0,1,\#\}$ a reasonable format could be:

$( 1 \; (0|1)^* \; \#)^* \#$

Where the first required argument is the value $y$ and $\#\#$ encodes the end of the input. For example:

 1  0  0  #  1  0  #  1  #  #
^^^^^^^^     ^^^^     ^
   y          x1     x2
Instance: y=4, A={2,1}

I would like to enumerate the SUBSET SUM instances.

Question: What is the (best) time complexity that can be achieved by a Turing Machine $TM_{Enum}$ that on input $m$ (which can be represented on the tape with a string of size $\log m + 1$) - outputs the $m$-th SUBSET SUM instance in the above format?

EDIT:

Yuval's answer is fine, this is only a longer explanation.

Without loss of  generality we set that $y > 0$ and $0 < x_1 \leq x_2 \leq ...  \leq x_n$, $n \geq 0$

And we can represent an instance of subset sum using this encoding:

$y \# x_1\# d_2\# ...\# d_{n} \#\#$ where $d_i \geq 1, x_i = x_{i-1} + d_i - 1 \; , i \geq 2$

Using a binary representation for $y,x_1, d_2, d_3, ...$ we have the following representation:

$1 \; ((0|1)^* \# 1)^* \; \#\#$

Equivalent to $1 \; (0|1|\#1)^* \; \#\#$. There is always a leading 1 and a trailing ## so we can consider only the $(0|1|\#1)^*$ part.

So the decoder TM on input $m$ in binary format should:

output the leading 1
convert $m$ to base 3 mapping digit 2 to $\#1$
when outputing the i-th intermediate $\#$ calculate $x_i = d_i + x_{i-1}-1$
output the trailing $\#\#$

No duplicate instances are generated.

SUBSET-SUM instances can be encoded in base 3. We have codes for $0,1,\#$. Some codings are invalid, but in that case we can just immediately output $\#\#$ (or $\#$, if we have just written $\#$). Every SUBSET-SUM problem has infinitely many encodings, I hope that's not a problem.

If the input has length $\ell$, then (assuming the tape alphabet has at least 4 symbols) we can do the conversion in time $O(\ell^2)$. I don't know whether this is the "best" time complexity achievable.

Edit: Here is a better encoding. We still have only three input codes, $0,1,\#$. The output string always starts with $1$ and ends with $\#\#$. Further, $\#$ is output as $\#1$. Now each output string is generated once, though several output strings could correspond to the same instance.

As an example, your instance is encoded by "00#0#".


counting binary, with moving position (turing machine) I'm trying to make a turing machine that will take in a binary string as input x and output the binary representation of the length of x. So M(0110) returns 100, M(1010101010) returns 1010, ect. It also has to have a runtime of O(N).

So I can prove that the number of "flips" (changing a 0 to a 1 or a 1 to a 0) that occur when counting from 1 to n in base 2 approaches 2n as n goes to infinity. meaning it's O(n) in terms of runtime, but i'm not sure how to factor in the movement of the head of the tape that is writing the binary. Near as I can tell, the head may have to move at most log(n) place to go from the 1s place to the last power of 2s place. For example, going from 11111 to 000001 requires moving from the 1s to the 64s place, or 6 places. It then has to move back to the ones to create the binary representation for 65.

How is this operation as a not O(nlogn)?

Noting that every increment starts from the lowest significant bit (LSB). Consider each increment operation this way: starting from LSB, move towards MSB, flipping 1's to 0's until a 0 is encountered. Flip it to 1 and move back to LSB, stop. It is then clear that the total move distance is just double the number of flips.


How does the Monte Carlo Tree Search Algorithm Decide When to Expand? I understand that the MCTS algorithm expands its tree after it has selected the best route to take. However, how does it decide when to end selection and then expand the tree? It cannot just traverse down the whole graph... then it would always produce child nodes at the same place (right?) So, how does the MCTS decide when to produce a child node when traversing down the search tree?

With each rollout the algorithm goes through steps of selection, expansion, simulation, and backpropagation. It does this incrementally one move at a time. 1 selection, 1 expansion, 1 simulation of random playouts them back propagated the values back to root. Next rollout and henceforth depending on ucb weights between exploration and exploitation.


Is it possible to write a program that calculates an algorithm's time complexity? Title is self explanatory.

I have searched here on this site and haven't found any discussion about this.

Is it somehow related to Turing's Halting problem (which is undecidable)?

Yes, you are right. There is no program that can calculate all algorithms' time complexity.

More formally speaking, there is no Turing machine which, given any Turing machine $T$ and an input of length $n$, it can calculate a finite upper bound for the computation time that will be used by $T$ and that input in case that computation does halt, or infinity in case that computation does not halt. The reason is simple, as you have mentioned, there is no Turing machine that can decide whether an arbitrarily computation will run forever or not in the first place. In fact, we cannot algorithmically tell even whether a given Turing machine halts on the empty input.

Notice that a trivial time complexity of all algorithms is an upper bound of running forever for any input. There are also trivial lower bounds such as whether the computation will run for less than for 7 steps. Those trivial time complexities have to be excluded from our discussion so as to keep our discussion interesting.

We can ask refined questions. For example, does an arbitrary Turing machine run in time $O(1)$? It turns out this question is undecidable as well.

For more information, you may want to read Verifying Time Complexity of
Turing Machines by David Gajser.


Upper bound on the number of subgraphs in a tree Is there an upper bound of the number of induced subgraphs in a tree (i.e., connected acyclic undirected graph)? The bound can be expressed in terms of vertices, edges, etc.
For example, consider the following graph $G$ represented as edge list: $\{(S,T),(T,G),(T,B),(B,H),(H,Q)\}$. The number of connected subgraph (i.e., tree) is (represented by the set of vertices): $\{S\}$, $\{T\}$, $\{G\}$, $\{B\}$, $\{S,T\}$, $\{T,G\}$, $\{T,B\}$, $\{S,T,G\}$, $\{B,T,G\}$,$\{S,T,B\}$, $\{S,T,G,B\}$,
$\{T,G,B,H\}$,$\{T,B,H,Q\}$, $\{S,T,B,H\}$,$\{S,T,B,H,G\}$,$\{T,G,B,H,Q\}$,$\{S,T,B,H,Q\}$, and
$\{S,T,B,H,G,Q\}$.
I find two seemingly relevant answer that can directly answer my questions 1 and 2 but I'm not sure.

Let us prove by induction that any tree on $n$ vertices has at least $2^{n-1} - n$ induced disconnected subgraphs.
When $n = 1$, this is clear since $2^{n-1} - n = 0$. Now suppose $n > 1$, and let $T$ be a tree on $n$ vertices. Choose an arbitrary leaf $v$, let $T'$ be the tree obtained by removing $v$, and suppose that $v$ is connected to $u \in T'$. By induction, $T'$ has at least $2^{n-2} - (n-1)$ induced disconnected subgraphs. Each of these correspond to two induced disconnected subgraphs of $T$, one including $v$ and one not including $v$. Moreover, for any $w \in T'$ different from $u$, the subgraph induced by $\{v,w\}$ is disconnected, and does not arise from an induced disconnected subgraph of $T'$ (since the subgraph of $T'$ induced by $\{w\}$ is connected). In total, we get this many induced disconnected subgraphs of $T$:
$$
2(2^{n-2} - (n-1)) + (n-2) = 2^{n-1} - 2(n-1) + (n-2) = 2^{n-1} - n. \quad \square
$$
This is tight, as the example of a star shows. If the center of the star is $x$ and the other vertices are $y_1,\ldots,y_{n-1}$, then the subgraph induced by any subset of $\{y_1,\ldots,y_{n-1}\}$ of size at least 2 is disconnected. There are $2^{n-1} - (n-1) - 1 = 2^{n-1} - n$ of these.


How to find size of each tree in a forest? Let $T$ be a tree with $n$ nodes. If I remove $k$ edges from $T$, I will have $k+1$ new trees i.e. a forest of $k+1$ trees.

How do I calculate the number of nodes in each of these new trees formed?

I need to do this for $q$ queries.

My approach:
I can remove the $k$ edges from the original tree and run DFS on each nodes from which edge was deleted and find the size of the new tree. And then join the nodes back after getting size of each tree.
But this is not optimal, can anyone suggest a better approach.

You can use any number of Dynamic Connectivity data structures, namely, an euler tour dynamic connectivity tree.

To summarize the reference, if you label the vertices of the original tree $T$ according to the first (denoted $label_f$) and last (denoted $label_l$) euler-tour visit order on $T$, you can maintain a BST $T^*$.

Each node $x$ in $T$ is linked to two nodes in $T^*$: $v_1$, $v_2$, where $key(v_1) = label_f(x)$ and $key(v_2) = label_l(x)$. Note $|T^*| = 2n $ and BST operations on $T^*$ will cost $O(\log n)$

Now, we can support the following operations on $T$:

$cut(u, v)$: Disconnect the edge $(u,v)$. Denote $x$ the vertex whose $label_f$ is lesser. It is done simply by splitting from $T^*$ the interval $[label_f(x),label_l(x)]$ which can be done in $O(\log n)$ by splitting and merging.
$findroot(v)$: Since the root of the tree has the minimum $label_f$, the root of $v$ will be the minimum node in the euler-tour BST in which he belongs

Since each node $x$ in $T$ is represented by exactly two nodes in $T^*$, by simply saving rank (tree size) on the euler tour BST ($T^*$), and dividing by $2$ you can answer the question "How many nodes are in the tree of $x$?" in $O(1)$, granted you are willing to pay $O(\log n)$ each time you disconnect an edge.


Explanation of recursive structure of Van Emde Boas Tree From Van Emde Boas trees lecture:

  We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of
  a bit vector, but shrink the universe size recursively by a square
  root at each tree level. The ${u^{1/2}}$ items on the ﬁrst level each hold
  structures of ${u^{1/4}}$ items, which hold structures of ${u^{1/8}}$ items, and
  so on, down to size 2.
  I have a  question regarding van Emde Boas trees :

How is the universe size getting reduced ? Aren't we just spreading the universe keys which is always constant at $u$ to different levels ? I can not understand the idea of "shriniking" the universe size .  I find similar language is used in defining the recursive structure for Van Emde Boas tree in Introduction to Algorithms by CLRS also .

Well the crucial idea about vEB trees is the following: You store all the elements as a 0/1 bitvector of size $s$. For example the vector $(0,1,1,0)$ denotes that in your universe of size $s=4$, the third and second elements are present. Now you subdivide the vectors in blocks of size $\sqrt{s}$ and for every block you also store a flag, if there is at least one $1$ in the block. This gives you a set of $\sqrt{s}$ flag bits. If you store also the $\min$ and $\max$ for every block, then you can determine in which block you have to continue your search for the successor after either perform a successor query in the block of your query element or in the flag bit vector.

This implies that the sup-problem you are requesting has size $\sqrt{s}$. But this is the same statement as saying that you go from a $k$-bit universe to a $k/2$-bit universe.

And this is meant by shrinking the universe.


Prove correctess of recurrence result by mathematical induction I have the following recurrence relation which I already solved using repeated substitution.

$T(n) = \begin{Bmatrix}
1 & if & n = 1\\
4T(\frac{n}2) + n & if & n >= 2
\end{Bmatrix} where$ $n=2^k$

The result I get is $T(n) = 2n^2 - n$
Let´s suppose my result is correct. Now, I am asked to prove the correctness of the result using mathematical induction.

Base case is easy:
For $n = 1$ we have $T(1) = 2(1^2) - 1 = 2 - 1 = 1$
This result agrees with initial formulation of the problem above.

Now, comes the $Inductive$ $Hypothesis$ which I guess is as follows:
Assume this holds for $2 <= k <= n$
$4T(\frac{k+1}2) + (k+1) = 2(k+1)^2 - (k+1)$

Am I doing things correctly?
How would the $Induction$ $Step$ would be?
I will very much appreciate your feedback.

We prove by induction that for every $n\in\mathbb{N}$ it holds that $T(n)=2n^2-n$.
The inductive hypothesis is that for all $1\le k<n$ we have:

$T(k)=2k^2-k$.

We proceed to show that $T(n)=2n^2-n$.

By definition, $T(n)=4T\left(\frac{n}{2}\right)+n$. Since $\frac{n}{2}<n$, we can use our inductive hypothesis and obtain $T\left(\frac{n}{2}\right)=2\left(\frac{n}{2}\right)^2-\frac{n}{2}$. After substituting this back into $T(n)$ we have:

$T(n)=4\left(\frac{n^2}{2}-\frac{n}{2}\right)+n=2n^2-n$.


O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question Question:  Given a time series of stock prices, what is the maximum profit you can make if you are allowed to Buy and sell the stock twice.  The second buy has to come after first sell.

Solution:  There is a O(N) time and O(N) space complexity solution, that keeps track of the maximum profit that can be made when selling at day i in a N size array.  Then it calculates the max profit by using this array in conjunction with max profit that can be made by buying at day i+1.

I would appreciate any hints on how I can get a O(N) time and O(1) space complexity solution?

Here's an O(1) space, O(n) time algorithm with Java code.
Logic:

Let $P_i$ denote the price of the stock on day $i$.

Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$.
If you had sold before day $i$ you can buy again at day $i$. If you do so, you'll need to deduct day $i$'s price from the 1st transaction's profit. Then, the maximum leftover profit at day $i$ is $Max(P_i - MaxProfit1_i)$. Call this $MaxLeftOver_i$.
In the same vein, if you had bought the 2nd stock before day $i$, you can sell it at day $i$. If you do so, you add
day $i$'s price to the previous leftover profit to arrive at your profit at day $i$ with 2 transactions. Then, the maximum profit at day $i$ with 2 transactions is $Max(P_i + MaxLeftOver_i)$ - which is the final answer.

public int maxProfitWith2Transactions(int[] prices) {
    if (prices.length == 0) return 0;

    int minPrice                      = prices[0];
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int i = 1; i < prices.length; i++) {
        final int p = prices[i];
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell);
        minPrice                    = Math.min(p, minPrice);
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
    }
    return maxProfitAfterSecondSell;
}

The below modified (slightly faster) variant of the above beats every solution in both space and time on LeetCode.
public int maxProfitWith2Transactions(int[] prices) {
    int minPrice                      = Integer.MAX_VALUE;
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int p : prices) {
        minPrice                    = Math.min(p, minPrice);
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell);
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
    }
    return maxProfitAfterSecondSell;
}

Here's the values that the above code calculates for prices 8, 10, 3, 7, 4, 9, 2, 3.
Clearly, the max profit after 1 transaction is 6 (Buy at 3, sell at 9). After 2 transactions, the max profit is 9 (Buy at 3, Sell at 7, Buy again at 4, sell at 9).
$$\begin{array}{l|r r r r r r r r}
\text{$i$} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} \\ \hline
\text{Price} & \text{8} & \text{10} & \text{3} & \text{7} & \text{4} & \text{9} & \text{2} & \text{3} \\ \\ \hline
\text{Lowest price seen} & \text{8} & \text{8} & \text{3} & \text{3} & \text{3} & \text{3} & \text{2} & \text{2} \\
\text{till day $i$} \\  \hline
\text{Max Profit if} & \text{x} & \text{2} & \text{2} & \text{4} & \text{4} & \text{6} & \text{6} & \text{6} \\
\text{bought at lowest} \\
\text{price before day $i$}  \\
\text{and sold before}  \\
\text{or on day $i$}  \\ \hline
\text{Max Profit left if} & \text{x} & \text{-8} &  \text{-1} & \text{-3} & \text{0} & \text{0} & \text{4} & \text{4} \\
\text{2nd buy is done on} \\
\text{day $i$.} \\
\text{= Max(PreviousRow$_i$ - $P_i$)} \\ \hline
\text{Max Profit if 2nd} &  \text{x} & \text{2} & \text{2} & \text{4} & \text{6} & \text{9} & \text{9} & \text{9} \\
\text{stock is sold before} \\
\text{or on $P_i$} \\
\text{= Max(PreviousRow$_i$ + $P_i$)} \\ \hline
\end{array}$$


Do the time and space complexities of a language depend on the Turing machine which is its recognizer? From Ullman and Hopcroft's Introduction to automata theory, languages, and computation

  Consider the off-line Turing machine M of Fig. 12.1. M has a read-only
  input tape with endmarkers and k semi-infinite storage tapes. If for
  every input word of length n, M scans at most S(n) cells on any
  storage tape, then M is said to be an S(n) space-bounded Turing
  machine, or of space complexity S(n).
  The language recognized by M is also said to be of space complexity S(n).

  Consider the multitape TM M of Fig. 12.2. The TM has k two-way
  infinite tapes, one of which contains the input. All tapes, including
  the input tape, may be written upon. If for every input word of length
  n, M makes at most T{n) moves before halting, then M is said to be a
  T{n) time-bounded Turing machine, or of time complexity T(n). The
  language recognized by M is said to be of time complexity T(n).

If I am correct, a language can be the one recognized by several Turing machines.

Do the last sentences in the two paragraphs assume that for a language, all of its recognizer TMs have the same time complexity and the same space complexity?

Is the assumption true?
If the assumption is not true, do the sentences imply taking supremum of the complexities over all of the recognizer TMs of the language?

Thanks.

Yes, you are correct. I applaud your careful reading.

This reading is most obvious if we view a TM as an algorithm (which they are). Clearly, for any computational problem, some algorithms are more efficient than others. Compare bubble sort to merge sort, for example.

But their definition is not wrong, just perhaps a little misleading. Any algorithm can provide a time-bound on a decision problem; but only one of them will be the lowest bound.


Characterization of lambda-terms that have union types Many textbooks cover intersection types in the lambda-calculus. The typing rules for intersection can be defined as follows (on top of the simply typed lambda-calculus with subtyping):

$$
\dfrac{\Gamma \vdash M : T_1 \quad \Gamma \vdash M : T_2}
      {\Gamma \vdash M : T_1 \wedge T_2}
      (\wedge I)
\qquad\qquad
\dfrac{}
      {\Gamma \vdash M : \top}
      (\top I)
$$

Intersection types have interesting properties with respect to normalization:

A lambda-term can be typed without using the $\top I$ rule iff it is strongly normalizing.
A lambda-term admits a type not containing $\top$ iff it has a normal form.

What if instead of adding intersections, we add unions?

$$
\dfrac{\Gamma \vdash M : T_1}
      {\Gamma \vdash M : T_1 \vee T_2}
      (\vee I_1)
\qquad\qquad
\dfrac{\Gamma \vdash M : T_2}
      {\Gamma \vdash M : T_1 \vee T_2}
      (\vee I_2)
$$

Does the lambda-calculus with simple types, subtyping and unions have any interesting similar property? How can the terms typable with union be characterized?

I just want to explain why intersection types are well-suited to characterize classes of normalization (strong, head or weak), whereas other type systems can not. (simply-typed or system F).

The key difference is that you have to say: "if I can type $M_2$ and $M_1→M_2$ then I can type $M_1$". This is often not true in non-intersection types because a term can be duplicated:

$$ (\lambda x.Mxx)N → MNN$$

and then typing $MNN$ means that you can type both occurrences of $N$ but not with the same type, for example
$$M:T_1→T_2→T_3 \qquad N:T_1 \qquad N:T_2$$
With intersection types you can transform this into:
$$M:T_1\wedge T_2→T_1\wedge T_2→T_3 \qquad N:T_1\wedge T_2$$
and then the crucial step is now really easy:
$$(\lambda x.Mxx):T_1\wedge T_2→T_3 \qquad N:T_1\wedge T_2$$
so $(\lambda x.Mxx)N$ can by typed with intersection types.

Now about union types: suppose you can type $(\lambda x.xx)(\lambda y.y)$ with some union type, then you can also type $\lambda x.xx$ and then get for some types $S, T_1, \dots$ $$x : T_1\vee T_2 \vee \dots \vee T_n ⊢xx:S$$ But you still have to prove that for every $i$, $x:T_i⊢xx:S$ which seems impossible even is $S$ is an union type.

This is why I don't think there is an easy characterization about normalization for union types.


Internal and External Fragmentation I am working over a homework problem and am confused on how to determine whether there is internal and external fragmentation given the following table:

Characteristic                   Design 1 Design 2 Design 3
Physical Memory Address Width:     8 bit    16 bit   32 bit
Virtual (Logical) Address Width:   12 bit   20 bit   24 bit
Page/Frame size in bytes:          16 bytes 32 bytes 64 bytes

More specifically, which design has the most internal fragmentation and external fragmentation and why?

I have found the answer. External fragmentation happens over time when small spaces in memory are not effectively employed. This leads to hole everywhere in memory. Therefore it cannot be determined from the chart that there is external fragmentation.

On the other hand, internal fragmentation is the idea when there is over-allocation of memory space to a process. In the above chart, internal fragmentation depends on the page/frame size. Since it is possible for a page to only have one byte of data then larger page sizes have more internal fragmentation. Design 3 has the most spread which is the answer.


Optimal path through a DAG with sparsely available edge weights I would like to create a plot of certain metrics that are collected at revisions of a software system.  The objective of the software engineers is to minimize those metrics.

For version control, the engineers are using Git, so there is a DAG of commits (revisions).  However, the metrics are only available for a subset of those commits.  It is not feasible to collect metrics for all of the commits.

What path finding algorithm would yield the most relevant data to plot a "downward trend" in the metrics that is minimally erratic, resolving ties in favor of the path with maximum detail?

Definitions

erraticism: The sum of the absolute differences between the metric at each pair of adjacent commits along the path.  Example: For path A-B-C where A=10, B=7, C=5, the erraticism is (10 - 7) + (7 - 5) = 3 + 2 = 5.

detail: The quantity of commits that have known metrics along a path.  Example: for path D-E-F where the metric at D and F is known, but E is unknown, the detail is 2.

Scenarios to illustrate objective function

Metrics available for all paths

Say that D is the most recent commit. D has two parents, B and C.  B and C share a single parent A.

  10 -> A
       / \
11 -> B   C <- 7
       \ /
   5 -> D

In this scenario, all four commits have metrics available. In this case, the least "erratic" path is preferred.

If A=10, B=11, C=7, and D=5, the path A-C-D is preferred.

Metrics available for only one competing path

If the metric is unavailable for commit C, then the path A-B-D is preferred.

  10 -> A
       / \
11 -> B   C <- unknown
       \ /
   5 -> D

Metrics available for no competing paths

If the metrics are only known for commits A and D, then it doesn't matter whether we traverse through commit B or commit C, because neither commit will be displayed on the plot.  The plot will display path A-D.

       10 -> A
            / \
unknown -> B   C <- unknown
            \ /
        5 -> D

Competing paths of various lengths

Maximum detail

This is where it gets complicated.

Generally it is preferable to have more detail in the plot.  So in the following example, path A-C-E-F is preferred:

       10 -> A
            / \
      7 -> B   C <- 8
           |   |
unknown -> D   E <- 6
            \ /
        5 -> F

Path A-B-D-F has erraticism=5, detail=3.  Path A-C-E-F has erraticism=5, detail=4.  Detail breaks the tie, and path A-C-E-F is selected.

Minimally erratic

However, we do not prefer the path with greater detail when that path is more erratic than the alternative.  In this case, path A-B-F is preferred:

       10 -> A
            / \
      7 -> B   C <- 11
           |   |
unknown -> D   E <- 6
            \ /
        5 -> F

Path A-B-D-F has erraticism=5, detail=3.  Path A-C-E-F has erraticism=7, detail=4. Path A-B-D-F is selected.

Your question is not self-consistent, so you first need to figure out exactly what you are looking for, before we can identify an algorithm to find it.

However, once you figure that out, it is likely that dynamic programming will solve your problem.  Dynamic programming is powerful and likely to solve your problem for any reasonable criterion that depends only on detail and erraticism (assuming it is monotonic in each variable separately).

In particular, define $f(v,d)$ as follows:

  $f(v,d) = $ the smallest possible erraticism that can be achieved by a path from $A$ to $v$ whose detail is $d$.

In other words,

$$f(v,d) = \min \{\text{erraticism}(p) : p \text{ is a path from $A$ to $v$ and } \text{detail}(p)=d\}.$$

Let $\text{pred}(v)$ denote the set of vertices $u$ such that there is a path from $u$ to $v$ where you have the metric for $u$ but not for any other intermediate vertex in the path (i.e., not for any other vertex in the path other than $u$ or $v$).

Notice you can compute $f(v,d)$ given the values of $f(u,c)$ for all $u \in \text{pred}(v)$ and all integers $c$ satisfying $0 \le c \le d$.  Call this "formula (*)".

Since the graph is guaranteed to be a dag, you can linearize it (topologically sort it).  Then, visit the vertices in topologically sorted order.  When you visit $v$, compute $f(v,d)$ for each possible $d$ using formula (*) -- this is possible because the topological sort ensures you will have computed $f(u,c)$ before visiting $v$.

There are $|V|$ possible vertices and at most $|V|$ possible values for the detail.  Calculating $f(v,d)$ can be done in $O(|V|)$ time, since the set $\text{pred}(v)$ has size at most $|V|$.  Therefore, the running time of this will be at most $O(|V|^3)$.

In practice, I expect the algorithm will be faster than that.  For instance, you only need to compute $f(v,d)$ for $d=0,1,2,\dots,\ell$, where $\ell$ is the length of the shortest path from $A$ to $v$.  Also, for most vertices, the size of $\text{pred}(v)$ will usually be much less than $|V|$ -- maybe more like $O(1)$.

Once you have computed $f(Z,0),f(Z,1),f(Z,2),\dots$, where $Z$ is the final node, then you can use all of that information to select which path you want.  For instance, if your criterion is "minimize erraticism, and break ties in favor of greater detail", you just compute $\min \{f(Z,d) : d=0,1,2,\dots\}$, resolving ties in favor of the larger $d$.  As another example, if you want to modify that criterion by ignoring all paths with detail 0, just ignore $f(Z,0)$.  Or, if you want to ignore all paths with detail 0 if there exists any path with detail $> 0$, then check whether any of $f(Z,1),f(Z,2),\dots$ are finite ($< +\infty$); if yes, then you ignore $f(Z,0)$.  And so on.  Hopefully you can see how to adapt the dynamic programming solution to handle many possible variations for the objective function.

For specific objective functions, there might well be even more efficient solutions -- but since it is not clear from your question at the time of writing just what objective function you want to minimize, I thought I would outline a general answer that works for a large class of possible objective functions.


When is a variable bound or free in a lambda application? I am currently reading the book "An Introduction to Functional Programming through Lambda Calculus" (the 2011 edition) and am a bit puzzled by the definitions of free and bound variables with regards to function application.
The book states, in section 2.10, that a variable is bound in an expression if

the expression is an application $(\langle function \rangle \langle argument \rangle)$ and the variable is bound in $ \langle function \rangle$ OR $\langle argument \rangle$, or
the expression is a function $\lambda \langle name \rangle. \langle body \rangle $ and the variable is named $\langle name \rangle$ or bound in $\langle body \rangle$.

Next, it states that a variable is free in an expression if

The expression is a single name and the variable has that name, or
the expression is an application $(\langle function \rangle \langle argument \rangle)$ and the variable is free in $\langle function \rangle$ OR $\langle argument \rangle$, or
the expression is a function $\lambda \langle name \rangle.\langle body \rangle$ and the variable is not named $\langle name \rangle$ and is free in $\langle body \rangle$.

What confuses me is the use of "or" in the definitions of both bound and free variables in applications. I figured that if a variable is not bound, it must be free, and if a variable is not free, it must be bound. So I would expect that if a variable is free, the point 1 in the definition of bound above is inverted, so with boolean logic $\neg(A \lor B)$ should become $\neg A \land \neg B$.
However, the book doesn't state that a variable is free if it is free in $\langle function \rangle$ AND $\langle argument \rangle$.
I checked Wikipedia for another reference and it states:

The set of free variables of a lambda expression, M, is denoted as FV(M) and is defined by recursion on the structure of the terms, as follows:

$FV(x) = \{x\}$, where $x$ is a variable

$FV(\lambda x.M) = FV(M) \setminus \{x\}$

$FV(M N) = FV(M) \cup FV(N)$

So the set of bound variables in (M N) should be the complement of $FV(M) \cup FV(N)$ which I believe would be $FV(M)' \cap FV(N)'$ where ' denotes the complement.
The book repeats this definition later in a summary of the chapter, so I'm hesitant to think it would be a typo. I'm thinking that either I'm

wrong in assuming that bound and free are full complements or
wrong in thinking that a variable with the same name in the function and argument expressions of an application is the same variable.

What is the correct interpretation here? As an example, in the application expression $(\lambda x.x\ \ \lambda y.x)$, is $x$ bound or free, or is it senseless to speak of "x" outside of the scope of either the function or argument expressions?

wrong in assuming that bound and free are full complements

Yes. Each occurrence of a variable is either bound or free, but not both. But a variable is considered free if it has any free occurrences, and it's bound if it has any bound occurrences; it can be both at once.


O(n*log(n)) Turing Machine with exactly 1 tape for “equal number of a's and b's in a given word”? I need to build a TM with exactly 1 tape for the language L = {w| w is a word with same number of a's and b's in it, for example: abba, aababb}

The TM has to have ONLY 1 tape and it has to run in O(nlog(n)) time. I understand how to do it in O(n^2) but i have no idea how to make it nlog(n).

If i have the input w = "aaaa....abbbbb....bb" for example, where w = a ^ n/2 * b ^n/2 (which is the worst case) then i will go backwards each time (to delete each a for each b) and the steps taken will be of size 1,2,3,4.....n. Sum(1 to n) is O(n^2)...

Help ? any ideas ?

The idea is to repeatedly apply the following algorithm:

Determine the parity of the number of $a$'s, deleting every second $a$ on the way.
Determine the parity of the number of $b$'s, deleting every second $b$ on the way.
Accept if there were no $a$'s or $b$'s.
Reject if the parities are different.
Jump back to Step 1.

Each phase of the algorithm takes $O(n)$ steps, and there are $O(\log n)$ phases, for a total of $O(n\log n)$.

As an aside, using crossing sequences you can prove a matching lower bound of $\Omega(n\log n)$. Consider all inputs of the form $a^ib^{n-i} a^nb^n b^ja^{n-j}$. Such an input should be accepted iff $i = j$. For every input $x$, trace the execution of the Turing machine. When it crosses from the $n$th letter to the $(n+1)$th letter, record the state $\sigma$ of the Turing machine, and wait until the Turing machine crosses from the $2n$th letter to the $(2n+1)$th letter, at which time add $\sigma$ to the crossing sequence, and go back to waiting for it to cross from the $n$th letter to the $(n+1)$th letter. A cut-and-paste argument shows that the crossing sequence must depend on $i$, and so must be of length $\Omega(\log n)$ in the worst case, where the hidden constant depends on the number of states in the machine. Since it takes the machine $n$ steps to add a state to the crossing sequence, we obtain a lower bound of $\Omega(n \log n)$.


Push-down automaton for a language with number of 1s double than 0s This questions is taken from a complexity theory course.

  Design a push-down automaton that recognize $L = x \in \{0,1\}^* $
  such that $x$ contains a number of ones double than a number of zeros.

Example: x = 011011, 100011111, 011011110.

My approach

I tried to push on the stack a symbol "A" every time I read "0", than pop "A" from the stack when I read two consecutive "1" but this approach works not for every string $x$ in the language. Maybe the final PDA is non-deterministic. Any hints?

Consider this algorithm:

Initialize a variable $x := 0$.
Scan the string, left to right. If you see $1$, set $x := x + 1$, if you see $0$, set $x := x - 2$.
When you are done, accept iff $x = 0$.

It should be obvious that it recognizes your language. Can you figure out a way to implement it replacing the counter with the stack?


This answer assumes the following interpretation of your question:

  What is the complexity of the following problem? Decide whether a given CSP is satisfiable, where at most half of the assignments satisfy each constraint.

It is likely that this problem is either in $\mathsf{P}$ or $\mathsf{NP}$-complete. In fact, if we bound the width of the constraints (how many variables appear in them), then Schaefer's dichotomy theorem implies that the problem is either in $\mathsf{P}$ or $\mathsf{NP}$-complete, giving a criterion to decide which of these possibilities holds.

In your case, it seems likely that the problem is $\mathsf{NP}$-complete already for width 3. You can verify (or refute) this using the criterion in Schaefer's theorem, which can be found in the Wikipedia article linked to above.


Fitting different rectangles inside a rectangle I have a fixed rectangle of size X x Y.
I also have a bunch of rectangles of different sizes.

I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate any one of them by 90°.

Any great algorithm to do this ?

I know that some packing algorithm exists and several threads discuss it but it's not exact and it does not support rectangle rotation, therefore I cannot apply it to find a minimum rectangle and compare it afterwards to the given X x Y rectangle.

As mentioned in the comments, this problem is known to be NP-hard. So, the only fast algorithms you're going to get will be approximation algorithms or heuristic. As this is a common practical problem (packaging for logistics, for example), there are many heuristic algorithms, both general and with more assumptions.

A lot approaches ignore rotation, but can be expanded fairly easily to support it. As you seem to be aware of approaches without rotation, I'll focus on the rotating part.

A good resource is 'One thousand ways to pack the bin', by Jukka Jylänki. It covers many heuristic algorithms, and considers rotation part of the problem. Most of the rest of this post summarizes this paper.

While rotation makes the problem a lot harder to solve exactly, it doesn't make most heuristic methods much more complicated, as they cannot afford to make complicated choices and so choose heuristically how to rotate.

Shelf heuristic

For the shelf algorithms, rotation is quite simple:

If the current rectangle starts a new shelf, we rotate such that the shelf height is minimal.
Otherwise, rotate such that the width is minimal while still fitting the shelf (if it fits at all)

Point 2 is actually the best way to rotate given that the rectangle will be packed in the current shelf while for point 1 one could argue to do the opposite and this could indeed be better in some cases. (such as the case that all remaining rectangles are squares with length equal to the long side of the first rectangle of the shelf)

Guillotine heuristic

For the guillotine algorithm, the choice for rotation isn't so clear (perhaps a reason why Jylänki leaves this open), but one reasonable method is to try both orientations to decide whether a rectangle 'fits'. If both fit, one could try to pick the one that matches the split rule (for example, choose the rotation that minimizes the area of the chosen free rectangle when using the Best Area Fit variant)

Other heuristics

For the Maximal rectangle algorithm and the Skyline heuristic, supporting rotation here is similar to the Guillotine case, there aren't really any particular choices other than trying to fit with both orientations and pick the one which makes more 'sense' with respect to the rest of the specific heuristic.

There are more algorithms, but I think this gives a good overview of the ideas of how to support rotation. As you might have noticed, these methods aren't too fancy, that is sometimes the best you're going to get.


How to reduce MAX-2SAT problem to finding a cut in a graph I'm trying to reduce the MAX-2SAT problem to finding a cut in a graph, with no luck so far.
Let me first show a description of the problem:
2SAT: Given a boolean formula $\varphi$ in a CNF form, where every clause has 2 literals (a variable or its negation), one should decide whether there is an assignment that will satisfy $\varphi$.
The 2SAT problem is in $P$.

MAX-2SAT: Given a boolean formula $\varphi$ in a CNF form, where every clause has 2 literals, and $k\in \mathbb{N}$, one should decide if there is an assignment that will satisfy at least $k$ clauses in $\varphi$.
This is an $NPC$ problem, and I'm trying to reduce it to finding the maximum cut in a graph:
MAX-CUT: Given $(G=(V,E), w, k)$, where $G$ is an undirected graph, $w$ is a weight function; $w: E\rightarrow \mathbb{N}$ and $k\in\mathbb{N}$, one should decide whether there exist a cut $(V_1,V_2)$, s.t its weight is at least $k$, meaning $k\leq \sum _{u\in V_1, v\in V_2}w(u,v)$.

I tried some obvious constructions that didn't work, like setting:
$G=(V,E)$
$V=\left \{ v_x|x\text{ is a literal in } \varphi \right \}$
$E=\left \{(v_x,u_z)|\text{ There exist a clause } x\vee z \text{ in } \varphi\right \}$
and finally setting $w(e)=1$  $\forall e\in E$

This obviously didn't work, since having $k$ satisfied clauses in $\varphi$ does not imply a $k$-weighted cut in $G$.
(If the above can be improved to achieve the desired reduction, I would love to get some guidance)
I looked around online, and found that it is possible to construct an "implication graph" from $\varphi$, where every clause $(x\vee z)$ in $\varphi$ is translated to the equivalent logical expressions: $\bar{x}\Rightarrow z$ and $\bar{z}\Rightarrow x$, and these, in turn, are translated to vertices $\bar{x}, z, \bar{z}, x$, and directed edges $\bar{x}\rightarrow z$ and $\bar{z}\rightarrow x$, but I just can't see how that helps, since, again, $k$ satisfied clauses in $\varphi$ does not imply $k$-weighted cut in $G$.
Any help would be greatly appreciated.

Idea: Have two vertices $x,\bar{x}$ for each variable, and connect them with an edge with some large weight which will force any maximal cut to put them in different parts of the cut. The idea is that for any two variables $x,y$, $x$ and $y$ get the same truth value iff the vertices $x,y$ are in the same part of the cut. This way you encode a truth assignment.

For each clause $x \lor y$, we would like to do something of the following sort: add a vertex $\varphi_{x \lor y}$ and connect it to both $x$ and $y$. In order to guarantee that $\varphi_{x \lor y}$ is in some specific part of the cut, add a new vertex and connect it to all "clause" vertices with an edge having some large weight. This idea doesn't quite work since the value of the cut depends on how many literals satisfy the clause. Find a way to fix it.


Understanding Closest Pair Algorithm (CLRS) I'm reading CLRS Section 33.4 Finding the closest pair of points. At exercise
33.4-2 they say

  33.4-2

  Show that it actually suffices to check only the points in the 5 array positions following each point in the array Y'

But I'm getting 4 array positions following each point in the array Y' will be suffice to check. See the fig below

Which possibility I'm missing. Can anybody point it out.

Assume that a point exists in every corner in the figure (including the inside corners). If points cannot overlap, then you have 6 points that can reside in the x2 box, and since you must be looking at one of them, you need only compare it to the next 5 in Y'.


Clarification of Hopcroft's proof that "deciding whether a program halts on all inputs" is not R.E $DoesNotHaltOn\_w=\{(M, w) : M$ does not halt on input w$\}$
$AlwaysHalt =\{ M : M$ halts on all inputs x $\}$

Hopcroft gives the following proof that $AlwaysHalt$ is not R.E.

1) Given an input x of length n, $M'$ simulates $M$ on w for n steps.
2) If during that time $M$ halts then $M'$ loops and $M'$ does not halt on its own input x.
3) However if $M$ does not halt on w after n steps then $M'$ halts.
4) Thus $M'$ halts if and only if $M$ does not halt on w.
5) Since the problem of telling whether $M$ does not halt on w is not R.E., it follows that whether a given TM halts on all inputs must not be R.E. either.

I don't understand why in (1) the number of steps to simulate needs to be dependent on the length of the input x.

I don't understand how step 3 implies step 4. I don't see how knowing that $M$ does not halt on w after n steps (or less) allows us to conclude that $M$ will not halt on w after more than n steps.

Could someone clarify? Thanks.

$M'$ doesn't "need" to do anything.  $M'$ is a machine that we construct for purposes of the proof.  Hopcroft wrote the theorem, so he can design $M'$ however he wanted -- of course, then it's his obligation to show how his choice of machine helps him prove the theorem.  He chose $M'$ cleverly in a way that helps make the proof easy, but that was his choice.

So, it was his choice to make the $M'$ simulate $M$ for only $n$ steps.  He could have chosen something else, but this particular choice makes the proof work out nicely.  In particular, this property of $M'$ is useful for showing that statement 4 is true.  (Exercise: try proving that statement 4 is true, and check where you used the fact that $M'$ will only simulate $M$ for $n$ steps, not more.)


Pumping lemma for linear languages Let $L$ be a linear language. Then there is a constant $p$ such that for all $w$ in $L$ with $|w| \ge p$, $w$ can be written as $uvxyz$ where (i) $|uvyz| \le p$ (ii) $|vy| > 0$ (iii) $uv^ixy^iz$ is in $L$, for all $i \ge 0$. How do I prove the first condition? I am having difficulty proving the bound and relating the bound k to the grammar.

Study the proof of the pumping lemma for context-free languages. The pumping property is obtained by finding a repeated non-terminal on a path in the derivation tree. By looking at the first repetition you can find a bound on the length of that path in the tree, and hence a bound on the length of the substring $uvyz$.

What is k?


Shortest path in a known room for a Roomba I had an interview question once which asked for an algorithm to ensure a Roomba vacuum cleaner visited/vacuumed every "cell" in an unknown shape/size room with unknown obstacles. Depth first search can do this, but I was left wondering if you could minimize the backtracking.

I looked into how it's actually done for Roomba and from what I read on Robotics stack exchange, it doesn't use a deterministic algorithm that guarantees shortest distance, because it doesn't know the room layout and obstacles ahead of time.

But what if we did know the full layout of the room at the start? Is there a way to use a map to generate a path through the room with minimum backtracking? In this example, the map is an undirected graph without weights (or every joining edge distance is 1), and it likely contains cycles.

The problem sounds similar to travelling salesman and Hamiltonian paths, but I don't think it maps to them exactly. Travelling salesman and Hamiltonian paths have the requirement that vertices are only visited once. In the Roomba example, we don't care if it vacuums the same spot twice, we just want it to thoroughly vacuum the whole room (don't miss anywhere) as fast as possible.

the classic A* algorithm was invented in 1968 and is used for the purpose of shortest path-finding by robots, and it is provably optimum in a limited sense (eg given an unchanging layout and other constraints). there are many other pathfinding algorithm variants, basically "smart graph traversal" algorithms, eg focused on the online problem with changing constraints, see eg "how do state of the art pathfinding algorithms differ", cstheory.

here is some information on the roomba algorithm which is somewhat proprietary based on an interview with one of the designers (the interview seems no longer available). it is somewhat random and apparently uses a locally optimizing algorithm aka "greedy".


Must reductions be injective? From Sipser,

Language A is mapping reducible to language B, written $A \leq_m B$,
if there is a computable function $f : \Sigma^* \rightarrow \Sigma^*$, where for every $w$, $w ∈ A \Leftrightarrow f(w) \in B$. The function $f$ is called the reduction from A to B.

A function is injective if every element in the co-domain is mapped to by at most one element of the domain.

I'm confused on how $w \notin A$ are handled. It seems that for $w \in A$ every element must map to a unique $b \in B$. Because $w \in A \Leftarrow f(w) \in B $.

New question then, is there any use to having an injective reduction? I've noticed that many proofs of NP-hardness seem to have reductions that are injective (at least on $w \in A$). If reductions are not injective ~~ Why don't we simply define our reduction function $R$ as follows, check if $w \in A$, If $w \in A$ then map to a constant $b \in B$. Else, map to a constant $c \notin B$?

The function $f$ does not need to be injective. It would be fine to map every $w \in A$ to the same element $w' \in B$ (and to map every $w \in \Sigma^* \setminus A$ to the same $w'' \in \Sigma^* \setminus B$). In fact, for every decidable language $A$, we have $A \leq_m B$ for every $B$ such that $B \neq \Sigma^*$ and $B \neq \emptyset$.


Practical importance of interval / circular-arc graphs in resource allocation A graph is called a circular-arc graph if each of its vertices can be assigned to a circular arc such that two vertices are adjacent iff their respective arcs have a non-empty intersection. Analogously, a graph is an interval graph if we can assign each of its vertices to intervals on a line in the above fashion. Note that interval graphs are a subclass of circular-arc graphs.

Wikipedia states that interval/circular-arc graphs are important in the modeling of (periodic) resource allocations problems in operations research. Can you provide a concrete example of such a problem and how it is modeled to CA/interval graphs? The problem should conceivably occur in practice.

Making Louis' comment into an answer:

Given a set of intervals (interval system) $\mathcal{I} = \{ [x_1, x_2] ,\dots, [x_{2n-1}, x_{2n}] \}$. Each of the $n$ intervals corresponds to the time period a certain job is being worked on. Now, we want to find all time periods in which the number of concurrently active jobs is maximal. These time periods happen to correspond to the maxcliques of maximal size of the intersection graph $G(\mathcal{I}) = (\mathcal{I} , E)$ with $E$ being defined as
$$ ([a,b] , [c,d]) \in E \iff [a,b] \cap [c,d] \neq \emptyset $$
The closed neighborhood of a vertice $v$ in a graph $G$ is defined as
$$ N[v] := \{ u \in V(G) : \{v,u\} \in E \} \cup \{v\}$$
It is known that for any interval graph every maxclique can be characterized as the intersection of two neighborhoods, i.e. for each maxclique $C$ of $G$ there exist some $u,v \in V(G)$ s.t. $C = N[u] \cap N[v]$.

With this we can easily devise an efficient algorithm to find the wanted time periods.

If you have any other answers along these lines I'd be happy to hear them.


Is a degree-$d$ pseudo distribution always a relaxation? The optimization problem we are generally concerned with looks like the following,
\begin{eqnarray*}
&\inf \{ p(x) \vert x \in K\} \\
&K = \{ x \in \mathbb{R}^n \vert q_i(x) \geq 0, i = 1,..,m \}
\end{eqnarray*}

where $p(x)$ is some polynomial objective function and $q_i(x)$ are polynomial constraints.

One can look at this corresponding question,

\begin{eqnarray*}
&\inf_D \{ \tilde{\mathbb{E}_D} [p] \} \\
&s.t \\
&D : \{ 0,1\} ^n \rightarrow \mathbb{R} \\
&\sum_{x \in \{0,1\}^n} D(x) = 1 \\
& \forall u \in SOS_d \\
&\tilde{\mathbb{E}}_D [u] \geq 0 \\
&\tilde{\mathbb{E}}_D[q_i] \geq 0
\end{eqnarray*}

Here we use the ``pseudo-expectation" notation" whereby we have for any function $f$, $\tilde{\mathbb{E}}_D[f] = \sum_{x \in \{ 0,1\}^n } D(x)f(x)$ And $SOS_d$ is the cone of all real polynomials in $n-$variables which can be written as a sum of squares of polynomials of degree at most $\frac{d}{2}$

Is it clear that for all $d$ the later is a relaxation of the former?

If we restrict the polynomials to be valued on the hypercube $\{0,1\}^n$ then I can think of an argument which shows that the latter is a relaxation of the former by going through an intermediate Lassere relaxation. But if the polynomials are valued on the whole of $\mathbb{R}^n$ (as written above) then my above argument works only if $n^d < 2^n$.
Is there a proof that if one keeps increasing the $d$ then at $d=n$ the later will exactly hit the infimum being searched for in the first?

To see that this is a relaxation, all you have to check is that each feasible solution to the first problem gives rise to a feasible solution to the second problem. All you have to do is, given $x \in K$, take an actual distribution $D$ concentrated on $x$. (This only works if in the definition of $K$ you replace $\mathbb{R}^n$ with $\{0,1\}^n$; your formulation doesn't make too much sense.)

When $d = n$, the conditions guarantee that $D$ is an actual distribution. If the objective function $p$ is concave then the optimal distributions are singletons, and so both programs have the same value. Otherwise it could be that for some distribution $D$ supported on $K$ it holds that $\mathbb{E}_{X\sim D}[p(X)] < \min_x p(x)$.


Comparing complexity of function Let's say I have a function that runs in $O(n \lg n)$.

Let's say instead of running this function with a $n$-sized input, I run it $k$ times with an $(n/k)$-sized input, so I want to check if

$$ O(n  \lg n) = k \left( O \left( \frac{n}{k} \lg \frac{n}{k} \right) \right)$$

I think it is, because of:

$$ O(n \lg n) =  O \left( \frac{kn}{k} \lg \frac{n}{k} \right) = O \left( n \lg \frac{n}{k} \right). $$

Supposing $0 < k \leq n$, as in worst case $k = 1$, we can say that $\dfrac{n} {k}$ is $n$.

Am I right?

In general, will the original $O(n \lg n)$ function be faster or slower? It seems to be slower because what was $\lg n$ now is $\lg \dfrac{n}{k}$ for some $k > 0$.

PS: $\lg = \log_2$

If a function $f$ is convex and $f(0) = 0$ then $f$ is superadditive: $f(a+b) \geq f(a) + f(b)$ for $a,b \geq 0$. The function $f(n) = n\log n$ is convex (since $f''(n) = 1/n > 0$) and $f(0) = 0$ (in the limit), and so for all $k>0$,
$$
f(n) \geq k f(n/k).
$$
If $f$ were concave rather than convex, $f$ would be subadditive, and then $f(n) \leq kf(n/k)$ for all $k>0$.


Complexity of "given a graph $G$ with vertex $v$, is there a maximum clique containing $v$"? The usual way of translating the maximum clique problem into a decision problem is to ask "does there exist a clique of size $\ge k$ in $G$?" Clearly this problem is in NP (and is NP-hard).

Another possible way of making it into a decision problem would be:

Instance: Graph $G=(V,E)$ and vertex $v\in V$.
Question: Does there exist a clique $C\subseteq V$ in $G$ that contains $v$ and is of maximum cardinality among cliques?

If P = NP, this problem is polynomial-time solvable. The problem is also contained in $\Sigma_2^p$ (does there exist a clique such that all other cliques are not bigger?). Has its precise complexity been studied?

(Very similar questions can of course also be asked about vertex cover, dominating set, independent set and the like).

I do not recall having seen this precise problem before, but it does have a Cook reduction (polynomial-time Turing reduction) to $k$-Clique:

  Let $Y$ be an oracle for $k$-Clique. On input $(G,v)$:

  Determine the maximum clique size $\omega(G)$ via at most $log_{2}(n)$ calls to $Y$ using binary search.
  Create $G'$ by removing all vertices $u \neq v$ where $uv \notin E(G)$ (i.e. $V(G') = N[v]$).
  Determine $\omega(G')$ using $Y$ and binary search.
  If $\omega(G') = \omega(G)$ answer YES, otherwise answer NO.

This puts it in $\Delta_{2}^{P} = P^{NP} = P^{SAT}$, a refinement of your observation.

As there are $O(\log{}n)$ calls to the oracle, we can squash containment a little further; the problem is in $\Delta_{2}^{P}[O(\log{}n)] = P^{NP}[O(\log{}n)] = P^{SAT}[O(\log{}n)]$.

[Thanks here to Ricky Demer] If $P=NP$, then $P^{NP} = P^{P} = P$, so you are correct about the polynomial time solvability in this case (contrary to my original, now edited, musings).

So perhaps the problem is $P^{NP}[O(\log{}n)]$-complete, it shouldn't be (as Dominik observed in his answer) $P^{NP}$-complete. I have tried to use the results of Theorem 3.5 from Krentel's paper to construct a reduction, but unless $P^{NP}$ is low for itself (which I don't think it is, but don't know), this has been without luck. (If it is low for itself, then I have a marvellous proof, sadly there are no margins here to put it in.)


Formal Languages: if $L_1^* = L_2^*$, then $L_1 = L_2$ The question is: For all languages $L_1$ and $L_2$ , if $L_1^* = L_2^*$, then $L_1 = L_2$.

We know that two languages are equivalent if $L(G_1) = L(G_2)$, where $L(G) = \{w \in T^* \mid S\Rightarrow^*w\}$. Two grammars are equivalent if the quadruple of $G_1 = (\Sigma_1,N_1,P_1,\sigma_1)$ and $G_2 = (\Sigma_2,N_2,P_2,\sigma_2)$ generate the same formal languages.

I think this statement is true, because they have to accept the same formal languages regardless if its called multiple times.

I'm asking this question so someone can confirm it, knows an exception, or has a proof.

Certainly not. Consider $L_1=\{a\}$ and $L_2=\{\epsilon, a\}$.


is this time complexity subexponential? Is next time complexity sub-exponential?

$O(2^{N^{LOG2(1.5)}}/8)$

unformatted: O((2^N)^LOG2(1.5))/8) just in case I didn't format it properly.

It depends on how you define subexponential. The definition I generally use is:

$$\textsf{SUBEXP} = \bigcap_{\varepsilon > 0}\textsf{DTIME}(2^{n^\varepsilon})$$

However some authors define:

$$\textsf{SUBEXP} = \textsf{DTIME}(2^{o(n)})$$

Since your function is $2^{n^c}$ for some constant $c<1$, it would be subexponential according to the second but not to the first.


Are Time-sharing and multi-tasking operating systems same or different My question is regarding time-sharing and multi-tasking systems.

Time-sharing operating system assigns time slot to each task while multi-tasking OS runs various jobs in parallel.

But as I get it, on a single processor system, time-sharing is the only way to achieve multi-tasking.  (I don't know if I am correct on this premise.)

So, are time-sharing and multi-tasking system same or different.
And if they are different, then what are the key differences (particularly on a single-processor/single-core system with no hyper-threading support etc) ?

Thanks

Just as multiprogramming allows the processor to handle multiple batch jobs at a time, multiprogramming can also be used to handle multiple interactive jobs. In this latter case, the technique is reffered to as time sharing, because processor time is shared among multiple users. In a time-sharing system, multiple users simultaneously access the system through terminals, with the OS interleaving the execution of each user program in a short burst or quantum of computation.

William Stallings, Operating Systems Internals and Design Principles, 7th Edition

You should keep in mind that the principal objective of a time sharing system is not to maximize processor use, but to minimize response time.

I think it would be correct however to assert that on a single processor system, multi-tasking is achieved through time sharing. Remember that a processor can execute only one task at a time at any given time.


Max cut in cubic graphs The following question is related to the max cut problem in cubic graphs. In this survey paper Theorem 6.5 states

  A maximal cut of a cubic graph can be computed in polynomial time

Browsing through some other related results (for example this SODA paper) one gets the impression that this problem is actually NP complete even for cubic instances. In particular, the last paper states that this is indeed so if the graph is subcubic.

That makes me wonder.. What's going on? Is the survey paper (and the result cited therein) faulty or is there some point that I am missing?

Maximal cut is different from maximum cut (MAX-CUT). In maximum cut, the goal is to find a cut cutting the maximal number of edges. In maximal cut, the goal is to find a local maximum: a cut such that switching the side of any single vertex does not result in more edges being cut. Such a cut exists, since the maximum cut is also maximal. But finding a maximum cut is apparently harder than finding just a maximal cut.


Writing a multitasking operating system for a processor without MMU I've been thinking of writing a hobby operating system for some of the ARM processors. There are many popular single-board computers with ARM MPU, so I simply wanted to purchase one of those (choosing one with more open documentation). I was surprised when I found out, that even boards with really enough memory do not have MPUs with Memory Management Unit.

As I've always been working with i386+ processors and never anything else (except for some Microchip PICs), I'm now confused and not sure if one can write a working operating system whose functionality wouldn't be limited when comparing to OSes written for MPUs with MMU.

I could think of few solutions for "replacing" or "simulating" MMU and I've got few questions:

On Intel processors in 16 and 32-bit modes there is a way of using segments and segment selectors to use different blocks of memory by different tasks. That means that I could change memory space by changing contents of segment registers when doing a task switch when on x86.
Are there any general concepts for memory segmentation that could be used on ARM architecture?
By loading a linked object file instead of executable I could use relocations (fix-ups) or position independent code to point tasks on pieces of memory in the same way as if I mapped the memory using paging structures. Would this be effective enough?
I have also read something about Memory Protection Units on ARM processors. Could these be helpful?

Are there any "usual" ways of managing tasks on systems without MMU?

It's actually not that hard to design an operating system that doesn't require an MMU. There are a few conveniences you'll have to do without, but nothing insurmountable.

Since different tasks will have to be loaded at different addresses, all your code (except for the kernel, the standard library, and any other code that's part of your base runtime environment) has to be compiled as position-independent. This means relative jumps and a base address for heap access stored in a register. Spending one register as a base address might seem costly if you're used to x86-32's four general registers, but most modern architectures have more, and even 8088 has the segment registers precisely for that.
A Unix-like architecture has to be revised, because you can't implement fork. That's ok, most operating systems don't have fork. (You can have vfork.)
You can't preallocate large gobs of space without also allocating the corresponding memory. This means no growing of the stack or heap on the fly by allocating one more page at a time.

If you have an MPU, then your tasks can still be separated from each other as usual in multitasking operating systems. Without an MPU, memory separation can only be cooperative if you allow tasks to execute arbitrary code. One way to achieve memory separation without an MPU is to restrict tasks to use only verified code on a virtual machine and implement memory protection in software as part of the VM engine.

uClinux is a project based on the Linux kernel that runs on processors (including ARM Cortex-M) without an MMU. Its restrictions on multitasking are essentially what I outlined above.


As a wannabe computer "scientist" I have problems differentiating theory and practice Specifically I'm studying towards a research degree in HCI (human computer interaction). I have problems however differentiating theory and practice, or science and engineering. I know science is about advancing human knowledge. Providing evidence about something specific in a field. But it's also about theory right? I guess there's different ways to do science; you can prove something with numbers and results, but you can also do science simply by creating a new method or theory about how something should work right? Engineering on the other hand is more about putting into practice the theory, right?

I'd like to have some guidance, perhaps with examples, to what differentiates theory and practice, science and engineering. Also books/articles to read on the subject would be greatly appreciated.

PS: In HCI it's hard to do research with experiments - it's very subject and not quantifiable as other fields of computer science. Perhaps this is why my confusion is greater than one would expect.

There is no universal objective answer to the question of how to tell what counts as theory and what counts as practice, or what counts as science vs engineering; the precise dividing line between theory and practice, or science and engineering, is subjective and a matter of opinion.  Those terms are not precisely defined -- they are fuzzy, subjective terms.  Different people use them differently.

For instance, sometimes people might use science to mean "understanding fundamental questions, identifying and testing laws of nature and hypotheses" and engineering to mean "building useful systems and solving practical problems", but even there the line is fuzzy.  Other times people use the term "science" to mean "what I do" or "the kind of work I respect" or "the really challenging stuff" and "engineering" to mean "what those other researchers do" or "the kind of work that I consider trivial/uninteresting/not deep".  You'll probably encounter many other variations on these kinds of meanings.

P.S. You are wrong that it's hard to do research with experiments in HCI.  Indeed, every human subjects study is itself an experiment, so experiments are very commonly used in HCI.  Perhaps you are thinking that it is challenging to find universal laws of nature in HCI (analogous to Newton's First Law, say, but for people), as people are complex.  That is true, but it doesn't mean no such laws exist or that such research is impossible.  Consider Fitt's Law, for instance.


inserting into min heap These are the instructions I been given :

  What does the array look like at each step when inserting "2" into the
  following min-heap?

  Give your answer as comma-separated numbers, with a space after each
  number, eg., 0, 2, 3, 4

  The heap starts at entry 1 (second entry) of the array, so begin with
  "0,..." for the unused entry.

and I need to write down the array at each step like

Immediately after item is added: for this step I got 4 6 8 7 2

After first sift up step: 4 2 8 7 6

but that is wrong apparently? I'm not sure why also I'm not sure where and why I'm suppose to put a 0.. is there a different way to write it?

For any element at index $i$ store its left chid at index $2i +1$ and right child at index $2i+2$.

Your heap in the form of array without any insertion. The $0$ in the array given below
 means no key at that index.
  $$\fbox{4}\fbox{6} \fbox{8}  \fbox{7}\fbox{0}\fbox{0} \fbox{0} \fbox{0}$$

After inserting $2$.

$$\fbox{4}\fbox{6} \fbox{8} \fbox{7}\fbox{2}\fbox{0} \fbox{0} \fbox{0}$$

But you need to maintain the min heap property. So

$$\fbox{4}\fbox{2} \fbox{8} \fbox{7}\fbox{6}\fbox{0} \fbox{0} \fbox{0}$$

Again $2$ is less than $8$. So

$$\fbox{2}\fbox{4} \fbox{8} \fbox{7}\fbox{6}\fbox{0} \fbox{0} \fbox{0}$$


Summation of $O(n)$ from $1\le k\le n$ Summation of $O(n)$ from $1\le k\le n$.

I think it should be $O(n)$ only. Because we are addition $O(k)$ and maximum order will be $O(n)$. But answer is given as $O(n^2)$.

Correct me if I'm wrong.

Suppose $T_n = O(n)$. That means that for some constant $C$, $T_n \leq Cn$. Therefore $$ \sum_{m=1}^n T_m \leq C \sum_{m=1}^n m = \frac{C}{2} m(m+1) = O(m^2). $$ If also $T_n = \Omega(n)$ then you can show in exactly the same way that the sum is $\Omega(n^2)$, so that no better bound is possible (for concreteness, you can take $T_n = n$).


How to find the symmetry group of a polynomial Say I have a polynomial in $n$ variables of maximum degree $m$. I define its symmetry group to be the subgroup of the permutation group which fixes the polynomial when it acts on the variables. Example: $x^2+y^2+z$ has the subgroup $\langle(x,y)\rangle$. Given such a polynomial, what is the best way to find such a polynomial.

Usage Note: I need this algorithm to terminate in "a short amount of time" for $n$ about 15, $m$ about 10. Short being, I guess, less than 1 minute.

Partial progress: If all I do is test particular elements of $S_n$, this problem is basically intractable as I need roughly $(n-2)!$ tests. Current implementation does basic checks such as the following. In my example $x$ cannot map to $z$ because $z^2$ terms do not exist. In this way we can eliminate much larger fractions of permutations. However, since $S_n$ is so large, this approach is still too slow.

There is a reduction from your problem to graph isomorphism, as explained in this question on Math Overflow.  In particular, that answer shows how to obtain a random automorphism of the polynomial, i.e., a random permutation in the symmetric group.  For example, you can start by randomly picking a pair of variables $x_i,x_j$ and testing whether there exists an automorphism that sends $x_i \mapsto x_j$; if so, you can search to find another variable $x_k$ such that there exists an automorphism that sends $x_i \mapsto x_j$ and $x_j \mapsto x_k$; and so on until you obtain a complete permutation.

To obtain a set of generators for the symmetry group, you can repeat this search many times to obtain multiple random permutations known to be in the symmetry group; if you repeat enough times, with high probability, the resulting set will generate the entire symmetry group.  Or, you can systematically enumerate the space of all permutations that are in the symmetry group; if the symmetry group is small enough, this will be efficient.

This requires us to have an oracle for solving graph isomorphism.  Fortunately, there are existing graph isomorphism solvers that can solve typical instances of graph isomorphism very rapidly.  For instance, you can take a look at nauty, a graph isomorphism solver that typically finishes within seconds on graphs with at most 100 vertices or so.  The question on Math Overflow describes how to reduce the problem to isomorphism of colored hypergraphs; the nauty manual describes how you can convert this to an ordinary graph isomorphism problem, at the cost of some small increase in the size of the graph.

If you put all of this together, I expect it will be possible to construct an algorithm for your problem that is pretty efficient in practice, for polynomials of the size you describe.


Constructing a pushdown automaton that accepts L* Would appreciate if you could take a look at what I did and help me finish it.

  Given a pushdown automaton that accepts a language $L$ by final state, construct a pushdown automaton that accepts $L^*$. Use a "double bottom" if need be.

My attempt:

Given  $M = (Q,\Sigma,Γ,\delta,q_0,⊥,∅)$, we'll add a double bottom by altering the function: $\delta' := \delta'(q_0',\epsilon, ⊥')={(q_0, ⊥⊥)}$, so M' is basically $M' = (Q\cup{q_0',q_f},\Sigma,Γ∪{⊥'},\delta',q_0',⊥',{q_f})$. The accepting state is reached by $\forall q \in Q\colon \delta' (q,\epsilon,⊥')={(q_f,⊥')}$.

How do I finish it so that it accepts $L^*$?

The Kleene star is, as you know, the union $\bigcup_n L^n$ of arbitrary powers $L\cdot L\cdot\ldots\cdot L$ of $L$.

If $M$ is the automaton that accepts $L$, then in order to make an automaton for $L^*$ you basically have to make it possible to restart the automaton after accepting $L$. Be careful in choosing final state or empty stack acceptance.


If $A$ is m-complete for $\Sigma_n$, is $\overline{A}$ m-complete for $\Pi_n$? If we have a set $A$ that is m-complete for $\Sigma_n$, then is it's complement $\overline{A}$ m-complete for $\Pi_n$?

I know that $\overline{A} \in \Pi_n$, but does it inherit the completeness?

I think this makes sense but I can't seem to think of any formal reasons why.

Hint: use the fact that $A\le_p B \iff \overline{A} \le_p \overline{B}$ (the same reduction works for both sides).

Try proving this for $NP,coNP$ first, and then check if your proof generalizes to the n'th level too.


Solve the recursive function $T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$ in one of my college assignments i came up with the following recursive function which I'm ask to solve:
$T(n) = T(\sqrt{n}) + T(n - \sqrt{n}) + \theta(n)$
I could not use master method on it and it is not an LHR either.
I assume this must have something to do with recursion tree but i cant figure the relation if so.

When $n$ is large, $T(n-\sqrt{n})$ is much larger than $T(\sqrt{n})$. Therefore, roughly speaking,
$$ T(n) \approx T(n-\sqrt{n}) + \Theta(n). $$
Now let us imagine extending $T$ to all inputs, and suppose that it was differentiable. Then $T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$, and consequently
$$ T'(n) \approx \Theta(\sqrt{n}) \Longrightarrow T(n) = \Theta(n^{3/2}). $$
Armed with this guess, let us now attempt to show that it indeed describes the order of growth of your recursion. On the one hand, unrolling $T(n) \geq \Theta(n) + T(n - \sqrt{n})$, we get
$$
T(n) \geq \Theta(n + (n-\sqrt{n}) + \cdots + (n-\lfloor \sqrt{n}/2 \rfloor \sqrt{n})).
$$
Here there are $\Omega(\sqrt{n})$ summands, each of which is at least $n/2$, and so $T(n) = \Omega(n^{3/2})$.
In the other direction, let us assume that $\Theta(n) \leq Cn$, and let us try to prove inductively that $T(n) \leq Kn^{3/2}$. For the inductive step to go through, we would need
$$
K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2}.
$$
The mean value theorem shows that for some $\theta_n \in [0,1]$,
$$
n^{3/2} - (n - \sqrt{n})^{3/2} = \sqrt{n} \cdot \frac{3}{2} \sqrt{n-\theta_n \sqrt{n}} \geq \sqrt{n} \cdot \frac{3}{2} \sqrt{n - \sqrt{n}},
$$
which is at least $n$ for $n \geq 4$. Therefore for $n \geq 4$, we have
$$
K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2} - Kn + Kn^{3/4} + Cn.
$$
For $n \geq 16$, we have $n^{3/4} = n \cdot n^{-1/4} \leq 16^{-1/4} n = n/2$, and so
$$
K(n-\sqrt{n})^{3/2} + Kn^{3/4} + Cn \leq Kn^{3/2} + (C-K/2)n,
$$
which is at most $Kn^{3/2}$ if $K \geq 2C$.

More generally, similar arguments should show that if $k(n) = o(n)$ then the recurrence $$T(n) = T(k(n)) + T(n-k(n)) + \Theta(n)$$ should have the solution $$T(n) = \Theta\left(\int \frac{n\,dn}{k(n)}\right). $$


Algorithm to enumerate all complete schedulings of finals tests? I'm creating an app that receives some map between finals and the respective periods during which they are held and a student's required finals. I was wondering if there was an algorithm to enumerate all complete schedulings of these finals. Concretely, I have a list of finals for a specific student and each $F_i$ has a list of periods $P_i$ that they are held. In my specific use case, there are $8$ periods.

$$
\begin{align}
F_1 &\rightarrow \{P_1, P_2, P_8\} \\
F_2 &\rightarrow \{P_4, P_7\} \\
F_3 &\rightarrow \{P_4\}
\end{align}
$$

And I want to find all assignments of periods to finals that are non-overlapping and complete, i.e. the student can attend all finals. One such assignment could be:

$$
\begin{align}
P_1 &\rightarrow F_1 \\
P_4 &\rightarrow F_3 \\
P_7 &\rightarrow F_2
\end{align}
$$

This is complete because all finals are associated to a period and the periods are non-overlapping. Another assignment could be $P_4 \rightarrow F_3, P_7 \rightarrow F_2, P_8 \rightarrow F_1$. My question is then, how could I enumerate all these assignments? I was thinking of a greedy approach whereby I choose a period starting with the finals with the fewest amount of available periods, the choosing for the next-most restricted final. But that only gives me one particular working schedule, not all  valid schedulings.

You're asking to enumerate all maximum matchings in a bipartite graph.  Unfortunately that problem is #P-complete, so there is unlikely to be any efficient algorithm that works on arbitrary size graphs.

There might be algorithms that work well enough for your situation, given the small numbers you're dealing with.  For instance, a simple approach is to use a backtracking search.  First nondeterministically choose a period for final $F_1$ (out of all possibilities).  Next choose a period for final $F_2$ (out of all possibilities, excluding the periods that have already been chosen), and so on.  If at any point there are no legal choices available (e.g., you want to choose a period for $F_i$ but all options have already been filled with a final), terminate.  Now replace the nondeterministic choices with branching over all possibilities, in a breadth-first or depth-first search, and that should provide a way to enumerate all valid schedules.

See also Counting and finding all perfect/maximum matchings in general graphs and https://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Counting_problems for references to the literature on the general problem.


Why doesn't Godel's Second Incompleteness Theorem rule out a formalizable proof of P!=NP? I'm sure there must be something wrong with the following reasoning because otherwise a lot of P vs. NP research would be curtailed but I cannot determine my error:

For any fixed integer $k>0$ define $$B_k := \{ \langle \varphi \rangle | \; \varphi \; \text{is a wff of ZF and has a proof of length} \; \leq k{|\varphi|}^k \; \}$$

Now for all $k$, the language $B_k$ is in NP since a valid proof for $\varphi$ of length $\leq k{|\varphi|}^k$ can be a NP-witness verified by an automated proof-checker in polynomial time.  Furthermore, for sufficiently large enough $k$, $B_k$ is NP-complete since SAT reduces to it: that is, for an instance $\phi$ of SAT make a corresponding wff of ZF $\varphi$ using existential quantifiers. Then a satisfying truth assignment of $\phi$ can be made into a formal proof of $\varphi$ of length polynomial in $|\varphi|$ since a truth assignment of $\phi$ is linear in $|\phi|$.

Now, if ZF is inconsistent, this means that there is a formal statement $\sigma$ such that both $\sigma$ and $\neg \sigma$ have proofs in ZF.  As is well known, any other statement $\tau$ can then be derived from the contradictory conjunction $\langle \sigma \wedge \neg \sigma \rangle$ (that is by following the path: $$\langle \sigma \wedge \neg \sigma \rangle \implies \text{both} \; \sigma \; \text{and} \; \neg \sigma \; \text{are true} \implies \langle \neg \tau \rightarrow \sigma \rangle \; \text{is true (since regardless of} \; \tau
\; \text{the implication is valid since} \; \sigma \; \text{is true)} \implies \langle \neg \sigma \rightarrow \tau \rangle \; \text{(by contraposition and double negation)} \implies \tau \; \text{ is true (by modus ponens with} \; \neg \sigma \, )$$

). Thus if ZF is inconsistent, then every statement $\varphi$ has a proof polynomial (it seems to me even just linear) in $|\varphi|$.

Let $B:=B_k$ for a sufficiently large $k$ a referred to above to allow for $B$ to be NP-complete.  Then if ZF is inconsistent, there are only finitely many $\varphi$ such that $\langle \varphi \rangle \notin B$ because the high-degree polynomial proof length allowance of $B$ is enough to cover the guaranteed short proofs of wffs of sufficient length.  This implies that $B$ is decidable in polynomial time which by its NP-completeness implies that P=NP. If we rephrase this chain of reasoning in terms of contrapositives, if P!=NP then ZF is not inconsistent (that is it is consistent).

Therefore If we have a formal proof of P!=NP then we have a formal proof of the consistency of ZF.  But by Godel's Second Incompleteness theorem, this implies that ZF is inconsistent which in turn get P=NP as outlined above (as well as the theoremhood of any negated theorem).

This is not exactly a proof that P vs. NP is independent of ZF.  It could be that ZF is consistent and that P=NP or that P!=NP can be proven through techniques not formalizable within ZF.  However, it does present another formidable barrier to resolving P vs. NP.

There seems to be a flaw as alluded to by Arno in his answer.  While the reduction $SAT \leq B$ seems innocuous enough (and is indeed a textbook exercise as pointed out by Ariel in his comment) it implicitly assumes the consistency of ZF. Otherwise, if ZF is inconsistent, since every statement of ZF would then have a proof, unsatisfiable SAT-instances would not necessarily be mapped to wffs $\varphi$ which do not have a relatively short proof.

Thus, if we assume that ZF is consistent and $ZF \vdash P \neq NP$ then although we can conclude metamathematically that $B \notin P$ (because being NP-complete, $B$ could not be in $P$ since we are assuming $P \neq NP$) we would not have a formal deduction of $ZF \vdash B \notin P$ (since this depends on $B$ being an established NP-complete set, so if we want to use the reduction above, we must assume that ZF is consistent, which cannot be formally asserted by Godel's Second Incompleteness Theorem).  Thus this argument cannot suggest any necessary implications of $ZF \vdash P \neq NP$.


Show that $\log n = o(n^\epsilon)$ I am trying to understand how to prove that a polynomial will always grow faster than a logarithm.

$\log n = o(n^\epsilon), \epsilon>0$

Intuitively, it is obvious, and plugging in a few numbers always yields true, but how can I prove this?

Maybe this can be done inductively (I would prefer this method if someone would explain it), but I attempted to prove through the use of derivatives and L'Hôpital's rule, namely:

$\lim_{n\rightarrow\infty}\frac{\log n}{n^\epsilon} = \lim_{n\rightarrow\infty}\frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}}$ = 0

Is this getting me in the right direction to prove that the upper bound of $\log n$ it is strictly less than $n^\epsilon$?

Here is a simple proof which avoids L'Hôpital's rule.

We start with the observation
$$
\log n = \int_1^n \frac{dx}{x} \leq \int_1^n dx \leq n,
$$
and so
$$
\frac{\log n}{n^2} \leq \frac{1}{n} \xrightarrow{n\to\infty} 0.
$$

Given $\epsilon > 0$, using the fact that $\lim_{n\to\infty} n^{\epsilon/2} = \infty$, we see that
$$
0 = \lim_{n\to\infty} \frac{\log (n^{\epsilon/2})}{(n^{\epsilon/2})^2} =
\lim_{n\to\infty} \frac{\frac{\epsilon}{2} \log n}{n^\epsilon}.
$$
It follows that
$$
\lim_{n\to\infty} \frac{\log n}{n^\epsilon} = 0.
$$