## Solving recurrence relation $T(n) \leq \sqrt{n}T(\sqrt{n}) + n$

Given the condition: $$T(O(1)) = O(1)$$ and $$T(n) \leq \sqrt{n}T(\sqrt{n}) + n$$. I need to solve this recurrence relation. The hardest part for me is the number of subproblems $$\sqrt{n}$$ is not a constant, it’s really difficult to apply tree method and master theorem here. Any hint? My thought is that let $$c = \sqrt{n}$$ such that $$c^2 = n$$ so we have $$T(c^2) \leq cT(c) + c^2$$ but I does not look good.

Posted on Categories proxies

## How to solve the following equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$?

I came with this interesting question and could understand how did we get to this equation: $$(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$$

But in the next step, it reached to the following step which I cannot understand. Please help me out in understanding this:

$$k\leq \frac{n+2^h}{2^{h+1}+2^h+1} \leq \frac{n}{2^{h+1}}\leq \left\lceil\frac{n}{2^{h+1}}\right\rceil$$ Reference: Problem 6.3.3, CLRS. Difficulty understanding the solution of heap problem in CLRS book?

Thank you.

Posted on Categories proxies

## Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

I am trying to find a context sensitive grammar for the type-1 language

$$L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$$

I can construct the first part with

\begin{align*} S &\to aSbB \mid B \mid \epsilon\ B &\to bB \mid \epsilon\ \end{align*}

but how do I continue from there? I tried

\begin{align*} S &\to aSbBcC \mid B \mid \epsilon\ B &\to bBcC \mid \epsilon\ CB &\to BC \ C &\to cC \end{align*} but this does not seem to work e.g. $$S \to aSbBC \to aaSbBCbBC \to aabBCbBC$$

## Sqrt(x) function implementation; what is $(i^2 \leq x) \land ((i + 1)^2 > x)$ checking?

Recently I was working on a LeetCode question

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.  Since the return type is an integer, the decimal digits are truncated and only  the integer part of the result is returned.  Example 1:  Input: 4 Output: 2 Example 2:  Input: 8 Output: 2 Explanation: The square root of 8 is 2.82842..., and since               the decimal part is truncated, 2 is returned. 

Here is a solution that I really like and understand, except for one line. It is using binary search to get to the solution:

int mySqrt(int x) {     if (x == 0) return x;     int left = 1, right = INT_MAX, mid;     while(left < right) {         mid = left + (right - left)/2;         if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {             return mid;          }         if (mid < x/mid) {             left = mid + 1;         } else { // mid > x/mid             right = mid;         }     }     return right; } 

The conceptual question is: why is it true that given a particular number, say $$i$$, $$(i^2 \leq x) \land ((i + 1)^2 > x)$$ returns whether or not $$i$$ is the truncated integer representation of the square root of $$x$$? (The code block above returns on the identical condition, but inequality is rearranged to avoid integer overflow)

Posted on Categories proxies

## Undecidable: $w$ on which a TM M $M$ halts after $\leq w$ steps

The detailed question is:

Is there a word $$w$$ on which a TM M $$M$$ halts after a maximum of $$|w|$$ (word length) steps?

I highly assume, that this problem is not decidable because in the worst case you have to test every word that exists (infinite) to realize, that the TM never holds. However this isn’t a proof and I have to proofe this question (without the Rice’s theorem).

My idea was to use the subroutine technique to “convert” the problem into the halt-problem, the $$\epsilon$$-halt-problem or the total halt problem. I have no idea on how to turn this problem into an existing one – could you help me here please?

## is it always true that the depth of BFS is $\leq$ DFS?

I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $$\leq$$ DFS?

From what I understand, the tricky part here is the possible cycles in the graph. Even though that I believe that the depth of BFS will always be less or equal to the depth of DFS.

In each iteration of BFS, from what I understand, the depth might grow by one, but DFS’s grows in each vertex it can not reach, sometimes above the maximal value of BFS.

So, is it always true that the depth of BFS is $$\leq$$ DFS?

## Prove that $T(n) \leq 8n^2$ or find value of $n$ when statement is not true (reccurence relation)

We have a function $$T: \mathbb{N}\to\mathbb{N}$$ defined recurrently:

$$T(n)=\begin{cases} 0 &\text{ if } n=0,\ 3T(\lfloor{n/2}\rfloor) + 2n^2 &\text{otherwise.} \end{cases}$$

Prove that for each $$n\in\mathbb{N}_0$$: $$T(n) \leq 8n^2$$

How can I prove such statement? I was thinking of using the Master Theorem to get asymptotically tight bounds of the recurrence but I think that is not a right approach. Any help appreciated

Posted on Categories proxies

## $M \leq X$. Is it true that $M^*$ is a subspace of $X^*$ where $*$ denotes the dual space?

Let $$X$$ be a Banach space and $$M$$ be a closed subspace i.e. $$M \leq X$$.

Is it true that $$M^*$$ is a subspace of $$X^*$$ where $$*$$ denotes the dual space?

What I have tried:

I know by Hahn Banach theorem that every $$f \in M^*$$ has an extension $$\hat f \in X^*$$ such that $$\hat f |_M =f$$ and the operator norm doesn’t change i.e. $$\|\hat f\| =\|f\|$$.

I found that such an extension can be chosen to be linear if $$X$$ is a Hilbert space here, hence my claim might not hold in the general case.

Any help is appreciated.

## let $I_{p,q}=\int_{\gamma}p(z)\overline{q(z)}dz$ where $\gamma$ is the closed contour $\gamma(t)=e^{it},0\leq t \leq 2\pi.$ Then

Consider the polynomial $$p(z),q(z)$$ in the complex variable $$z$$ and let $$I_{p,q}=\int_{\gamma}p(z)\overline{q(z)}dz$$ where $$\gamma$$ is the closed contour $$\gamma(t)=e^{it},0\leq t \leq 2\pi.$$ Then

1. $$I_{z^m,z^n}=0,\forall m,n\in \mathbb Z^+,m\neq n$$

2. $$I_{z^n,z^n}=2\pi i,\forall n\in \mathbb Z^+$$

3. $$I_{p(z),1}=0,\forall$$ polynomials $$p$$

4. $$I_{p,q}=p(0)\overline{q(0)},\forall$$ polynomials $$p, q$$

My Attempt

When I flashed through the options, I got (3) as the answer. Since Polynomial function is analytic. By Cauchy’s theorem, $$\int_{\gamma}p(z)dz=0$$. option (1) is wrong. Since, If $$m-n+1=0$$, I got $$I_{z^m,z^n}=2\pi i$$. For option (2), $$I_{z^n,z^n}=\int_{\gamma}z^n\overline{z^n}dz=\int_0^2\pi 1.e^{it}i dt=2\pi i.$$ Using option (2), We can deduce that (4) is a wrong answer. But the answer given in the answer key is only (3). Can you please help me?

Posted on Categories proxies

## In a bipartite graph $G$ show that 1) there are adjacent vertices with degree > k or 2) there are non-adjacent vertices with deg $\leq k.$

Note in this question $$G$$ has a bipartition $$(A, B)$$ where $$|A|=|B|>k.$$ Moreover the vertices are from different parts of the bipartition (one from $$A$$ one from $$B$$). And the above can be either or both (not xor).

Progress: I was thinking induction on $$k.$$ Suppose $$u \in A$$ has $$\deg(u) > k.$$ If one of its neighbors in $$B$$ has degree > k we’re done. Otherwise all of them have degree $$\leq k.$$ Pick one of them $$v \in B.$$ Since $$\deg(v) \leq k$$ there is at least one vertex in $$A$$ nonadjacent to $$v.$$ If it has degree $$\leq k$$ then we’re done. Otherwise all nonadjacent vertices will have degrees > k. The remove $$u, v$$ and use induction…

Actually I’m not sure how to continue from here. Any help would be appreciated.