Construct a DFA which accepts a string of length 5 with at least 2 0's How to design a DFA of all strings over (0,1) such that every block of 5 consecutive symbols contains at least 2 0's?

The question asks HOW TO DESIGN, you don't have to write the whole DFA, but you can if you want to. Just describe how you would design.

There are 32 strings of length 5. Some of them do not contain at least two 0s, some do. Those that do not contain at least two 0s should lead to the DEAD state (from which there is no return). But those that do have at least two 0s should lead to a state that checks another block of 5 symbols.

Try to draw a binary tree of depth 5, with 0 as the left child and 1 as the right child for each node. Does it help design the DFA? For simplicity first try to design for blocks of 3 symbols not 5.


Fractional Knapsack in linear time How to solve fractional knapsack in linear time? I found this on Google but don't really understand it.

Choose element $r$ at random from $R$ (set of profit/weight ratios)
Determine

$R_1 = \{ p_i / w_i | p_i / w_i > r, for 1 \leq i \leq n \}, W_1 = \sum_{i \in R_1} w_i$
$R_2 = \{ p_i / w_i | p_i / w_i = r, for 1 \leq i \leq n \}, W_2 = \sum_{i \in R_3} w_i$
$R_3 = \{ p_i / w_i | p_i / w_i < r, for 1 \leq i \leq n \}, W_3 = \sum_{i \in R_3} w_i$

if $W_1 > W$

recurse $R_1$ and return computed solution

else

while (there's space in knapsack and $R_2$ is not empty)

add items from $R_2$

if (knapsack gets full)

return items in $R_1$ and items just added from $R_2$

else

reduce knapsack capacity by $W_1 + W_2$
recurse on $R_3$ and return items in $R_1 \cup R_2$
add items returned from recursive call

I don't get how it works, what $R$ and $W$ are supposed to represent ... can someone explain? Or maybe if you have another algorithm to propose?

It would be nice if you stated the problem. I assume that you have $n$ items $x_i$, each having profit $p_i$ and weight $w_i$. You want to maximize your profit under the constraint that the total weight is at most $W$. For each item $x_i$, you are allowed to put any fraction $\theta \in [0,1]$ of it, which will give you profit $\theta p_i$ and weight $\theta w_i$.

Here is an example. You have raw gold, with a profit of $1000$ and weight $1$. You also have bananas, with a profit of $1$ and weight $10$. Suppose you can carry a weight of $2$. What would you do? Naturally, you would first put as much gold as you can - namely, all of it, and then you would put it as many bananas as you can - namely, a tenth of it, for a total profit of $1000.1$.

The general algorithm is similar. Suppose you divide $W$ into a $1000$ "slots", which you want to fill with the most profitable item-parts of weight $W/1000$. For an item weighing $w_i$, we have $w_i/(W/1000)$ pieces (suppose for the moment that this is an integer), and each of them is worth $p_i/(w_i/(W/1000))$. When choosing what to put in a slot, we would like to maximize our profit, and so we choose the item with maximal $p_i/w_i$, and put it as many pieces as possible. If we run out, we choose the item with the next largest $p_i/w_i$, and so on.

You can implement this without dividing $W$ into a $1000$ pieces: Choose the item with maximal $p_i/w_i$, and put as much of it as possible. If you run out, choose the next one, and put as much of it as possible. And so on. Implementing this algorithm requires sorting the list $p_i/w_i$, which takes time $O(n\log n)$. The algorithm you describe uses the same trick use in quickselect to reduce the running time to $O(n)$, at the cost of making the algorithm randomized.

I suggest the following route to understand the algorithm:

Understand the classical greedy algorithm for fractional knapsack.
Understand quickselect.
See how the algorithm you quote combines the technique of quickselect with the greedy approach.


Context-free grammar for language involving multiplication I'm struggling to find the context-free grammar for the following language:
$$
L = \{a^sb^tc^m:s,t,m\in\mathbb{N}^+\land1\leq t\leq3\land s\times t=m\}
$$
Any help would be appreciated.

Write $L$ in the following way:
$$
L = \{ a^sbc^s : s \in \mathbb{N}^+ \} \cup \{ a^sb^2c^{2s} : s \in \mathbb{N}^+ \} \cup \{ a^sb^3c^{3s} : s \in \mathbb{N}^+ \}.
$$


Why is the Marking Algorithm takes O(number of marks) ? I am referring to the Marking algorithm defined in this article: https://arxiv.org/pdf/1602.00621.pdf

The Marking method is defined at the bottom of page 4 and has a pseudo code at the beginning of page 5.

In page 7 they claim "The runtime of the marking stage is O(B)". B being an upper bound for the number of marks of the marking algorithm.

To me It seems like the Marking algorithm should take O(|A|n), A being the positions in its input.

Can someone help me understand this?

After mailing the author, I've found the answer:

The marking algorithm can be done in $O(B)$ by making sure that every unit of time we spend produces one mark. Consider the following piece of code:

for i in 1..|T|
  for j in A s.t. T[i]==P[j]
    m[i-j+1]++

The second loop need not take $O(|A|)$, it can be implemented more efficiently by precomputing the matching positions for every character in the alphabet. For example, if $T[i]$ happens to be '$c$' then we precompute all the offsets $j$ in $A$ for which P[j]=='c'. Then every iteration of the second loop produces a mark, like this:

for i in 1..|T|
  for j in offsets[T[i]]
   m[i-j+1]++

The total number of marks is $\sum_{a\in A} F_a=B$ because every position $a\in A$ has $F_a$ marks. So the run time is $O(B)$.


Djikstra algorithm analysis My textbook says that the Dijkstra algorithm's runtime is  $O(n) + O(m \log(n)) = O((n+m) \log(n))$. How did they come up with that?

Dijkstra algorithm pseudocode:

 1. Dijkstra(V, E, s):
 2.    Create an empty priority queue

 3.    for each v ≠ s:
 4.        d(v) ← ∞
 5.        d(s) ← 0

 6.    for each v ∈ V:
 7.        insert v with key d(v) into priority queue

 8.    while (the priority queue is not empty):
 9.        u ← delete-min from priority queue

10.        For each edge (u,v) ∈ E leaving u:
11.            If d(v) > d(u) + l(u,v):
12.                decrease-key of v to d(u) + l(u,v) in priority queue
13.                d(v) ← d(u) + l(u,v)

My runtime analysis:

 1.
 2. O(1)

 3. O(n)
 4.     O(1)
 5.     O(1)

 6. O(n)
 7.     O(log(n))

 8. O(n)
 9.     O(log(n))

10.     O(m)
11.         O(1)
12.             O(log(n))
13.             O(1)

From my analysis, the largest runtime would be from lines 8, 10, 11, and 12, resulting in $O(nm\log(n)) \ne O((n+m) \log(n))$.

8.    while (the priority queue is not empty):
 9.        u ← delete-min from priority queue

10.        For each edge (u,v) ∈ E leaving u:
11.            If d(v) > d(u) + l(u,v):
12.                decrease-key of v to d(u) + l(u,v) in priority queue
13.                d(v) ← d(u) + l(u,v)

Consider the multi-set of all edges that appear on line 10, where $u$ goes through all vertices thanks to the line 9 inside the while loop. There are two cases.

The graph is undirected. Each of those edges must be incident to a vertex $u$. So each edge in the graph appears exactly twice.
The graph is directed. Each of those edges must have $u$ as its starting endpoint. So each edge in the graph exactly appears once.

So in total, the number of edges that appear on line 10 is either $2|E|$ with undirected graph or $|E|$ with directed graph. So the running time from lines 8, 10, 11, and 12 is $2mO(\log(n))$ or $mO(\log(n))$. That is, $O(m\log(n))$.

Had the line 10 been For each edge (w,v) ∈ E:, your analysis might have had a chance to be correct.


Algorithmic problem of regular, context-free, and recursively enumerable languages Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free.
Are the following problems algorithmically decidable?

Is $L_1 \cap L_2 = L_3$?
Is $L_1 \cap L_3 = L_2$?

I think problem 1 is undecidable since $L_1 \cap L_2$ is a recursively enumerable language it can be expressed as a Turing machine and since $L_3$ is context free it can be expressed as a Grammar or Turing machine. Since we cannot determine the equivalence of two Turing machines, the problem is undecidable.
I think problem 2 is also undecidable for similar reasons, only the right hand side ($L_2$) is regular instead of context-free.
Am I correct?

Both questions are undecidable.
Notice that the empty language is both regular and context-free.
Thus we can state that the problem of determining if $L_1 \cap L_2$ is context-free is at least as hard as determining if $L_1$ is context-free (and similarly determining if $L_1 \cap L_3$ is a regular language is at least as hard as determining if $L_1$ is a regular language). By Rice's Theorem any non-trivial property about a Turing-Machine is undecidable and thus your two questions are undecidable.
For a detailed proof/answer to your second question look at this post.
IT shows how you would apply Rice's Theorem in your cases.


How much can we trust mathematical software when working with large numbers, and how much memory it needs to work with these numbers? For example, I want to evaluate the expression:

$3^{3^{{3}^{3}}}$

so I used wolframalpha.com (it's free, and I don't own any software), which returned the scientific notation of the number above, namely:

$ 1.258014290627491317860390698... × 10^{3638334640024}$

Which is huge. However, for the number below

$4^{4^{{4}^{4}}}$

Wolfram can't return a scientific notation, probably because it's a much larger number and it needs a lot of memory.

  Questions: a) How much can we trust that

$3^{3^{{3}^{3}}} \approx 1.258014290627491317860390698... × 10^{3638334640024} $

  b) how much memory (aproximate) it needs to evaluate

$3^{3^{{3}^{3}}}$

and

$4^{4^{{4}^{4}}}$

I'm guessing a lot of terabytes and something that a home computer can't handle. But for the first number, Wolfram can, and the second number, it can't. How do we even find how much size we need to calculate these numbers?

Question a):

Here is the output from python console.

>>> import math
>>> math.log(3,10) * (3**(3**3))
3638334640024.0996
>>> math.pow(10, 0.0996)
1.2577664324512539

The first 5 most significant digits are almost the same of that of Wolfram, 12577 vs 12580.

If we try the following at my favorite online arbitrary precision calculator,

pow(3.0000000000000000000000000000000, pow(3, pow(3, 3)))

we get

1.2580142906274913178603906982032e3638334640024

which is completely consistent with Wolfram. So Wolfram can be fully trusted on this particular result.

You might be wondering why "$3.000000$$000000$$000000$$000000$$0000000$" is entered instead of a simple "$3$". Had "$3$" been used, that calculator would have performed integer calculations without loss of precision, which will run out of 30-second time limit in our case. "$3.0$" would be enough to instruct that calculator to use floating numbers, which, however, would have only 2 digits of precision. That long string of 0s is used to specify 32 digits of precision of floating-point numbers.

Question b):

The computation above showed there are 3638334640025 digits if we express $3^{3^{3^3}}$ as a decimal integer. It we store 2 digits in one 8-bit byte, we need 1.82 terabyte storage.

However, if we ask that online calculator to compute $4^{4^{4^4}}$,

pow(4.0000000000000000000000000000000, pow(4, pow(4, 4)))

it say,

Complete loss of accurate digits

That is not a surprise since the exponent $4^{4^4}$ $=$ $1340780792994259$$7099574024998205$$8461274793658205$$9239337772356144$$3721764030073546$$9768018742981669$$0342769003185818$$6486050853753882$$8119465699464336$$49006084096$ $\approx$ $1.34×10^{154}.$
We can work around this out-of-limit error by computing directly the exponent of 10 in $4^{4^{4^4}}$ by using $\log$ with base 10.

log(4.0000000000000000000000000000000,10) * pow(4, pow(4, 4))

The answer is

8.0723047260282253793826303970853e153

That number of digits, about $8\times10^{153}$ is much more than vigintillion in long scale. To store $4^{4^{4^4}}$ as a decimal integer, it is not enough even if all atoms in the known universe are used, assuming each of them can store more digits than all available computer storage on earth.

However, not a lot of memory is needed for the calculations above to obtain the result above. It is possible that a few megabyte or just several kilobytes of extra memory could support the calculations above.


TM for $0^{5^n}$. Describing a turing machine that decides the language consisting of all strings of zeroes whose length is a power of 5 I am trying to describe a TM that decides the language $A=\{0^{5^n} \mid n\ge0\}$.
I know how to do this for $0^{2^n}$, marking off every other 0 in each pass. In my case would it work marking off every fifth 0 in each pass? It would reject if there are an even number of 0s. Every pass reduces the number of 0's by a fifth until there are no more 0s.

I'm gonna guess you're in s.datta's class?
I am not sure if this is correct but I tried to cross off 4 0's each time instead of 1.
It's like multiplying by 0.2 or the inverse operation of *5)

1*5 = 5
5*5 = 25
25*5 = 125

125*0.2 = 25
25*0.2 = 5
5*0.2 = 1

Edit: formatting


How does worst-fit memory allocation react when encountering contiguous empty memory blocks? So I have a problem understanding how the worst-fit protocol for memory allocation reacts to contiguous blocks of empty memory.  None of the examples I have found address this possibility.

For example, say you have the following blocks (where 'O' stands for occupied block and 'E' stands for empty block) and are to allocate 10 MB via the worst-fit algorithm:

------------------------------------------------------------
|10 MB O | 40 MB E | 10 MB O | 20 MB E | 30 MB E | 10 MB O |
------------------------------------------------------------
----0---------1---------2---------3---------4---------5-----

My question is does the worst-fit algorithm select block one leaving behind a 30 MB hole in block 1, or does it select block 3 leaving behind a cumulative 40 MB hole between blocks 3 and 4?

You have to assume that the blocks are what they are; if they can be coalesced into larger blocks, then this has already happened (ergo, perhaps the blocks that you have before you are not in fact adjacent in memory; they are an abstract list!) So, in short, there is no cumulative hole which spans multiple blocks.

So worst fit just walks the list of free blocks that it knows about and finds the largest block and takes from there.


How to write a DFA where the second digit is equal to the last digit of binary strings? I'm having some trouble writing a DFA for the language  $$\{w =b_1\dots b_k \in\{0, 1\}^* \mid b \ge 2 \text{ and } b_2=b_k\}\,.$$

What I thought for this is writing a DFA where there are 4 states, that accepts at the states (00) and (11), where the 1st element in the state is the 2nd element in the string, and the 2nd element in the DFA is the last element in the string. After trying to draw out examples this clearly doesn't work. I'm quite lost, any advice?

You are on the right track.

When constructing a DFA, you have to consider what information you need to store to decide in the end whether the string is accepted or not. The information you need is indeed: the second symbol of the string and the symbol which was read last. So you need four states to store all combinations of these two flags, and the accepting states are the ones where the second symbol and the last symbol are equal. The only thing you still need to do, is glue these states together.

First, there is a third kind of information: the length of the string. If you have read less than two symbols, you are not in one of four states mentioned earlier. So there are six states:

A: no symbols have been read (this is the initial state)
B: one symbol has been read
C: at least two symbols have been read, the second symbol is a 0 and the last a 0
   (this is an accepting state)
D: at least two symbols have been read, the second symbol is a 1 and the last a 0
E: at least two symbols have been read, the second symbol is a 0 and the last a 1
F: at least two symbols have been read, the second symbol is a 1 and the last a 1
   (this is a in accepting state)

To finish the automaton, you have to consider what happens to the state if you read in a 0 or a 1. This will then give you the transition function.


Applying information theory to processor clocks Has there been any research on the subject of applying information theory to a processors clock? It occurred to me that a clock is actually transmitting data that is used for synchronization of different processor components. Once I started to apply information theory concepts to the clock a lot of interesting ideas came up. I.e. clock speed is equivalent to bandwidth, the two voltage levels it transmits are the equivalent to symbols making is a 2-level transmitter (duh), and the logical limitations on how to usefully apply those two symbols is equivalent to noise. Processor manufacturers increase channel capacity by increasing processor speed and processor architects try to increase information rate by designing smarter encoding/decoding techniques like pipe-lining, branch prediction, speculative execution, and even multi-core processors.

After looking at it like this, and considering that systems designers are going to greater and greater lengths to squeeze greater information rates from just two symbols, wouldn't it make sense to increase the symbol rate? I don't mean going to ternary or quaternary or any other-ary processing, but just giving the clock more symbols or using multiple "clocks". Of course the incredibly high speeds in modern processors and the extremely tiny transistor sizes tend toward not doing so, but it does introduce some interesting thought experiments.

Has anyone explored this in an academic or experimental setting?

Technically, clock skew does this already. Specifically the technique known as "useful skew". When a data signal is going to travel from one storage element to another (both updating based on the clock), the clock that the source and destination elements receive are not quite the same.

In "useful skew", the clock at the destination is delayed such that the data has more time to travel before the capture clock edge arrives at the destination storage element. This allowed more distance of travel as well as more computation.


Explanation of proof of why connectedness is not conjunctively local of any order $k$ I was reading Minsky's and Papert's book on perceptrons and I was reading theorem 0.6.1 and I was having a hard time understanding it. The theorem was about proving that the property "connected" was not a local property i.e. that you somehow had to see the whole picture to know if something was connected or not. In particular their prove shows that "connected" is not a conjunctively local property of any order (for definition of conjunctively local see appendix at the end of this question).

In particular goes as follows:

Suppose that $\psi_{CONNECTED}$ has order K. Then to distinguish between these two $k+1$-wide figures:

there must be some $\varphi_0$ such that $\varphi_0(X_0) = 0$, because $X_0$ is not connected. All $\varphi$'s have value 1 on $X_1$, which is connected. Now $ \varphi_0$ can depend on at most $k$ points, so there must be at least one middle square, say $S_j$, that does not contain one of these points.

This last sentence is the one that does not make sense to me. Why does there must be at least one middle square that does not contain one of these points? I don't understand this. When it says "these points" what does that mean? Why are we talking about the middle points? Why does that matter? Also, the sentence as a whole doesn't make sense to me nor its purpose.

Like the first two properties make sense:

of course there must exist a $\varphi_0$ that rejects $X_0$, since $\psi_{CONNECTED}$ can only work properly if all of its predicates say YES if and only if the shape is connected. Since $X_0$ is not connected then some predicate must reject it. That is clear.
For a similar reason its obvious that all the predicates say YES on $X_1$ since its connected. More precisely, that is the definition of connected according to $\psi_{CONNECTED}$, that all its predicates say YES. Since $X_1$ is connected then all its predicates must say YES.
Last part that does make sense before my brain gets confused is that of course $\varphi_0$ can depend on at most $k$ points. This is obvious from the definition of $\psi_{CONNECTED}$. i.e. we assume $\psi_{CONNECTED}$ is conjunctively local of order $k$ so all of the predicates $\varphi$ can only see $k$ points.

however, the existence of $S_j$ doesn't make sense to me and thus, the remaining of the proof remains a mystery to me. If anyone can clarify that and the remains of the proof that would be fantastic!

Also, for completion, the whole proof is provided in the appendix2.

Appendix::

Recall the definition of Conjunctively local:

A predicate $\psi$ is conjunctively local of order k if it can be computed by independently computing a set of functions $\varphi_1(X)$...$\varphi_n(X)$ and then combined by the results of another function $\Omega$ of n argument by a set $\Phi $ of predicates $\varphi$ such that each $\varphi$ depends no more than $k$ points on a 2D Euclidean plane $R$ and:
$$
\psi(X) = \begin{cases}
1 \text{ if } \varphi(X) = 1 \text{ for every } \varphi \text{ in } \Phi \\
0 \text{ otherwise. }
\end{cases}
$$

or directly from Minsky's and Papert's book:

Appendix 2:

Proof of theorem 0.6.1

The predicate $\varphi_0$ depends on at most $k$ points. There are $k+1$ middle squares. So $\varphi_0$ cannot depend on all of them. That is, there is a middle square that $\varphi_0$ does not depend on. Therefore, if we add that square, the value of $\varphi_0$ doesn't change, and so $\psi$ is still 0, even though the figure is now connected.


Skip List randomization complexity I understand the basics of Skip Lists and their implementation also the basic Search Insert Delete functions and their run time complexity. Recently after a lecture, a professor proposed an interesting question. He asked what we suspected the total time building a skip list using randomization.

A few hints were given:

$n \times (1/2 + 1/4 + \dots + 1/2^{k})$.
I understand this as, For every level of the skip list their is said to be half the nodes working from bottom level to the next one above it.
Using a geometric equation we came up with this formula: $n \times \frac{1/2^{k+1} - 1/2}{1/2 - 1}$

So ultimately what is the time complexity? $\Theta(n^2)$?

According to the hint, the number of elements in the levels beyond the first is expected to be
$$
n \cdot (1/2 + 1/4 + \cdots + 1/2^k).
$$
Presumably, $k \approx \log n$, though as we will see, this doesn't really matter.

Let's plug in some numbers to see how this behaves. When $n = 100$ and $k = 10$, we get
$$
100 \cdot (1/2 + 1/4 + \cdots + 1/2^{10}) \approx 99.9.
$$
When $n = 1000$ and $k = 15$, we get
$$
1000 \cdot (1/2 + 1/4 + \cdots + 1/2^{15}) \approx 999.97.
$$
When $n = 10000$ and $k = 20$, we get
$$
10000 \cdot (1/2 + 1/4 + \cdots + 1/2^{20}) \approx 9999.99.
$$
What is happening here? Massaging the formula for the sum of the geometric series, we get
$$
n (1/2 + 1/4 + \cdots + 1/2^k) = n (1 - 1/2^k).
$$
So as $k$ gets larger, the value of this formula gets closer and closer to $n$. Moreover, if $k \geq 1$ (say), then
$$
\frac{n}{2} \leq n (1/2 + 1/4 + \cdots + 1/2^k) \leq n.
$$
So from the point of view of asymptotic analysis, this expression is $\Theta(n)$ rather than $\Theta(n^2)$.


Generate a random graph with geometrical degree distribution I'm working on graph generation, trying to implement the RT-nested-Smallworld network model described in this paper.

We are talking about generating an undirected graph in a slightly different way than what the Watts-Strogatz model does.

One of the very first steps of the algorithm is

  instead of selecting links to connect most immediate $\langle k \rangle / 2$ neighbors to form a regular lattice, our model selects a
  number $k$ of links at random from a local neighborhood $N_{d_0}$ with
  the distance threshold of $d_0$, where $k$ comes from a geometric
  distribution. The local neighborhood is defined as the group of
  close-by nodes with mutual node number difference less than the
  threshold $d_0$, that is $N^{(i)}_{d_0} = \{j; |j-i| < d_0\}$, for
  node $i$. It is worth noting that our model adopts a geometric
  distribution with the expectation $\langle k \rangle$ of for the
  initial node degree settings (i.e, for the link selection).

In other words, each node with index $i$ should have a (possibly different) random degree $k$, obtained by linking it with nodes with an index-distance $d_0$.

First of all, I need to choose the parameter $p$ to generate the geometric distribution. If the average is $\langle k \rangle$, I choose $p = 1/\langle k \rangle$.

However, picking $n$ node degrees from a geometric distribution may not result in a feasible graph of $n$ nodes.

Moreover, Since this is an undirected graph we are talking about, going through each node and creating a random number $k$ of links will most likely not produce the desire average degree. E.g. during the ith iteration, the node i may already have more than $k$ links, created by the previous iterations of nodes randomly linking to it.

I tried to implement my own algorithm to distribute the node degrees as close as possible to the distribution outcome. Pseudocode

k_values = n values from the geometric distribution with p = 1/<k>
for each node in [0, n)
    if degree(node) < k_values[node]
        for each neighbor closer than d_0
            if degree(neighbor) < k_values[neighbor]
                if not link_exist(node, neighbor)
                    create_link(node, neighbor)

The problem is, this approach tends to consistently result in nodes having lower degrees than the output of the geometric distribution.

I know there are ways to generate an undirected graph with a given degree distribution. The biggest problem here seems to be the additional constraint on the potential neighborhood of each node (i.e. nodes within index-distance $d_0$). Any ideas on how to solve that?

I would be happy getting a graph that is within a certain threshold from the outcome of the geometric distribution, and still quite close to the intended average degree $\langle k \rangle$.

You can use the configuration model for this. Create a "stub" array where each of the $n$ vertices appears in the array $k_i \sim \text{Geom}(p)$ times. Shuffle the array and then treat each adjacent pair in the array as an edge in the graph. Here's some python code to illustrate.

from numpy.random.mtrand import geometric
from random import shuffle
from _collections import defaultdict

if __name__ == '__main__':
    # Number of vertices
    n = 1000

    # Geometric distribution probability parameter
    p = 0.5

    stubs = []
    for i in xrange(0, n):
        # Sample the degree from the geometric distribution
        degree = geometric(p)
        # Insert into the stubs array the current vertex label degree times
        stubs += [i] * degree

    # Shuffle the values
    shuffle(stubs)

    # Build the graph
    G = {}
    for i in xrange(0, n):
        G[i] = []

    for i in xrange(1, len(stubs), 2):
        G[stubs[i]].append(stubs[i-1])
        G[stubs[i-1]].append(stubs[i])

    # Recover the degree distribution
    degrees = { i : len(neighbors) for i, neighbors in G.items() }

    dist = defaultdict(int)
    for (vertex, degree) in degrees.items():
        dist[degree] += 1

    print("Degree, empirical, theoretical")
    for (degree, freq) in dist.items():
        print("%d %f %f" % (degree, freq / float(n),  pow((1 - p), degree - 1) * p ))

Sample output:

Degree, empirical, theoretical
1 0.496000 0.500000
2 0.254000 0.250000
3 0.128000 0.125000
4 0.071000 0.062500
5 0.023000 0.031250
6 0.018000 0.015625
7 0.005000 0.007812
8 0.003000 0.003906
9 0.002000 0.001953

For more detailed description of the the configuration model, see Section 13.2 p. 435 of Networks by Newman.


Examples of sophisticated recursive algorithms I was explaining the famous deterministic linear-time selection algorithm (median of medians algorithm) to a friend.

The recursion in this algorithm (while being very simple) is quite sophisticated. There are two recursive calls, each with different parameters.

I was trying to find other examples of such interesting recursive algorithms, but could not find any. All of the recursive algorithms I could come up with are either simple tail-recursions or simple divide and conquer (where the two calls are "the same").

Can you give some examples of sophisticated recursion?

My favorite recurrence shows up in output-sensitive algorithms for computing convex hulls, first by Kirkpatrick and Seidel, but later repeated by others.  Let $T(n,h)$ denote the time to compute the convex hull of $n$ points in the plane, when the convex hull has $h$ vertices.  (The value of $h$ is not known in advance, aside from the trivial bound $h\le n$.)  Kirkpatrick and Seidel's algorithm yields the recurrence
$$
  T(n,h) = \begin{cases}
       O(n) & \text{if }n \le 3 \text{ or } h \le 3 \\
       T(n_1, h_1) + T(n_2, h_2) + O(n) & \text{otherwise}
  \end{cases}
$$
where $n_1, n_2 \le 3n/4$ and $n_1 + n_2 = n$ and $h_1 + h_2 = h$.

The solution is $T(n,h) = O(n\log h)$.  This is a little surprising, since $h$ is not the parameter being split evenly.  But in fact, the worst case of the recurrence happens when $h_1$ and $h_2$ are both about $h/2$; if somehow magically $h_1$ is always constant, the solution would be $T(n,h) = O(n)$.

I used a variant of this recurrence in one of my first computational topology papers:
$$
  T(n,g) = \begin{cases}
       O(n) & \text{if }n \le 3 \text{ or } g = 0\\
       T(n_1, g_1) + T(n_2, g_2) + O(\min\{n_1, n_2\}) & \text{otherwise}
  \end{cases}
$$
where $n_1 + n_2 = n$ and $g_1 + g_2 = g$.  Again, the solution is $O(n\log g)$, and the worst case occurs when both $n$ and $g$ are always split evenly.


How to efficiently select the initial node to start a search in a Skip Graph Checked out a few papers on Skip Graphs:

Locally Self-Adjusting Skip Graphs
Adaptive Probabilistic Skip Graphs
Skip Graphs
Family Trees

All of the insertion/deletion algorithms assume that you have selected a start node to begin the search. However, it is not described how the start node is selected. In doing some initial exploration into how to do this, I start thinking in terms of the following:

level1nodechunk1 = count next node node node ....
level1nodechunk2 = count next node node node ....
...

Basically, a level is just a bunch of nodes:

node node node ...

If you are to randomly select a starting node, and they are not contiguous in memory, then you have to navigate your way there. So instead of going one node at a time, I group it into chunks for the particular level, and specify the count and next so you can jump ahead to the next one if desired.

So say you generate a random number x = random num between 0 and totalnodecount. Say it is 20 and each level chunk has 5 nodes. Then you would do:

level1nodechunk1 = [count] [next] (5)
level1nodechunk2 = [count] [next] (5 + 5 = 10)
level1nodechunk3 = [count] [next] (10 + 5 = 15)
level1nodechunk4 = count next node node node node [node5]

You would jump over chunks 1-3 and get to chunk 4, see it has 5 contiguous nodes, and jump to that one. So it's just ~5 instructions instead of 20 (one per node) roughly.

But the problem is if you have 1 billion nodes. Then if each one is only 5 nodes, then you have 200 million chunks, so ~200 million instructions. So maybe you make the chunks to be 10,000 nodes each, that's still 100,000 instructions to find the start node.

I'm wondering how they do this efficiently.

If all the nodes were contiguous then it would be easy, $O(1)$ lookup by index. If you hardcode a chunk count so we only have say 20 chunks, no matter how many nodes, then you have to account for the worst case of lets say 1 billion nodes. So that means each chunk is 50 million nodes. But if you have only currently used 10 nodes out of 1 billion, then that's tons of wasted memory reserved.

The only other thing I can think of is that the start node is always the actual first node in the lowest level of the skip graph, then you navigate to the top-level for that node and work your way back down.

IIRC, the reason to "randomly" select a start node is to prevent hotspots.

Another possible solution is to cycle through the level 0 nodes. Basically:

Start at the start level 0 node.
Cache the next node it points to as the future start node.
Next query, the start node is that cached node. Then set next node to its pointer, etc.

But that would give preference to the first nodes more than the last (i.e. it's not random).

First, the skip graph is a distributed data structure. There is no reason to use it in a single machine context.

For a singly-linked skip list (on a single machine), you would start at the beginning. This is trivial to find; you just hold a pointer to the first node. For a doubly-linked skip list, you could start at any node, though unless you had some cursor-like abstraction, you'd presumably start at the beginning for most operations anyway.

A skip graph is effectively a collection of doubly-linked skip lists that share structure. There is no need to start at the beginning. This allows the machine on which to initiate an operation to be chosen arbitrarily. In a public peer-to-peer context, you are usually only aware of one or a few machines. In a data-center context, usually a load balancer will choose the machine.

A machine will generally host many nodes of the skip graph. It's not clear to me how much it matters to pick a local node at random. Typically, only some of the nodes will be connected to nodes on other machines, so picking any other node is the same as picking one of these as far as spreading load between the machines. Nevertheless, if you wanted to pick randomly from the local nodes there are a variety of approaches. Since you are only concerned about local nodes, you are free to use any non-distributed data structure to keep track of them. For example, a size-balanced tree would work. You would pick a number between 0 and the number of local nodes, and then do a rank query on a size-balanced tree containing (pointers to) the local nodes. Alternatively, you could probably get something close to a uniform distribution on average by assuming that the any one of the local portions of the skip lists making up the local portion of the skip graph is perfectly "balanced". This lets you estimate how many nodes you are skipping when you traverse a link at a given level which lets you do an approximate rank query directly against (the local portion of) the skip graph. Neither of these approaches is likely to affect the asymptotic complexity of any operation.


Partial intersection of 10 sorted lists of integers Suppose I want to find the numbers that appear in at least 3 of the 10 sorted lists, is there an efficient way to do it apart from iterating over all 10 of them in parallel?

The simplest way is to first remove duplicates from the 10 lists, and then merge all of them. Any number appearing 3 times in the merged list also appears in 3 of the 10 sorted lists.

A more complicated way is using pointers as you indicate. Briefly, the pointers start at the beginning of the lists, and then you keep incrementing the pointer pointing at the minimal element. You can use a heap to implement detecting which pointer to advance.

If you have $m$ lists containing $n$ elements in total, the first way takes optimal time $O(n)$ but uses up space (or modifies the input), and the second takes time $O(n\log m)$ (the $\log m$ comes from the heap) but uses less auxiliary space.


Why do most scientists believe that P≠NP? I read that most scientists don't believe that P=NP. It might be subjective but can you simplify why not? I'm not informed enough to have an opinion but I'd like to know the definitions and some "pretty simple" explanation why to believe one or the other case, for instance why even believe that it can be proved?

An NP-complete problem can be transformed into another NP-complete problem. There's an abundance of known NP-complete problems, in fact, one could even say that any really interesting problem is NP-complete. So if you know of a way of solving any NP-complete problem $X$ quickly, you can take any other NP-complete problem, transform it into an instance of $X$, and solve that quickly as well.

Several smart researches have spent a lot of time on researching these hard problems. Despite all the efforts and years, we still don't have a polynomial time algorithm for any of the NP-complete problems. We also have conditional results of the form "if you can do this faster/better, then P=NP".

As for proving the claim, we don't perhaps know much for sure. What we do know is that whatever the proof looks like, it can't be of a certain type. So at least if there ever was a proof, it will have to address how it avoids some known difficulties.

For more details, you could first have a look at Sipser's book, and then the Arora-Barak book.


surprizing reducibility and challenge on it Assume that Problem $A$ is polynomial-time reducible to problem $B$.
Claim 1: If problem $A$ is NP-hard then problem $B$ is NP-hard.
Claim 2: If problem $B$ is NP-hard then problem $A$ is NP-hard.
Claim 1 is obviously true, but why the second one is false?

I am assuming that $A$ is a non-trivial problem. If $A$ is trivial, then the claims cannot be correct in their current form (make sure you understand why).
Consider an  NP-complete problem $B$, and consider some non-trivial problem $A \in \text{P}$. Clearly, $A\leq_p B$. If we assume that claim 2 is correct, then as $A\leq_p B$, we get that $A$ is $\text{NP}$-hard and thus for every problem $L\in \text{NP}$, it holds that $ L\leq_p A$. Hence, as $A\in \text{P}$, we get that $L\in \text{P}$ as well, and so $\text{NP}\subseteq \text{P}$.
Conversely, if we assume that $\text{NP}\subseteq \text{P}$, then as every non-trivial problem is $\text{P}$-hard, we get that every non-trivial problem $A$ is $\text{NP}$-hard. Hence, claim 2 holds trivially.
So we have in total that claim 2 is correct iff $\text{P} = \text{NP}$ which is quite open.


What is the "Chairman Tree"? My competitive programming coach told me of a balanced binary tree used by a lot of Chinese competitors that has all the functions of any other balanced binary tree and is fully persistent and runs queries and updates in ${O(log^2N)}.$ What information is there on this tree, and does it go by a different, more popular name?

To be clear, any data structure that fulfills the above will be considered as a correct answer. The first one will be marked correct. If there is a link, that would be the best.

I've been doing competitive programming for several years at a very high level and haven't ever heard of a Chairman tree. Though I still can tell you how to make any data structure persistent. In case of BSTs and segment trees it even doesn't increase the running time (asymptotically, of course; you can notice some slowdown in practice).

First, let's consider a basic segment tree. I'll write C++-ish code because such trees, when made persistent, are most conveniently interpreted with pointers. For sake of simplicity I'll describe a (rather stupid) tree with two simple operations: assign a number to a position $i$ and get a number on a position $i$.

struct node {
    int l, r;
    node *L, *R;
    int value;

    void put(int i, int x) {
        if (l == r) value = x;
        else if (i <= L->r) L->put(i, value);
        else R->put(i, value);
    }

    void get(int i) {
        if (l == r) return x;
        else if (i <= L->r) return L->get(i);
        else return R->get(i);
    }
}

For those who are not familiar with notation (though it should be clear from the code): a node represents a segment $[l, r]$ of an array. When $l = r$ the node is a single element, else it has two children, $L$ and $R$, having ranges, respectively, $[l, (l+r)/2]$ and $[(l+r)/2+1, r]$.

When you put a value to a tree, you modify it. But we may notice that each modification touches only $O(\log n)$ nodes of a tree, so instead of modifying existing nodes we may copy them and apply updates only to the new vertex.

Here is the outline: whenever the function wants to modify a node, it makes a copy, modifies a copy and returns the copy back to the caller (because the caller wants to update himself too). In this example only put must be modified, and here we go:

node* put(int i, int x) {
    node *t = this->makeCopy();

    if (l == r) t->value = x;
    else if (i <= L->r) t->L = t->L->put(i, value);
    else t->R = t->R->put(i, value);

    return t;
}

Voi-la! Now we have got a fully-functional persistent array which takes $O(\log n)$ time and space per operation. You only have to store pointers to the roots of versions you need, and as long as the pointer is saved, it will stay untouched. Forever.

The very same technique may be applied to any kind of a segment tree, giving no overhead in time (because segment tree queries are already $O(\log n)$. More, you can use this approach with BST's. The most reasonable choice of a structure to make persistent is a Treap, mostly because it does not require storing pointers to parents. It might be hard to understand which values exactly one should clone while splitting and merging, but it is done in several minutes with pencil and paper.

Now a bonus and a tiny warning. First, you can make any data structure persistent: just implement it using persistent arrays :) If the structure itself is not tree-ish, this will cost you a logarithmic increase in time, of course. Second, this technique cannot be applied to any DS which running time is amortized, so be careful with persistent splay tree.

Hope this helps, and don't hesitate to ask something in comments!


Big O and program calls with varied input sizes Suppose I have a program p that has time complexity $O(n)$ and a second program q that calls program p $m$ times. If we know the input size of p will be the same every one of those times (n), we can say that the complexity of q is $O(m \times n)$. This case sounds pretty simple to me.

However, suppose the input size of p varies over these $m$ times, from $0$ to $m-1$.

If we knew that p ran precisely $f(n) = a \times n$ instructions for an input of size $n$, it would be simple: q would run $a \times 0 + a \times 1 + \ldots + a \times (m-1) = am(m-1)/2$ instructions exactly, which is $O(m^2)$.

However, in this case, all we know is that $f(n)$ is below $a \times n$ for all $n$ greater than some $n_0$, by the definition of big-O. We can't say for sure that $f(0) + f(1) + ... + f(m-1)$ is below $a \times 0 + a \times 1 + \ldots + a \times (m-1)$, because we don't know that $0, 1, \ldots, m-1$ are greater than this $n_0$. For this reason, I don't think we can say that q runs in $O(m^2)$.

Is there a way, in this case, when all we know is the big-O behaviour of p, to analyze q?

What if we replace all the big-O's with big-Theta's?

Actually, since you did not specify what q does beyond calling p, there is too little information to know anything about the time complexity of q, except that it is $\Omega(m)$ since it must execute at least $m$ calls to p, whatever else it does.

Let's look at a special case which is probably what you were thinking of. Suppose that q looks like this:

data := preprocess(input);
for i = 0 to m -1 do
    data := p(data);
end

That is, p potentially has access to all the internal data of q. This is the most general case. Where this program is not general is that in the loop, it does nothing but call p.

The running time of this program is $Q = A + \left( \sum_{i=0}^{m-1} P(S_i) \right) + O(m)$ where

$A$ is the time taken to run the preprocessing step;
$P(s)$ is the maximum time taken by p to process data of size $s$;
$S_i$ is the size of data when the $i$th step starts.

The assumption on the running time of p is that $P(s) = O(s)$. That is, there exists $n_0$ and $a$ such that if $s \ge n_0$ then $P(s) \le a \, s$. This gives us a bound for the running time when $s$ is large. When $s$ is small, we can simply use the maximum running time of p for small sizes: there are only a finite number of sizes that are smaller than $n_0$. Let $\hat P = \max\{P(0), P(1), \ldots, P(n_0-1)\}$.

Then, expanding the definition of $O(m)$ in the equation for $Q$ above, we get that there exist $m_0$ and $b$ such that for $m \ge m_0$,
$$ \begin{align}
  Q &\le A + \left( \sum_{i=0}^{m-1} P(S_i) \right) + b m
     \le A + \left( \sum_{i=0}^{m-1} \max \{\hat P, a\, S_i\} \right) + b m \\
    &\le A + \left( \sum_{i=0}^{m-1} (\hat P + a\, S_i) \right) + b m
     \le A + a \left( \sum_{i=0}^{m-1} S_i \right) + (b + \hat P) m \\
    &\le A + a \left( \max\nolimits_{i=0}^{m-1} S_i \right) m + (b + \hat P) m
\end{align} $$

Notice how the constant $\hat P$ resulting from the small cases of running the subprogram has been absorbed into the multiplicative constant for the calling program. This is a general phenomenon: when studying the complexity of algorithms, the performance of subtasks on small inputs is irrelevant for obtaining a first bound on the complexity of the whole task. It can be relevant to prove better bounds (sometimes, the inequalities above are too crude).

We aren't quite there yet: the component $\max\nolimits_{i=0}^{m-1} S_i$ remains unevaluated. The behavior of this component depends on what p does. For example, if p is a program that duplicates its input, say

return arg ++ arg

where ++ is the string concatenation operator and string concatenation takes $\Theta(n)$ where $n$ is the length of the string, then $S_i = S_0 2^i$ and all the analysis above tells us is that $Q$ grows exponentially with $m$ — which is the case.

If we additionally assume that p does not change the size of the data and that the preprocessing step is linear in the size of the input, then $S_i$ does not depend on $i$ and is $O(n)$ (i.e. $S_i \le S n$ for large enough $n$), and we have (for sufficiently large $n$ and $m$):
$$
  Q \le a' n + S n m + (b + \hat P) m
$$
For sufficiently large $n$ and $m$, the dominant term is $S n m$: the time complexity of Q is $O(m n)$.

Note again that the reason why it took a lot of additional assumptions to prove that Q runs in $O(m n)$ is not the running time of p on smaller inputs, it's because for all we knew p could receive some very large inputs.


Solving recurrence relations using substitution followed by tree method/masters theorem $T(n) = 4T(\sqrt n) + n$

First I substitute n = $2^k$:

$T(2^k) = 4T(2^{k/2}) + 2^k$

Now I rename the above as follows:

$S(k)=4S(k/2) + 2^k$

Now if I try to use tree method on this in the following way:

Work done at Level 1 = $2^k$

Work done at Level 2 = $2^{k/2} * 4$

Work done at Level 3 = $2^{k/4} * 16$
and so on.
We have a total of $log\ k$ levels. The final term is dominant. So we should get $2^{k/{2^{log\ k}}} * (log\ k)^2$

That gives me the answer as $T(n)=(log\ k)^2$ = $(log\ log\ n)^2$

Second method:

$T(2^k) = 4T(2^{k/2}) + 2^k$

Divide each term by $2^k$:

$T(2^k)/2^k = 2T(2^{k/2})/2^{k/2} + 1$

Now rename it as follows:

$S(k)=2S(k/2) + 1$

Now using masters theorem on the above gets us $T(n) = k = log\ n$

The actual answer seems to be $n$.
So, where am I making the mistake? Please let me know the the mistake in both the methods.

(Note: I actually mean asymptotic notation as the final answer).

For your first method, it is dominated by the first term, not the last.  (The second term is $2^{k/2} * 4 = 2^{(k/2)+2} < 2^k$ for $k$ large.)

In your second method, when you divide each term by $2^k$, you didn't.  You divided the second term by $2^{(k/2)+1}$ instead.


construct a TM decides in linear time, if valid bracket I want to construct a 2-tape Turing Machine, which decides in linear time if the input string over $\Sigma^* := \{(, [, ], )\}$ is a valid bracket.

I have not constructed too many TM's yet, this is why I need your help.

If you are not allowed to use two or more tapes then as Yuval Filmus commented you cannot solve in linear time. Otherwise you can convert the following steps into TM instructions:

 Initially input on the tape 1, the tape 2 is empty.
 Machine reads input symbols stored on the tape 1, and tape 2 is used as stack (for push/pop operations).

 1)  x = Read a symbol.
 2)  If x is '[' or '(' Then
 3)    push x and go to 1)
 4)  Else If x is ')' Then
 5)    sym = pop()
 6)    If sym != '(' Then
 7)       Reject and Halt.
 8)    Else
 9)       go to 1)
 10) Else If x is ']' Then
 11    sym = pop()
 12)   If sym != '[' Then
 13)      Reject and Halt.
 14)   Else
 15)      go to 1)
 16) Else If x is '$' Then (if end of input)
 17)   If stack is empty Then
 18)      Accept and Halt
 19)   Else
 20)      Reject and Halt
 21) Else
 22)   Reject and Halt

I think translation to a TM of this piece of code is quite tedious work.

In computability theory if you want to prove existence of a TM then informal description (or just description using one of the high-level programming languages) is enough. You may use a single tape TM model or multitape model. However, when dealing with time complexity selection of a model matters.


Estimating run time of of while loops? i, sq ← 1, 1
while sq < n
    for j ← 1 to sq
        k ← 1
        while k ≤ j
            k ← 2 ∗ k
    i ← i + 1
    sq ← i ∗ i

I have Expressed the running time of the for loop as a sum in this way :
$$\sum_{j=1}^{i^2} log(j)$$
In a similar way, how can I express the running time of outer while loop with sigma in terms of i ?
I have tried the following:
$$\sum_{i=1}^\sqrt{n} i^2log(i)$$

The outer most while loop ends when $\text{sq} = n$ and by definition $\text{sq} = i^2$ and thus it will run $i^2 = n \Rightarrow i = \sqrt{n}$ times ( as we increment $i$ by one each iteration).
Note that -
The for loop runs at $\log(j)$ from $1$ to $\text{sq} = i^2$ and $1 \leq i \leq \sqrt{n}$  so we have this sum:
$$\sum_{k=1}^{i^2}\log(k) ~~ \forall i \in\{1,2, \dots,\sqrt{n}\}$$
Recall: $\log(a) + \log(b) = \log(a \cdot b)$
Some examples:
$i=1 \Rightarrow \sum_{k=1}^{1}\log(k) \Rightarrow \log(1!)$
$i=2 \Rightarrow \log(4!)$
$i=3 \Rightarrow \log(9!)$
$i=4 \Rightarrow \sum_{k=1}^{16}\log(k) = \log(1)+\log(2) + \dots + \log(16) \Rightarrow \log(16!) ~~~~~~ \\
\text{etc... until } i=\sqrt{n}$
And thus this whole system of loops runs at:
$$\sum_{k=1}^{ \sqrt{n}}\log[(k^2)!] = \log{( \prod_{k=1}^{\sqrt{n}}k^2! )}$$
This can be bounded by $O(\sqrt{n} \log(n!))$ or $O(n^{1.5} \log(n))$ by taking the largest element in that sum ( $\log(n!)$ ) and multiplying it by the number of elements ( $ \sqrt{n}$ )


Is this padded version of the Halting Problem in NP? I'm using the following definition of $NP$:

$$A \in NP \Longleftrightarrow A(x) = \exists w: B(x,w) $$
where $B \in P$ and $|w| = poly(|x|)$.

Now instead of the problem whether the program $\Pi$ halts on input $x$, I'll use the close cousin that asks whether $\Pi$ halts on $0$. Then I can write:

$$HaltsOnZero(\Pi) = \exists t: HaltsOnZeroInTime(\Pi, t) $$

where $HaltsOnZeroInTime$ is the decidable problem of checking whether $\Pi$ halts on input $0$ after $t$ steps. Comparing this with the definition of $NP$ $HaltsOnZeroInTime$ is already in $P$ as long as $t$ is encoded in unary. After all running $\Pi$ for $t$ steps takes only about $t$ steps, so this is a linear algorithm.
The only issue is that $t$ isn't in $poly(|\Pi|)$ because programs of size $|\Pi|$ when given $0$ as input run for $BusyBeaver(|\Pi|)$ time, which isn't even computable, much less polynomial. But now suppose we insist that $\Pi$ is padded until it reaches length $BusyBeaver(|\Pi|)$ and call that new input $\Pi'$. Then $t$ would be polynomial (in fact linear) in the size of $\Pi'$ and $HaltsOnZero(\Pi')$ would be in $NP$.
At this point there's of course a voice inside me shouting that this is all nonsense because $BusyBeaver$ isn't computable. Well I certainly haven't reduced the classical formulation of the Halting Problem to a problem in $NP$ because I had an uncomputable step in the reduction. But it seems to me like I've still defined a problem in $NP$ with the strange property that just writing down a problem instance requires uncomputable superpowers.
Is this really a bona fide $NP$-problem or am I making a subtle mistake somewhere?

Unless you're talking about promise problems, you are required to handle arbitrary inputs.

Given a string $x\in\left\{0,1\right\}^*$, we have $x\in L$ iff $x=\langle M\rangle \cdot BB\left(|M|\right)$ and $M$ halts for some fixed input ($\cdot$ denotes concatenation).

This means that even before talking about the witness (which is indeed linear), you must verify that $x$ has this specific form (unlike in promise problems, where you only care about specific inputs), and this is undecidable.

Note that this only shows why your justification to why this problem is in NP does not work. However, this language is obviously undecidable, since otherwise you could compute $BB(x)$, and thus lies outside of NP.


Is a bitstring easier to compress if it has lower Kolmogorov complexity? I have two bitstrings that are 100 bits long.  Bitstring A has a Kolmogorov complexity (KC) of 90 and bitstring B has a KC of 10.  Intuitively, I think bitstring B is probably easier to compress than bitstring A.

"Easier to compress" means a larger proportion of 100 bit bitstrings with B's KC can be compressed by a standard compression algorithm, than bitstrings with A's KC.

What I mean is that B probably has much more regularity that can be exploited by a compression algorithm such as Lempel-Ziv, whereas A is probably much more random and irregular.

Is this intuition correct?  If so, how is this relation quantified?  Can I say B is 9 times as likely to be compressible than A?

I think your intuition is not correct. We can't effectively reason over the space of all programs, even all programs up to a given size (e.g. 90 for A and 10 for b) and it's not certain what the units are in your given KC measures for B and A.

As a simple example, imagine a program B that decompressed a highly compressible message and then encrypted it using some cipher and a hardcoded key. And imagine a different program A that simply output a hardcoded random string of the same length as the one produced in B. Given a long enough output, you could make K(output(B)) << K(output(A)), but both would be highly uncompressible without having the decryption key for B available.

What you're talking about sounds something like this:  https://en.wikipedia.org/wiki/Algorithmic_probability. It is uncomputable, but if you are willing to e.g. limit the execution time of programs and randomly sample from random programs, you can start to analyze very simple examples.


What circuit depth is required to add? If we suppose that we are given two numbers $a$ and $b$ to add, what circuit depth do we require to add them?

I'm wondering if $a$ and $b$ are $O(n)$, and thus the amount of bits required to store $a$ and $b$ are $O(\log_2(n))$, how much time and/or space we must require to add them.

I'm interested in the general case.  However, I am wondering if there is anything else to be said about the case of adding $a+2a+1$.  It would be spectacular if we could do this addition in constant circuit depth.

To add two $n$-bit numbers, you need a circuit of depth $\Omega(\lg n)$.  Depth $O(\lg n)$ is also achievable, so the lower bound is tight.

There are many examples of such circuits; for instance, a carry lookahead adder has depth $O(\lg n)$ (and size $O(n)$).  One can even achieve depth $\lg n + o(\lg n)$; for instance, a Krapchenko adder has depth $\lg n + O(\lg^{1/2} n)$ (and size $O(n)$).

This all assumes bounded fan-in gates, as usual.  If you allow AND and OR gates with arbitrary fan-in, then you can achieve constant depth (depth 3, I think).  See, e.g., https://en.wikipedia.org/wiki/AC0.


Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$ Possible Duplicate:
  Solving or approximating recurrence relations for sequences of numbers

I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is  $ T(n) = O(n \log(n))$

But how do you get to that point? I don't understand when it says put t into the equation repeatedly until it drops out...

Any help?

It means "open" the recursion.

For simplicity - denote $O(n)$ as $c\cdot n$:

$$ \begin{align}
T(n) &= 2T(n/2) + cn \\
&= 2(2T(n/4) + cn/2) + cn\\
&= 2  (2  (2T(n/8) + cn/4) + cn/2) + cn\\
& \vdots
\end{align}$$

It might give you intuition, but it is NOT a proof. To prove it, you will need mathematical induction or the master theorem.

Proving with induction (assuming O(n) component  is n for simplicity):

Claim: T(n) <= n*logn + n

Base:
T(1) = 1 (assumption)

Assumption: the claim is correct for all k < n.
Proof:

T(n) = 2T(n/2) + n = (assumption) <= 2* (n/2 * log(n/2) + n/2) + n
     = n*log(n/2) + 2n = n*(log(n)-log(2)) + 2n = (assuming base 2 for log)
     = n*(log(n) -1 ) + 2n = nlogn -n + 2n = n*logn +n

QED


Algorithm. Input: pointers to k unsorted arrays of different lengths. Needed output: k sorted arrays $k = \Theta(n)$

The arrays consist only natural numbers $1$ to $n$

The sum of the length of all arrays = $\Theta(n)$

It should return the $k$ original arrays, each sorted on its own.

The running time should be at worst $\Theta(n)$.
How is it even possible? There's something I must be missing because I have no idea how to approach this.
The data I gave you is all the given data. Any ideas?

Using counting sort on each array won't work, for it will be $\Theta(n^2)$, but maybe a different approach using this method?

You can solve the issue by using some pointers. First, run counting sort algorithm on all arrays in $\Theta(n)$ (suppose all of them are in a set). In the meanwhile, when running the algorithm, set a pointer for each number of each array  to the sorted index of that number.

Using this data structure, you will have $k$ sorted arrays at the end.


Context-free grammar for $\{a^x b^y : x \neq y\}$ I am trying to create a context free grammar in Extended Backus–Naur form, which starts with a non-empty sequence of a's and is followed by a non-empty sequence of b's. With the special condition that the number of b's has to be unequal to the number of a's.

Thus, the grammar should generate words like:

aaaabbb
aaabb
abbb

So basically I could do something like this:

$\ G=(N,T,P,S)$

$\ N = \{S\}$

$\ T = \{a,b\}$

$\ P = \{S=aa(S|\epsilon)b\}$

But then the words would always have $\ 2n$ a's and n b's:

aab
aaaabb
aaaaaabbb

So how is it possible to make the number of a's uncorrelated of the number of b's, without being equal?

Let $L = \{a^n b^n : n \in \mathbb N\}$. Your language can be written as $a^+L \cup Lb^+$, and this leads to the following grammar:
$$
\begin{align}
&S \to AT \mid TB \\
&T \to aTb \mid \epsilon \\
&A \to aA \mid a \\
&B \to bB \mid b
\end{align}
$$
We can save a nonterminal by factoring $L$ differently:
$$
L = \{a^na^mb^n : n \geq 0, m \geq 1\} \cup \{a^nb^mb^n : n \geq 0, m \geq 1\}.
$$
This leads to the following grammar:
$$
\begin{align}
&S \to aSb \mid A \mid B \\
&A \to aA \mid a \\
&B \to bB \mid b
\end{align}
$$
There are many other possible variants, for example:
$$
\begin{align}
&S \to A \mid B \\
&A \to aAb \mid aA \mid a \\
&B \to aBb \mid Bb \mid b
\end{align}
$$


Helping prove this notation for Big-O(n!) Hello, I was wondering if anyone can help me prove the right part of this double equation. I know the left one is possible due tolog(n!) = Θ(nlogn). Any help is much appreciated.

Remember that $\Theta(5n \log n^5) = \Theta(n \log n)$, since constant factors don't matter.

Then $\Theta(n \log n) = \Omega(n \log n)$, by the definition of big theta.

$\Omega(n \log n) = \Omega(n)$, because log is monotonic increasing (so we can remove it and still have a valid lower bound).

Finally, $\Omega(n) = \Omega(n^{2/3})$, by the properties of power functions.


Why does SAT not reduce to QBF? So, I remember the professor saying that SAT does not reduce to QBF (Quantifier Boolean Formula)

$QBF ::= prop|-QBF|(QBFoQBF)|\exists pQBF |\forall pQBF$

So, I guess this is not NP, since solving a QBF could grow exponentially.

However, $P \subseteq NP \subseteq PSPACE \subseteq PSPACE$-complete, so shouldn't I be able to reduce NP < PSPACE-complete, hence SAT < QBF?

The reduction would just use the same formula of PSAT in QBF.

Am I correct?

First, be carefull, it might be that PSPACE ⊄ PSPACE-complete. If you suppose PSPACE ⊆ PSPACE-complete (thus PSPACE = PSPACE-complete since the other inclusion is true), then every problem of PSPACE is PSPACE-complete.
Thus, all problems of PSPACE can be reduced to some easy problem of P (which is also in PSPACE). This is very unlikely (but not (yet) proved true or false).

Now, let us consider the reduction you propose.

If I understood well, you want to take a formula of SAT. The reduction would be to take the same formula for QBF (with, I suppose, an existential quantifier for each variable, otherwise it would not be a valid QBF formula).

This is indeed a valid reduction, and the SAT formula would be satisfiable if and only if the QBF formula was true.

By doing so, you reduce SAT to QBF. This shows that QBF is at least as hard as SAT. Since SAT is NP-complete, this shows that QBF is NP-hard.

The reduction in the other way (taking a QBF formula and making a SAT formula) is not known. This is why we do not know whether NP=PSPACE or not.


Heap-like notation of a BST (BFT bit-vectors) for succinct representation I'm researching the topic of succinct tree representations right now and came across this presentation. On slide 17 there is an example of heap-like notation of a BST (using BFT bit-vectors) and the author claims that the amount of bits needed to represent a tree of $n$ elements (without their values) is exactly $2n+1$.

According to my calculations, it's $2n-1$. Here they are:

As in this representation every BST is represented as a complete tree, for the complete tree of height $k$ it has $2^{k+1}-1$ nodes.
On average for $n$ nodes tree has a height of $log_2n$.
Replacing the $k$ from the first list item with the average BST height from the second list item I received:

$$2^{log_2n+1}-1=2n-1$$

What am I missing in my calculations? Where do these 2 extra bits come from?

Thanks in advance for your answer!

You can count it like this:

Let $n$ be the original number of nodes

Each original node has 2 children after adding the external nodes.

So 1 bit for the original node and 2 for its children. Total $3n$ bits.

But we are over counting here because original node is child of one other original node. So we subtract $n$ and get $2n$.

But we over corrected the count because root node has no parent so we add back 1 bit.

$2n + 1$.


Solve recurrence relation that depends on depth of recursion The specific problem I'm working on is the puzzle presented in this video. For those who don't want to watch the video, my summary of the puzzle is:

A frog is sitting on the edge of a pond facing the opposite bank. In front of the frog, running along the pond's diameter, is a line of $N$ lilypads. This is a very athletic frog: it is able in a single leap to land on any of the $N$ lilypads in the pond or on the opposite bank (for a total of $N + 1$ possible destinations). The frog first considers all $N+1$ positions in front of it, chooses one randomly with uniform probability, and then jumps to this location. It then repeats the process of choosing a new random position from those remaining in front of it (never jumping backwards). This goes on until the frog eventually reaches the opposite bank.
The puzzle is twofold: First, if $N=10$, what is the expectation value of the number of jumps the frog will take to reach the other side of the pond? Second, find an explicit formula (NOT a recurrence relation!) for the expectation value of the number of jumps in general for $N$ lilypads.

(It's a great puzzle; if you haven't yet given it a shot, I'd highly recommend doing so before reading any possible spoilers in the rest of this post!).
To attempt this puzzle, I first calculated the first few terms by hand and then tried to generalize my result. I eventually came up with a recursive algorithm for the expectation value $f$:
def f(n, depth=1):
    if n == 0:
        return depth
    else:
        return (n * f(n - 1, depth) + f(n - 1, depth + 1)) / (n + 1)

However, the second part of the puzzle explicitly disallows recurrence relations as solutions, so I am trying to un-roll/solve the recurrence relation. There are already several questions on strategies for solving recurrence relations (see this and this), but none I can find on solving recurrence relations which are dependent on the depth of recursion. Any help on how to do this is appreciated.

diplodoc explained in the comments one way to solve the recursion. Your recursion is
$$
A_n = 1 + \frac{A_0 + \cdots + A_{n-1}}{n+1}, \quad A_0 = 1.
$$
The trick is to calculate
$$
(n+1)A_n - n A_{n-1} = (n+1 + A_0 + \cdots + A_{n-1}) - (n + A_0 + \cdots + A_{n-2}) = 1 + A_{n-1},
$$
and so $A_n = A_{n-1} + 1/(n+1)$. From here it follows easily that $A_n$ is the $(n+1)$th harmonic number.

Another possibility is to use generating functions. Let
$$
P(x) = \sum_{n=0}^\infty A_n x^n.
$$
Since $\frac{1}{1-x} = 1 + x + x^2 + \cdots$, it follows that
$$
\frac{xP(x)}{1-x} = \sum_{n=0}^\infty (A_0 + \cdots + A_n) x^{n+1}.
$$
Integrating, we get
$$
\int_0^x \frac{yP(y)}{1-y} \, dy = \sum_{n=0}^\infty \frac{A_0 + \cdots + A_n}{n+2} x^{n+1}.
$$
It follows that
$$
\frac{1}{1-x} + \frac{1}{x} \int_0^x \frac{yP(y)}{1-y} \, dy = P(x).
$$
In terms of $Q(x) = \int_0^x \frac{yP(y)}{1-y} \, dy$, this reads
$$
\frac{1}{1-x} + \frac{Q(x)}{x} = \frac{(1-x)Q'(x)}{x},
$$
which simplifies to
$$
\frac{x}{1-x} + Q(x) = (1-x)Q'(x) = [(1-x)Q(x)]' + Q(x),
$$
and so
$$
(1-x)Q(x) = \int^y \frac{y}{1-y} \, dy = \int^y \left(\frac{1}{1-y}-1\right) \, dy = C - x - \log(1-x).
$$
It follows that
$$
Q(x) = \frac{C-x-\log(1-x)}{1-x}.
$$
Since $Q(0) = 0$, we deduce $C = 0$.
Differentiating and multiplying by $(1-x)/x$, we find that
$$
P(x) = \frac{-\log(1-x)}{x(1-x)} = \frac{\sum_{n=0}^\infty x^n/(n+1)}{1-x},
$$
from which we can extract the coefficient of $P(x)$ to be $H_{n+1}$.

Finally, we can solve this without using any recurrences. Consider a random permutation of the numbers $1,\ldots,n+1$, which we think of as the $n$ places and the goal. The frog jumps to the first number. If it is not $n+1$, it scans the list to the first larger number, and jumps there. Repeat in this way, until you get to $n+1$. You can check that this defines the same random process.

Given a permutation, the number of jumps is the number of left-to-right maxima, that is, elements which are larger than all that precedes them. The probability that the $i$th number is a left-to-right maximum is exactly $1/i$, and so linearity of expectation shows that the expected number of jumps is $1 + 1/2 + \cdots + 1/(n+1)$.

As a bonus, the last solution allows us to calculate higher moments of the distribution. The main observation is that the indicator variables $X_i$ for the $i$th number being a left-to-right maxima are independent Bernoulli random variables. This implies that the variance of the number of left-to-right maxima is
$$
\sum_{i=1}^{n+1} \frac{1}{i} \left(1-\frac{1}{i}\right) = H_{n+1} - \sum_{i=1}^{n+1} \frac{1}{i^2} = H_{n+1} - \frac{\pi^2}{6} + O\left(\frac{1}{n}\right).
$$

One checks that the central limit theorem applies, and so the total number of left-to-right maxima is asymptotically normal.

Why is the answer roughly $\log n$? One might expect the answer to be closer to $\log_2 n$, since at each step, $n$ is roughly cut in half. However, this argument assumes that the changes to $n$ are additive, whereas in reality they are multiplicative. It is better to consider instead the effect of each step on $\log n$. If $m$ is the new value of $n$, then the expected value of $\log m$ is
$$
E[\log m] = \frac{\log 1 + \cdots + \log n}{n+1} \approx \frac{1}{n}\int_0^n \log x \, dx = \left.\frac{1}{n} (x\log x-x)\right|_0^n = \log n - 1.
$$
Therefore the value of $\log n$ decreases by roughly 1 each step, and so we expect the number of steps to be around $\log n$ rather than $\log_2 n$.

(With some work, this intuition can be made rigorous.)


Prove Minimum AABB Construction Assume a point set $P[n]$ with $n$ points which align in one plane in the euclidean space, so $p(x,y) \in \mathbb{R}^2$. Looking for an algorithm to construct an AABB (axis aligned bounding box) I did not find anything. But I thought that the simpliest appraoch could be the best: traverse all $p \in P$ and keep track of the minimum and maximum value of each dimension. The AABB is spanned by the two points $(x_{min},y_{min})$ and $(x_{max},y_{max})$. This clearly runs in $\mathcal{O}(n)$.

Now I struggle proving this kind of obvious fact (the best algorithm runs in $\mathcal{O}(n)$). It is clear that all points of the set have to be checked for inclusion which the algorithm does, given the fact that the set is not preprocessed in any way, like ordered.

What is a good formal approach for proving this?

Side note: Is there a better algorithm for constructing an AABB?

Suppose that the points are $(x_1,y_1),\ldots,(x_n,y_n)$. You are looking for the smallest (in some sense) bounding box $[X_m,X_M] \times [Y_m,Y_M]$ containing all your points. For every $i$, we must have $X_m \leq x_i \leq X_M$ and $Y_m \leq y_i \leq Y_M$. In particular,
$$
\begin{align*}
X_m \leq \min_i x_i =: x_{\min}, \\
X_M \geq \max_i x_i =: x_{\max}, \\
Y_m \leq \min_i y_i =: y_{\min}, \\
Y_M \geq \max_i y_i =: y_{\max}.
\end{align*}
$$
Summarizing, this shows that every bounding box must satisfy
$$
X_m \leq x_{\min} \leq x_{\max} \leq X_M, \\
Y_m \leq y_{\min} \leq y_{\max} \leq Y_M,
$$
that is, it must contain $B := [x_{\min},x_{\max}] \times [y_{\min},y_{\max}]$. Conversely, $B$ is itself a bounding box, since $x_{\min} \leq x_i \leq x_{\max}$ and $y_{\min} \leq y_i \leq y_{\max}$ for all $i$. We conclude the following fact:

  $B$ is the intersection of all bounding boxes.


How does the Stockham FFT work? I'm trying to implement a Fourier transform in an OpenGL shader. I found some literature that explains the general principles, but is a bit sparse on some details. And those details are seriously confusing me.
This paper describes the use of the Stockham FFT on the GPU. It contains the following diagram:

I understand how to calculate the discrete fourier transform for any individual point, but I'm confused how exactly the Stockham FFT proceeds. My understanding was that the FFT in general divides the input into odd and even data points, and then recursively processes these. But the diagram I added above looks reversed to me. It starts by dividing the input into the smallest segments and then adds up to larger ones, I would have expected this to work exactly the other way around.
How exactly does the divide-and-conquer part of the Stockham FFT work?

Both algorithms are DIT, but the main difference is in memory access patern.
Cooley-Tukey - the most popular form of transformation from DFT to FFT comes from cache awareness, which is optimal for CPU pipeline.
Cooley-Tukey in first phase reverses bit order while Stockham changes order at each stage.
This is observable if you take look at edges - once you have half of the data it stays in place for Cooley-Tukey but moves for Stockham.

For CPU Stockham makes cache mispredictions while Cooley-Tukey makes thread serialization for GPU.

FFT - look at BFS vs DFS strategy.

FFT stage decomposition - very nice pdf showing butterfly explicitly for different FFT implementations.


Proof of the undecidability of the Halting Problem I'm having trouble understanding the proof of the undecidability of the Halting Problem.

If $H(a,b)$ returns whether or not the program $a$ halts on input $b$, why do we have to pass the code of $P$ for both $a$ and $b$?

Why can't we feed $H()$ with $P$ and some arbitrary input, say, $x$?

Ignore the picture for a moment; we'll get to it shortly. The program $H(a, b)$ is supposed to be a halt tester: when we give $H$ an input of a program $a$ (think of $a$ as the listing of a program) and anything at all for $b$, $H(a, b)$ acts as follows

If the program represented by $a$ halts when given $b$ as input, $H(a, b)$ will answer "yes". On the other hand, if the program described by $a$ runs forever when given input $b$ then $H(a, b)$ will answer "no".
Importantly, program $H$ will always halt and give the correct answer for any pairs $(a, b)$.

The argument that $H$ is impossible to build relies on the action of a particular "perverse" program, $P$, one which uses $H$ as a subroutine. $P$ takes as its input a listing of any program, $x$, and does the following:

P(x) =
  run H(x, x)
  if H(x, x) answers "yes"
      loop forever
  else
      halt

It's not hard to see that

  $P(x)$ will halt if and only if the program $x$ will run forever when given its own description as an input.

So far so good: $P$ will certainly be a program as long as its subroutine $H$ is a program.

Now return to the picture. What happens if $P$ is given its own description as input? The picture describes just that scenario: Let $p$ be the description of program $P$, then, substituting into the highlighted part above, we'll have

  $P(p)$ will halt if and only if the program $P(p)$ will run forever.

Clearly, this paradoxical behavior is impossible, so we're forced to the conclusion that the subroutine $H$ cannot be a halt tester, since it fails in the one case, where it's given $(p, p)$ as input. There might be other cases where $H$ works as it should, but since $H$ fails in at least one situation, it cannot be a complete halt tester, as required.


how to verify permutation generated in constant amortized time? Here is an algorithm that generates the next permutation in lexicographic
order, changing the given permutation in-place:

Find the largest index k such that a[k] < a[k+1]. If no such index exists, exit (the permutation is the last permutation).
Find the largest index l such that a[k] < a[l].
Swap a[k] with a[l].
Reverse the sequence from a[k+1] up to and including the final element a[n].

Is the next permutation generated in constant amortized time and if yes, how to verify it?

For a number $m$, let $\alpha(m) = \max \{ k : k! | m \}$. This sequence starts at $\infty,1,2,1,2,1,3,\ldots$. I claim that in iteration $t$ of the algorithm (where $1 \leq t \leq n!-1$), we have $n-1-k = \alpha(t)$. The average value of $\alpha(m)$ is roughly
$$
\left(1 - \frac{1}{2}\right) 1 + \left(\frac{1}{2} - \frac{1}{6}\right) 2 + \left(\frac{1}{6} - \frac{1}{24}\right) 3 + \cdots = \\
1 + \frac{1}{2} + \frac{1}{6} + \cdots = e-1.
$$
Since the running time of each step of the algorithm is proportional to $n-1-k$, we get that the algorithm runs in constant amortized time.

It remains to prove the claim $n-1-k = \alpha(t)$, which I leave to the OP.


What is it called when two problems are similar? Suppose that there are two problems $P$ and $Q$.

How can I say that "solving $P$ is same thing with solving $Q$"?

For instance, if $P$ is NP-Hard, then we can say "$P$ can be solved in polynomial time iff there exists an algorithm $A$ that solves $Q$ in polynomial time".

There should be a shorter term for this, and I'm sure that is not similar.

Is equivalent the right word?

In complexity theory we prefer, when possible, to use formal definitions. Two problems $P,Q$ are polynomially equivalent if there are polytime functions $f,g$ such that $x \in P$ iff $f(x) \in Q$ and $y \in Q$ iff $g(x) \in P$. This is the usual notion of equivalence in complexity theory.

Sometimes we prefer a coarser notion of equivalence which allows using a problem as an oracle. Two problems $Q,R$ are polynomially equivalent with respect to oracle reductions if $Q \in \mathsf{P}^R$ and $R \in \mathsf{P}^Q$, or in other words, $Q$ can be solved in polynomial time with oracle access to $R$, and $R$ can be solved in polynomial time with oracle access to $Q$. Under this notion, 3SAT and co-3SAT (its complement) are equivalent.

Unless I have made a blunder, both these notions are equivalence relations. In both cases, if one problem can be solved in polynomial time, then so can the other. Since the second is more general, it seems to fit your description better, though in complexity theory we usually prefer the finer first notion, or even finer notions such as logspace reducibility and AC0 reducibility.


Irregularity of language of prefixes of decimal expansion of pi Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$:
$$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$
Prove that Lπ is not DFA-recognizable. You may use the fact that $\pi$ cannot be written as a repeating decimal, that is, there are no sequences of digits $d_1, d_2, \ldots,d_m$ and $e_1, e_2, \ldots,e_n$ such that

$$\pi =  d_1.d_2\cdots d_ne_1e_2\cdots e_n=d_1.d_2 \cdots d_m(e_1\cdots e_n)(e_1\cdots e_n)(e_1\cdots e_n)\cdots.$$

This is how I started my proof:

Proof: by contradiction.

Assume $L_\pi = L(M)$ for some DFA $M$. We'll construct a diabolical string $x$ such that $x\notin L_\pi$, but $M$ accepts $x$.

Let $x = d_1.d_2\cdots d_ne_1e_2\cdots e_n=d_1.d_2 \cdots d_m(e_1\cdots e_n)(e_1\cdots e_n)(e_1\cdots e_n)\cdots$; clearly $x\in L$.

Go through $n + 1$ states, only $n$ states in $M_1$ so $q_i = q_j$ for some $i, j$.

I based my proof off of this: https://courses.cs.cornell.edu/cs2800/wiki/images/2/29/Sp19-lec24-pumping-board.pdf

I'm stuck at the part where I'm trying to make a contradiction.

The pumping lemma tells you that, if $L_\pi$ is regular, there is a word of the form $uvw$ such that $uv^kw\in L_{\pi}$ for all $k\in\Bbb N$, where $|v|>0$.

Note that if a word is in $L_\pi$, any nonempty prefix of that word is also in $L_\pi$. In particular, $uv^k\in L_\pi$ for all $k\in\Bbb N$. In other words, $uv$, $uvv$, $uvvv$, $\cdots$ are prefixes of the decimal expansion of $\pi$.

So $\pi=uvvv\cdots$, which contradicts the fact that $\pi$ cannot be written as a repeating decimal.

Here are several exercises that describe the general situation. The first two exercises are pointed out by gnasher729's comment. The last exercise comes from Yuval's comment

Exercise 1. Show the set of all prefixes of the decimal expansion of a rational number is a regular language.

Exercise 2. Show the set of all prefixes of the decimal expansion of an irrational number is not a regular language.

Exercise 3. What about binary expansion? What if the base is changed to another number?

Exercise 4. A language is a prefix language if for any two of its words $w_1$ and $w_2$, either $w_1$ is a prefix of $w_2$ or $w_2$ is a prefix of $w_1$. Show that for a prefix language $L$, $L$ is regular if and only if $L$ is context-free. In particular, $L_\pi$ cannot be context-free.


Is Group Theory useful in Computer Science in areas other than cryptography? I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot find out where and how to apply Group Theory to other areas in CS, such as algorithms, data structres, graphs, complexity and so forth.

Algorithms for isomorphism problems such as graph isomorphism rely heavily on group theory.
An unusual example of group theory applied to computer science is the famous proof of Barrington's theorem, which uses the nonsolvability of the symmetric group $S_5$ to show equality of two complexity classes that superficially have nothing whatsoever to do with groups.


Data structure/aglorithm for strings to see if there exists two strings you can concatenate to get a target? I want to come up with an arbitrary string, and feed it into my program to see if there exists two strings that I can concatenate to get the target string. What kind of data structure and algorithm would be good for this? I'm thinking a sorted array would be good, and then walk down the list, binary searching for the suffix/prefix needed. That would be O of NlogN I think.

Store the strings in a trie.  Build a second trie that stores the reverse of the strings.  Now you can quickly check whether the target string T is a concatenation of some pair of strings: start walking the first trie, using the left-most characters of T (walking left to right), and simultaneously start walking the second trie, using the right-most characters of T (walking right to left).  By walking the first trie, you find all prefixes of T that are in the dataset; by walking the second trie, you find all suffices of T that are in the dataset; and then you can look for a pair of a prefix and a suffix of the right length to cover all of T (without overlap).

Your approach of storing the strings in sorted order is also reasonable, but you'll need two sorted arrays: one to store the strings; another to store the reverse of the strings.  Given a target string T of length n, for each i, you look up T[1..i] in the first sorted array (using binary search) and look up reverse(T[i+1..n]) in the second sorted array (using binary search).  As an optimization, start each binary search from where the previous search left off (i.e., once you've found T[1..i] in the first sorted array, that helps you find T[1..i+1]; you shouldn't need to start over from scratch.)

So yeah, your idea based on sorted arrays works too, though two tries might be somewhat more efficient.


Dijkstra's Algorithm with different color nodes You are given a directed graph G = (V, E) and nodes s, t. Nodes are colored red, white, and blue. A path from s to t is called colorful if it contains both a red node and a blue node. The task is to determine if a colorful path exists, and if so, find one that contains a minimum number of white nodes.

Im not sure how to get started on this. Any help is greatly appreciated!

Expanding on hengxin's idea, in order to find whether such a path exists, go over all choices of two nodes $x,y$, one red and the other blue, and see if there are paths $s \leadsto x \leadsto y \leadsto t$. In order to find the one containing the minimum number of white nodes, assign weight 1 to edges entering white nodes, and weight 0 to all other edges. The weight of a path is now the number of white nodes. Go over all possible choices of $x,y$, and calculate the minimum-weight path $s\leadsto x\leadsto y\leadsto t$; choose $x,y$ that minimize that weight.


If f(n) = Θ(g(n)) then what all can one say about f(h(n)) and Θ(g(h(n)) I was going across some problems which translated the fact that $\log (n!) = \Theta(n\log n)$ to give
$$\log(\lceil\log n\rceil!) = \Theta(\lceil\log n\rceil \log \lceil\log n\rceil)$$
and therefore $\log(\lceil \log n\rceil!) =  \omega(\lg n)$.

Now I just have this intuition that this sort of conversions shouldn't and wouldn't be always right.

Would it be right to think that.

Any justification as to why am I wrong in thinking that and guidance to what I should have a look at, what texts I should go through to understand it better for myself are very much appreciated.

Thank you.

In general, you can prove nothing. You know $f(n) = \Theta(g(n))$. Now assume f (n) = g (n) = n for all n except g (n) = 0 if n ≤ 1000. And h (n) = 1000 for all n.

So we now have f (h (n)) = 1000 and g (h (n)) = 0.

The problem is that $O (n)$ and $\Theta (n)$ only work for large n. You are fine if h (n) -> inf, or if you look specifically at f (n) and h (n).

If the limit of h (n) is infinity, then you overcome the problem that $\Theta(g(n))$ only gives you information for n ≥ N for some possibly large N, because h (n) will eventually be greater than that N.


How to find i-th root of n whose remainder is the smallest? Given a number n, what is the most assymptotically fast algorithm to express it in terms of base^exponent + rem such that rem is the smallest possible and base is limited from 2 to some relatively small number (e.g. the maximum number that can be represented by a unsigned int)?

I'm currently using gmp bignum library in C, and my algorithm is as follows:

It first finds the smallest possible base and the greatest possible base given the circunstances (binaries searches are performed) and then we know the range of i.

Then, for each possible i, we take the i-th root of n and the corresponding remainder. The smallest remainder is updated if the current remainder is smaller than it.

The algorithm does work, but it's far too slow (even using such a powerful library as gmp). For comparison, for a number with roughly 6 mega bits when expressed in binary the algorithm takes ~90 days to complete.

Intuitively, I think there is a better way to solve the problem (i.e. faster way, an algorithm with a smaller time complexity). What can be done to speed up this process?

Obs: Problem: Given n, find i such that the remainder, n - (floor(ithRootOf(n))^i, is the smallest possible. 2 <= floor(ithRootOf(n)) <= 2147483647

You want to write $n$ as $b^x + r$ with $x,r \ge 0$ and $b \in \{2, \dots, 2^{31} - 1\}$.

Since you're asking for the asymptotic complexity and the base $b$ is in a set of constant size, you can just focus on a single value of $b$.
The exponent is then $x = \lfloor \log_b n \rfloor$ and can be found using $O(\log \log n)$ operations (search for the first $y$ such that $b^y > n$ by trying $b, b^2, b^4, b^8, \dots$, where each term is the product of the previous term by itself, then binary search for the last $x \in \{y/2, \dots, y\}$ such that $b^x \le n $).

The above procedure already gives you $b^x$, from which you can compute $r = n - b^x$. Return the triple $(b, x, r)$ that minimizes $r$.

If the time of each arithmetic operation is constant, the above requires $O(\log \log n)$ time. If each arithmetic operation takes logarithmic time in the value of its operands, then the complexity is $O(\log n \cdot \log \log n)$.


No subset of RE captures the set of TMs halting on themselves as input For a property $P$ of languages, which we identify with the set of languages satisfying it, let $L_P = \{ \langle M \rangle \mid L(M) \in P \}$ be the set of descriptions of Turing machines whose languages satisfy $P$.

  How can we prove that there's no property $\displaystyle P\subseteq RE $ for which $ L_{P}=K $, where $K=\{\langle M \rangle \mid M(\langle M \rangle)\!\downarrow\} $?

According to the recursion theorem, there is a Turing machine $M$ such that $L(M) = \{\langle M \rangle\}$. If $P$ is a property such that $L_P = K$ then $\langle M \rangle \in K$ implies that $L(M) = \{ \langle M \rangle \} \in P$. Now it is easy to construct a different machine $M' \neq M$ such that $L(M') = \{ \langle M \rangle \}$. Since $L(M') \in P$ and $L_P = K$, we must have $\langle M' \rangle \in K$, yet $M'$ doesn't halt on $\langle M' \rangle$.

Note that this solution doesn't use the condition $P \subseteq RE$.


Why number of possible cuts in a graph differ from maximum number of minimum cuts? According to this wikipedia link, under the title "Success probability of the contraction algorithm":
Number of possible cuts in a graph is $2^{n-1}-1$, while maximum number of minimum cuts is ${n}\choose{2}$, where $n$ is number of vertices.

My question:
Why number of possible cuts differ from maximum number of minimum cuts? why isn't any cut a candidate minimum cut?

In a specific graph, not any cut is a minimum cut. What Wikipedia claims is that out of the $2^{n-1}-1$ potential cuts, at most $\binom{n}{2}$ can be minimum cuts in any given graph. Some graphs contain even fewer minimum cuts. For example, if you connect two cycles by a single edge then there is a unique minimum cut.

The upper bound on the number of minimum cuts follows by analyzing Karger's algorithm (linked to in the question): you can show that the probability that the algorithm produces any specific minimum cut is at least $1/\binom{n}{2}$, and so there can be at most $\binom{n}{2}$ of them.


Proving that if L is regular. Then L′ = {ww : w ∈ L} is regular I believe this statement to be true. And here's my reasoning:

  Based on regular languages properties, the concatenation of two regular languages is regular. And since L′ = L · L, it follows that L′ must also be regular.

Do you think my reasoning is valid?

The statement is false. Consider the language $L = \{a^n b : n \geq 0\}$. Then $L' = \{ a^n b a^n b : n \geq 0 \}$ is not regular (exercise).

The invalid point in your reasoning is a confusion between the following two languages: $L' = \{ ww : w \in L \}$ and $L'' = \{ w_1w_2 : w_1,w_2 \in L \}$. It is $L''$ which is the concatenation of $L$ with itself. Whereas $L'$ need not be regular, $L''$ is always regular when $L$ is.


Minimal number of changes to make string into concatenation of $k$ palindromes The following question is taken from leetcode: 1278. Palindrome Partitioning III

  You are given a string $s$ containing lowercase letters and an integer $k$. You need to:

  First, change some characters of $s$ to other lowercase English letters.
  Then, divide $s$ into $k$ non-empty disjoint substrings such that each substring is a palindrome.

  Return the minimal number of characters that you need to change to divide the string.

So I did find the cost array to make a string to a palindrome. Something like below:

[('bcccdefg', 4), ('ccde', 2), ('ccdef', 2), ('ef', 1)] # (character, cost to make it a palindrome)

I am thinking whether this can be done using knapsack recurrence relations, where profit will be cost and weight will be length of the substring; the total backpack weight will be the length of the main string. Though I am not sure what to do with $k$. Do I need 3 states, or are 2 states enough?

Is my thinking correct? If no, what is the right way to write a recurrence relation for this?

Let $s=s_1 s_2 \dots s_n$.
Suppose that you already know, for each substring $s[i:j]=s_is_{i+1}\dots s_k$ of $s$, the minimum number $D(i,j) $ of character substitutions needed to make $s[i:j]$ palindrome. These values can be found in $O(n^2)$ time using dynamic programming since $D(i,j) = 0$ if $i>j$ and $D(i,j) = D(i+1,j-1) + \mathbb{1}_{s_i \neq s_j}$ if $i \le j$.

Your problem exhibits the optimal substructure property. Suppose that you already known the beginning position $i$ of the last substring $s[i:n]$ of $s$ in an optimal partition: clearly you will need to make $D(i,n)$ changes in order to transform $s[i:n]$ into a palindrome. You are then left with the prefix $s[1:i-1]$ of $s$. This prefix still needs to be partitioned into $k-1$ nonempty substrings that are palyndromes. Fortunately this is exactly an instance of the problem you were trying to solve in the first place. You can exploit this property as follows:

Define $OPT[j,h]$ as the minimum number of character substitutions needed in order to partition $s[1:j]$ into $h$ substrings, each of which is non-empty and palindrome. If no such partition can exist, regardless of the number of character substitutions, let $OPT[j,h]=+\infty$.

By definition $OPT[0,0]=0$  (since $s[1:0]$ is the empty string) and, for $h=1,\dots,k$, $D[0,h] = +\infty$.

Moreover, for $i=1,\dots,n$ and $h=1, \dots, k$:
$$
OPT[j,h] = \min_{i=1,\dots,j} \left\{ OPT[i-1,h-1]  + D(i, j) \right\}.
$$

This gives you a dynamic programming algorithm with time complexity $O(k n^2)$.
The optimal solution to your original problem is $OPT[n,k]$.


Reduction from PARTITION to MAX-CUT I am trying to prove the NP-Hardness of the MAX-CUT problem. Other sources seem to reduce from the NAE-3SAT problem, however I have been trying to reduce from PARTITION because PARTITION and MAX-CUT are both in Karp's list of 21 NP-Complete problems and this is the reduction that he did [1].

PARTITION: Given ($c_1,c_2,\dots,c_n)\in\mathbb{Z}^n$, does there exist $S\subseteq\{1,2,\dots,n\}$ such that $$\sum_{i\in S}c_i=\sum_{j \not\in S}c_j$$

MAX-CUT: Given a weighted graph $G=(V,E)$ with weight function $w:E\rightarrow\mathbb{Z}$ and a target weight $W\in\mathbb{Z}^+$, does there exists $S\subseteq V$ such that $$\sum_{(u,v)\in E\::\:u\in S,\,v \not\in S}w((u,v))\geq W$$

After spending a lot of time trying to construct a reduction to prove PARTITION $\leq_p$ MAX-CUT myself, I eventually gave up and looked at Karp's paper. The problem I could not manage to solve is how you encode the equality constraint of PARTITION in a MAX-CUT instance which only has one inequality constraint. The reduction that Karp gives (which I would not have been able to come up with) is as follows:

Given a PARTITION instance $(c_1,c_2,\dots,c_n)$, construct a MAX-CUT instance $(G=(V,E),\,w,\,W)$ such that:
 $$V=\{1,2,\dots,n\}$$
 $$E=\{(u,v) \: : \: i,j\in V,\, u\neq v\}$$
 $$\forall (u,v) \in E,\,w((u,v))=c_ic_j$$
 $$W=\lceil \frac{1}{4} \sum_{i=1}^{n}c_i^2\rceil$$

I am having trouble proving the correctness of this reduction (the paper does not seem to give any justification). I can kind of appreciate the need to be squaring values - is my intuition correct that this is to account for needing to the equality constraint with an inequality constraint?

I have tried using the Cauchy–Schwarz inequality to prove this with no luck. Similarly, I have tried to relate this to the variance/covariance of two partition sets, but I'm not sure if this is helping me understand why this reduction works.

A proof plus any intuition of how one might have arrived at this reduction would be greatly appreciated.

[1] Richard M. Karp (1972). "Reducibility Among Combinatorial Problems". In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. (pdf)

Since the graph is complete, any set $S$ will induce a cut of weight

$$\sum_{i\in S, j\notin S} c_ic_j ~~=~~ \sum_{i\in S} c_i \cdot \sum_{j\notin S} c_j.$$

Denote the two sums in the latter formula by $A$ and $B$. The problem of finding a maximal cut then means maximizing $A\cdot B$, while $A+B$ is fixed. It is well-known that the maximum of this product is achieved for $A=B$. In this case the product becomes $\left(\frac 12 \sum_{i=1}^n c_i\right)\cdot \left(\frac 12 \sum_{i=1}^n c_i\right) =  \frac 14 \left(\sum_{i=1}^n c_i\right)^2$. So $W$ should not be a quarter of the sum of squares, but a quarter of the square of the sum.

So the reason you could not prove the correctness of the reduction is, that the reduction as given is not correct. (And I'm somewhat embarrassed that I only noticed this after your followup question in the comment.)


How curves are represented in a computer I am confused now (in thinking about limits and continuity) how curves are represented in a typical modern computer. Curves are "continuous" in that there is no discrete change from one angle to the next. Wondering how the computer approximates this and/or what equations it uses/approximates.

A curve can be quantized (also known as rasterized) to a certain precision after which it is discrete, and the issue is gone. If you see a picture that contains a curve on a modern computer, there's a good chance it already has been rasterized (e.g. PNG or jpeg).

However, it is possible to represent curves (and other primitives) directly. Then you're looking at vector graphics. In most implementations of vector graphics only a couple specific subsets of curves are supported, most often circles, ellipses and Bézier curves. Especially the latter is the most common powerful generic way of storing curves.

It is possible to describe an arbitrary curve through some mathematical framework and storing the mathematical description of the curve. But such a generalized approach is rarely done for computer graphics.


What is a batch compiler? I have the following quotation from my compiler's course (in the context of graph coloring):

  Because it is slow, graph coloring tends to be used in batch
  compilers, while linear scan tends to be used in JIT compilers.

I couldn't find a clear definition online. So, what makes a compiler be a batch compiler?

A JIT (Just-In-Time) compiler compiles code at run-time, i.e. as the program is running. Therefore the cost of compilation is part of the execution time of the program, and so should be minimized.

The opposite of this is an ahead-of-time (AOT) compiler which is basically synonymous with "batch compiler". This converts the source code to machine code and then just the machine code is distributed. Therefore, the compiler can be very slow as it doesn't impact the execution time of the resulting program.

Nowadays, when people say "compiler" they typically mean an AOT compiler. Indeed, the term "AOT compiler" only really started becoming popular relatively recently when people started making AOT compilers for JIT compiled languages, particularly JavaScript. Many of these languages, e.g. C#, compile to an intermediate language for a VM which is then JIT compiled to machine code at run-time. The term "AOT compiler" has the connotation that the source code will be compiled directly to machine code, so no form of JIT compilation is required at run-time.

"Batch compiler" is a bit of an archaic term at this point.  The real contrast to a batch compiler when the term was popular was an incremental compiler.  Incremental compilation is often associated with languages like Lisp where you had a REPL and you could interactively request the language implementation to compile a specific function. If a function was executed whose compilation had not been requested before, it would typically be interpreted. A batch compiler, by contrast, compiled all functions at once, i.e. in a batch.