# Question
Title: Algorithm to find the minimum (additional) popular votes to win the electoral college
So I'm thinking of a simple election prediction program to keep track of the minimum ballots the candidates must gain from the uncounted votes in order to win the election.

Assuming we are considering n states each with some different electoral votes. The candidate who has a majority receive all these votes from that state; and the one with the majority of electoral votes win the presidency. The number of electoral votes of a state is not necessarily proportional to its size of voters.

At a certain instance of vote counting, each candidate receives certain amounts of votes and there are still some uncounted in every states. I want to keep track of the minimum number of the remaining votes (regardless which state they are from) from these candidates to win the election until its secured.

---

So far the only algorithm in my head is to compute all the combinations of states to win the majority electoral votes, then weed out those which are not possible (the candidate won't win even he/she gains all the remaining votes). Compute the additional popular votes needed (win each of these states by exactly 1 vote) and then find\_min among them. But this would rather have redundant time complexity as it would take the same amount of time to compute no matter how many votes left...

# Answer
> 1 votes
Here's a hint (and a sketch).

I believe the problem is NP-hard and that it is equivalent to Subset Sum.

Reducing from Subset Sum: Suppose your instance has sum $S$ and values $v\_1, v\_2, \dots, v\_n$.

Create $n+1$ states, one with $S$ electorals that Party $A$ is guaranteed to win. The remaining $n$ states is such that $i$ has $v\_i$ electorals. These cost Party $B$ $v\_i$ to win.

Now, the optimum solution is $S$ which exists if and only if you have a yes instance for Subset Sum.

---
Tags: optimization, program-optimization
---


# Question
Title: Minimum cost problem of breaking containers in $O(n\log n)$
Can anyone kindly give me some hint on solving this?

There are $n$ water containers placed on the top of each other (container1 on top of container2, container2 on top of container3, ...), each with capacity $c\_i$ and initial water $a\_i$ ($a\_i\<c\_i$). In case of breakage of any container, all the water inside it will pour into the container below. Each container will break if the water inside it is more than its capacity. On the other hand, we can always break a container manually by paying the cost $p\_i$.

Provide an algorithm to find the minimum cost to break the $n$th container in $O(n\log n)$. Using a binary heap may be useful.

# Answer
> 2 votes
To solve this problem in $O(n\log n)$, we can use a min-heap.

Consider $s\_i = \Sigma\_{k=i}^{n}{a\_k}$ and $b\_i = s\_i + c\_i - a\_i$. You can see that if $b\_i \< s\_j$ for $j \< i$, by starting from $j$ and breaking every container from $j$ to $i$, container $i$ will break by the amount of water from the containers $j$ to $i$.

First set $cost = 0$ and $min = p\_i$. Then do the following for $i$ from $n$ to $1$:

1. Calculate $s\_i$.
2. Calculate $b\_i$.
3. Add $p\_i$ to $cost$.
4. Add $b\_i$ to the mean-heap and heapify it.
5. While $b\_j \< s\_i$ ($b\_j$ is the root of the heap): Remove the root and subtract $p\_j$ from $cost$.
6. If $cost \< min$, update $min$.

At every container, we know that if we start from that container, we need to break some of them and the rest will break by the water. When we remove a container from the heap, we can be sure that if we start from that container, the removed container will break by itself, and the total cost will be to break the rest, so we can subtract the cost of breaking the removed container from the total cost.

Since the while loop is run once for each container, and the for loop runs $n$ times, the total time will be $O(n\log n)$.

---
Tags: algorithms
---


# Question
Title: How to prove that the subset sum problem is polynomially reducible to the knapsack problem
I want to prove that the **subset sum** problem is polynomially reducible to the **Knapsack problem**.
Overall I want to show that **Knapsack is NP-complete**.
There are two parts to showing knapsack is NP-complete

1. knapsack is in NP
2. If I show that the subset sum problem is polynomially reducible to the knapsack.
Then since subset sum problem is known to be NP-hard. Knapsack is NP-Hard

Both 1) and 2) imply that Knapsack is NP-Complete

1. Is trivial as given any sequence of items we can verify the sum of their value
and weights in linear time. So the knapsack is in NP. Correct me If I am wrong here.

How do I approach 2)? I am not sure how to phrase the polynomial conversion
from the subset sum problem to the knapsack.

# Answer
The **subset-sum** problem is a pair $(S,k)$ and a question whether there exists $S' \subset S$ such that $\sum\_{s \in S'} s = k$.

The **knapsack** problem is a tuple $(w,v,W, V)$ that is weights, values, the knapsack capacity and the target value, and a question can you pick such a set of items $\mathcal{I}$ such that:

1. $\sum\_{i \in \mathcal{I}} w\_i \leq W$
2. $\sum\_{i \in \mathcal{I}} v\_i \geq V$

**Hint:** Given an instance $(S,k)$ of **subset-sum**, is there a way to set the weights and values of our items in the **knapsack**, so that these inequalities turn into a single equality related somehow to $k$?
> 1 votes

---
Tags: np-complete, knapsack-problems, subset-sum, polynomial-time-reductions
---


# Question
Title: Bit complexity of $n$-th Fibonacci number using matrix multiplication
I want to find the bit complexity of finding the $n$-th Fibonacci number using the matrix multiplication method. I know that it has complexity $O(\log n)$ if we assume that the standard operations have complexity $O(1)$, but if we now consider their true complexity, for example $O(n)$ for addition, I don't know how to calculate its true complexity. Can anyone help?

# Answer
> 1 votes
Let us recall that $$ F\_n = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}. $$ We compute the $n$-th Fibonacci number using the method of repeated squaring, applied to the $2\times 2$ matrix. The matrices encountered during this process are all of the form $$ A\_m = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^m = \begin{pmatrix} F\_{m+1} & F\_m \\ F\_m & F\_{m-1} \end{pmatrix}. $$ Repeated squaring runs in $\ell \approx \log n$ steps. In the $t$-th step, we square a matrix $A\_m$ with $m = \Theta(2^t)$, and possibly multiply it by the base matrix. Since the entries of $A\_m$ are $\Theta(m)$ bits long, squaring takes $\Theta(m\log m) = \Theta(2^tt)$ bit operations, and this is the dominant operation in the $t$-th step. The overall bit complexity is thus proportional to $$ \sum\_{t=1}^{\ell} 2^tt = \Theta(2^\ell \ell) = \Theta(n\log n). $$

---
Tags: time-complexity, matrices
---


title: Big O vs Theta Vs Omega?

text:
# Question
Title: Big O vs Theta Vs Omega?
I was given the following recursive formula: L(m)=16L(m/2)+m and I want to find for which function f, L(m) is theta of f.

In other words L(m) is big O of f and also small omega of f.

---

What I did until now? Nearly 95% of the job but still not sure whether this is an omega or big O or theta...

# Answer
Your problem can be solved using the Master theorem. In your case:

$a = 16, b = 2, f(n) = n$

$c\_{crit} = \log\_b a = 4$

$f(n) \in O(n^1)$ , is less than $O(n^{c\_{crit}})$. Thus using case 1, and the answer is

$L(n) \in \Theta(n^{c\_{crit}})$

$L(n) \in \Theta(n^4)$
> 0 votes

# Answer
Solution using series expansion: \begin{align} L(m) &= 16 \cdot L(m/2) + m \\ &= 16 \cdot (16 \cdot L(m/4) + m/2) + m\\ &= 16^{2}(16 \cdot L(m/8) + m/4) + 16 \cdot m/2 + m \\ &=...\\ &= 16^{t}\cdot L(2^{t}) + 16^{t-1} \cdot m/2^{t-1} + ... + 16 \cdot m/2 + m \\ \end{align}

Now, assuming that $L(1) = 1$ (although it is not mentioned explicitly in the problem statement, it is generally is the case).

Since, $t \leq \lceil \log m\rceil \leq \log m + 1$ (assuming $\log$ with base $2$)

we get, \begin{align} L(m) \leq m \cdot \frac{8^{t+1} - 1}{7} \leq m \cdot \frac{64 \cdot m^{3} - 1}{7} \leq 10 \cdot m^{4} = O(m^{4}) \end{align}

Since, $t \geq \lfloor \log m\rfloor \geq \log m - 1$.

we get, \begin{align} L(m) &\geq m \cdot \frac{8^{t+1} - 1}{7} \\ &\geq m \cdot \frac{8^{\log m} - 1}{7} \\ &= m \cdot \frac{ m^{3} - 1}{7} \\ &\geq \frac{ m^{4}}{14}, \quad \quad \textrm{ for } m \geq 2 \\ &= \Omega(m^{4}) \end{align}

The definition of $\Omega$ allows us to assume the threshold to be greater than any positive constant. Therefore, in the last second inequality, I assumed $m \geq 2$.

This proves that $L(m ) = \Theta(m^4)$
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Drawing a DPDA for the language $L=\{w\in\{a,b\}^*|n_a(w)=n_b(w)\}$ in Sipser's format
As I know $L=\\{w\in\\{a,b\\}^\*\mid n\_a(w)=n\_b(w)\\}$ is a deterministic context free language. I have drawn a push dawn automata for this language in the format of Sipser as the following

However, as you may know, in Sipser's format, the transition $$\varepsilon,$;\varepsilon$$ means that "don't read any thing from the input" and it doesn't mean "read $\varepsilon$ from the input". In Sipser's format this is a non-deterministic push down automata, since in deterministic one, we have that if there is a transition $$\varepsilon,$;\varepsilon$$ outgoing from the state $q\_1$ then it must not be an outgoing transition $$a,$;a$ $$ from that state.

Could you please help me to draw a DPDA for that language in Sipser's format?

# Answer
> 2 votes
I myself have found that DPDA as follows:

---
Tags: context-free, pushdown-automata
---


title: Permutation Array

text:
# Question
Title: Permutation Array
Hello I have a problem and would like a help to prove if it is P or not.

> Given an array $\mathcal{A}$ of integers. Is there a permutation of the elements of $\mathcal{A}$ such that, $\forall i \in \\{1, ..., |\mathcal{A}|-1\\} : \mathcal{A}\[i\] \neq \mathcal{A}\[i + 1\]$?

Could anyone give me some direction on how to show if it's Polynomial or not?

# Answer
> 1 votes
Suppose for simplicity that the number $n=2k$ of elements in the array is even. Let $a$ be the (one of the) most frequent element(s) and let $m$ the number of occurrences of $a$ in $\mathcal{A}$.

A polynomial time algorithm that solves your problem is the following: return "yes" if $m \le k$, otherwise return "no".

To see this notice that if $m\>k$ the answer is trivially now, since two occurrences $a$ must necessarily be adjacent in any permutation of $\mathcal{A}$.

If $m=k$ then the answer is trivially yes: just interleave the copies of $a$ with the other elements in $\mathcal{A}$.

If $m \< k$, then consider the elements of $\mathcal{A}$ in nonincreasing order of their number of occurrences. Create the permutation $B$ of $\mathcal{A}$ by first filling in all odd indices and then all even indices (indices start from $1$). For each distinct element $x \in \mathcal{A}$, let $i$ be the index of the first occurrence of $x$ in $B$. If $i=1$ or $i$ is even, then no pair of elements equal to $x$ can possibly be adjacent in $B$. Suppose then that $i$ is odd and that $i\>1$. In order for $B\[i-1\]$ to be equal to $x$, at least $k$ copies of $x$ would be needed, but at most $m \le k-1$ copies are available.

---
Tags: polynomial-time
---


# Question
Title: Name of binary encoding scheme for integer numbers
I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log\_2n$ average bits/symbol, thanks to a simple to compute variable length code. Basically it used $\log\_2n$ for some symbols and $\log\_2n - 1$ for some others.

Unfortunately all my Googling has failed me. I recall something similar to "variable length binary", but I keep ending on VLQ which are a different beast. Since I know your memory better than mine, can you help me?

# Answer
The technique idea is perfectly described in Yuval Filmus answer. Even if slightly different, it is called Truncated binary encoding in Wikipedia. I couldn't find an original source for that, apart from a mention in a patent, in this book, or in this Google API

Another mention can be found in the ACM ICPC 2011–2012, Northeastern European Regional Contest, November 27, 2011.
> 3 votes

# Answer
Suppose $k = 2^{n-1} + t$, where $0 \leq t \< 2^{n-1}$. Use the following to encode $z \in \\{0,\ldots,k-1\\}$:

* If $z \< 2^{n-1}-t$ then encode $z$ as its own $(n-1)$-bit encoding.
* Otherwise, write $z = 2^{n-1}-t + 2\delta+\epsilon$, where $\delta \in \\{0,\ldots,t-1\\}$ and $\epsilon \in \\{0,1\\}$. Encode $z$ at the $(n-1)$-bit encoding of $2^{n-1}-t+\delta$ followed by $\epsilon$.

Here is an example. Let $k = 11 = 2^3+3$. The encoding is as follows:

* $0 \to 000$.
* $1 \to 001$.
* $2 \to 010$.
* $3 \to 011$.
* $4 \to 100$.
* $5 \to 1010$.
* $6 \to 1011$.
* $7 \to 1100$.
* $8 \to 1101$.
* $9 \to 1110$.
* $10 \to 1111$.
> 2 votes

# Answer
Usually (a, b) is an open interval, excluding a and b, and \[a, b\] is a closed interval, including a and b. So $(2^{n-1}, 2^n)$ is the set of numbers from $2^{n-1} + 1$ to $2^n-1$.

To encode, subtract $2^{n-1}+1$ from a number x, leaving $0 ≤ x \< 2^{n-1}-1$. There are $2^{n-1}-1$ possible numbers, each with same probability, so you can use Huffman coding for just under n-1 bits on average. To be precise, you have $2^{n-1} - 2$ numbers encoded in n-1 bits, and one number encoded in n-2 bits, for an average of $n-1-1/(2^{n-1}-1)$ bits.

You could use arithmetic coding, which would be a tiny, tiny bit shorter on average with a very good implementation, but would be much much more complicated. Not worth it in this case; possibly worth it if you had say $1.5 \cdot 2^n$ different numbers to store and storage size is *very* important to you.
> -2 votes

---
Tags: coding-theory, encoding-scheme, binary
---


title: Universal hash functions - Proof

text:
# Question
Title: Universal hash functions - Proof
### Problem statement

Let $K$ be a set of keys with $|K| = n$ and define the index set $I = \\{0, \ldots, m-1\\}$. Now let $H = \\{h \mid h : K \to I\\}$, i.e. $H$ contains **all** hash functions which map the keys from $K$ to the set $\\{0, \ldots, m-1\\}$.

Prove or disprove that $H$ is universal.

### Attempt

Reiterating the definition

> A family of hash functions $H$ is universal if and only if for $\forall x, y \in K, (x \neq y)$ we have $\left|\\{h \in H : h(x) = h(y)\\}\right| = \frac{|H|}{m}$

I know you can construct specific families of universal hash functions and there are families which aren't universal. But if you consider *all* of them how would you know which part would outweigh which to decide if this statement still holds?

I'm probably going the wrong way so I would appreciate any help or hints!

# Answer
> 2 votes
Let us first look at the total number of hash functions in $H$. Since each key can be mapped to $m$ different indexes and there $n$ different keys. We get:

\begin{align} |H| = m^{n} \end{align}

Now, **without loss of generality**, let us consider the first two keys $x = k\_{1}$ and $y = k\_{2}$. We will compute the number of hash functions where $x$ and $y$ will collide i.e., $h(x) = h(y) = i$ for any $i \in \\{0,\dotsc,m-1\\}$.

\begin{align} |\\{h \in H : h(x) = h(y) = i\\}| = m^{n-2} \end{align}

Therefore, summing up for all $i \in \\{0,\dotsc,m-1\\}$, we get: $$|\\{h \in H : h(x) = h(y)\\}| = m^{n-1} = \frac{|H|}{m}$$

Hence, $H$ is a universal hash family.

---
Tags: hash, hashing
---


# Question
Title: If $A \leq B$, $B \leq \overline{A}$, and $B$ is r.e., is $A$ recursive?
We know that $A ≤ B$, $B ≤ \overline{A}$ and $B$ is recursively enumerable. Is $A$ recursive or not?

I tried negating whats given, but didn't achieve much. I know that from the very first inequality that $A$ is also recursively enumerable. I assumed whether $B$ is also recursive or not to maybe get to a contradiction of some sort, but I always ended up with "sometimes recursive, sometimes not".

# Answer
> 1 votes
Notice that $A \leq B \leq \overline{A}$. Since $B$ is r.e., $A$ is r.e., hence $\overline{A}$ is co-r.e. Since $A \leq \overline{A}$, $A$ is also co-r.e. Hence $A$ is recursive.

---
Tags: computability
---


# Question
Title: Where should "imply" be placed in this formalisation?
I have to formalize the following sentence:

> If any house is green then there exists a horse that is white.

I have formalized it the following way: $$\forall(x)(\mathit{house}(x)\rightarrow \mathit{green}(x))\rightarrow \exists(y)(\mathit{horse}(y) \rightarrow \mathit{white}(y))$$ A friend formalized it in a slightly different way: $$\forall(x)((\mathit{house}(x)\rightarrow \mathit{green}(x))\rightarrow \exists(y)(\mathit{horse}(y) \rightarrow \mathit{white}(y)))$$ Notice how in my formalisation, the right-most implication is separated from the $\forall(x)$, while in his formalisation the $\forall(x)$ encompasses the last implies as well.

I believe my way is correct because I think the sentence means that all houses being green implies that there's a white horse, and not that for any green house there's a white horse.

We haven't been able to reach a conclusion by ourselves, so any help would be appreciated!

# Answer
Here is how to break your statement up:

> If (any house is green) then (there exists a horse that is white).

An equivalent statement would be

> If some house is green, then some horse is white.

The condition is "there exists a house which is green", and the consequence is "there exists a horse which is white".

If we wanted a different quantifier for the condition, we would change it to

> If all houses are green, then some horse is white.

As you mention in the comments, this is more of a question in the semantics of the English language. This doesn't necessarily make it a bad question, since it highlights the need for a logical formalism which transcends such linguistic difficulties.

You can formalize the original statement as $$ (\exists x \\, \mathit{house}(x) \land \mathit{green}(x)) \to (\exists y \\, \mathit{horse}(y) \land \mathit{white}(y)). $$ The prenex form is $$ \forall x \exists y \\, (\mathit{house}(x) \land \mathit{green}(x)) \to (\mathit{horse}(y) \land \mathit{white}(y)), $$ or equivalently, $$ \forall x \exists y \\, \lnot \mathit{house}(x) \lor \lnot \mathit{green}(x) \lor (\mathit{horse}(y) \land \mathit{white}(y)). $$
> 1 votes

---
Tags: formal-methods
---


# Question
Title: Splay trees: why are depths of nodes on the access path halved?
The original paper describing splay trees Self-Adjusting Binary Search Trees by Sleator and Tarjan claims that:

> Splaying not only moves x to the root, but roughly halves the depth of every node along the access path.

What is the intuition for this claim? The paper includes some figures (splaying in a tree of all zig-zigs or all zig-zags) and while I can see at a high level that splaying helps other parts of the tree, it's not really clear to me where the halving comes from?

# Answer
> 1 votes
Nobody has answered this question yet, and I can give some hints how to solve it. I would much rather post this as a comment, but I can't since I don't have enough reputation.

So here is a link to the original paper: https://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

The basic idea is looking at zig-zig and zig-zag (zig only happens once when the parent of x is the root!):

1. Notice that if a node was in the search path before x was pushed to that position, it is now either in A or in B.
2. Notice that all nodes in A and B have at least **1 depth less** than before the zig-zig operation

1. Notice that if a node was in the search path before x was pushed to that position, it is now either in B or in C.
2. Notice that all nodes in B and C have at least **1 depth less** than before the zig-zag operation

Now just think about how many zig-zig and zig-zag operations there are for a node with depth d in the search path.

---
Tags: data-structures, trees, binary-trees, splay-trees
---


title: Algorithm for checking hour periods

text:
# Question
Title: Algorithm for checking hour periods
I have the following array that contains a day and the scheduled hours, i wanna know how to check if the given time falls in a period of that array, for example let's say the current time is 20:50 how to know if it's in that scheduled array?

```
{
   "monday":[
      "00:00", // Period number 1
      "00:15",
      "00:30",
      "00:45",
      "01:00",
      "01:15",
      "01:30",
      "01:45",
      "02:00",
      "02:15",
      "02:30",
      "02:45",
      "03:00",
      "03:15",
      "03:30",
      "03:45",
      "04:00",
      "04:15",
      "04:30",
      "04:45",
      "05:00",
      "05:15",
      "05:30",
      "05:45",
      "06:00",
      "06:15",
      "06:30",
      "12:30", // Period number 2
      "12:45",
      "13:00",
      "13:15",
      "13:30",
      "13:45",
      "14:00",
      "19:30", // Period number 3
      "19:45",
      "20:00",
      "20:15",
      "20:30",
      "20:45",
      "21:00",
      "21:15",
      "21:30",
      "21:45",
      "22:00",
      "22:15",
      "22:30",
      "22:45",
      "23:00",
      "23:15",
      "23:30",
      "23:45"
   ],
}

```

# Answer
As @D.W. is suggesting, you can use the binary search technique which takes $O(\log n)$ time, where $n$ is the number of elements in the list.

Furthermore, if you want to know the corresponding period, there are many ways to it. For example, You can make a separate array of periods and then perform a binary search on it.

---

Furthermore, you can improve the query time to $O(1)$ by maintaining an array of size 1440 = 24x60 as follows:

The $i^{th}$ entry of the array corresponds to the time $a:b$ where $a = i /60$ and $b = i \mod 60$. And, the value at $i^{th}$ entry is $1$ if time $a:b$ is in the list else it is $0$. Therefore, you can check in $O(1)$ time if an entry exist in the array.

To know the period in $O(1)$ time, you can maintain additional information in the array about the period in which the time lies. For example: an $i^{th}$ entry lies in $2^{nd}$ period. So basically it would be a two-dimensional array.
> 2 votes

# Answer
Use binary search. This will find whether the time is in the list, and if it is not, the entry immediately before and after that time.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Should i work with tree representation as an array of nodes and an array of edges
Here is the problem, i have a graphical component that displays a tree. It takes as input an array of nodes and array of edges(eg:an edge has a source and target).

I will be performing complex tasks, such as building the tree dynamically from user input, removing nodes adding nodes, hiding a node's children, i would need to traverse certain paths and collect information, and all things of tree such as getting children of a node or get all leafs etc.

I have two solutions: either manipulate directly both arrays i already tried with hiding a node's children and it was fine.

Or map the two array into a tree structure and manipulate the tree to do what i want since there will lots of ready algorithms then map it back to the two arrays.

The first solution sounds better and easier at first, however if things get more complex i will implement each function i need (such getting leafs etc) and the diffculty is manupilating a tree in a non tree representstion.

The second solution is better since its a tree there are a lot of algorithms but there is more work on mapping back and forth on each addition or deletion.

What do you think is better? (A compromise between being it easier fof me and performance)

# Answer
> 1 votes
In the unforgettable words of Donald Knuth

> Premature optimization is the root of all evil.

Your best option is as follows. Do what is simplest for you, while maintaining a good abstraction with good encapsulation. A good abstraction (a well-defined and thought out API) will make it easy for you to change and improve the underlying implementation in the future while not having to change the rest of the application.

When (or really *if*) you discover that the application is too slow, *then* you start changing the underlying implementation, but only after a proper complexity analysis.

It is very difficult (if not impossible) to say in advance what will be the bottleneck of the application, so it's best to leave this decision until you actually know.

---
Tags: trees, search-trees
---


# Question
Title: Find amount of elements greater then number k in a BST
I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K.

I found it problematic as there are elements which might be greater then K but wont be found by traveling constantly to the right child, as there might be elements that are greater then K in the left sub-tree.

The Algorithm must be executed in a run-time complexity of O(h), while h is the height of the tree.

# Answer
You can do it in $O(h)$ time only if you know some additional information at every node about the subtree rooted at that node. (Maybe @greybeard is suggesting the same in the comments). For example:

Suppose $x$ is any node in the tree, and suppose you know the number of nodes in the sub-tree rooted at $x$. Let us call this variable "x.total". Then, the following algorithm works in $O(h)$ time:

```
fun(root,K) // It returns the number of elements greter than K
---if (root = NULL)
------- return 0;
---if(root.value > K)
-------- return fun(root.left_child,K) + 1 + root.right_child.total
---else
-------- return fun(root.right_child,K)

```

The correctness of the above algorithm follows due to the fact that the given tree is a Binary Search tree (BST).

Moreover, you can maintain the extra information (i.e, x.total) for all nodes by traversing the tree only once. You can use DFS procedure for the same. Thus, the preprocessing time is only $O(n)$. And, the query time complexity would be just $O(h)$.

---

If you do not store any kind of extra information, then you can not do better than $O(n)$. For example: suppose the tree contains only positive elements and the query is for $K = 0$. Then, this query is the same as finding the total number of elements in the tree, which requires you to traverse every node and it essentially requires $\Omega(n)$ time.
> 1 votes

---
Tags: time-complexity, search-algorithms, binary-search-trees
---


# Question
Title: CLRS Question 8-6 Lower bound on merging sorted lists
I'm doing the CLRS Problems and there's a part I'm having trouble following.

The question is: Part a) Given 2n numbers, compute the number of possible ways to divide them into two sorted lists, each with n numbers.

Part b) Using a decision tree and your answer to part (a), show that any algorithm that correctly merges two sorted lists must perform 2n−o(n) comparisons.

Part a) makes senses to me. The first line to the solutions of part b) states any decision tree to merge two sorted lists must have at least $2n$ choose $n$ leaf nodes.

I don't follow why this is. In particular, what is each branch comparing to get to this result? And what does each leaf node represent?

# Answer
> 3 votes
Let us consider any comparison-based algorithm for merging two ordered lists $A,B$ of length $n$, focusing on the case in which all $2n$ numbers are distinct. When the algorithm terminates, the results of the comparisons determine the merged list. Stated differently, if we describe the algorithm as a decision tree, then each leaf is labelled with the merged list, which is some permutation of the elements in $A \cup B$. Since all elements are different, each possible such permutation must be represented as some leaf.

Since the lists $A = (a\_1,\ldots,a\_n)$ and $B = (b\_1,\ldots,b\_n)$ are ordered, the permutation $\pi$ labeling each leaf must satisfy the following property: if $i \< j$ then $a\_i$ appears before $a\_j$ and $b\_i$ appears before $b\_j$. This implies that $\pi$ is determined from the set of indices containing elements of $A$. There are $\binom{2n}{n}$ such possible sets, and all corresponding permutations can actually happen, as can be seen by assigning the element in the $k$th the number $k$. For example, if $n = 2$ then the possible orders are:

1. $a\_1,a\_2,b\_1,b\_2$ – achieved for $A = 1,2$ and $B = 3,4$.
2. $a\_1,b\_1,a\_2,b\_2$ – achieved for $A = 1,3$ and $B = 2,4$.
3. $a\_1,b\_1,b\_2,a\_2$ – achieved for $A = 1,4$ and $B = 2,3$.
4. $b\_1,a\_1,a\_2,b\_2$ – achieved for $A = 2,3$ and $B = 1,4$.
5. $b\_1,a\_1,b\_2,a\_2$ – achieved for $A = 2,4$ and $B = 1,3$.
6. $b\_1,b\_2,a\_1,a\_2$ – achieved for $A = 3,4$ and $B = 1,2$.

Therefore the decision tree must contain at least $\binom{2n}{n}$ leaves. Since it is binary (we assumed that no two elements are equal), its depth must be at least $\log\_2 \binom{2n}{n}$. Stirling's approximation shows that $\binom{2n}{n} = 4^n/\Theta(\sqrt{n})$, hence $\log\_2 \binom{2n}{n} = 2n - \Theta(\log n)$.

---
Tags: algorithm-analysis, lower-bounds
---


# Question
Title: maximum Hamilton cycle and NP-completeness
we know max tsp (maximal Hamilton cycle) is NP-Hard. is there any decision version for this problem to conclude this is NP-Complete?

# Answer
A decision problem is NP-complete iff it is in NP and it is NP-hard.

The decision version of Max-Hamiltonian cycle would be "given a weighted graph $G$ and a value k, decide whether there exists a Hamiltonian cycle of weight at least $k$ in $G$".

Your problem is clearly in NP (since a yes-certificate is the sought Hamiltonian cycle). Moreover it is also NP-hard since it is a generalization of the classical Hamiltonian cycle problem on unweighted graphs (simply set all edge weights to $1$ and $k=n$ to obtain an instance of your problem).

We can then conclude that this problem is NP-complete.
> 2 votes

---
Tags: complexity-theory, computability, np-complete, np
---


title: Cubic Cycle is Np-Complete

text:
# Question
Title: Cubic Cycle is Np-Complete
HAMCYCLE = {\<"G"\> : G is a simple undirected graph that has a Hamiltonian cycle}
CUBIC CYCLE = {\<"G"\> :G is a simple undirected graph that contains a simple cycle of length at least |V (G)|^1/3}

The reduction i figured out is : G has a ham-cycle \<==\> G has a cubic cycle of a given length(V^1/3). Prooving ==\> part is simple as we have to show that if a cycle of V exists, then in G a cycle of V^1/3 exists. But i got stuck in proving the other direction. Any insights would be helpful.

# Answer
The reduction that you suggested does not work. For example, consider a graph $G = (V, E)$ that consists of 9 disjoint triangles ( triangles that do not touch each other). $G$ has a triangle which a hamiltonian cycle of length $3 = 27^{\frac{1}{3}} = |V|^{\frac{1}{3}}$, yet $G$ has no hamiltonian cycle.

A simple correct reduction operates as follows. Given an undirected graph $G = (V, E)$, the reduction outputs $G$ with additional $|V|^3 - |V|$ isolated vertices. I leave the details to you.
> 1 votes

---
Tags: algorithms
---


# Question
Title: How to find mean ,max ,min in constant time?
I was asked to be able to find minimum, maximum and mean of a large array in constant time. I used 3 variables to track these statistics and updated them on every insert operation. I don't feel like it is the correct answer or maybe there is more nuance. Given that *nothing was said about extra space*, is this the simplest(and correct) way to do it ?

# Answer
If you are just given an array and asked to find these statistic there there is no way to do that (unless the size of the array is upper bounded by a constant). An easy way to convince yourself that this is true is noticing that in $O(1)$ time you can only access $O(1)$ entries of the array. Then the maximum, minimum, or median could be in the unread entries (notice that you can safely assume that any $O(1)$-time algorithm always accesses the returned entry).

You talk about "insert operations" which makes me thing that you were actually asked to design a data structure that supports some set of operations, among which there are insertions and reporting the above statistics. If this is the case then the answer depends on how what the other operations are and how much time do you want to spend on those.

If the only updates to the array are insertion then it suffices to keep track of the number of elements, their sum, and the maximum and minimum element after each insertion. This will require $O(1)$ time per insertion and $O(1)$ time to report the statistics.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, space-complexity
---


# Question
Title: How would I go about calculating the index field / tag field?
For index field I got '9' because 2^(9) = 512 words. But I'm stuck on what the formula for calculating the tag field is... any ideas?

Given a cache that holds 512 words and block size of one word. Assume 32-bit addresses. The index field is \____ bit. The tag field is \____ bit.

# Answer
Okay let's go step by step.

The cache has $512$ words, each block is $1$ word. Hence the cache has $512$ blocks. Since you have not mentioned anything about ways(not an n-way associative cache) and are actually demanding index bits(not a fully associative cache) I am assuming it is a direct-mapped cache. So now since we had $512$ blocks(/lines) we need $9$ bits($log\_2{2^9}$) to uniquely identify a block, so we have $9$ index bits. Now assuming the memory is byte organised and the size of a word is $4$ bytes, we need $2$ bits to uniquely identify a byte from the $1$ word block. Now we have $32 - 9 - 2=21$ bits remaining and they are the tag bits.

Hope it helps!
> 0 votes

---
Tags: computer-architecture
---


title: Time complexity of Tsp using DP

text:
# Question
Title: Time complexity of Tsp using DP
this is the recursion formula for problem :

```
C(i,S) = min { d(i,j) + C(j,S-{j}) }

```

In fact, when I tried to implement it as a code, the following code came to my mind:

```
int TSP(i, S){
    if(S.size == 0)
    return dist(start_vertex,i)
min = inf
cost = inf
  for(int j=0;j<S.size;j++)
     {
      cost = dist(i,S[j])+TSP(j,S-{j});
      if(cost < min)
       min = cost;
      }
global_cost+=min;
return min;
}

```

Because this `for` compares n times to find the minimum, it means its recursion as:

```
T(n) = nT(n-1)+n ==> T(n) = O(n!)

```

Because each step we compare to find the minimum size of size S is, of course, the code is factorial. So what does it have to do with the subset and So why the complexity of time in the form of (n^2\*2^n)? And what is the proof of its time complexity?

# Answer
Your algorithm is known as the Held–Karp algorithm, and is described on Wikipedia, and also mentioned on the Wikipedia page on the traveling salesman problem.

Your implementation of the algorithm is wasteful. Using memoization, there are only at most $n2^n$ inputs. Since TSP runs in time $O(n)$ ignoring recursive calls, when using memoization, the total running time will be $O(n^22^n)$.
> 0 votes

---
Tags: algorithms, graphs, time-complexity, traveling-salesman
---


# Question
Title: Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$
> Prove that $\mathsf{P} \neq \bigcup\_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$.
> Hint: Assume that there is an equality, show that this implies $\mathsf{DTIME}(n^{\log n})\subseteq \mathsf{P}$ via a padding argument.

I proved that $L'=\\{x\\#1^{|x|^{\log|x|}}\mid x\in L\\}$ is in $\mathsf{P}$ but I'm not sure how to conclude that $L\in\mathsf{P}$, or how do I get the contradiction to the assumption.

# Answer
> 3 votes
The proof is by contradiction. We assume that $\mathsf{P} = \bigcup\_{k=1}^\infty \mathsf{DSPACE}(\log^k n)$, and reach a contradiction.

Let $L$ be any language in $\mathsf{DTIME}(n^{\log n})$. Thus there is a Turing machine for $L$ which runs in time $n^{C\log n}$, and in particular, uses space at most $n^{C\log n}$. Let $L' = \\{ x10^{|x|^{C\log |x|} - |x| - 1} : x \in L \\}$. Then $L' \in \mathsf{P}$, and so $L' \in \mathsf{DSPACE}(\log^k n)$, for some $k$. In terms of the true input size $m$, we have $n = m^{C\log m}$, and so $L \in \mathsf{DSPACE}(\log^k (n^{C\log n})) \subseteq \mathsf{DSPACE}(\log^{2k} n) \subseteq \mathsf{P}$. This contradicts the time hierarchy theorem.

---
Tags: complexity-theory, time-complexity, space-complexity
---


# Question
Title: Is L = { <M,w> | M is a TM and L(M)={w}} turing recognizable? And its complement?
My approach is to prove that the complement is turing recognizable and undecidable, so that we can prove L not recognizable. But what is the complement of such L?

# Answer
> 2 votes
Intuitively, $L$ is not recognizable as given $\langle M, w\rangle$, to know Whether $M$ accepts $w$ we need to simulate the run of $M$ on $w$, but $M$ need not to halt on $w$, so the simulation may not halt. This obviously smells like the halting problem. Even if we somehow know that $M$ accepts $w$, how can you check whether $w$ is the only word in $L(M)$? What about the other infinite words over $M$'s alphabet? It seems impossible to go over all of these words and verify that all of them are not in $L(M)$ and then halt.

If you consider the complement of $L$, $\overline{L} = \\{ \langle M, w\rangle: L(M)\neq \\{w\\} \\}$, you get the same problamatic issue. How can you check whether $L(M)$ does not include $w$?

So intuitively, both $L$ and $\overline{L}$ are not recognizable. Formally, to show that a language $B$ is not recognizable, we show that there a non-recognizable $A$ that reduces to $B$. We consider the non-recognizable language $A = \overline{Halt\_{TM}} = \\{ \langle M, w \rangle: \text{M does not halt on w}\\}$, then we show that there are mapping reductions, one from $A$ to $L$, and the other is from $A$ to $\overline{L}$:

* $\overline{Halt\_{TM}} \leq\_m \overline{L}$: we need to show that there is a reduction from $\overline{Halt\_{TM}}$ to $\overline{L}$. Consider the reduction that operates as follows. On input $\langle M, w\rangle$, the reduction outputs $\langle K, w\rangle$, where $K$ is a machine that operates as follows. On input $x$ for $K$, the machine $K$ simulates the run of $M$ on $w$. If $M$ halts on $w$ (if the simulation halts), then $K$ accepts $x$ only if $x = w$, and otherwise $K$ rejects $x$. If $M$ does not halt on $w$, that is the simulation does not halt, then clearly $K$ does not halt. The reduction is correct: if $\langle M, w\rangle \in \overline{Halt\_{TM}}$, then $M$ does not halt on $w$. Hence, $K$ does not halt on any input $x$, and thus $L(K) = \emptyset \neq \\{w\\}$. Meaning that $\langle K, w\rangle \in \overline{L}$. Conversely, if $\langle M, w\rangle\notin \overline{Halt\_{TM}}$, then $M$ halts on $w$. Hence, $K$ halts on every input $x$, but accepts only if $x = w$, and so $L(K) = \\{ w\\}$. Thus, $\langle K, w\rangle \notin \overline{L}$.
* $\overline{Halt\_{TM}} \leq\_m L$: we need to show that there is a reduction from $\overline{Halt\_{TM}}$ to L. Consider the reduction that operates as follows. On input $\langle M, w\rangle$, the reduction outputs $\langle K, 1\rangle$, where $K$ is a machine that operates as follows. On input $x$ for $K$, the machine $K$ checks whether $x = 1$. If $x = 1$, $K$ accepts. If $x\neq 1$, $K$ simulates the run of $M$ on $w$. If $M$ halts on $w$ (if the simulation halts), then $K$ accepts $x$. If $M$ does not halt on $w$, that is the simulation does not halt, then clearly $K$ does not halt. The reduction is correct: if $\langle M, w\rangle \in \overline{Halt\_{TM}}$, then $M$ does not halt on $w$. Hence, for every input $x\neq 1$ for $K$, $K$ does not halt, and thus $L(K) = \\{1\\}$. Meaning that $\langle K, 1\rangle \in L$. Conversely, if $\langle M, w\rangle\notin \overline{Halt\_{TM}}$, then $M$ halts on $w$. Hence, $K$ halts on every input $x$ (as when $x\neq 1$, the simulation of the run of $M$ on $w$ halts), and accepts. Hence, $L(K) = \Sigma^\* \neq \\{ 1\\}$. Thus, $\langle K, 1\rangle \notin L$.

Final note: I have assumed w.l.o.g that $\overline{L}$ does not contain words that are not a description of a pair $\langle M, w \rangle$. This is okay, as a reduction (a machine) can easily check whether an input is of the form $\langle \text{ machine, word}\rangle$. If the input of the reduction is not of this form, then the reduction outputs some constant word that is in the language that we're reducing to. So for readability issues, I sticked to this assumption.

---
Tags: turing-machines, computability
---


# Question
Title: Calculate the sum of all sub-arrays with given indices
I am new to Algorithms and Competitive Coding. I have a problem as follow:

For this problem, the time limit is 1 second so brute force is not a good way to solve. The only way I think must be Dynamic Programming or any other way which can run in less than O(nlogn) or even O(n) and the limit memory is 256 Mb.

Initially, I have a simple approach to dynamic programming as follows: I just create a table size `nxn` and fill it with numbers that represent the minimum element from the index I to index j (i \<= j). After that, I refer to the given indexes (ik and jk) on the table and add them up.

However, as submitting the code as the previous approach, I get 3 cases of wrong answers and even runtime errors. The runtime error is due to the input constraint: up to 10^6 elements which cause the exceed of memory (10^6 * 10^6 = 10^12, which is very large). I also get accepted status on 3 tests however, the number of wrong answers makes me quite confused. I really need your help to check and update the algorithms.

Sample test case:

```
Input:

16

2 4 6 1 6 8 7 3 3 5 8 9 1 2 6 4

4

1 5

0 9

1 15

6 10

Output:

6

```

void make_table()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = i; j < n; j++)
        {
            if(i == j)
            {
                Table[i][j] = arr[i];
            }
            else
            {
                Table[i][j] = min(arr[j], Table[i][j - 1]);
            }
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    make_table();
    ll sum = 0;
    cin >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;
        sum += Table[x][y];
    }
    cout << sum << endl;
}
```

# Answer
You can use the concept of **segment trees**. Check this link: https://en.wikipedia.org/wiki/Segment\_tree and https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

The above link works for finding the sum of all the elements in a given range \[i,j\]. However, you can use the same approach to find the minimum element in the range \[i,j\] in $O(\log n)$ time. The idea is that you can break the range \[i,j\] into $O(\log n)$ smaller ranges, and for each of these ranges you already know their minimum values via some binary tree (built during pre-processing step). Thus, you can take the minimum over all these small ranges, and it will give the overall minimum in the range \[i,j\] in $O(\log n)$ time.

---

Building the binary tree comes under the pre-processing step and it will only take $O(n)$ time.
Also, there are $m$ queries and each query takes $O(\log n)$ time. The overall time complexity would be $O(n + m \log n)$. Since $m \< n$, the overall complexity is $O(n \log n)$.
> 1 votes

---
Tags: algorithms, dynamic-programming, c++
---


title: Subclass specification

text:
# Question
Title: Subclass specification
From http://web.mit.edu/6.031/www/fa19/classes/12-interfaces-enums/#implementing\_generic\_interfaces

"That means B is only a subtype of A if B’s specification is at least as strong as A’s specification. When we declare a class that implements an interface, the Java compiler enforces part of this requirement automatically: for example, it ensures that every method in A appears in B, with a compatible type signature. Class B cannot implement interface A without implementing all of the methods declared in A.

But the compiler cannot check that we haven’t weakened the specification in other ways: strengthening the precondition on some inputs to a method, weakening a postcondition, weakening a guarantee that the interface abstract type advertises to clients. If you declare a subtype in Java — implementing an interface is our current focus — then you must ensure that the subtype’s spec is at least as strong as the supertype’s."

However, later they define a generic class Set with method contains(E e) and a non-generic subclass CharSet with method contains(Character e). Does this count as strengthening pre-condition? If so, does it contradict the above?

# Answer
`CharSet` is not a subtype of `Set<E>`, but it *is* a subtype of `Set<Character>`. If you compare the signatures of the `contains` methods for `Set<Character>` and `CharSet`, you'll see that the preconditions are identical.

It might be helpful to imagine that `Set` is not a type and is not meaningful on its own; you have to instantiate the generic parameter to obtain a type.
> 2 votes

---
Tags: programming-languages, software-engineering, object-oriented
---


# Question
Title: Prime factorization for compressing streams of random numbers
We covered compression/encoding/decoding of data streams very briefly last lecture and I had an odd idea: Let's say I have a stream of random 8-Bit numbers. Now the probabilty to encounter each number is 1/256. If I prime factorize each number though I get a stream of prime numbers where I can calculate the probabilty of encountering a specific prime number by looking at how often it appears in all prime factorizations of all 8-Bit numbers. Here's a couple of issues straight away:

* 0 and 1 are special cases, they dont have a prime factorization per-se
* the transform is not invertible, you'd have to use seperation symbols

One way to "solve" both issues is to include 1 as a prime number and encode a number x as a prime factorization of number (x + 1) which allows for 0 and 1 and still fits into 8-Bits because the largest 8-Bit prime is 251. The 1 at the beginning of each prime factorization also serves as a separation symbol.

Could I use this way to somehow ("efficiently") encode a random stream of data?

# Answer
> 4 votes
No. If it is a stream of random bytes, where each byte is independently and uniformly distributed, it cannot be compressed. It doesn't matter what method you're using. You're trying to do something analogous to inventing a perpetual motion device; we don't have to look at the detailed blueprint to know that it won't work.

---
Tags: data-compression, entropy, primes
---


title: Finding right quotient of $a^*b^*/b^*.$

text:
# Question
Title: Finding right quotient of $a^*b^*/b^*.$
I argue that right quotient of $a^\*b^\*/b^\*$ is $a^\*$,is that true?any help or argument to accept or reject my argument will be appreciated:)

# Answer
> 1 votes
$a^\*b^\* / b^\* = \\{ w \ | \ \exists \ x, \ x \in b^\* \land wx \in a^\*b^\*\\} = a^\*b^\*$. This is because $wx \in a^\*b^\* \text{ AND } x \in b^\*$ means $w$ is of the form $a^ib^j$ for some $i,j \in \mathbb{N} \cup \\{0\\}$. Finish it off now.

---
Tags: formal-languages, automata, regular-languages
---


# Question
Title: Does throughput includes CPU idle time also?
I have 3 processes P1,P2,P3 having gantt chart as follows =\>

Now, CPU remains idle in 0 - 2 sec and 44 - 47 seconds as I/O is taking place.

Does, this affect throughput as 3 processes can be completed in total 47 sec .

Hence, throughput = 3 / 47 .

Is this correct or am i missing something ?

# Answer
You are correct!

According to the defenition Throughput (in case of scheduling in OS) is :

> Number of processes that can be completed in a unit of time.

The process can use both the CPU or the I/O operations. So the I/O time and idle times and CPU time are calculated in throughput.

**Note**: CPU idle time is not calculated when you want to have the Utilization of the CPU. So in your case CPU Utilization is 42/47.
> 1 votes

# Answer
But one more thing I want to add, let say first process is available at 2 units then time period from 0 to 2 will not be considered in CPU total time while computing throughput. As processes are not yet available.

---

Throughput actually includes total time where processes are available and executing doing either computation (in CPU) or I/O.
> 0 votes

---
Tags: operating-systems, process-scheduling
---


title: Why is XML hard to parse?

text:
# Question
Title: Why is XML hard to parse?
I was chatting with a friend about my love/hate relationship with XML. He made the comment that, "xml is broken primarily because parsers for recursive self-defined document are basically impossible to get right."

I've heard the critique that XML is very difficult to parse before, but my understanding is limited to difficulties around balancing memory usage (i.e. streaming) and the impedance mismatch between XML and most programming languages (such as not supporting basic primitives like an array).

What is unique about XML as a self-defining document that makes parsing difficult?

# Answer
Thanks for posting your question! See, normally parsers implement huge usage of regex or regular expressions. But regular expressions are just for text manipulation and cannot count. Because of this defect of regular expressions, it becomes quite difficult to balance number of open and close tags. Hence, software engineers have to do some extra work to deal with it. You can read more about regular expressions at Mozilla Developer Network Docs and at this post on Medium.
> -1 votes

---
Tags: parsers
---


# Question
Title: Explanation of O(n2^n) time complexity for powerset generation
I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward:

```
def power_sets(A):
    """Returns the power set of A as a list of lists"""

    if len(A) == 0:
        return [[]]

    else:
        ps_n1 = power_sets(A[:-1]) # Powerset of set without last element
        # Add nth element to each subset of the powerset of n-1 elements
        ps_n = [sub + [A[-1]] for sub in ps_n1]

        # Combine the two sets and return
        return ps_n1 + ps_n

```

It's clear that the space complexity is $O(n2^n)$, since there are $n$ items in the set, and each element is in half of the $2^n$ sets.

However, the book that I'm working from says the time complexity is also $O(n2^n)$, which makes perfect intuitive sense, but I'm having a hard time justifying it mathematically.

Other than by saying "there are x number of items to mess with, so time complexity is at least as much", can anyone offer an explanation of the runtime analysis based on the runtime of the statements in my algorithm?

This answer pretty much only says that the runtime is such because of the space complexity (not very satisfying, but as an aside--can the runtime ever be better than the space complexity?)

I saw this answer, but to be honest it is a bit difficult to understand. It seems to suggest in the last line that the runtime is $O(n^2\*2^{n!})$ (since (I think) $|P\_i| = 2^i$), and that doesn't seem right either.

I tried drawing out the call tree and that didn't help, as there are only $n-1$ recursive calls made, and from what I can tell each spends $O(n^2)$ time.

Anyway, can someone offer a compelling explanation for this runtime?

# Answer
> 5 votes
Observe that:

$T(N) = 2T(N-1) + 2^{N-1}$

$T(1) = 2$

Note that the entire runtime, our algorithm only spends time generating more data. Therefore, our function T represents both the amount of time that the function spends running on an input of size N, and also the amount of data it generates from an input of size N.

We have $2T(N-1)$ because we first make the recursive call, and the following line makes a copy of all that data again in preparation to tack on the element we left out in the recursive call. We tack on exactly $2^{N-1}$ copies of the element we intentionally left out so that's where the last term comes from. Finally, T(1)=2 because with 1 element, we return 2 possible subsets (the entire set and the empty set).

Unrolling this recurrence we have:

$T(N)=2T(N-1)+2^{N-1}$

$\quad \quad =2(2(T(N-2)+2^{N-2})+2^{N-1}$

$\quad \quad =2(2(2(T(N-3)+2^{N-3})+2^{N-2})+2^{N-1}$

$...$

$\quad \quad = 2^N + (N-1)\*2^{N-1}$

$\quad \quad = O(N\*2^N)$

# Answer
> 0 votes
Basically we are checking whether each element is present or not. eg. if we say set=\[1,2,3\] and one of its subset is \[1,2\] .i.e 1 is present, 2 is present and 3 is absent, so combination is \[1,1,0\], present,present,absent. generate all combinations from \[0,0,0\] to \[1,1,1\]. total 2^3= 8 combinations. ie 2^n

while generating subsets you have to go through all elements ie. \[1,2,3\] and compare them with these combinations ie.\[0,0,0\] to \[1,1,1\]..so total n\* 2^n operations

---
Tags: time-complexity, asymptotics, runtime-analysis, recursion, sets
---


# Question
Title: NP-completeness of Induced disjoint paths
In graph theory, it is well-known to be NP-complete the problem of given a set of $k$ pairs of source-sink, deciding whether there exists $k$ vertex-disjoint paths connecting these pairs.

Our problem is a variant in which the requirement of being vertex-disjoint is replaced by being induced.

A set of $k$ paths is said to be induced if:

1. They are vertex-disjoint.
2. Each one is itself an induced path.
3. No edge connects two vertices of two different paths.

> **Input**: A graph $G(V,E)$ and $k$ pairs of source-sink $\\{(s\_1,t\_1),\dots,(s\_k,t\_k)\\}$
>
> **Output**: **YES** if there exists (a set of) $k$ induced paths connecting $s\_i$ to $t\_i$ for every $1\leq i\leq k$, **NO** otherwise.

Is this problem NP-complete?

# Answer
Your problem is NP-hard (and so NP-complete), by reduction from 3SAT.

Consider a 3SAT instances with variables $x\_1,\ldots,x\_n$ and clauses $C\_1,\ldots,C\_m$.

For each variable $x\_i$, there are four vertices $a\_i,T\_i,F\_i,b\_i$, connected as follows: $a\_i-T\_i-b\_i$ and $a\_i-F\_i-b\_i$.

For each clause $C\_j = \ell\_{j,1} \lor \ell\_{j,2} \lor \ell\_{j,3}$ (where $\ell\_{j,1},\ell\_{j,2},\ell\_{j,3}$ are literals), there are five vertices $c\_j,L\_{j,1},L\_{j,2},L\_{j,3},d\_j$, connected as follows: $c\_j-L\_{j,k}-d\_j$ (for $k=1,2,3$). Additionally, if $\ell\_{j,k} = x\_i$ then we connect $L\_{j,k}$ with $F\_i$, and if $\ell\_{j,k} = \bar{x}\_i$ then we connect $L\_{j,k}$ with $T\_i$.

The source-sink pairs are $(a\_i,b\_i)$ (for $i=1,\ldots,n$) and $(c\_j,d\_j)$ (for $j=1,\ldots,m$).

Each $a\_i-b\_i$ path corresponds to a truth assignment of $x\_i$, and each $c\_j-d\_j$ path corresponds to a choice of a satisfied literal in $C\_j$.
> 3 votes

# Answer
Another way to see that this problem is NP-hard would be to construct a reduction from the "$k$ vertex-disjoint paths" problem mentioned in the question itself. The reduction takes the input graph $G$ and subdivides every edge — i.e. a new vertex $v\_{ab}$ is introduced for each edge $ab$ of $G$ and the the edge $ab$ is replaced with the path $a,v\_{ab},b$ — to obtain a new graph $G'$. Note that $G'$ is a bipartite graph with partite sets $V(G)$ (the *old* vertices) and $\\{v\_e\colon e\in E(G)\\}$ (the *new* vertices), with the additional property that every new vertex has degree 2. It is quite straightforward to see that there is a set of $k$ vertex-disjoint paths in $G$ (between the given terminals) if and only if there is a set of $k$ induced paths (between the same terminals) in $G'$. For each path $P=a\_1,a\_2,\ldots,a\_t$ in $G$, let $P'$ be the path $a\_1,v\_{a\_1a\_2},a\_2,v\_{a\_2a\_3},a\_3,\ldots,a\_{t-1},v\_{a\_{t-1}a\_t},a\_t$ in $G'$. If $P\_1,P\_2,\ldots,P\_k$ is a set of $k$ vertex-disjoint paths in $G$, then $P'\_1,P'\_2,\ldots,P'\_k$ form a set of $k$ induced paths in $G'$ between the same pairs of terminals. (Note that for every new vertex that appears on a path $P'\_i$, the two edges incident on that vertex also belong to $P'\_i$. Also, one endpoint of every edge in $G'$ is a new vertex, and the terminal vertices of each path $P'\_i$ are old vertices. Thus there can be no edge in $G'$ between vertices that lie on two different paths $P'\_i$ and $P'\_j$, or between two non-consecutive vertices of some path $P'\_i$.) Similarly, consider a path $Q$ between two old vertices $x$ and $y$ in $G'$. Then $Q$ is of the form $x=a\_1,b\_1,a\_2,b\_2,\ldots,b\_{t-1},a\_t=y$ where $a\_1,a\_2,\ldots,a\_t$ are old vertices and $b\_1,b\_2,\ldots,b\_{t-1}$ are new vertices. Clearly, for $i\in\\{1,2,\ldots,t-1\\}$, $b\_i=v\_{a\_ia\_{i+1}}$, which also means that $a\_ia\_{i+1}\in E(G)$. Let $Q^\*$ be the path $a\_1,a\_2,\ldots,a\_t$ in $G$. Now if $Q\_1,Q\_2,\ldots,Q\_k$ form a set of $k$ induced paths (in fact even just a set of $k$ vertex-disjoint paths) in $G'$, then $Q\_1^\*,Q\_2^\*,\ldots,Q\_k^\*$ are vertex-disjoint paths in $G$ between the same pairs of terminals.
> 1 votes

---
Tags: graphs, np-complete, np
---


# Question
Title: Write a pseudo code for a Graph algorithm
Given a DAG $G=(V, E)$ and a function $f(v)$ which maps every vertex to a unique number from 1 to $|V|$, I need to write a pseudo code for an algorithm that finds for every $v\in V$ the minimal value of $f(u)$, among all vertices $u$ that are reachable from $v$, and save it a an attribute of v. The time complexity of the algorithm needs to be $O(V+E)$ (assuming that time complexity of $f(v)$ is $\Theta (1)$).

I thought about using DFS (or a variation of it) and/or topological sort, but I don't know how to use it in order to solve this problem.

In addition, I need to think about an algorithm that gets an undirected graph and the function $f(v)$, and calculate the same thing for every vertex, and I don't know how to do it either.

# Answer
Given a vertex $v$, let $F(v)$ be the minimum value $f(u)$ among all nodes $u$ reachable from $u$ in the input DAG $G=(V,E)$.

Notice that a vertex $u$ is reachable from $v$ if and only if $u=v$ or $u$ is reachable from some out-neighbor $w$ of $v$. Then, we can write:

$$ F(v) = \min\\{ f(v), \min\_{(v,w) \in E} F(w) \\}, $$ where the minimum of over an empty range is $+\infty$.

Let $v\_1, \dots, v\_n$ be the vertices of $G$ in reverse topological order, and notice that the previous equation for $F(v\_i)$ only depends on $f(v\_i)$ and on the values $F(v\_j)$ with $j\<i$.

If we compute $F(v\_1), F(v\_2), \dots, F(v\_n)$ in this order, then we will only need time proportional to the out-degree $\delta\_i$ of each $v\_i$. More precisely, we will spend time $O( 1 + \delta\_i)$ to compute $F(v\_i)$. Since $\sum\_{i=1}^n ( 1 + \delta\_i) = |V| + |E|$, the overall time complexity is also $O(|V| + |E|)$.

If the graph $G$ is not a DAG then, the same approach works once you preprocess $G$ by identifying all the connected components $C$ into a single vertex $v\_C$ having $f(v\_C) = \min\_{u \in C} f(u)$. This preprocessing requires time $O(|V|+|E|)$, since this is the time required to compute the connected components of $G$ (which are a partition of $G$). In particular this captures the case where $G$ is an undirected graph since it is equivalent to solving the problem using the directed version of $G$: just replace each undirected edge $\\{u, v\\}$ with the pair of directed edges $(u,v)$ and $(v,u)$.
> 1 votes

# Answer
Yes, you can use the topological sort. Suppose topological sorting of the vertices gives you the sequence: $v\_{1}, \dotsc, v\_{n}$ such that there is no edge of the form $(v\_{j},v\_{i})$ for any $i \< j$.

Following would be the pseudocode to compute the minimum reachable $f(u)$ value for each vertex $v\_{i} \in V$:

```
fun()
----- int min_val_reachable[n];    // array that stores minimum reachable f(u) value for each vertex

----- for(i = n to 1; i--)
-------- min_val_reachable[i] = f(v_i) // since a vertex v_i is reachable to itself
-------- for each vertex 'u' in adj_list[v_i]
-------------- if (min_val_reachable[i] > min_val_reachable[u])
-------------------min_val_reachable[i] = min_val_reachable[u]
-------------- end
--------- end
----- end
----- return min_val_reachable[];

```

The time complexity of the topological sort is $O(|V| + |E|)$, and the time complexity of the above procedure is also $O(|V| + |E|)$. Thus, the overall complexity is $O(|V| + |E|)$.

---

You can prove the correctness of the above procedure using the induction technique as follows:

**Hypothesis:** After $t$ iterations of the outer "for loop", we get the correct min\_value\_reachable\[\] for every vertex from $v\_{n}$ to $v\_{n-t+1}$

**Base Case:** For $t = 1$, it is easy to see that min\_value\_reachable\[$v\_n$\] = $f(v\_n)$ since $v\_{n}$ does not has any child, and $v\_{n}$ is reachable to itself.

The induction case is also simple. Hope you can figure out the details yourself.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Run-time of a summation function and its complexity
I am trying to analyze the running time of the following function:

```
def algo(array: List[int]):
    x = 1
    y = 0
    sigma = 0
    for ix in range(1, len(array)):  #len(array) always >= 1
        summation = 0
        for jx in range(ix, 0, -1):
            summation = summation + array[jx]
            if summation > sigma:
                x = jx
                y = ix
                sigma = summation
    return (x,y)

```

I have identified a basic unit of the algorithm to count as the number of iterations/total loops, $L$, it runs through. So for instance, if the length of array, $n$, is $1$, then $L = 1$. If, $n = 5$, then $L = 15$. The pattern follows that of the triangular numbers sequence. If you plot a set of points $(n, L)$ you will see that it kind of looks exponential. Is my line of thinking so far okay?

# Answer
The body of the inner for loop is executed in constant time per iteration and it does not affect the number of iterations of the outer loops.

Let $n$ be the length of `array`. The outer for loop iterates $n$ times. During the $i$-th iteration of the outer loop, the inner for loop iterates $i$ times.

The overall time complexity is therefore: $$ \Theta(1) \cdot \sum\_{i=1}^{n} i = \Theta(1) \cdot \Theta(n^2) = \Theta(n^2). $$
> 1 votes

---
Tags: time-complexity
---


# Question
Title: How efficient of this prime sieving algorithm?
I just found there is an old program of mine where I implemented the following prime sieving algorithm:

```
#define MAX=1000001
#define SQRT=1000
// ...
not_prime[1] = 1;
for (int a = 2; a <= SQRT; a++)
  if (!not_prime[a])
     for (int c = MAX / a, b = a * c; c >= a; c--, b -= a)
        if (!not_prime[c])
           not_prime[b] = 1;

```

It seems like my logic that time is: For any given composite `a` and all corresponding composite `c`s such that `MAX >= b; b = a * c`. But I forgot why I set restriction on `c` that `c >= a`? Could anyone help explain this line for me and help me analyze how efficient this algorithm is?

# Answer
The loop "int c ... " is much too complicated and difficult to get right, just start with c = a, b = a\*a, and iterate upwards.

Most people create a sieve for odd numbers only. Some create a sieve only for the eight out of 30 numbers that are not multiples of 2, 3 or 5. That's a factor of 3.75 in space. And removing multiples of 2, 3 and 5 takes substantial time.

Only checking multiples of 2, 3 or 5 also allows you to check fewer multiples of the prime. Another factor 3.75.

If you want to be fast, you use a bit array, and use SIMD instructions to remove multiples of small primes, say up to 100, which saves a huge amount of time. Checking whether c is still considered a prime is time consuming and likely takes more time than it saves, especially since you will end up with lots of mispredicted branches.

Now for primes up to a million that's all irrelevant, but for larger ranges it makes a huge difference.
> 1 votes

---
Tags: algorithms, time-complexity, primes
---


# Question
Title: Number of nodes at given depth in binary tree
> Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction of $1/2^n$?
>
> * The running time of a specific input is linear if the corresponding leaf node is within a linear distance from the root. Considering a binary tree, the maximum number of nodes within a linear distance from the root is $2^{kn+1}-1$.

How $2^{kn+1}-1$ was reached? just I need an intuitive idea not a proof. this is my notes not an homework or exercises. $k$ and $n$ not defined on it context.

# Answer
> 2 votes
Intuitively, the maximum number of leaves at distance at most $d$ from the root is obtained when all of these leaves are at distance exactly $d$ from the root. Since there are at most $2^d$ nodes at distance exactly $d$ from the root, this suggests that the maximum number of leaves at distance at most $d$ from the root is $2^d$.

We can easily prove this bound formally using Kraft's inequality, which states that $$ \sum\_{\ell} 2^{-d(\ell)} \leq 1, $$ where $\ell$ goes over all leaves, and $d(\ell)$ is the distance of $\ell$ from the root. Kraft's inequality implies that $$ 1 \geq \sum\_{\ell\colon d(\ell) \leq d} 2^{-d(\ell)} \geq \sum\_{\ell\colon d(\ell) \leq d} 2^{-d},$$ from which it immediately follows that there are at most $2^d$ leaves at distance at most $d$ from the root.

---

The text you quote is less sophisticated. It is bounding the number of leaves at distance at most $d$ from the root by the number of *nodes* at distance at most $d$ from the root. Since there are at most $2^e$ nodes at distance exactly $e$ from the root, it follows that the number of nodes at distance at most $d$ from the root is bounded by $$ \sum\_{e=0}^d 2^e = 2^{d+1} - 1. $$

---
Tags: algorithms, data-structures, trees, discrete-mathematics
---


# Question
Title: Number of maximal cliques in graphs without common neighbourhoods
Let's consider a graph $G(n)$ of $n$ vertices such as no two vertices in $G$ have the same exact neighbors (different open neighbourhoods to be more specific; I wonder if this kind of graphs have already a name). Which is the maximum number of maximal cliques of such graphs? Is that amount polynomically bounded?

**Additional related question:** which extra conditions must such graphs have to be planar? This is in fact a related question because planar graph does indeed have a polynomically bounded amount of maximal cliques.

# Answer
Suppose that $n$ is a perfect square, and identify its vertex set with $\\{1,\ldots,\sqrt{n}\\}^2$. Connect $(a,b)$ to $(c,d)$ if $a \neq c$ and $b \neq d$. You can identify a vertex from the set of its neighbors, so the open neighborhoods are all distinct. The number of maximal cliques is $\sqrt{n}!$, which isn't polynomial.
> 3 votes

---
Tags: graphs
---


title: Hardcore bit of a one way function

text:
# Question
Title: Hardcore bit of a one way function
Let $b:\\{0,1\\}^\*\mapsto \\{0,1\\}$, be a hardcore bit of a one way function $f$. I want to show that $\vert Pr\_{x\in U\_n}\[b(x)=1\]-Pr\_{x\in U\_n}\[b(x)=0\]\vert=n^{-\omega(1)}$. Intuitively, it looks correct as if it is not the case then the bit is not hardcore, but I do not have any ideas how to proceed with the proof. Can anyone help?

# Answer
> 2 votes
For completeness, I'll make my comment an answer. Under the current formulation the statement is wrong, a hardcore bit can be non-negligibly biased towards $0$ or $1$, i.e. $\Pr\_{x\sim U\_n}\left\[b(x)=0\right\]\ge \frac{1}{2}+n^{-c}$ infinitely often. However $b$ of course cannot be biased on the image of $f$. To illustrate this point, suppose there exists a (length preserving) one way function and let $g(x,r)=(f(x),r)$, where $(x,r)\in\\{0,1\\}^n$. Also assume that the leftmost bit of $f(x)$ is always $1$ (one can always construct a new one way function from $f$ satisfying this).

Now define:

$b(y,r)=\begin{cases} \langle y,r\rangle, & y\_1=1 \\ 0, & y\_1=0 \end{cases} $

where $y,r\in\\{0,1\\}^n$ and $\langle y,r \rangle=\sum\limits\_{i=1}^ny\_ir\_i\pmod 2$. Since the leftmost bit of $f(x)$ is always $1$, $b$ is hardcore for $g$ (direct application of Goldreich-Levin). Note that for every $y\neq 0$ exactly half the strings $r\in\\{0,1\\}^n$ satisfy $\langle y,r\rangle = 0$. We conclude that $\Pr\_{(y,r)\sim U\_{2n}}\left\[b(y,r)=0\right\]\ge\frac{3}{4}$. This bias was made possible by the fact the $b$ can be easy outside the image of $f$. The statement is true if we instead require no bias for $b(f(x))$ where $x$ is random.

---
Tags: complexity-theory, cryptography
---


title: Runtime Complexity of Memoization

text:
# Question
Title: Runtime Complexity of Memoization
I am struggling to analyze the runtime complexity of the following algorithm formally:

> Given a string s and a dictionary of words dict(wordDict), add spaces in s to construct a sentence where each word is a valid dictionary word.
>
> Return all such possible sentences.
>
> For example, given s = "catsanddog", dict = \["cat", "cats", "and", "sand", "dog"\].
>
> A solution is \["cats and dog", "cat sand dog"\].

The proposed algorithm:

```
    wordBreak(s, wordDict) {
        res; //a container used to store the final result.
        if(the length of s is zero or s is invalid) {
            just output res directly.
        }
        if(we have already encountered s before) {
            return the res that s corresponds to.
        }
        if(wordDict contains s) {
            add s to res.
        }
        (looping index from 0 to the length of s) {
            t = the substring of s starting from index to the end of s
            if(wordDict contains t) {
                temp = wordBreak(substring of s from 0 to index , wordDict);
                if(temp is not empty) {
                    (looping index j from 0 to the length of temp) {
                        cancatenate the jth element of temp with t and add it to res.
                    }
                }
            }
        }
        store the result of s to storage.
        return res;
    }
}

```

My analysis:

Giving the algorithm, denote the length of $s$ by n. Suppose the runtime complexity is $T(n)$, then we would have something like $T(n) = T(n - 1) + T(n - 2) + \ldots + T(0) + n + 2^{n-1} - 1$, where I add $n$ because we are looping through $s$. In the meantime we are looping through temp which is a list of results. In the worst case temp can contain $2^{n-1} - 1$ results(subdivisions coming from a string of length $n - 1$). However this does not take into consideration the effect of memoization and I do not know how to achieve that. Specifically my question are:

1. What is the correct time complexity analysis? My guess is that it is at least $n 2^{n-1}$ which is the time taken to create the result list but this is a wild guess without formal proof.
2. How does the analysis differ from the case where there is no memoization.

# Answer
> 1 votes
Memoization is related to dynamic programming in the following way.

Let $V$ be the set of all possible inputs to the function $f$. Draw an edge from $x \in V$ to $y \in V$ if the computation of $f(x)$ invokes $f(y)$. The resulting graph is a directed acyclic graph (DAG).

Now suppose that you want to compute $f(x)$. Let $V(x)$ be the set of all vertices reachable from $V(x)$. In dynamic programming, we arrange $V(x)$ in reverse topological order, and compute $f$ in that order.

As an example, consider the Fibonacci recurrence $F(n) = F(n-1) + F(n-2)$, with base cases $F(1) = 1$ and $F(0) = 0$. In this case $V$ consists of all natural numbers, the edges are $n\to n-1$ and $n \to n-2$ (for all $n \geq 2$), $V(n) = \\{0,\ldots,n\\}$, and reverse topological order is $0,\ldots,n$. That is, we compute $F(0),F(1),F(2),\ldots,F(n)$ in this order. Whenever compute $F(m)$, all other values of $F$ which are needed are already available.

---

How do we compute the complexity of a memoized function? We imagine that instead of implementing it in a recursive fashion, we use dynamic programming. This means that each recursive call now takes $O(1)$; but when running $f(x)$, we actually evaluate $f$ on all inputs in $V(x)$.

---

In your case, $V(x)$ consists of all prefixes of $x$. In order to evaluate the running time, you need to compute, for each $n$, the running time of your procedure $T(n)$ on inputs of length $n$, assuming that all recursive calls are $O(1)$. The final answer is then $T(0) + \cdots + T(n)$.

---
Tags: algorithms, time-complexity, runtime-analysis
---


# Question
Title: What is the language of Sigma^n? Confused about meanining
I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet?

Thank you so much!

# Answer
By definition $\Sigma^n$ is simply $\underbrace{\Sigma\times \Sigma \times \cdots \times\Sigma}\_{n \ \text{times}} = \\{(\sigma\_1, \sigma\_2, \ldots, \sigma\_n): \forall \ i\in \[n\], \sigma\_i \in \Sigma \\}$ which is the set of ordered tuples of length $n$ over $\Sigma$. Usually, when we refer to a tuple $w = (\sigma\_1, \sigma\_2, \ldots, \sigma\_n)$, we omit the commas "," and the parenthesis "(" and ")", so the tuple $w$ is written as $\sigma\_1\cdot \sigma\_2\cdots \sigma\_n$ to which we refer as a word of length $n$ over $\Sigma$. In other words, $\Sigma^n$ is the set of all words of length $n$ over $\Sigma$.

Formally, the map that maps a tuple in $\Sigma^n$ to the word that we get by omitting the commas and the parenthesis from the tuples, is a bijection from $\Sigma^n$ to the words of length $n$ over $\Sigma$.
> 1 votes

---
Tags: formal-languages, automata, regular-languages, computation-models
---


# Question
Title: Category Set language using simply typed lambda calculus
I am currently self learning Category Theory and Simply typed lambda calculus (STLC). For learning purposes, I have implemented an STLC interpreter as given in *Types and Programming Languages book of Benjamin Pierce*. Now i am wondering if I can extend this interpreter with category of sets (category **Set** ). i.e. interpret expressions to construct sets, pushouts, pullbacks etc.

Unable to find any directions on how to do this. Can someone please provide any helpful suggestions on this?

# Answer
> 2 votes
There are at least two directions in which you can proceed.

First, Church's simple type theory (see also this explanation) extends the simply typed $\lambda$-calculus with the types of natural numbers and booleans, and other constructs that make it sufficiently expressive to encode a certain kind of classical set theory. These ideas were pursued in the HOL theorem provers. For instance, HOL light for a small implementation. This approach has the flavor of doing *logic*, i.e., there is no general notion of computation - as opposed to the simply typed $\lambda$-calculus, which is a programming language.

Second, dependent type theory, of which there are many variants, is also an extension of the simply typed $\lambda$-calculus. It can be used as a foundation of mathematics. They are used in proof assistants, such as Coq, Agda, and Lean. Some variants, notably Martin-Löf type theory, do retain the character of a programming language. In fact, Idris is a programming language based on dependent type theory.

None of the above is "set theory", but these formalisms are quite suitable for expressing mathematics, including category theory.

---
Tags: lambda-calculus, category-theory, types-and-programming-languages
---


# Question
Title: Trying to find two CFGs for the following languages
I'm trying to get CFGs for these two languages which still remain unsolved in my practice problems sheet:

$L = \\{ a^kb^ra^m | m=k+r\\}$

$L = \\{ a^nb^m | 1\leq n\leq 2m\\}$

With the first one, I thought of this:

$$S\rightarrow aSa | T$$ $$T\rightarrow b T a | \epsilon$$

but what if $k\>r$ or $r\>k$?

With the second one, I think it is really simple but I cannot wrap my mind with $1\leq n\leq 2m$ (maybe I'm special...), should I have at least as many $a's$ as the double of $b's$ but not strictly? how could I specify that?

# Answer
You can write the first language as $$ \\{ a^k b^r a^r a^k \mid k,r \geq 0 \\}. $$ The corresponding context-free grammar is exactly the one you give. If you apply $k$ times the rule $S \to aSa$ and $r$ times the rule $T \to bTa$, then you will get $a^k b^r a^r a^k$.

As for the second language, let us start with the slightly easier $$ \\{ a^n b^m \mid n \le 2m \\}. $$ For each $b$ that you add, you can add up to two $a$'s. This leads to the grammar $$ S \to Sb \mid aSb \mid aaSb \mid \epsilon. $$ In your case, you have to guarantee at least one $a$. Write this as follows: $$ \\{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m+1 \\} = \\{ a^{n+1}b^{m+1} \mid 0 \leq n \leq 2m \\} \cup \\{ a^{n+2}b^{m+1} \mid 0 \leq n \leq 2m \\}. $$ Thus you can add the following rules to the preceding grammar, making $T$ the new starting symbol: $$ T \to aSb \mid aaSb. $$
> 1 votes

---
Tags: context-free, formal-grammars
---


title: Myhill-Nerode equivalence classes

text:
# Question
Title: Myhill-Nerode equivalence classes
I need to find the Myhill-Nerode equivalence classes for the language $$ L = \Sigma^\*\setminus \left( \\{\epsilon, cc \\} \cup \\{ cca^i: i\geq 2 \\} \right) $$ over $\Sigma = \\{a, b, c \\}$

I'm familiar with the idea of separating suffix, but I really don't know where to start here. Thanks!

# Answer
> 2 votes
To begin with, note the the Myhill-Nerode equivalence classes for a language $L$ is the same as the Myhill-Nerode classes for its complement $\overline{L}$. This follows immediately by definition, and I leave it you (it also appears here).

So given $\Sigma = \\{a, b, c\\}$, we need to find the Myhill-Nerode classes for $\overline{L} = \\{ \epsilon, cc\\}\cup \\{cca^i: i\geq 2 \\}$. There are many ways to do so, one can, for example, consider what happens in a minimal deterministic automaton for the language - it is known that the states of the minimal deterministic automaton correspond to the Myhill-Nerode classes. Yet, the given language is simple enough, you can actually experiment with it a bit and show that the following are the equivalence class for $\overline{L}$ (indeed, $\overline{L}$ has a simple structure - every word of length at least $4$ in the laguage is of the form $cca^i$, so clearly all these words are equivalent. Then, you can look at words of length \< 4, and try to see which among them are equivalent, etc.):

* $C\_1 = \\{ \epsilon\\}$.
* $C\_2 = \\{ c\\}$.
* $C\_3 = \\{ cc\\}$.
* $C\_4 = \\{ cca\\}$.
* $C\_5 = \\{ cca^i: i\geq 2\\}$.
* $C\_6 = \Sigma^\*\setminus \left( \bigcup\_{i\in \[5\]} C\_i\right)$.

Clearly the 5 sets above partition $\Sigma^\*$, so to show that they are indeed the Myhill-Nerode classes, we need to show that all the words in the same set are Myhill-Nerode equivalent, and for every $ 1\leq i \< j \leq 6$, it holds that the words in the set $C\_i$ are not equivalent to the words in the set $C\_j$.

There you go, try to prove that the above sets are indeed the equivalence classes. That should be easy enough now.

# Answer
> 0 votes
The equivalence classes for $L$ are the same as those for $\overline{L} = \\{cca^i \\, : \\, i \ge 2\\} \cup \\{\varepsilon, cc\\}$.

All the words in $\\{cca^i \\, : \\, i \ge 2\\}$ belong to the same equivalence class $C\_1$. Indeed let $\alpha, \beta \in \\{cca^i \\, : \\, i \ge 2\\}$ and consider any extension $x$, if $x \neq a^k$ for some $k$, then neither $\alpha x$ nor $\beta x$ belong to $\overline{L}$. Otherwise they both belong to $\overline{L}$.

The word $cc$ belongs to some equivalence class $C\_2 \neq C\_1$. Indeed $a$ is a distinguishing extension for $cc$ and $ccaa \in C\_1$.

The word $\varepsilon$ belongs to some equivalence class $C\_3 \not\in \\{C\_1, C\_2\\}$. Indeed (i) $cc$ is a distinguishing extension for $\varepsilon$ and $cc \in C\_2$, and (ii) $a$ is a distinguishing extension for $\varepsilon$ and $ccaa \in C\_1$.

The word $c$ belongs to some equivalence class $C\_4 \not\in \\{C\_1, C\_2, C\_3\\}$. Indeed $\varepsilon$ is a distinguishing extension for $c$ and any word in $C\_1$, $C\_2$, or $C\_3$.

The word $cca$ belongs to some equivalence class $C\_5 \not\in \\{C\_1, C\_2, C\_3, C\_4\\}$. Indeed (i) $\varepsilon$ is a distinguishing extension for $cca$ and any word in $C\_1$, $C\_2$, or $C\_3$, and (ii) $a$ is a distinguishing extension for $cca$ and $c \in C\_4$.

All other words $\gamma$ do not start with any prefix of $cca^\*$. Therefore there exist no extension $x$ such that $\gamma x \in \overline{L}$. Moreover (i) $\varepsilon$ is a distinguishing extension for $\gamma$ and any word in $C\_1$, $C\_2$, or $C\_3$, and there exists at least one distinguishing extension for $c \in C\_4$ (namely $c$), and for $cca \in C\_5$ (namely $a$). This shows that all these words $\gamma$ belong to the same equivalence class.

The equivalence classes are then: $$ \\{cca^i \\, : \\, i \ge 2\\}, \\; \\{cc\\}, \\; \\{ \varepsilon\\}, \\; \\{ c\\}, \\; \\{ cca \\}, \Sigma^\* \setminus \\{cca^k \\, : \\, k \ge 0 \\}. $$

---
Tags: automata
---


# Question
Title: Time complexity of the travelling salesman problem (Recursive formulation)
According to this recursion formula for dynamic programming (Held–Karp algorithm), the minimum cost can be found. I entered this code in C ++ and this was achieved (`neighbor` vector is the same set and `v` is cost matrix):

recursion formula :

```
C(i,S) = min { d(i,j) + C(j,S-{j}) }

```

my code :

```
#include <iostream>
#include <vector>
#define INF 99999
using namespace std;
vector<vector<int>> v{ { 0, 4, 1, 3 },{ 4, 0, 2, 1 },{ 1, 2, 0, 5 },{ 3, 1, 5, 0 } };
vector<int> erase(vector<int> v, int j)
{
    v.erase(v.begin() + j);
    vector<int> vv = v;
    return vv;
}
int TSP(vector<int> neighbor, int index)
{
    if (neighbor.size() == 0)
        return v[index][0];
    int min = INF;
    for (int j = 0; j < neighbor.size(); j++)
    {
        int cost = v[index][neighbor[j]] + TSP(erase(neighbor, j), neighbor[j]);
        if (cost < min)
            min = cost;
    }
    return min;
}
int main()
{
    vector<int> neighbor{ 1, 2, 3 };
    cout << TSP(neighbor, 0) << endl;
    return 0;
}

```

In fact, the `erase` function removes the element `j` from the set (which is the `neighbor` vector)

I know about dynamic programming that prevents duplicate calculations (like the Fibonacci function) but it does not have duplicate calculations because if we draw the tree of this function we see that the arguments of function (i.e. `S` and `i` in formula and like the picture below) are never the same and there is no duplicate calculation. My question is, is this time **O(n!)**?

picture : If yes,why? This function is exactly the same as the formula and it does exactly the same thing. Where is the problem? Is it doing duplicate calculations?

# Answer
The full recursion tree for your problem has as root $(1,\\{2,\ldots,n\\})$. The children of a node $(i,S)$ are $(j,S \setminus \\{j\\})$, where $j$ ranges over all elements of $j$. Nodes with $S = \emptyset$ have no children.

Let us annotate each node in the tree by its "history". Instead of annotating each node by an index and a set, we annotate it with a *sequence* and a set. The root is $(1;\\{2,\ldots,n\\})$. The children of a node $(a;S)$ are $(a,j;S \setminus \\{j\\})$ for all $j \in S$. For example, if $n = 3$ then the nodes are:

1. $(1;\\{2,3\\})$.
2. $(1,2;\\{3\\})$.
3. $(1,3;\\{2\\})$.
4. $(1,2,3;\emptyset)$.
5. $(1,3,2;\emptyset)$.

A node $(a\_1,\ldots,a\_m;S)$ in the new tree corresponds to the node $(a\_m,S)$ in the original tree. Conversely, each node $(a,S)$ corresponds to nodes $(1,a\_2,\ldots,a\_{m-1},a;S)$, where $m = n - |S|$ and $\\{1,a\_2,\ldots,a\_{m-1},a\\} = \overline{S}$. There are $(n-2-|S|)!$ ways to choose $a\_2,\ldots,a\_{m-1}$, and so the node $(a,S)$ appears $(n-2-|S|)!$ times in the original tree.

This shows that the full recursion tree for your problem does contain duplicates.
> 1 votes

---
Tags: algorithms, graphs, traveling-salesman, c++
---


title: Similarity Of Matrices

text:
# Question
Title: Similarity Of Matrices
Give a randomized algorithm that takes input two $n \times n$ matrices $A$ and $B$ with integer entries and does the following: If $A$ and $B$ are similar, then with high probability the algorithm outputs an $n \times n$ invertible matrix $C$ with rational entries such that $CAC^{−1} = B$; otherwise it outputs $A$ not similar to $B$. Ensure that your algorithm runs in polynomial time.

# Answer
I don't get very well the point of the requirement in the problem of a randomized algorithm. Or maybe I am misinterpreting what is the notion of problem size with respect to which the running time is required to be polynomially bounded. With respect to the number of entries of $A$ and $B$ there is the following deterministic algorithm.

The requirement of $C$ having rational entries, or more generally entries in the same field as the entries of $A$ and $B$ points to using the Frobenius/Rational normal form (FNF). The Jordan normal form is inconvenient because, in general, it requires working in a field extension in which the characteristic polynomials of $A$ and $B$ factor completely (split).

Just like in the case of Jordan normal form, there are invertible matrices $P\_1,P\_2$ such that $P\_1AP\_1^{-1}=A\_f$ and $P\_2BP\_2^{-1}=B\_f$ and $A\_f, B\_f$ are the Frobenius normal forms of $A,B$, respectively. The additional property that we mentioned before is that all these matrices have entries in the same field as the entries of $A$ and $B$.So, if your matrices have integer entries, then these matrices will have rational entries.

Now, the matrices $A$ and $B$ are similar if and only if $A\_f=B\_f$. When this happens we can compute the required $C$ from $P\_1AP\_1^{-1}=A\_f=B\_f=P\_2BP\_2^{-1}$, since we get $(P\_2^{-1}P\_1)A(P\_2^{-1}P\_1)^{-1}=B$. So, we can take $C=P\_2^{-1}P\_1$.

The FNF can be computed (without emphasis on efficiency) by considering the polynomial matrices $A-xI$ and $B-xI$ and reducing them to their Smith normal form. This consists in a combination of Gauss elimination (row/column reduction, if you call it that way) combined with Euclid algorithm to compute some polynomial GCDs that are required. The Smith normal form tells you the *invariant factors*, and then the Frobenius normal form is the block-diagonal matrix in which the blocks are the companion matrices of the invariant factors. The sequence of steps to reduce $A-xI$ and $B-xI$ to their Smith normal forms give you the $P\_1$ and $P\_2$ required above.

Justifying all these claims requires a long exposition of the linear algebra (and either explicitly or implicitly the structure theorem of finitely generated modules over a principal ideal domain). This can be found in many linear algebra books. One that I know has it is Dummit and Foote's *Abstract Algebra*.

---

A guess of how randomization could be used is by trying random vectors $v$ and finding the maximal Krylov subspaces that it generates. This is, the space generated by $v,Av,A^2v,A^3v,...$, which ought to be generated by finitely many of those vectors. Each one of those give you a cyclic invariant subspace of $A$, which tell you a block of the Frobenius normal form. Then pass to the quotient space by this subspace and repeat until you find all blocks of the FNF. Understanding the theory is required again to see why.
> 3 votes

---
Tags: algorithms, complexity-theory, randomness
---


# Question
Title: What's the difference between Computer Science and Informatics?
The Terms are much used in actual IT (Information Technology). Is it possible to make a difference or are this terms nearly synonyms for the same fact?

# Answer
> 4 votes
I deliberately use very common, not necessarily professional resource.

### Computer Science

> Computer science is the study of the theory, experimentation, and engineering that form the basis for the design and use of computers. It is the scientific and practical approach to computation and its applications and the systematic study of the feasibility, structure, expression, and mechanization of the methodical procedures (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information. An alternate, more succinct definition of computer science is the study of automating algorithmic processes that scale. A computer scientist specializes in the theory of computation and the design of computational systems.

source: Computer Science @ Wikipedia

### Informatics

> Informatics is a branch of information engineering. It involves the practice of information processing and the engineering of information systems, and as an academic field it is an applied form of information science. The field considers the interaction between humans and information alongside the construction of interfaces, organisations, technologies and systems. As such, the field of informatics has great breadth and encompasses many subspecialties, including disciplines of computer science, information systems, information technology and statistics. Since the advent of computers, individuals and organizations increasingly process information digitally. This has led to the study of informatics with computational, mathematical, biological, cognitive and social aspects, including study of the social impact of information technologies.

source: Informatics @ Wikipedia

It is for sure time and place dependent, after further research it seems that the German term *Informatik* was a synonym of the *Computer Science* at first, was adapted virtually everywhere, but evolved since 1956, and diverged with meaning, but it is still overlapping. Tt seems that currently *Informatics* is used more as applied *Computer Science* (ref: search engine coin toss).

The IT (Information Technology) in some languages has broader meaning, and simply merges *telecommunication* with *computer sciene* and *informatics*. Unfortunately this is not well-defined term, it is part of the language so it may vary in time up to the moment when people think it is too broad and start some finer classification.

Please see also Informatics vs. Computer Science

# Answer
> 2 votes
In simple words: Computer science is the study of computers Informatics is the study using computers This is what I personally think. Hope it helps you.

---
Tags: terminology
---