Scheduling / Queuing jobs with multiple different workers I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system.

Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue).

However, it's not the case that the workers can equally well do all jobs (think delivery -- delivery people who are closer to the pickup can do the job better than those that are further away). So there are two costs. First the cost to assign job X to worker Y (which varies with each worker -- for example time from worker's location to pickup point) and second the cost of doing the job (for eg. time from pickup to customer location).

It's perfectly alright to re assign jobs from one worker to another as long as they have not started processing the job (so only the jobs that are queued up can be "shuffled" amongst the workers).

What's a good away to do assignment of jobs to workers so as to reduce the cost (or in our example, time for delivery) across all the jobs? It doesn't have to perfectly optimal.

One simple solution would be as soon as a job comes in to find the worker that can finish the job fastest (it could be worker who is working on another, but his initial cost could be very little -- for eg. somebody who is delivering an item to a customer and the pickup for the next item is very close by). This would obviously not be very optimal.

Then periodically, try and re assign the queued up orders by swapping jobs between pairs of workers that would result in faster delivery (or rather least waiting time) for all of the jobs. But how good is this?

The simplest option is a single queue that workers can scan for a good job for them. In other words job distribution is done when a worker just finished his previous job and needs a new one.

Using only this will create suboptimal distribution when the queue is nearly empty due to the first come first serve.

Swapping jobs between workers is very difficult to implement in a way where the overhead of the swap does not exceed the work of the actual job. One way could be to periodically in the job have it be queued back partially completed but only if the current worker is suboptimal for that task and a better job for it is available in the queue.


CPU scheduling Decisions Operating System - CPU scheduling Decisions

The question above talks about why CPU scheduling does not take place when ready to running.
But I wonder why CPU scheduling does not take place when new to ready. I think it is similar to the process of waiting to ready. They both add processes to ready without changing processes that are running.

When you put a new process in the ready queue, you are just adding the process, not changing anything to running as a result. With a non-preemptive scheduler this is also the case for waiting to ready. But, when you have a preemptive scheduler, tasks that come from waiting to ready get a higher priority than newly running tasks, so that "scheduler decision-making" is determining the priority of this newly ready task in the queue. It looks like they get a higher priority than new tasks because they've already been delayed enough waiting for IO.


BST - Sufficient condition for connecting a node to a parent Let's assume that we have a binary search tree with node Y that hasn't a right child and for whom a successor exists in the tree.

I want to prove that if I insert a node X into the tree and node X is greater than node Y and less than the successor of node Y then X will be added as the right child of Y.

Intuitively, this makes sense to me but my question is how do we prove this formally?

Due to the lack of definitions in the question, let us pick up a couple of definitions that are needed for a formal proof.

  A binary rooted tree is a BST if its nodes are visited in its natural order by the inorder traversal. Inserting a new node into a BST means adding a new edge so that the new node becomes the child of some old node and the tree remains a BST.

Let us prove a useful lemma.
(Uniqueness of insertion into BST) Let $T$ be a BST. Let node $X$ be a new node that is not equal to any node in $T$. Then there exists a unique way to insert $X$ into $T$ so that $T$ remains a BST with the same root, where the insertion must add one edge to $T$ (without modifying the existing edges).

Proof by mathematical induction on $n$, the number of vertices in $T$.

The base case when $n=1$. If the new node is less than the root node, it has to inserted as the left child of the root node; otherwise, it has to be inserted as the right child of the root node.
Assume the lemma is true for BST whose number of vertices is smaller than $n$. Suppose $T$ is a BST of $n$ vertices with node $R$ as its root node. Suppose $X$ is a new node that is not equal to any node of $T$. There are two cases.

$X$ is less than $R$. If $R$ has no left child, then $X$ has to be inserted as the left child of $R$. Otherwise, $R$'s left subtree is a BST (because of the recursive nature of the inorder traversal). $T$ has to be inserted into $R$'s left subtree. By induction hypothesis, there exists a unique way to insert $X$ into $R$'s left subtree.
$X$ is greater than $R$. Just switch every "left" to "right" in the above case.

Proof is done. As you have indicated, this is intuitively so obvious!

Now let us prove a proposition that is slightly more general than what you want to prove.
(Right child insertion) Let $T$ be a BST with node $Y$ that does not have a right child. Let node $X$ be a new node larger than $Y$ such that any node that is larger than $Y$, if exists, must be larger than $X$. Then node $X$, if inserted, will be inserted as the right child of $Y$.

Proof. Let $T'$ be the binary tree obtained from $T$ when $X$ is added as the right child of $Y$. Compare the inorder traversal on $T$ and that on $T'$. By the definition of inorder traversal, the difference between them can happen only when each traverses the subtree rooted at $Y$.

Both traversals will visit the same left subtree of $Y$ first. Then both will visit $Y$.  When it is time to visit the right subtree of $Y$, the former traversal has nothing to do since $Y$ has no right child in $T$ while the latter traversal will visit one more node, $X$ since $Y$ has $X$ as its right child in $T'$.

Since the nodes in $T$ is visited in its natural order by the former traversal, the nodes in $T'$ is visited in its natural order by the latter traversal as $X$ is the very next node that is larger than $Y$. By definition, $T'$ is a BST. According to the above uniqueness lemma, $X$ must be inserted as the right child of $Y$. Q.E.D.


What is the right term/theory for prediction of Binary Variables based upon their continuous value? I am working with a linear programming problem in which we have around 3500 binary variables.

Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best bound. In the solution, we get around 85-90 binaries which have value of 1 and others are zero. The objective value is around 20 to 30 million. I have created an algorithm in which I am predicting (fixing their values) 35 binaries (with the value of 1) one by one and letting the remaining ones solved through the Cplex. This has reduced the time to get the same objective to around 24 hours (the best bound is slightly compromised). I have tested this approach with the other (same type of problems) and it worked with them also. I call this approach as "Probabilistic Prediction", but I don't know what is the standard term for it in mathematics?

Below is the pseudocode:

Let y=ContinousObjective(AllBinariesSet);
WriteValuesOfTheContinousSolution();
Let count=0;
Let processedbinaries= EmptySet; //Binaries processed per iteration.
while (count < 35 ) {
    Let maxBinary =AllBinariesSet.ExceptWith(processedbinaries).Max();//Having Maximum Value between 0 & 1 (usually lesser than 0.6)
    processedbinaries.Add(maxBinary);
    maxBinary=1;
    Let z = y;
    y = ContinousObjective(AllBinariesSet);
    if (z > y + 50000) {
        //Reset maxBinary
        maxBinary.LowerBound = 0;
        maxBinary.UpperBound = 1;
        y = z;
    } else {
        WriteValuesOfTheContinousSolution();
        count=count+1;
    }
}

Explanation of the pseudo code:
Step 1: Initialize an empty list of processed binaries.
Step 2: Run the continuous solution and get the binary which has maximum value and not the part of processed binaries. Add that binary to processed binaries list.
Step 3: Fix the value of that binary to 1 and run the continuous solution again.
Step 4: If the objective is not around 99.75% of previous objective then revert to Step 1 and add the fixed binary to the list of ignored binaries.
Step 5: Repeat from Step 1 to Step 3 until we have fixed 35 binaries in the LP.
Step 6: Start the integer optimization run (mipopt in cplex) of the fixed LP.

So basically we are predicting around 40% of the binaries (with the value of 1) and at every iteration we are ensuring that the continuous objective is not reduced below 0.25% (approx. 50000) of its actual value before the previous prediction.
According to me, it's working because the solution matrix is very sparse and there are too many good solutions.

I would say that this approach falls under the umbrella of iterative rounding. I believe that the seminal paper regarding this kind of strategy is [1]. The heuristic outlined here differs in signifcant ways from the algorithm described in Jain's paper but I think the basic idea is in the same vein.

Jain, K. (2001). A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1), 39-60.


Recursion: base case vs. small version I'm reviewing the definition of recursion and in my notes are two questions about a recursive problem. One question asks about the base case, the other one about the small version of the problem, I always get confused about which is which... can you help me to find a way to better understand these concepts?

The examples in the exercise are:

a function that determines if there is a "x" element in an array
a function that determines if the string is palindrome or not

for both:

Find the base case
Find the small version of the problem
(Implement the recursive solution)

When you use recursion to solve a problem, you typically partition your input into one or more smaller instances (and possibly a part that you don't process further). Those smaller instances are what your exercise calls the small version.

Upon recursing, your inputs get smaller and smaller until it is no longer possible (or sensible) to further split them up. The inputs that are left to be solved directly are called the base case.


Exponential time local search heuristics for Weighted MAX-CUT-Flip I have read multiple times [Theorem 5.15, 1][End of page 2, 2] that local search heuristics for $\textsf{Weighted Max-Cut}$ with $\textsf{Flip}$ neighbourhood takes an exponential time in some cases.

In particular, the problem is as follows. Given a partition $(V1,V2)$, its neighbours are partitions which can be obtained by moving one vertex from $V1$ to $V2$, or from $V2$ to $V1$. Such neighbourhood is polynomial in size. At each step algorithm chooses the neighbour with highest value strictly greater than that of the current partition (o/w, it is locally optimal and so the algorithm terminates).

I am asking for a weighted graph and an initial partition of the vertices such that the above local heuristics would need exponential number of iterations to get to a local optimum.

I have not seen a single concrete example.

References

[1] Alejandro A. Schäffer and Mihalis Yannakakis. Simple local search problems that are hard to
solve. SIAM J. Comput., 20(1):56–87, February 1991.

[2] Lecture notes: https://courses.engr.illinois.edu/cs598csc/sp2011/lectures/lecture_12.pdf

Check out the paper: On the Power of Nodes of Degree Four in the
Local Max-Cut Problem - Burkhard Monien and Tobias Tscheuschner.

In the paper they take a sub-graph of size 5 constructed from two types of vertices (they call them type-1 vertices and type-3 vertices). Then they build a graph from n sub-graphs concatenated, and show a specific initial start of the max-cut algorithm. In this initial start, there would be an exponential number of flips until the local optima would be obtained.


Decide if a string is in a language without simulating the automata accepting the languge Is it possible for a Turing machine with input of a DFA that accepts a finite language and a string to decide whether the string is in the language without "fully simulating" the DFA on the string?

More formally, Is there a TM $M$ with a constant $C_M$ that can decide $L$, where for every input it halts at most $C_M$ steps after reading $w$'s last bit where $L$ is given by:

$L=\{\langle D,w\rangle \mid D\text{ is a DFA that accepts a finite language and $D$ accepts $w$}\}$?

I was thinking it is not possible, though I am not sure because maybe one can deduce from the encoding of the DFA without simulating the DFA what is the language.

I can't see how this can be done but not sure how to prove it can't be done.

You ask two questions.

For your first question, about whether a TM can do this without fully simulating the DFA:

The problem statement is not well-defined.  Given a TM, you can't tell whether it "fully simulates the DFA on a string" or not.  (That's undecidable.)  There are all sorts of ways that a TM might effectively "simulate", but in an obfuscated way that makes it hard for you to realize that's what it is effectively doing.

Your language $L$ is certainly decidable.  It has the form $L=L_1 \cap L_2$ where $L_1$ and $L_2$ are both decidable, hence $L$ is decidable too.

For the second question, about whether a TM can do this using at most a constant number of steps after reading the last bit:

Sure.  That's always possible, for any decidable language.  After reading all but the last bit, the TM can decide what it will do if the last bit is 0 and what it will do if the last bit is 1 (doing as much computation as necessary to handle both cases).  Then, when it reads the last bit, it will immediately be able to produce the correct output, using only a constant number of steps.  This doesn't really have anything to do with whether the TM is or isn't simulating the DFA, though.


Number of words of a given length in a regular language Is there an algebraic characterization of the number of words of a given length in a regular language?

Wikipedia states a result somewhat imprecisely:

  For any regular language $L$ there exist constants $\lambda_1,\,\ldots,\,\lambda_k$ and polynomials $p_1(x),\,\ldots,\,p_k(x)$
  such that for every $n$ the number $s_L(n)$ of words of length $n$ in $L$ satisfies the equation
  $s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n$.

It's not stated what space the $\lambda$'s live in ($\mathbb{C}$, I presume) and whether the function is required to have nonnegative integer values over all of $\mathbb{N}$. I would like a precise statement, and a sketch or reference for the proof.

Bonus question: is the converse true, i.e. given a function of this form, is there always a regular language whose number of words per length is equal to this function?

 This question generalizes Number of words in the regular language $(00)^*$

Given a regular language $L$, consider some DFA accepting $L$, let $A$ be its transfer matrix ($A_{ij}$ is the number of edges leading from state $i$ to state $j$), let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then
$$ s_L(n) = x^T A^n y. $$

Jordan's theorem states that over the complex numbers, $A$ is similar to a matrix with blocks of one of the forms
$$ \begin{pmatrix} \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix}, \ldots $$
If $\lambda \neq 0$, then the $n$th powers of these blocks are
$$ \begin{pmatrix} \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} \\ 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2} \lambda^{n-2} \\ 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \binom{n}{3}\lambda^{n-3} \\ 0 & \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} \\ 0 & 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & 0 & \lambda^n \end{pmatrix}, \ldots $$
Here's how we got to these formulas: write the block as $B = \lambda + N$. Successive powers of $N$ are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that $\lambda$ commutes with $N$),
$$ B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots. $$
When $\lambda = 0$, the block is nilpotent, and we get the following matrices (the notation $[n = k]$ is $1$ if $n=k$ and $0$ otherwise):
$$ \begin{pmatrix} [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] \\ 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] \\ 0 & [n=0] & [n=1] \\ 0 & 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] & [n=3] \\ 0 & [n=0] & [n=1] & [n=2] \\ 0 & 0 & [n=0] & [n=1] \\ 0 & 0 & 0 & [n=0] \end{pmatrix} $$

Summarizing, every entry in $A^n$ is either of the form $\binom{n}{k} \lambda^{n-k}$ or of the form $[n=k]$, and we deduce that
$$ s_L(n) = \sum_i p_i(n) \lambda_i^n + \sum_j c_j [n=j], $$
for some complex $\lambda_i,c_j$ and complex polynomials $p_i$. In particular, for large enough $n$,
$$ s_L(n) = \sum_i p_i(n) \lambda_i^n. $$
This is the precise statement of the result.

We can go on and obtain asymptotic information about $s_L(n)$, but this is surprisingly non-trivial. If there is a unique $\lambda_i$ of largest magnitude, say $\lambda_1$, then
$$ s_L(n) = p_1(n) \lambda_1^n (1 + o(1)). $$
Things get more complicated when there are several $\lambda$s of largest magnitude. It so happens that their angle must be rational (i.e. up to magnitude, they are roots of unity). If the LCM of the denominators is $d$, then the asymptotics of $s_L$ will very according to the remainder of $n$ modulo $d$. For some of these remainders, all $\lambda$s of largest magnitude cancel, and then the asymptotics "drops", and we have to iterate this procedure. The interested reader can check the details in Flajolet and Sedgewick's Analytic Combinatorics, Theorem V.3. They prove that for some $d$, integers $p_0,\ldots,p_{d-1}$ and reals $\lambda_0,\ldots,\lambda_{d-1}$,
$$ s_L(n) = n^{p_{n\pmod{d}}} \lambda_{n\pmod{d}}^n (1 + o(1)). $$


For a flow network, is it possible to show that there always exists a maximum flow which would assign integer values to all the edges? Is it possible to prove that for a flow network, there always exists a maximum flow which assigns an integer value to every edge?

If edges have real valued capacities, there may not exist a maximum flow which assigns an integer value to every edge. For example consider a single edged $s-t$ network with $c(s,t)=0.1$ where $c$ is capacity function. However if edges have integer valued capacity, there exists a maximum flow which assigns integer value to every edge because in each iteration of ford-fulkerson algorithm, each edge in residual graph is assigned an integer value. So the result is an integer.


Can problems of class P be transformed into SAT formula? I know that NP problems can be transformed into SAT (due to this fact, SAT is considered to be a NP Complete problem). I am not sure if P problems can too be transformed into SAT.


What is the worst case time complexity for intersection tests with BVHs? This question is in the context of computer graphics. We have a scene with $n$ triangles and a ray. We want to find if the ray intersects any triangle and get the closest one.

There is a datastructure called Bounding Volume Hierachy (BVH) which groups triangles and fits a bounding volume (e.g. AABBs - axis-aligned bounding boxes) around it. The idea is that if the ray does not intersect the bounding volume, it does not intersect any of the contained triangles / other bounding volumes.

Now assume a BVH with AABB bounding volumes and a scene of $n$ triangles is given. You can spend arbitrary much time for constructing the BVH, but you don't know which rays will come.

What is the worst case time complexity for intersecting a ray with such a BVH? What would a worst case scene look like?

edit: What is the worst case time complexity if triangles may not cross each other?

I thought of something like the following, where the bounding volumes intersect with themselves a lot (think of a recursive definition where the scene is continued to the center).

Worst time complexity is $O(n)$: If all triangles are identical the bounding boxes are the same as well and every triangle needs to be intersected.

Btw.: The triangles do not need to be identical for the bounding boxes to be the same. The result is still $O(n)$ in that case.


Is traversing an unconnected graph possible? I have been assigned a fun project: design and implement a program that maintains the data of a simple social network. Each person in the network should have a profile that contains his name, current status, and a friends list.

I think it is clear that the project calls for the use of the ADT graph. Each vertex represents a person in the network and an edge between vertices a friendship. Now, the graph may not be connected because some members do not have any friends in the network. With that in mind, consider this feature that must be implemented:

•The network must have a feature that computes the “emergency phone chain," make sure that each member in the network is contacted, and only by one person. Any of the people in the network may initiate the first call. Utilize a depth-first graph traversal algorithm.

Now, what I think my professor is suggesting is merely a full traversal of the graph. How is that possible for an unconnected graph? Any suggestions?

(btw, the wording above is somewhat unclear - does the professor mean that everyone in the network is contact by the same one person? Thoughts? I would ask her, but she is unavailable until next week.)

That's a question only your professor can answer. There are at least two possible solutions:

Each "chain" involves a single connected component.
Some links will be among non-friends.

In the latter case, you would like to minimize the number of unfriendly links. If there are $c$ connected components, then you only need $c-1$ of these.


How do I use induction to show that the language of a grammar is contained in a given set? Given that I have the grammar

$\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$,

how am I supposed to prove that

$\qquad\displaystyle S(G1) ⊆ \{a^{n+1} b^{n+1} c^{m+1} d^{m+1} \mid n, m ≥ 0\}$

by using Induction?

When proving something about a language generated by a grammar, your induction should be on the number of derivation steps.

Here, the induction hypothesis should be:
$S=>^i a^kAb^kc^jBd^j $ for $i,j < i, A \in \{ X, \epsilon\}, B \in \{ Y, \epsilon\}$ .

base: for $i=1$ we have that $S=>^1 XY = a^0Xb^0c^0Yd^0$. and the hypothesis holds.

step: Assume $S=>^i a^kXb^kc^jYd^j => a^{k'}Xb^{k'}c^{j'}Yd^{j'}$. We have 4 case for the last derivation step.

if it was $X \rightarrow aXb$, then $k' = k+1$ and $S=>^{i+1} a^{k+1}Xb^{k+1}c^jYd^j$
Similar case if it was $X \rightarrow ab$, and then $S=>^{i+1} a^{k+1}b^{k+1}c^jYd^j$
If last derivation was $Y \rightarrow cYd$, then  $j' = j+1$ and $S=>^{i+1} a^{k}Xb^{k}c^{j+1}Yd^{j+1}$
Similar case if it was $Y \rightarrow cd$, and then $S=>^{i+1} a^{k}Xb^{k}c^{j+1}d^{j+1}$

Since $L(G1)$ contains terminal words, the last derivations must be $X \rightarrow ab$ or $Y \rightarrow cd$.

By that we proved that $L(G1) \subseteq \{ a^nb^nc^md^m | n,m > 0\}$


Recognizing loops in computation on LBA In the case of LBAs (Linear Bounded Automaton), in writing a decider for the language

$\qquad A = \{ \langle M,w\rangle \mid M\ \mathrm{LBA}, w \in \mathcal{L}(M) \}$

we reject the input after a specific number (number of possible different configurations) of computation steps.
We say that the machine must be looping after this many steps.
Why don't we just check in every step to see if there is a loop (repetition of the same configuration) and if it is the case then just reject the input?

If I understand the question correctly, you are asking why are we bounding the number of configurations, rather than checking for a repeating configuration?

Well, clearly these are equivalent in the sense that in both ways you will detect a repeating configuration.

In the first method, we use the pigeonhole principle, and we say that if we passed a certain number of configurations, then there must be a repetition, since in an LBA the number of configurations is bounded (after fixing the input). In order to detect this, we must keep a counter of the number of configurations we passed. The advantage of this method is that keeping the counter is simple (it takes linear space). The disadvantage is that the loop may have occurred early in the run, and we will only detect it late (after an exponential number of steps).

In the second method, we need to track the configurations we have seen so far, and compare every new configuration to all the configurations we have already seen. The advantage is clear- we will detect the loop immediately when it is caused. But the disadvantage is huge - we need to track all the configurations - this may take exponential space, and in every step we need to compare all the configurations to the current one.

Essentially, the first method solves $A$ in PSPACE, whereas the second solves it in EXPSPACE, so we usually take the first.


Closure of regular languages under deleting a 1 from each even run of 1s Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using closure
  properties for the class of regular sets.

Current Approach:

For the first part, using a machine construction, I was thinking that you take a simple FA that accepts only strings with an odd number of 1's (let's call this language $S$). This would be the simplest way of forcing strings in $R$ to have blocks of 1 of odd length. Then I would have some sort of $\epsilon/1$ transition to the original machines states where I would see if a string $x$ that is in the language $S$ would also be in $R$ if I were to add a 1 to any odd block of 1s.

I am unsure of how to describe that using the 5-tuple, $M = (Q, \{0,1\}, \delta, q_0, F)$, or if my methodology is correct. Any advice on where I should go and how I might prove closure in the two different ways is welcome.

Below you can find solutions for the similar problem in which we want to delete a single 1 from each odd length run of 1s. I'll let you adapt them to your question.

First, let me explain how to solve it using closure properties. We start with your language $R$. We then apply a regular substitution that optionally "marks" every 1, i.e. changes it into $\mathbf 1$. We intersect the resulting language with $0^*((11)^*(\mathbf{1}+\epsilon)0^+)^*((11)^*(\mathbf1+\epsilon)+\epsilon)$ – this has the effect of marking the final 1 out of each odd run. Finally, we apply a homomorphism that deletes all marked 1s.

Second, let me explain how to explicitly construct an NFA for the new language given an NFA for $R$. Let the NFA for $R$ be $\langle Q, \{0,1\}, \delta, q_0, F \rangle$. The new states will be $(Q \times \{0,1\}) \cup \{q_f\}$, and the new initial state will be $\langle q_0, 0 \rangle$; the second entry is the parity of the current run of 1s. The new accepting states are $(F \times \{0\}) \cup \{q_f\}$ (note that in the new language, all runs of 1s must have even length). It remains to define the new transition function:

If there is a transition $q_1 \stackrel 0 \to q_2$, then we add a transition $\langle q_1, 0 \rangle \stackrel 0 \to \langle q_2, 0 \rangle$; that is, we allow the transition only if the parity of the current run of 1s is even.
If there is a transition $q_1 \stackrel 1 \to q_2$, then we add the following transitions:

$\langle q_1, 0 \rangle \stackrel 1 \to \langle q_2, 1 \rangle$ and $\langle q_1, 1 \rangle \stackrel 1 \to \langle q_2, 0 \rangle$; these just maintain the parity of the length of the run.
If $q_2 \in F$: $\langle q_1, 0 \rangle \stackrel \epsilon \to q_f$. This handles odd runs of 1s at the very end of input.

If there are transitions $q_1 \stackrel 1 \to q_2 \stackrel 0 \to q_3$, then we add the transition $\langle q_1, 0 \rangle \stackrel 0 \to \langle q_3, 0 \rangle$. This corresponds to deleting a 1 from the end of an odd run.


Why aren't numbers stored this way? I read that the further you get from 0, the less precision, due the way they are stored.

So why aren't numbers stored like this:
$32$ bits for representing a value between $-2^{31}$ and $2^{31}-1$ before the decimal point and another $32$ bits for representing the precision. $\frac{1}{2^{32}} = 0,00000000023$, which would be a fairly precise interval.

With this type of storage there would be no precision loss at high values.

In a floating point, by definition, the point floats. What you're proposing is fixed point (which is occasionally used in practice).

A normal IEEE 754 64-bit double precision can store values in the range from $-10^{308}$ to $10^{308}$. This is a much larger range than your system can store given 64 bits (you would need nearly 800 bits to achieve the same).

The precision loss is often acceptable. When you are dealing with a very large value (like $10^{308}$) what comes at the $10^{\textrm{th}}$ place after the decimal point has no significant impact on the outcome of your calculation. When you are dealing with a very small value (like $10^{-20}$), what comes at the $10^{\textrm{th}}$ place after the decimal point has a huge impact on your calculation.

Using floating point thus makes a lot of sense: you get a level of precision that is appropriate for the range of values you're dealing with, and it can represent a very wide range of values in limited space.


Binary code with constraint Suppose I have an alphabet of n symbols. I can efficiently encode them with $\lceil \log_2n\rceil$-bits strings. For instance if n=8:
A: 0 0 0
B: 0 0 1
C: 0 1 0
D: 0 1 1
E: 1 0 0
F: 1 0 1
G: 1 1 0
H: 1 1 1

Now I have the additional constraint that each column must contain at most p bits set to 1. For instance for p=2 (and n=8), a possible solution is:
A: 0 0 0 0 0
B: 0 0 0 0 1
C: 0 0 1 0 0
D: 0 0 1 1 0
E: 0 1 0 0 0
F: 0 1 0 1 0
G: 1 0 0 0 0
H: 1 0 0 0 1

Given n and p, does an algorithm exist to find an optimal encoding (shortest length) ? (and can it be proved that it computes an optimal solution?)

EDIT

Two approaches have been proposed so far to estimate a lower bound on the number of bits $m$. The goal of this section is to provide an analysis and a comparaison of the two answers, in order to explain the choice for the best answer.

Yuval's approach is based on entropy and provides a very nice lower bound: $\frac{logn}{h(p/n)}$ where $h(x) = xlogx + (1-x)log(x)$.

Alex's approach is based on combinatorics. If we develop his reasonning a bit more, it is also possible to compute a very good lower bound:

Given $m$ the number of bits $\geq\lceil log_2(n)\rceil$, there exists a unique $k$ such that
$$ 1+\binom{m}{1} + ... +\binom{m}{k} \lt n \leq 1+\binom{m}{1} + ... + \binom{m}{k}+\binom{m}{k+1}$$
One can convince himself that an optimal solution will use the codeword with all bits low, then the codewords with 1 bit high, 2 bits high, ..., k bits high. For the $n-1-\binom{m}{1}-...-\binom{m}{k}$ remaining symbols to encode, it is not clear at all which codewords it is optimal to use but, for sure the weights $w_i$ of each column will be bigger than they would be if we could use only codewords with $k+1$ bits high and have $|w_i - w_j| \leq 1$ for all $i, j$.
Therefore one can lower bound $p=max(w_i)$ with $$p_m = 0 + 1 + \binom{m-1}{2} +... + \binom{m-1}{k-1} + \lceil \frac{(n-1-\binom{m}{1}-...-\binom{m}{k}) (k+1)}{m} \rceil$$

Now, given $n$ and $p$, try to estimate $m$. We know that $p_m \leq p$ so if $p \lt p_{m'}$, then $m' \lt m$. This gives the lower bound for $m$. First compute the $p_m$ then find the biggest $m'$ such that $p \lt p_{m'}$

This is what we obtain if we plot, for $n=1000$, the two lower bounds together, the lower bound based on entropy in green, the one based on the combinatorics reasonning above in blue, we get:

Both look very similar. However if we plot the difference between the two lower bounds, it is clear that the lower bound based on combinatorics reasonning is better overall, especially for small values of $p$.

I believe that the problem comes from the fact that the inequality $H(X) \leq \sum H(X_i)$ is weaker when $p$ gets smaller, because the individual coordinates become correlated with small $p$. However this is still a very good lower bound when $p=\Omega(n)$.

Here is the script (python3) that was used to compute the lower bounds:

from scipy.misc import comb
from math import log, ceil, floor
from matplotlib.pyplot import plot, show, legend, xlabel, ylabel

# compute p_m
def lowerp(n, m):
  acc = 1
  k = 0
  while acc + comb(m, k+1) < n:
    acc+=comb(m, k+1)
    k+=1

  pm = 0
  for i in range(k):
    pm += comb(m-1, i)

  return pm + ceil((n-acc)*(k+1)/m)

if __name__ == '__main__':
  n = 100

  # compute lower bound based on combinatorics
  pm = [lowerp(n, m) for m in range(ceil(log(n)/log(2)), n)]
  mp  = []
  p = 1
  i = len(pm) - 1
  while i>= 0:
    while i>=0 and pm[i] <= p: i-=1
    mp.append(i+ceil(log(n)/log(2)))
    p+=1
  plot(range(1, p), mp)

  # compute lower bound based on entropy
  lb = [ceil(log(n)/(p/n*log(n/p)+(n-p)/n*log(n/(n-p)))) for p in range(1,p)]
  plot(range(1, p), lb)

  xlabel('p')
  ylabel('m')
  show()

  # plot diff
  plot(range(1, p), [a-b for a, b in zip(mp, lb)])
  xlabel('p')
  ylabel('m')
  show()

Here is a lower bound and an asymptotically matching construction, at least for some ranges of the parameters. Denote by $m$ the number of columns, and suppose for simplicity that $p \leq n/2$.

We start with a lower bound on $m$. Let $X$ be the encoding of symbol chosen uniformly at random. Let $X_1,\ldots,X_m$ be the individual coordinates, and let $w_i \leq p$ be the weight of the $i$th column. Then
$$
\log n = H(X) \leq \sum_{i=1}^m H(X_i) = \sum_{i=1}^m h(w_i/n) \leq m h(p/n).
$$
Therefore
$$
m \geq \frac{\log n}{h(p/n)}.
$$
Here $H$ is the entropy of a random variable $H(X) = -\sum_x \Pr[X=x] \log \Pr[X=x]$ and $h$ is the entropy function $h(x) = -x\log x-(1-x)\log(1-x)$. (You can use whatever base for the logarithm you want.)

The asymptotically matching construction, that should work for $p = \Omega(n)$, chooses $m$ a bit larger than this lower bound, and chooses a random encoding scheme, each bit being set to $1$ with some probability $q/n$ which is a bit smaller than $p/n$. Choosing the parameters correctly, we should get that this results in a legal encoding (all codewords are different and all column weights are at most $p$) with positive probability.


Computational power of deterministic versus nondeterministic min-heap automata This is a follow-up question of this one.

In a previous question about exotic state machines, Alex ten Brink and Raphael addressed the computational capabilities of a peculiar kind of state machine: min-heap automata. They were able to show that the set of languages accepted by such machines ($HAL$) is neither a subset nor a superset of the set of context-free languages. Given the successful resolution of and apparent interest in that question, I proceed to ask several follow-up questions.

It is known that deterministic and nondeterministic finite automata have equivalent computational capabilities, as do deterministic and nondeterministic Turing machines. However, the computational capabilities of deterministic push-down automata are less than those of nondeterministic push-down automata.

  Are the computational capabilities of deterministic min-heap automata less than, or are they equal to, those of nondeterministic min-heap automata?

It seems that for this model, non-deterministic machines are not equivalent to deterministic ones, for basically the same reason that deterministic PDAs are not equivalent to non-deterministic ones.

Consider the language
$$L =\\{ x\$y \mid |x|=|y| \wedge x\ne y\\}$$
(where $\$$ is a special sign not contained in $x$ and $y$).

I claim that a non-deterministic machine $N$-$HAL$ can decide this language: It performs the same as the PDA for $L$. The standard PDA solution uses the stack only to count offsets: it nondeterministically guesses an offset $i$, remembers the value of $x_i$ (adding a symbol to the stack at each step), then the PDA ignores the input until it find the $\$$, and then it pops symbols out of the stack until it is empty. At this stage we are exactly at $y_i$ and he PDA can check if $x_i \ne y_i$. (if anything goes wrong in the middle, the PDA "dies").
Since the stack alphabet is unary, it can be simulated with a min-heap machine.
Actually: any $L$ that is is accepted by a PDA with a unary alphabet can be accepted by a min-heap machine. (I'm ignoring, maybe, another special sign added to identify an empty stack, but an equivalent sign can be added to the heap)

For the other direction, I don't have the formal proof, but here are my thoughts:

I claim that a deterministic machine $D$-$HAL$ is incapable of deciding this language. Intuitively, the content of the heap can not be correlated with $x$ (otherwise, permute $x$. the content of the heap remains the same..). This suggests that only thing that matters is the number of elements in the heap, but then, if $D$-$HAL$ can decide $L$, so can a deterministic-$PDA$.

Edit: more details about the "permute $x$" claim. Assuming Raphael's conjecture
there exist $x_1$ and $x_2$ that after reading them, the content of the heap is the same.
Then consider the words $x_1\$x_1$ and $x_2\$x_1$. The content of the heap is the same when the HAL gets to the dollar sign, thus it must either accept both or reject both. contradiction.

anyone sees an immediate proof for the conjecture?


What exactly is the LL(k) grammar condition? I have a bit of trouble understanding the definition of LL(k) grammars.

Here it's defined as:

  for every pair of production rules
  $A\rightarrow
α$
   and
  $A \rightarrow
β$
   the following condition holds.
   $\text{FIRST}_k$
  (
   $\text{α FOLLOW}_k$
  (A)) $\cap$
   $\text{FIRST}_k$
  (
   $\text{β FOLLOW}_k$
  (A))
  $=\emptyset$

What does this mean concretely? What is the subscript $_k$?
Why is it for a "pair of production rules"?

It's actually a definition of a strong LL(k) grammar.

First of all, see Raphael's comment.

In short, the condition means that while parsing $A$ you can choose the next production rule in a deterministic manner using only the next $k$ lookahead symbols.

An important thing is you don't need any context for that decision, i.e. you don't need to remember the previous steps in the left-most derivation that led you to the non-terminal $A$ to parse $A$ itself.

By the way, every LL(1) grammar is strong, but there are non-strong LL(k) grammars, $k > 1$.

If you need a more detailed explanation, then I think it's better to use a book for that (it's too long for an answer here). I'd suggest "Parsing Techniques - A Practical Guide" by Dick Grune et al.


Is there a tactic to help resolving existential quantifiers in Coq? I am working on Software Foundations Volume 1 on my own it is its 2019 version by the way, and I have reached to its lesson Inductively Defined Propositions, and there, for almost one month I have been stuck on an exercise re_not_empty expressed like this in Coq (the exercise itself begins at Fixpoint):
Inductive reg_exp {T : Type} : Type :=
  | EmptySet
  | EmptyStr
  | Char (t : T)
  | App (r1 r2 : reg_exp)
  | Union (r1 r2 : reg_exp)
  | Star (r : reg_exp).

Inductive exp_match {T} : list T → reg_exp → Prop :=
  | MEmpty : exp_match [] EmptyStr
  | MChar x : exp_match [x] (Char x)
  | MApp s1 re1 s2 re2 (H1 : exp_match s1 re1) (H2 : exp_match s2 re2) :
      exp_match (s1 ++ s2) (App re1 re2)
  | MUnionL s1 re1 re2 (H1 : exp_match s1 re1) :
      exp_match s1 (Union re1 re2)
  | MUnionR re1 s2 re2 (H2 : exp_match s2 re2) :
      exp_match s2 (Union re1 re2)
  | MStar0 re : exp_match [] (Star re)
  | MStarApp s1 s2 re (H1 : exp_match s1 re) (H2 : exp_match s2 (Star re)) :
      exp_match (s1 ++ s2) (Star re).

Notation "s =~ re" := (exp_match s re) (at level 80).

Fixpoint re_not_empty {T : Type} (re : @reg_exp T) : bool Admitted.

Lemma re_not_empty_correct : ∀T (re : @reg_exp T),
  (∃s, s =~ re) ↔ re_not_empty re = true.
Proof. Admitted.

Although I am obliged not to tell anything about solutions but to get help I have to say at least about Fixpoint that is defined like this:
Fixpoint re_not_empty {T : Type} (re : @reg_exp T) : bool :=
  match re with
  | EmptySet => false
  | EmptyStr | Char _ => true
  | App re1 re2 => re_not_empty re1 && re_not_empty re2
  | Union re1 re2 => re_not_empty re1 || re_not_empty re2
  | Star re => re_not_empty re
  end.

I could prove the backward case easily. For the forward case I stuck at Star re there is a ∃ s, s =~ Star re in the evidences or context and a ∃ s', s' =~ re in the goals. The most probable thing to pass it is using inversion on that evidence but how to tell Coq with destruct to put s1 ++ s2 instead of s and put the results in the context instead of in the goals?

I was similarly stuck on this problem. I believe your Fixpoint for Star re should just be true. In regular expressions, the empty string is always accepted under star.


What is the difference between symbol and enumerated datatypes? I wonder what differences and relations are between symbol and enumerated types?

A symbol is a primitive datatype whose instances have a unique human-readable form
an enumerated type is a data type consisting of a set of named values called elements, members or enumerators of the type.

Since a data type is a set of values, what exactly is the data type "symbol",  and the data type "enumerated"?
It seems to me that a value in an enumerated type is just a symbol.
But the first quote says that "A symbol" is a data type, which contradicts with my thought that a symbol is a value.

This is again much a question about terminology, without only history
as a possible authority to determine "what is right".

These two kinds of values are very similar in the sense that they
should be considered as atomic entities, distinguished only by their
representation as a string of character over some alphabet, possibly
with some minor constraints regarding the use of some characters (e.g.,
should start with alphabetic character,).  These constraint are really
immaterial, since what matters mainly is whether two symbols are the
same or are different.

A major difference is that the set of symbol is potentially infinite
(like the set of strings meeting the constraints) though actually
limited by the implementation of the language, like anything else.

An enumerated type, is defined by giving explicitly an enumeration of
the values of that type, which also have a representation as a string
of characters. Since the enumeration is explicit, there is only a
finite number of values in an enumeration type. Languages often consider that
these values are ordered in by the order of the definition. Thus these enumerated
value can be compared for equality, of for order.

Symbols can only be compared for equality. Sometimes, an arbitrary (alphabetical ?) ordering may be provided as it may help for some algorithms. But there is no semantics attached to it.

In a language, You usually have only one type for symbols. However, it
is easy to make more when you have data abstraction available. Symbols
are usually implemented like identifier tables in interpreted
languages, and can actually stand for identifiers in meta-circular
interpreters.

Enumerated types are defined by the programmer, and he may define
several such types.  One source of problems is that he may (at least in some languages)
use the same name for different enumerated values, not in the same
type of course, but in different enumerated types.

type month = (January, February, March, April, ...)
type girl = (Mary, April, Nancy, Ann, ...)
type city = (London, Paris, Nancy, Roma, ...)
type writer = (Hemingway, London, ...)

Of course, I am abbreviating illegally, since the list must be
completely enumerated.

But if I use the identifier Nancy in the program, I may not know
which is meant, the girl or the city. This can be resolved by various
means (scoping, casting, etc.)

You do not usually get this problem with symbols, as there is only one
type and a specific syntax for its values.

If you can define more by abstraction, then you usually have to use
different syntaxes for the values. But this is getting into other
issues.

For more specific points.

Your quote would be more accurate if it said "Symbol is a primitive
datatype ..." A symbol is a value in that datatype.

It is likely that some people will talk of symbols for values of an
enumerated type. Another word is token.  But these two words have so
many uses...  Again, I do not wish to enter a terminology dispute. It
is moderately constructive.


Complexity of a graph parity-coloring problem Suppose I have a positively weighted (bounded-degree) graph $G$ where each vertex in $G$ is colored either black or white.  I'm curious about the complexity of the following problem:

Find a subset $S$ of edges of G of maximal weight, subject to the constraint that any node colored black is incident to an odd number of edges in $S$, and any node colored white is incident to an even number of edges in $S$.  The constraint is sort of a $2$-coloring up to parity.

The problem seems hard in general.  I'm more interested in the simpler case that $G$ is a tree.  In this case, are there any efficient algorithms to determine such a set $S$?  Also, does this problem have a name?

Note for each node $v$, there is a one-to-one mapping between the parity of incident edges in $S$ and that of incident edges in $\bar{S}$. This means we can consider the problem with minimum weight equivalently.

The minimum weight version is named min-cost T-join that is studied in this note, which is an application of min-cost matching.

The idea is, one can decompose $S$ ($\bar{S}$ in the maximum weight version) into a set of edge-disjoint paths joining black nodes (nodes requiring an odd degree), thus the solution is exactly a min-cost matching of the complete graph induced by black nodes where the cost of edge $(u,v)$ is the length of the shortest path between $u$ and $v$ in the original graph. So this problem can be solved by any algorithm solving min-cost matching.

If the graph is a tree, the solution is much simpler as Yuval Filmus pointed out in the comment.

  Try solving it on a tree using "dynamic programming" (i.e., recursion). For each subtree, solve the corresponding instances with both colors for the root.

Note for a tree, there is at most one feasible solution. So asking for maximum/minimum weight may be meaningless.


NP-complete problem whose corresponding optimization problem is not NP-hard For this question I will refer to$\ NP-hard$ problems as those that are at least as hard as$ \ NP-complete$ problems. That is, a problem$ \ H$ is$\ NP-hard$ if there is an$ \ NP-complete$ problem$\ G$, such that$\ G$ is reducible to$\ H$ in polynomial time.$\ NP-hard$ problems are not restricted to decision problems and are not necessarily in$\ NP$.

Considering the above, is there any optimization problem$\ L$  such that$ \ L \notin NP-hard $ and whose corresponding decision problem is$ \ NP-complete$?

For example, consider the case for the travelling salesman problem. (TSP)

  Optimization problem: Given a list of cities and the distances between each pair, what is the shortest path that visits each city and returns to the original city?

  Decision problem: Given a list of cities, the distances between each pair and a length$ \ L$, does there exist a path that visits each city and returns to the original city of length at most$\ L$.

It is well known that the decision problem of TSP is$ \ NP-complete$ and its corresponding optimization problem is$\ NP-hard$.

To sum up, what is an example of a$\ NP-complete$ problem whose corresponding optimization problem lies outside the class$\ NP-hard$? Perhaps, it is$\ EXPTIME$.

Take a look at Bellare and Goldwasser, "The complexity of decision vs. search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119. It discusses the issue at length. Perhaps a bit more readable is the class note by Bellare, "Decision versus search".


Determine if an array is divisible in pairs of equal sum I'm currently studying the time complexity of the solution provided by my teacher to this problem, and I can't understand the logic:

Let A be an unordered array of positive natural numbers. Write an algorithm that checks if it's possible to divide A into pairs (subsets of two elements) of equal sum.
Example [1 7 4 2 4 0 8 6] is composed of 1+7, 4+4, 2+6 etc all of which give 8.

Now, the solution works like this: it sorts the array, and then checks if the sum of $A[i]$ and $A[length-i]$ (indexes start at 1) always give the same value.

Example: [0 1 2 4 4 6 7 8] is the above array after reordering. Checks 0+8=8, then 1+7=8, then 2+6=8 etc.

So the algorithm returns True, since every $(n,n-i)$ pair in the array always gives the same sum.
My problem with this is that I can't understand why positioning the elements with this symmetry would give an equal sum everytime.
Why taking the $i$ and $n-i$ elements would give the same sum?

You sort the array in increasing order.

If you pair an element equal to the largest element with any element that is larger than the smallest element, then pairing the smallest element with any other element will give a smaller sum, and therefore a different sum.

Therefore, to find pairs that all have the same sum, you must pair an element equal to the largest with an element equal to the smallest, and then repeat for the remaining elements. This will give you pairs with equal sums if it is possible. If not possible, then of course you won't get equal sums.


How many bits representation of data on tape of Turing machine consumes I am wondering how to represent signed number, vector, matrix on binary tape of Turing machine to consume the smallest possible amount of memory.

For signed number it is obvious: encode sign as a single bit and sum it with the length of number representation $\lceil\log_2(\mathrm{abs}\,(n)+1))\rceil$.

But how is it possible to represent a vector of numbers with different size. How to consume minimal amount of memory?

Note that the usual representation of signed integers in binary is not the one you propose.

In general, though, being super-efficient about coding in Turing machines isn't really important. We mainly use Turing machines for:

computability, where we don't care about efficiency at all;
complexity, where we only care about efficiency up to constant or even polynomial factors.

We don't use Turing machines for real computation where we care about the "real" efficiency, where making your program twice as fast makes it twice as good.

So, from the point of view of Turing machines, it's completely adequate to code vectors and so on by something like the following. Pick any sensible format for the individual data items and write those out with each bit doubled (i.e., $1011$ becomes $11001111$). Then separate each item with $01$. This means that storing the vector/matrix/whatever takes "twice as many bits as it should" but that constant factor just isn't important for the things we use Turing machines for.


Proof that if P=PSPACE, RP=BPP Like the title says. I can't figure out how to prove this.
I think it probably has to do with the polynomial hierarchy collapsing but I'm not sure.

$P \subseteq RP $, $BPP \subseteq PSPACE $.
So $PSPACE \subseteq P $, $-->$ $BPP \subseteq RP $.


Feasibility of linear inequalities with binary variables I have a system of linear inequalities of the form $A^t x \leq b$, where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a feasible solution or prove that the system has no solutions?

I need this to generate an initial solution to the heterogenuous fleet VRP where the number of unknowns is ~ 10s of millions in each instance.

Use an off-the-shelf integer linear programming solver.  That's exactly what they are designed to do.  The problem is NP-hard in general, so there are no guarantees -- there are certainly some problems that no existing solver can solve in any reasonable amount of time -- but you might get lucky.

Checking whether a feasible solution exists is also NP-complete, and it is (asymptotically, in general) about as hard as finding a feasible solution if one exists.


Are there any algorithms or data structures that need to find the median value of a set? I have been reading this book for my class, Randomized Algorithms. In this particular book, there is a whole section dedicated to finding the median of an array using random selection, that leads to a more efficient algorithm. Now, I wanted to know if there are any practical applications of this algorithm, in the domain of computer science, besides a theoretical improvement. Are there any algorithms or data structures that need to find the median of an array?

if there are any practical applications of this algorithm in the domain of computer science besides being a theoretical improvement

The application of this algorithm is trivial - you use it whenever you want to compute a median of a set of data (array in other words). This data may come from different domains: astronomical observations, social science, biological data, etc.

However, it is worth mentioning when to prefer median to mean (or mode). Basically, in descriptive statistics, when our data is perfectly normal distributed then mean, mode, and median are equal, i.e. they coincide. On the other hand, when our data is skewed, i.e. the frequency distribution for our data is (left/right) skewed, the mean fails to provide the best central location because the skewness is dragging it away from the typical value to left or right, while the median is not as strongly influenced by the skewed data, and thus best retains this position pointing to a typical value. Thus computing a median might be preferable when you deal with skewed data.

Also, machine learning is where statistical methods are heavily used, for example $k$-medians clustering.


Unsupervised Learning: BCM or Oja's Rule I am learning about unsupervised machine learning, and am a bit confused regarding different algorithms to update weights. So, I understand that both Oja's Rule and BCM can be used.

In Oja's rule:

dw/dt = k*x*y - w*y^2

Where x is the value at the input neuron, y is the value at the output neuron and w is the connection strength between the two. The idea is that this prevents weights from growing out of proportion.

In BCM:

dw/dt = k*(y-theta)*x

Where the idea is that unless my postsynaptic strength exceeds a threshold theta then I don't want my connectio to be strenghtened.

Studying competitive learning, which is yet another type of unsupervised learning I cam across another rule:

dw/dt = n*(x-y)

In this case however x is the full input vector and y is the vector representation of the output vector. The idea being that we move the prototype that responded the strongest to a given input closer to it, making the two more similar.

However, I don't understand when should I use which rule? For example, why couldn't I use a rule that combines both Oja's and BCM, hence only increasing connection weights when the output exceeds a given threshold, and preventing weights from growing out of proportion?

Oja's learning rule and the BCM share the underlying generative model, a linear perceptron: $$y = w^T x,$$ where $w$ and $x$ are vectors of the similar dimension.

But they differ in their goals:

Oja's rule (run with a sufficiently small learning rate) extracts the 1st principle component of the covariance matrix of the data: $$C = \langle xx^T \rangle_{p(x)}$$ s.t. $ \lambda_1 w_1 = C w_1$, where $\lambda_1$ is the largest eigenvalue.

The BCM rule maximizes the input selectivity with respect to a specific input pattern. The selectivity is defined as $$ s(w) = 1 - \frac{\langle w^T x^{(i)} \rangle}{ \max_i w^T x^{(i)} }. $$ The selectivity is maximized if the output neuron responds strongly to one of the input patterns (e.g. the kth stimulus $x^{(k)}$) but barely responds to all others.

The third rule doesn't make sense to me (I'll use explicit notation for vectors now). Assuming that $n$ is a scalar (e.g. learning rate), $\vec{x}$, $\vec{y}$ and $\vec{w}$ must have the same dimensions. Then, what's your generative model? Neither can it be $y = \vec{w}^T \vec{x}$ (because $\vec{y}$ is a vector) nor $\vec{y} = W \vec{x}$ because your weights are vector and not a matrix..


What will be T(n) after second step in a Recurrence Relation T(n) = 2T(n-1) + n

Using back Substitution at first step we get

T(n) = 4 T(n-2) + 2(n-1) +n

If i go further one more step then what i am getting is

T(n) = 16 T(n-4) + 8(n-3) +4(n-2) + 2(n-1) +n

What you get is correct, but you haven't gone further one more step, but two more steps.

T(n) = 2T(n - 1) + n

First :

T(n - 1) = 2T(n - 2) + (n - 1)

T(n) = 4T(n - 2) + 2(n - 1) + n

Second :

T(n - 2) = 2T(n - 3) + (n - 2)

T(n) = 8T(n - 3) + 4(n - 2) + 2(n - 1) + n

Third :

T(n - 3) = 2T(n - 4) + (n - 3)

T(n) = 16T(n - 4) + 8(n - 3) + 4(n - 2) + 2(n - 1) + n


What is the formal description of a Turing machine? I was asked to give a formal description of a Turing machine I have no experience with this, and was wondering what "formal description" entails.

In class you must have seen a formal definition of a Turing machine, such as the one given by Wikipedia. Formally, a Turing machine is given by a bunch of sets and functions. A formal description of a Turing machine is just this data. You can check out some examples on Wikipedia.

The definition in Wikipedia is only one possible definition — you will need to use the formal definition given in class. While the different formal definitions give rise to slightly different Turing machine models, these models are always equivalent in power (up to some small differences), in particular they are equivalent in terms of which functions can be computed in them.

Programming a Turing machine "formally" is like writing a program in a programming language (or assembly language). In contrast, informal descriptions of Turing machines are similar to pseudocode or to informal descriptions of algorithms. Programming Turing machines is very messy, and the point of this exercise is just to show you that it is possible in principle, and to help you understand how a Turing machine actually "works".


building a polynomial algorithm that solves SAT when given a polynomial TM that solves SAT on two formulas Here's the question:

  Assume there exists a polynomial time machine $M$ that receives two formulas $\varphi_1,\varphi_2$ and satisfies the following:

  If $\varphi_1 \in \mathrm{SAT}$ and $\varphi_2 \notin \mathrm{SAT}$, then $M(\varphi_1,\varphi_2)=1$
  If $\varphi_1 \notin \mathrm{SAT}$ and $\varphi_2 \in \mathrm{SAT}$, then $M(\varphi_1,\varphi_2)=0$

  Show that there also exists a polynomial time algorithm for SAT.

  Note that we have no guarantee for the output of $M(\varphi_1,\varphi_2)$ whenever $\varphi_1,\varphi_2$ are both satisfiable (or when both are not).

Can I get any hint on how to start the solution?

Here is something your oracle can do: if you are given two formulas $\alpha,\beta$, and are guaranteed that at least one of them is satisfiable, then you can find one of them which is satisfiable by calling $M(\alpha,\beta)$: if $M(\alpha,\beta) = 1$ then $\alpha$ is satisfiable, and if $M(\alpha,\beta) = 0$ then $\beta$ is satisfiable.

Given a satisfiable formula $\varphi$ over $x_1,\ldots,x_n$, you can use this to find a satisfying assignment, variable by variable: at each step, you consider assigning the variable the two possible truth values, and use the method described above to find an assignment under which the formula is still satisfiable. Finally, you can check whether the supposed satisfying assignment indeed satisfies $\varphi$. If so, $\varphi$ is satisfiable. Otherwise, it isn't.


in function declarations, what advantages are there to having the type of the parameter specified after the parameter name? For typed languages, what advantages/disadvantages are there to specifying the parameter type after the parameter name?

For languages like C and Java, the type comes first:

void myfunc(TypeA param1, TypeB param2);

For other languages like Scala, Rust, etc, the type comes after the parameter name:

fn myfunc(param1: TypeA, param2: TypeB) {}

What advantages are there to this approach?   I could see in languages where specifying a type is optional (or inferred) and can be left off, but at least for Rust types have to be specified in a function's parameter list.

It's completely arbitrary.

In a given programming language, one would hope that the same convention is used throughout, so either int f(int x) or f(x: int): int but not int f(x: int) or f(int x): int; but even that is arbitrary.


What kind of recurrence relations has p < 0? By the master method,
$T(n) = aT(\frac {n}{b})+\Theta(n^k\log^pn)$
where $p$ is real.

I know $\log^4n=\log(\log(\log(\log n)))$ but how do you calculate something like $\log^pn$ where $p<0$?

As Rick Decker mentions, in this context $\log^p n = (\log n)^p$, and so $p$ can be an arbitrary real number. If you wanted to denote composition, you would use $\log^{(p)} n$ (which in other contexts signifies the $p$th derivative!). In that case, when $p$ is a negative integer, you just need to use the inverse of $\log$, namely $\exp$:
$$
\begin{align*}
\log^{(2)} x &= \log\log x \\
\log^{(1)} x &= \log x \\
\log^{(0)} x &= x \\
\log^{(-1)} x &= e^x \\
\log^{(-2)} x &= e^{e^x}
\end{align*}
$$
This definition ensures that $\log^{(a)} \log^{(b)} x = \log^{(a+b)} x$ for all integers $a,b$. The natural domain of this definition is integer $p$, though it can probably be extended for fractional $p$ in such a way that the equation above still holds.


Difference between substitution, morphism, and homomorphism In closure properties, I got confused between substitution and morphism.

1) According to Wikipedia, string substitution means to map letters in a set of alphabets to languages (possibly in a different alphabet), that is, $f(a) = L_a$.  Does that means to replace a letter with a language? Or replace 1 letter from a set of alphabets with 1 letter another set of alphabets?

2) According to Wikipedia, string homomorphism means to replace each letter with a single string, that is, $f(a) = s$, where $s$ is a string. What does 'a single string' mean? Does this mean the letter 'a' may be replaced by a string such as 'owl'? A webpage says that homomorphism is a group maps, which make me even more confused. What's the difference with substitution?

3) I thought that if $\left| f(a) \right|=1$, it's called morphism. Then this is not a string but only a letter. Are morphism and homomorphism the same thing?

I am a beginner and really confused. Hope somebody can help me clear this confusion, as well as the difference in proving the closure properties of substitution, homomorphism, and morphism. Your knowledge and help are very appreciated.

Indeed morphism and homomorphism are the same in formal language theory. They are letter-to-string mappings $h:\Sigma \to \Delta^*$, and then extended to string-to-string mappings  $h:\Sigma \to \Delta^*$ in a morphic way: $h(\varepsilon) = \varepsilon$, and $h(xy) = h(x)h(y)$ for strings $x,y\in \Sigma^*$.

A substitution is a letter-to-language mapping, which is likewise extended to a string-to-language mapping. By identifying a singleton language $\{x\}$ to the string $x$, morphisms are seen as special case of substitutions.

A letter-to-letter morphism is sometimes called a coding.


Showing a problem is in coNP We have the problem $C = \{<G,S>| \text{ S is a minimal cover of G }\}$ and we want to show that $C\in coNP$.

I can easily show that there's a ND TM that decides $coC$ using a guess to check if the drawn vertices are a minimal cover and if they are, return false. But it seems like it's wrong since this can be done with anything.

So is there another way to show that?

Since coNP is confusing, let us construct an NP machine for $\overline{C}$. The input to the machine is a pair $\langle G,S \rangle$, where $S$ is a cover of $G$. The machine guesses another cover $T$, and verifies that $T$ is a cover of $G$ which is smaller than $S$. The cover $T$ is thus a witness to the fact that $S$ is not a cover of minimum size.

If $S$ is not a minimal cover, then there exists some smaller cover $T$, and so the machine accepts the instance $\langle G,S \rangle$ if it guesses $T$. Conversely, if $S$ is a minimal cover, then no smaller cover exists, and so the machine rejects the instance $\langle G,S \rangle$ whatever the guess is. In total, the machine accepts the language $\overline{C}$.

Here is a another way to look at things. We construct a machine that on input $\langle \langle G,S \rangle,T \rangle$, accepts if $S,T$ are covers of $G$, and $T$ is smaller than $S$. Then

  There exists $T$ such that the machine accepts $\langle \langle G,S \rangle,T \rangle$ if and only if $\langle G,S \rangle \in \overline{C}$.

This machine is polytime, and it accepts $\overline{C}$, showing that $\overline{C} \in \mathsf{NP}$, and so $C \in \mathsf{coNP}$.


Algorithm Running Time I'll do my best to explain my question but what I'm wondering is how to calculate a theoretical running time of an algorithm. In my textbook I have questions written as such:

  If a $\Theta(\log_2{n})$ algorithm requires 20 seconds to execute on an input of one million elements, approximately how long should it take on an input of two million elements?

The answer it gives is 21 seconds and I'm stuck on how they come up with that number.

Basically, the complexity of an algorithm gives the relation of the change in the running time with respect to the change in the input size. You can think it as,

$log_2(1M)$ -> 20 sec

$log_2(2M)$ -> ? sec

$log_2(2M) = log_2(2 *1M) = log_2(2) + log_2(1M) = 1 + 20 = 21 sec$


Computer Vision algorithm to tell if camera is moving? I'm looking for a computer vision algorithm or method that can tell if the camera is moving in a video. Or maybe an alternate way of telling if the background is moving. I have a lot of videos and only want to keep the ones where the camera is stationary.

All videos feature a person talking directly to the camera (the person is mostly stationary throughout the video). I want to keep videos where the camera is stationary, but there are a lot of videos where the person is holding the camera and walking or the camera is moving around too much

I plan to run some algorithm one by one on a collection of videos to determine which video IDs have a moving camera in them.

Use background detection algorithm, say Gaussian Mixture-based background detection (present in OpenCv) and then make some assumption - say backround takes more than 60% of image.
Then convert frames to color model which keeps luminance as separate component. Compare consecutive frames with small tolerance per color per pixel and bigger tolerance per light (to take into account shadows). If your camera is not really stationary, check by movement algorithm if frame is shifted by some distance (camera may move slightly even if it stands still), in that case compare it with shifted frame after detecting shift.

Now gather frames with some tolerance, say 95% of frames match background in at least 60% of pixels with slight shifts (it depends on distance from camera to background).
If it matches, camera was still, if not then either parameters were too big or it was moving.
Adjust parameters, done.


To what does typing correspond in a Turing Machine? I hope my question makes sense: Starting with the premise that the untyped $\lambda $ calculus is equivalent in power to a Turing machine, to what in a Turing machine does adding types to the $\lambda $ calculus correspond? Is there some kind of automaton analog to typing, whether static or dynamic?

I can't give you a direct answer for automatons, but for functions on numbers.

The untyped lambda calculus corresponds to $\mu$-recursive functions.

For typed systems, it naturally varies for different systems.

An interesting one is System F, also known as the polymorphic lambda calculus. There is a theorem that says that

  A function (on natural numbers) is expressible in System F if and only if it can be proved in the second order Peano arithmetic that the function is total.

This means that in System F you can express basically all imaginable total functions.

There is a bit weaker system, Gödel's System T, for which there is a very similar theorem for first order Peano arithmetic. (However this system is not as nice as System F. In System F you can represent natural numbers, booleans etc. natively, while System T is constructed as the simply typed lambda calculus with externally added naturals and booleans. Also System F has type polymorphism, which makes it much more elegant in many cases.)

See also:

Girard, Lafont and Taylor, Proofs and Types. Cambridge University Press, 1989, ISBN 0-521-37181-3.
Is there an always-halting, limited model of computation accepting $R$ but not $RE$?


Is the best known algorithm for the shortest path problem for an undirected and unweighted graph $O(E)$ or $O(E+V)$? I'm a bit confused by Wikipedia's tables of algorithms for the shortest path problem.
For an unweighted graph with $E$ edges and $V$ vertices, it gives the best algorithm as breadth-first search, with a time complexity of $O(V+E)$. But above that, for an undirected graph with natural-number weights, it gives the best algorithm as an $O(E)$ algorithm due to Thorup (1999). This seems faster than the $O(V+E)$ for breadth-first search despite applying to a more general problem.
Am I correct in understanding that the $O(V+E)$ breadth-first search algorithm applies to a directed unweighted graph, and for an undirected and unweighted graph, Thorup's 1999 $O(E)$ algorithm is faster even though it's capable of handling arbitrary natural number edge weights? This seems surprising to me.

To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the "source" node and visiting only nodes that we can reach using the BFS (that is, we don't run BFS from every node if we didn't see that node already. Only one instance starting from the source node is enough), would require $O(E)$ time.
It follows since the graph BFS traverses is guaranteed to be connected, hence $\forall v:deg(v)\ge 1$. Thus $|E_{traverse}| \ge \frac{|V_{traverse}|}{2}$ where $E_{traverse}$ and $V_{traverse}$ are the sets of edges and vertices the BFS "saw" while running.
Clearly, the BFS works in $O(|E_{traverse}|+|V_{traverse}|)$ but since $|V_{traverse}|=O(|E_{traverse}|)=O(|E|)$, we can conclude that the BFS instance runs in $O(E)$.
Note: This is only true if the BFS is ran only from one source, unlike the usual BFS algorithm description that starts the traversal from a node we didn't mark yet if we finished the last traversal instance.

Honestly, I don't know about Thorup's algorithm, so I can't answer this part of the question about it. However, I know that BFS works for both directed and undirected graphs, but doesn't work with natural weights.


Can we do better than $O(n\log n)$ building a balanced binary tree? I'm (foolishly it turns out) confident that the answer to this question is no. So why am I asking?

Because Dr. Aleksandar Prokopec at EPFL in his parallel programming course introduces a data-structure for which he asserts various properties. If these properties hold then it seems to me that it must be possible to build a balanced binary tree in better than $O(n\log n)$ time.

I don't believe this so I'm wondering where the flaw is in my thinking.

The data-structure is the conc-tree list. In it's standard form it looks like a normal binary tree and comes with a concat operation that ensures the invariant that the left and right subtrees of any node never differ in height by more than one. As expected concat has complexity $O(\log n)$.

But there's a builder variant of the conc-tree list called the Append list. This variant allows for temporary height differences in subtrees of more than one. Amortized $O(1)$ time appends are claimed for this variant.

So it seems appending $n$ elements must have a complexity of $O(n)$.

However it's a characteristic of this variant that whenever $n$ is a power of two one ends up with a complete balanced binary tree (containing all elements inserted so far). So while temporary imbalances are allowed the tree becomes balanced every power of 2 insertions.

In this variant a new class of nodes, called Append nodes, are introduced and it's these nodes whose subtrees are allowed differ in height by more than one. However every $2^k$ insertions all such temporary nodes are eliminated.

The Wikipedia page page describes the algorithm fairly succinctly (see the description of the basic data-structure and the append method in particular).

So when $n$ is a power of two our cost for inserting elements is $O(n)$ and we've built a balanced binary tree. Or so it seems.

In a separate question I effectively asked "if I can state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, is this enough to allow me to state the complexity for all values of $n$?"

I can see from Yuval Filmus's answer that the answer is no, but that "in many cases we would expect $T$ to be monotone in $n$. In that case, the deduction does hold."

So it seems to me that in this case if inserting $n$ elements has complexity $O(n)$ and every $2^k$ elements I have a balanced binary tree then the cost of building balanced binary trees with this conc-tree variant approach must be $O(n)$.

So what's wrong here? To be honest I can't see the amortized $O(1)$ append time claimed for this variant. I can see that often insertions do have cost $O(1)$ but that when one looks at what's happening with the temporary Append nodes the overall insertion cost looks to me to be amortized $O(\log n)$.

If this is the case then building our balanced binary tree has an unsurprising $O(n\log n)$ cost.

Sorry for such a long question and sorry for not going into detail about the algorithm in question - instead leaving you to look around on Wikipedia.

If I understand your question correctly, then yes of course you can build a balanced binary tree in $O(n)$ time. Here is a simple pseudocode:

L = [2, 4, 1, 3, 5, 6, 8]
q = Queue()
node root{value = L[0]}
q.add(root)
k = 1
while !q.isEmpty:
  n = q.pop
  if k < L.size:
     n.left = node{value=L[k]}
     k++
     q.add(n.left)
  if k < L.size:
     n.right = node{value=L[k]}
     k++
     q.add(n.right)

It is not hard to see that this code does run in linear time and builds a balanced binary tree.

What you cannot do, is build a balanced binary search (ordered) tree in $O(n)$ time (using only comparisons on the values). The algorithm above does not guarantee that the value on the root is greater than or equal to every value in the left sub-tree and is less than or equal to every value in the right sub-tree, for every sub-tree.

The algorithm above does not guarantee it and neither does the conc-tree (using appends and prepends). From the wikipedia page, it only guarantees $O(1)$ amortized time for appends and prepends. For inserts, it can only guarantee $O(\log n)$ time.


Regular languages, automata I want to ask about the definition of regular languages. My book says there has to exist a deterministic finite automaton that recognizes it. Does this mean the finite automaton recognizes exactly this language and nothing else or it can recognize possibly some other words not in the language?

It means the automaton recognizes exactly it. in fact, you can even build an automaton that accepts every word (try to do it yourself), so there would be no meaning in the other definition


Neural network for PDE: Should we train the PDE using more initial and boundary data at the beginning? I was trying to solve a partial differential equation (PDE) using a neural network. The solution to the PDE is not unique unless the boundary condition is determined.

In my case, the neural network takes $(x, y)\in [0, 10]\times[0, 10] = A$ and outputs a scalar. Suppose at the beginning of the training, I only sample from the middle of $A$, which will give us a neural network that satisfies the PDE except for the boundary condition. Then we sample from the boundary of $A$.

My question is, will it be costly to train using the algorithm above? My guess is yes since we have to drag that solution to somewhere else based on the boundary condition, causing large change to the output value. And intuitively, it's better to construct the solution on the boundary first to make the foundation of the solution correct.

I know that we can test it by experiments, but I'm more interested in a theoretical explanation, e.g., why / why not will it be costly to update parameters of the neural network after the boundary data get considered?

There is sadly very little theory that is useful for predicting the behavior of neural networks.  Also, their effectiveness tends to be dependent on the particular workload/task you are trying to solve it.  While I know it's not what you were hoping to hear, I suggest that you try it in empirical experiments.


Why is this language involving reversal regular? For a language to be regular it needs to be recognized by DFA/NFA.

Let $L = \{ xy^rzyx^r \mid |x| , |y|, |z| \ge 1 \}$ over the alphabet $\{0,1\}$.

$x^r$ means the reverse of $x$.

A DFA has no memory, so how can it handle the reverse check?

Notice that big unconstrained $z$ in the middle. You don't need the DFA to check anything if there is a way to decompose the word that dumps almost everything into $z$.

In particular, any word of the form $a b z b a$ where $a$ and $b$ are letters and $z$ is an arbitrary non-empty word is in $L$ (with words of length 1 for $x$ and $y$).

Conversely, suppose that you have a word $w \in L$: it can be broken down as $x y^r z y x^r$ with $|x| \ge 1$ and $|y| \ge 1$. If $|x| \ge 2$ then write $x = a b x'$: we have $w = a b x' y^r z y x'^r b a = a b z' b a$ where $z' = x' y^r z y x'^r$. If $|x| = 1$ then write $y = b y'$ and do a similar decomposition.

Conclusion: another way of describing $L$ is $L = \{a b z b a \mid a,b \in \{0,1\}, z \in \{0,1\}^{+}\}$. This language is regular; a regular expression that matches it is
00..*11|01..*10|10..*01|11..*11. Intuitively, an autotomaton recognizing $L$ only needs a finite amount of memory, because it only needs to memorize the first two letters.


Is it NP complete to decide whether a graph has bigger clique or bigger independence number? Is it $\mathsf{NP}$ complete to decide whether a graph $G$ has bigger clique $\omega(G)$ or bigger independence number $\alpha(G)$?

Note that there is a slight technicality with regards to whether you consider the graph where the clique is larger a "yes"-instance, or a graph where the independent set is larger a "yes"-instance (i.e. the complement problem) and what you do in the event of a tie. I have picked one particular way of settling ties, but this proof can easily be adapted to the other way of settling ties (i.e. by fudging with a $\pm 1$).

If $NP\not = coNP$ then neither this problem nor its complement is in $NP$, so neither problem is likely to be $NP$-complete.

It is $NP$-complete to decide whether a graph has an independent set of size $k$. We show that, if there exist polynomial certificates for your problem then there exist polynomial certificates for the complement of the independent set problem. We note that IS remains $NP$-complete even when restricted to maximum degree $3$ graphs and $k>4$.

Given a graph $G$ that does not have an independent set of size $k$, we create a new graph $G'$ as the union of $G$ and a clique of size $k$ (note that this increases the independence number by one).

$G'$ is a "yes"-instance of the problem "Is the Clique greater or equal to the IS?". A polynomial certificate for this fact would give a polynomial certificate testifying to the fact that $G$ does not have an IS of size $k$, which is impossible unless $NP=coNP$. (The largest clique in $G$ is of size $4$ since $G$ has maximum degree $3$, so the largest clique in $G'$ is of size $k$. The certificate for $G'$ thus has to certify that $G'$ has no IS of size $k+1$ and equivalently, that $G$ has no IS of size $k$).

If we instead consider the complement problem "Is the Clique strictly smaller than the IS?", we create $G'$ by adding a clique of size $k+1$ and then taking the complement graph $\bar{G'}$. Since a Clique becomes an IS in the complement graph and vice-versa, the largest IS in $\bar{G'}$ is of size $k+1$ while the largest Clique is of size at most $k$. $\bar{G'}$ is thus a "yes"-instance of the complement problem, but a certificate for this fact would give a certificate for $G$ not having an IS of size $k$ which is impossible unless $NP=coNP$.

However, the problem "Is the Clique strictly smaller than the IS?" is $NP$-hard. We reduce from Independent Set on a maximum degree $3$ graphs $G$ where $k>4$. We create $G'$ by adding a clique of size $k$ to $G$. If $G$ has an IS of size $k$ then $G'$ has one of size $k+1$ (obtained by adding any of the clique's vertices to the IS). The largest clique in $G'$ has size $k$, so $G'$ is a "yes"-instance if and only if $G$ has an Independent Set of size $k$.


Prove that the depth function of a Binary Search Tree is $O(\log n)$ on average I am struggling with this question because I am not sure how to see that a depth function is $\mathcal{O}(\log n)$ on average when it clearly traverses through the whole tree which should make it $\mathcal{O}(n)$:

depth(tree):
    if tree is a leaf:
        return 0
    else:
        return 1 + max(depth(tree.left_subtree), depth(tree.right_subtree))

It goes through each and every node. Could someone explain to me how finding the depth of a BST can be done is $\mathcal{O}(\log n)$ on average?

If your input binary search tree is like the one given below  then no matter what the program does, the depth function will return $n-1$ (because the depth  is $n-1$, in this case). And it will take $n$ operations if  the program does not know the depth beforehand or by some trickery, or the depth is not stored, say, in nodes.

You are confusing three things in your question:
(1) depth function returns $d$, the depth of the tree, which is fixed for a given tree.
(2) depth function the way it is defined will always run in $O(n)$ time for any tree, skewed or balanced.
(3) the average depth $E(d)$ of a random binary search tree (which is got by randomly inserting $n$ uniform random values) is $O(\log n)$.


Data structure with init $O(n)$ and interval max $O(\log n)$ I need to find a data structure that supports the following operations:

init(A): gets an array of size $n$ of different numbers and builds the data structure - should be $O(n)$.
max(i,j): gets two indexes $i<j$ and returns the maximum value between these two cells, that is, $A[i],A[i+1],\dots,A[j]$ - should be $O(\log n)$.

It should be a tree related data structure.

Assume for simplicity that $n$ is a power of 2. Construct a complete binary tree in which the vertices at depth $k$ correspond to subarrays of length $n/2^k$, and contain as auxiliary information the maximum element of the subarray.

This data structure can be initialized in $O(n)$, and it supports your type of range queries in $O(\log n)$. You can also update the data structure by modifying arbitrarily a single element of the array in $O(\log n)$.

Details left to you.


Finding a vertex coverage that is also an independent set Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?

This problem is called the independent vertex cover problem and it is solvable in polynomial time. Note that the set $S$ must be a vertex cover means that each edge has an endpoint in the set. On the other side, being an independent set means that each edge has at most one endpoint in the set. Hence, each edge has exactly one endpoint in the set. That means we are looking for the smallest possible subset of vertices $S$ such that $(S, V\setminus S)$ is a bipartition of the graph. This can be done in linear time since each connected component has either non or exactly one bipartition.

Here is also another solution of the problem based on a reduction to the 2-sat problem (also using the fact that each edge has exactly one endpoint in the set).

https://cstheory.stackexchange.com/questions/36707/smallest-vertex-cover-which-is-also-an-independent-set


Does input space size contribute at all to the runtime of an algorithm? I just started learning about NP-Complete problems and one of the first examples they give is Set Cover:

  Given a set $U$ of $n$ elements, a collection $S_1, \ldots, S_m$ of subsets of $U$, and a number $k$, does there exist a collection of at least $k$ of these sets with the property that not two of them intersect?

This is I'm sure a very basic question, but I was wondering whether the amount of space in $n$ the input takes up matters at all in the formulation of runtime. This is the first example of an algorithm I've seen where the input itself takes up space exponential in $n$ since of course there are $2^n$ possible subsets of $U$. Thus, it seems that possibly the time needed to allocate the space necessary to even "handle" the input prevents there from being a polynomial time algorithm.

Or rather, do we just assume that the input magically appears in our hands already allocated before we start keeping track of algorithm runtime? And as a side question, can we choose what data structure it is given to us in? This seems more natural to me, but I wanted to make sure. I know, for example, that the time needed to allocate an output (or allocate anything in between) does matter.

We measure the running time as a function of the length of the input, not as a function of $n$.  So, it doesn't matter whether the length of the input is $2^n$ or not.

When we talk about an exponential-time function, we normally mean exponential in the length of the input, not exponential in some other parameter (like $n$).

For your problem, the length of the input could be $2^n$, but it will typically be a lot less than $2^n$, because typically we'll have many fewer sets than that.  Either way, it doesn't matter, because we're measuring the running time as a function of the input length.

Typically, the format/representation of the input doesn't affect the running time much; the running time will be identical for any reasonable way to represent or encode the input.  So, typically that doesn't matter.  In the cases where it does matter, be careful to specify the input representation, or ask if it isn't specified.


Is it decidable whether a TM is a LBA? Given an arbitrary TM, can you decide whether it's a LBA?

An LBA is limited to working only on the space defined by the input. That means it won't ever move right on reading a blank space (if your model doesn't allow writing blank, only a fake blank, that is). That is easy to check by looking at the transitions of the TM.
To check if the language is accepted by an LBA is undecidable by Rice's theorem.


Analysis of a randomized algorithm for independent set construction Suppose that $G = (V,E)$ is a 3-regular graph on $n$ vertices and $m$ edges. Below I propose a randomized algorithm for obtaining an independent set for $G$.

Step $1$: Delete each vertex (independently) with $\frac{2}{3}$ probability.
Step $2$: For each remaining edge, delete one of its endvertices.

I want to upper bound the probability that this $2$-step algorithm yields an independent set of size smaller than $\frac{n(1-\varepsilon)}{6}$, where $0 < \varepsilon  \leq 1$. My partial attempt is below.
Let $X_1, X_2, \dots, X_n$ be independent Poisson trials satisfying $\textbf{Pr}[X_i = 1] = \frac{1}{3}$. Hence, $X = \sum_{i=1}^{n} X_i$ gives us the number of vertices in $G$ that survive Step $1$, and $\textbf{E}[X] = \frac{n}{3}$.
Let $Y_1, Y_2, \dots, Y_m$ likewise be independent Poisson trials satisfying $\textbf{Pr}[Y_i = 1] = \frac{1}{9}$. Hence, $Y = \sum_{i=1}^{m} Y_i$ gives us the number of edges in $G$ that survive Step $1$, and $\textbf{E}[Y] = \frac{n}{6}$.
Thus, $X-Y$ gives us the minimum number of vertices remaining after the algorithm terminates.
Now, the following Chernoff bound seems especially pertinent to this problem, where $Z$ is a sum of independent Poisson trials, $\mu$ is its expectation, and $0 < \delta \leq 1$:

$\textbf{Pr}[Z < (1 - \delta)\mu] < \exp(\frac{-\mu \delta^2}{2})$

Of course, $X-Y$ is a lower bound on the size of the output independent set, but I'm not sure how I can apply the expression to the Chernoff bound. Can $X-Y$ can be conceived as a sum of Poisson indicator variables, which would be required if I wanted to put $X-Y$ in place of $Z$ in the above bound? If so, then it seems to me that I can use this Chernoff bound to derive an upper bound on the probability that the minimum size of the output independent set is smaller than $\frac{n(1-\varepsilon)}{6}$. How can I get from this to my objective: an upper bound on the probability that the actual size of the output independent set is smaller than $\frac{n(1-\varepsilon)}{6}$?

You can obtain a weak upper bound by resorting to the Markov inequality instead. Specifically, let random variable $\small Z$ be the size of the independent set remained. We have then
\begin{align}
\small
\Pr\left[Z \leq \frac{n(1 - \epsilon)}{6}\right] \leq&~\small\Pr\left[X - Y \leq \frac{n(1 - \epsilon)}{6}\right] \\
=&~\small\Pr\left[n - (X - Y) \geq n - \frac{n(1-\epsilon)}{6}\right] \\
=&~\small\Pr\left[n - (X - Y) \geq \frac{(5 + \epsilon)n}{6}\right] \\
\leq&~\small \frac{5n / 6}{(5 + \epsilon) n/ 6} = \frac{5}{5 + \epsilon}
\end{align}
where the last inequality is by Markov inequality and $\small \mathbb{E}[n - (X - Y)] = \frac{5n}{6}$.

Though the bound is weak, we can reduce it by repeating your algorithm multiple times (e.g., $\small \ell$) and then selecting the independent set with maximum size. The probability that the resultant size is still smaller than $\small \frac{n(1- \epsilon)}{6}$ then is at most $\small \left(\frac{5}{5+\epsilon}\right)^\ell$.


If the decision problem can be solved in poly time, show the optimization problem also can Here is a problem I am trying to solve:

  The bin packing decision problem is defined as follows: given an unlimited number of
  bins, each of capacity equal to $1$, and $n$ objects with sizes $s_1$, $s_2$, $\dots$, $s_n$ ($0 < s_i ≤ 1$), do the objects fit in $k$ bins (where $k$ is a given
  integer)? The bin packing optimization problem is to find the smallest
  number of bins into which the objects can be packed. Show that if the
  decision problem can be solved in polynomial time, then the
  optimization problem can also be solved in polynomial time.

I know what it is asking but I don't know what the "optimization" problem for this is. Is it the grouping of all the objects into different bins (for instance, $s_1$, $s_3$, and $s_6$ are in bin #$1$, $s_2$, $s_4$, $s_5$ are in bin #$2$, etc.)? Or is it simply the number of bins you need to store them? I feel like the number of bins is the decision problem...

In the decision problem, $k$ is given, so the answer is yes, or no (a decision). In the optimization problem $k$ is unknown, and we have to find out how small can it be (the optimal solution). The bigger question asks if there is a logical connection between possible solutions to these two problems, such that the complexity of the respective algorithms is corelated.