texts:
It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and
a computer program is also a sequence of instructions to perform a (some) tasks with computer.

Then what makes a program different from an algorithm? is it a type of algorithm too?

In fact, I look for formal definitions for an algorithm and a computer program so I can distinguish them from each other or identify algorithms within a program.

Update:I have noticed in  Wikipedia by an informal definition (at least syntactically) any program is an algorithm.

  An informal definition could be "a set of rules that precisely defines a sequence of operations." which would include all computer programs, including programs that do not perform numeric calculations. Generally, a program is only an algorithm if it stops eventually.


texts: Show $USELESS_{TM}=\{ M | M$ is a Turing machine with at least one useless state$\}$ is recursively enumerable?

texts: I know $USELESS_{TM}$ is undecidable, but am having trouble showing that it is recursively enumerable. I wanted to reduce $USELESS_{TM}$ to the halting problem, which would show that $USELESS_{TM}$ is recursively enumerable but don't see a way to go about doing this. (I think I would need to check every possible input to see if a state is not entered which I don't know how to simulate using a halting problem subroutine.)


texts: What could we say about that conjecture that yields P != NP?

texts:
Let $F$ be the set of all Boolean formulae.
We say that a Boolean formula $\varphi$ is positive (=monotone) if
$\forall \alpha\in F,i\leq n$, if $\alpha\wedge\neg x_i\models\varphi$, then $\alpha\models\varphi$.
Let $\psi,\xi\in F$. We say that $\psi\vdash \xi$ if $\psi\models \xi$ and $\psi$ is equivalent to a formula $\psi'$ over the connective $\wedge$ only (for example, $\psi'$ could be $x_1\wedge x_2$ but not $x_1\vee x_3$). This is, of course, different from the usual meaning of this notation.
Let $n>1$ and a formula $\varphi:\{0,1\}^n\to\{0,1\}$ that satisfies:

Positivity

Almost Linearity
That is:

$\forall \alpha,\beta,\gamma,\delta\in F.
\begin{cases}
\alpha\wedge\gamma\vdash\varphi \\
\alpha\wedge\delta\vdash\varphi \\
\beta\wedge\gamma\vdash\varphi
\end{cases}
\Rightarrow
\begin{cases}
(\alpha\wedge\gamma)\vee (\alpha\wedge\delta)\models\beta\wedge\gamma \\
 \ \ \ \ \   \text{or}\\
 (\alpha\wedge\gamma)\vee(\beta\wedge\gamma)\models\alpha\wedge\delta\end{cases}$.
Intuitively, that means that $\varphi$ could not be succinctly written as $\bigvee_i{(\alpha_i\vee\beta_i)\wedge(\gamma_i\vee\delta_i)}$.
============
Let us denote $||\varphi||=\#\{\xi\in F|\xi\vdash\varphi\}$, where here $\#$ stands for set cardinality.
Let us denote by $|\varphi|$ the number of logical gates (=connectives) in the minimal Boolean circuit $C$ representing $\varphi$ over the connectives $\{\vee,\wedge,\neg\}$. This is, of course, the usual definition of minimal circuit size.
============
I am looking for a lower bound on $|\varphi|$ as a function of $||\varphi||$ and $n$.
I conjecture that $|\varphi|\geq {||\varphi||}^{1/\log n}$, but is that true?
Could we say any better?
===========
The Half Clique problem (HCP) is: given a graph, does it contain a clique whose length is exactly half of the graph's number of vertices?
HC is a formula that treats its variables as graph edges, and returns "true" iff the assignment to the variables represents a graph with half clique (as defined above).
Let $\xi\in F$ such that $\xi\vdash HC$, so $\xi$ represents exactly one half clique. We denote $V(\xi)$ = the set of vertices that the edges in $\xi$ touch. For example, if $\xi=E_{12}\wedge E_{25}\wedge E_{15}$ then $V(\xi)=\{1,2,5\}$. So clearly if $x\wedge y\vdash HC$, then either $V(x)\subseteq V(y)$ or $V(x)\supseteq V(y)$. Hence, either $x$ or $y$ uniquely defines the Half Clique. From this, the almost linearity trivially follows. Also, clearly HC is positive.
If the above conjecture is true, then we could apply it to $HC$ to get super polynomial lower bound on its size, so $HCP\notin PSize$. Since $HCP\in NP$, we get $NP\ne PSize$, which is known to imply $P\ne NP$.


texts: For the question below, it is asking to prove the lower bound on the worst case is log(n). I have no problem proving this and the solution makes 100% sense to me. However, there is a comment at the bottom of the solution which asks why we had to assume that if the loop does not return early, then it runs for omega log(n) iterations. Why is it not obvious based on the fact that the upper bound on the worst case is log(n)? I hope someone can help.


texts: Novel escape analysis algorithm for Java

texts:
Today I read a very interesting article about escape analysis in Java called Escape Analysis for Object Oriented Languages: Application to
Java

I think I have some grasp on how escape analysis works and how it is implemented, but I don't understand how the above algorithm works at all. I have also read two other papers on escape analysis in Java, Escape analysis for Java and Compositional pointer and escape analysis for Java programs. The algorithms in those papers are very similar and I understand on a high-level how they work.

But Blanchet's escape analysis algorithm appears to be completely different and I do not understand it at all. So the question is if someone can explain how his algorithm works? How is it different from "normal" escape analysis algorithms?

(this question comes from Stack Overflow)

Edit: I think I have finally figured out one big difference in Blanchet's algoritm vs the others. He does not build a tree at all and instead just uses forward and backward propagation. Consider this example:

Object foo() {
    ...
    a = c;
    a = b.f;
    return a;
}

The backward propagation starts at return a; and sees that a is returned, so a escapes. It then goes to line a = b.f; and sees that a is assigned b.f. Since a escapes, b.f also escapes. Next, it looks at a = c; and like before a escapes so c escapes. And so on. This appears to be a big flaw in his algorithm, it overestimates the number of escapees. Because he is not building a reference graph like the other algorithms he cannot see that c doesn't escape at all because of the a = b.f; on the next line. So  the algorithm is likely very fast (doesn't build a graph) but not precise enough.


texts: Why are not programs already in binary code?

texts: First of all, please forgive me if this question shows ignorance on my behalf. What I'm asking is not why we don't program in languages written in binary code, I know the answer for that. What I would like to ask instead is: considering all information we input into a computer is registered as binary code, and all data is stored in binary code, are not common programming languages already binary code, and what we see as instructions or variables just a translation? If that is so, why are assemblers or compilers necessary?


texts: What all can be said when you say that the CPU is 32 bit?

texts:
When someone tells a computer scientist that a CPU is, say, 32 bits, what all does he/she infer from this information?

I know that it means that the physical address has 32 bits. This meas that the physical memory can't hold more that 2^32 bytes of RAM. This also means that the word size is 32 bit or 4 bytes. Please correct me if I am wrong and also tell me what more we can infer from this.

I have searched over the internet only to get websites answering the above question to layman. Can anyone answer it from the technical point of view?


texts:
I wrote pseudocode for Selection Sort, but I'm not sure what is the running time of my algorithm, can you help me with that?

My Pseudocode: Selection Sort(int a[], int n)

Input: array of length $n$

Output: sorted array

for r=1 to n
    min=a[r]
    for i=r to n
        if (a[i]<min)
              min=a[i]
              k=i
              a[k]=a[r]
              a[r]=min

The external for takes $\Theta (n)$ but I'm not sure about the internal for because it depends on $r$.


texts:
Recently, I was facing some problems in effectively proving the following :
Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of digit such that when viewed as numbers, satisfy the mathematical equation x+y=z.

For example, the string 123#45#168 is in this language because 123 + 45 = 168.

Is this language regular and why ?
I was trying to apply the Pumping Lemma, but am unsure of how to complete the proof. Could anyone please help ?


texts:
My algorithm professor said a recursive function should not have side-effects since it's a methodological error because recursion is "pure".
Anyway I don't understand why, even because I find side-effects useful and difficult to replace a recursive side-effect function with a "pure" one.


texts:
The language is $L = \{a^{i} b^{j} c^{k} \;|\; k \neq 2j\}$. I'm trying to write a grammar for this language, what I have so far is:

$S \rightarrow AT_{1} \;|\; AT_{2} \;|\; AT_{3} \;|\; AB \;|\; AC$

$A \rightarrow aA \;|\; \varepsilon$

$B \rightarrow bB \;|\; \varepsilon$

$C \rightarrow cC \;|\; \varepsilon$

$T_{1} \rightarrow bbB'T_{1}c \;|\; \varepsilon $   (for $2j > k$)(1)

$B' \rightarrow bB' \;|\; b$

$T_{2} \rightarrow bT_{2}ccC'\;|\; \varepsilon$ (for $2j < k$)

$C' \rightarrow cC' \;|\; c$

$T_{3} \rightarrow bT_{3}c \;|\; \varepsilon$ (for $j = k$)

the problem that I am having is, the string $bbccc$  can't be generated although valid, in that case $j = 2$ and $k = 3$  so $2\times 2 > 3$  corresponding to production rule (1), how can I fix this?


texts: Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list?

texts:
I have a quick question on the bubble sort algorithm. Why does it perform $\Theta(n^2)$ comparisons on an $n$ element list?

I looked at the Wikipedia page and it does not seem to tell me. I know that because of its magnitude it takes a lot of work with large numbers.


texts: What is the relationship between the complexity class $L^n$ and $NL^m$?

texts:
The space hierarchy theorem shows that
$$\mathrm{\mathbf{L}}^{1} \subsetneq \mathrm{\mathbf{L}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{L}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{PSPACE}}$$
and
$$\mathrm{\mathbf{NL}}^{1} \subsetneq \mathrm{\mathbf{NL}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{NL}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{NPSPACE}} = \mathrm{\mathbf{PSPACE}}$$
where
$$\mathrm{\mathbf{L}}^{m} = \mathrm{\mathbf{DSPACE}}\left( \log^{m}(n) \right)$$
and
$$\mathrm{\mathbf{NL}}^{m} = \mathrm{\mathbf{NSPACE}}\left( \log^{m}(n) \right)$$

Thus, there exists a function $\varphi \colon \mathbb{N}^{+} \mapsto \mathbb{N}^{+}$ such that for every $m \in \mathbb{N}^{+}$,

$$\mathrm{\mathbf{L}}^{\varphi(m)-1} \subset \mathrm{\mathbf{NL}}^{m} \subset \mathrm{\mathbf{L}}^{\varphi(m)} \subsetneq \mathrm{\mathbf{PSPACE}}$$

The Savitch's theorem shows that for every $m \in \mathbb{N}^{+}$,
$$\mathrm{\mathbf{L}}^{m} \subset \mathrm{\mathbf{NL}}^{m} \subset \mathrm{\mathbf{L}}^{2m}$$

Now, we know that $m+1 \leq \varphi(m) \leq 2m$ and $\varphi(1) = 2$.

Can we find $\varphi$ ? Is it an open problem or not?


texts: Turing Machine that triples a unary format number?

texts: I managed to figure out how to double a unary format number however I have had no such success in tripling it. An input tape would be of the following format Λ111Λ and the output would be like Λ111Λ111111111Λ with the tripled number coming directly after the initial input tape. Any help would be greatly appreciated.


texts: Can I run Dijkstra's algorithm using priority queue?

texts:
I think I can run Dijkstra's algorithm using any data structure. I do not see any implementation details of Dijkstra's algorithm.

Is a priority queue a possible data structure? Will running Dijkstra's algorithm using a priority queue reduce or increase the complexity? Will I overshoot the problem?


texts: Just another Divide-And-Conquer question - but somehow different

texts:
Please consider the following Divide-And-Conquer Problem:

  You’re consulting for a small computation-intensive investment
  company, and they have the following type of problem that they want to
  solve over and over. A typical instance of the problem is the
  following. They’re doing a simulation in which they look at n
  consecutive days of a given stock, at some point in the past. Let’s
  number the days i=1,2,...,n; for each day i, they have a price p(i)
  per share for the stock on that day. (We’ll assume for simplicity that
  the price was fixed during each day.) Suppose during this time period,
  they wanted to buy 1,000 shares on some day and sell all these shares
  on some (later) day. They want to know: When should they have bought
  and when should they have sold in order to have made as much money as
  possible? (If there was no way to make money during the n days, you
  should report this instead.)

There already is a discussion about the same problem, but I don't understand why they try to make it that complicated. I think the following Algorithm will yield the result they ask for:

DivideAndConquer(1,..,n)
(i1,j1) := DivideAndConquer(1,..,n/2)
(i2,j2) := DivideAndConquer(n/2 + 1,..,n)
return (min(p(i1),pi2),max(p(j1),p(j2)))

Even if they ask for the range, we can get it from (i,j) := DivideAndConquer(1,..,n) by j-i. So, what am I missing?

PS: I don't see the point of using a DivideAndConquer approch at all. Why not sorting the input twice. Once in ascending and once in descending order induced by p(i).

EDIT: According to the explanation of Yuval Filmus, the algorithm should look like the following:

DivideAndConquer(1,..,n)
(i1,j1) := DivideAndConquer(1,..,n/2)
(i2,j2) := DivideAndConquer(n/2 + 1,..,n)
Let p(i) be minimal in 1,..,n/2
Let p(j) be maximal in n/2 + 1,..,n
return (i,j)


texts: Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

texts:
Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, then $H\le L_1 \le H+1$ and $H\le L_2< H+2$,
where $H$ is the (base-2 Shannon) entropy of the symbol distribution.

Is anything known about the average redundancy of Huffman and Hu-Tucker codes, that is, the expected value of $R_1 = L_1-H$ or $R_2 = L_2-H$, when the symbol weights are random?

Definition & Details:

Assume we have $n$ symbols $a_1,\ldots,a_n$ with weights $\vec P=(P_1,\ldots,P_n)$,
where these weights are themselves random, e.g., they are uniformly drawn from all stochastic vectors (so that $P_i\ge0$ and $P_1+\cdots+P_n = 1$ a.s.); stated otherwise: $\vec P$ has a $\mathrm{Dirichlet}(1,\ldots,1)$ distribution).

Then $H = - \sum_{i=1}^n P_i \log_2(P_i)$ and $L_{1,2} = \sum P_i \operatorname{depth}(a_i)$, where $\mathrm{depth}(a_i)$ is the depth (number of edges on path from root) of leaf $a_i$ in an optimal binary tree on leaves $a_1,\ldots,a_n$ (Huffman tree) for $L_1$ and
the depth in an optimal binary search tree with leaves $a_1\le a_2\le\cdots a_n$ (optimal alphabetic tree).

My Attempts:

I am seeking an analytic solution, in the best case as a closed formula in $n$.
I can approximate the expectations with a Monte Carlo simulation, here are a few example values (from 10,000,000 repetitions each; up to the given digits several repetitions agreed; * only 10,000 repetitions)

n    E[R2]
3    0.297
4    0.284
5    0.268
6    0.253*
10   0.217*

Note that the upper bound of $2$ is far from tight here.

This question is probably related, but was posed unclearly and does not have an answer.

A somewhat similar problem, has been solved by Szpankowski.
There, alphabet symbols are blocks of bits of length $n$,
generated by a memoryless source with $p<0.5$ is the probability for $0$ in the block. The average redundancy of different codes, including Huffman's, are computed for large $n$.
Here the symbol probabilities are fixed, and so is the redundancy; the average here means average redundancy over all symbols, not over random symbols weights.

This does not answer my question above thus.


texts: Proving Blank-halt to be recursively enumerable through reduction to Halting problem

texts:
To prove the blank-halt problem is undecidable (does a given Turing machine halt on the empty input), it's a case of reducing the halting problem to the blank-halt problem and since the halting problem is undecidable, the blank-halt problem is undecidable.

However to prove the blank-halt problem is recursively enumerable just like the Halting problem, isn't the reduction then the other way around? In order to prove this part does the blank-halt problem get reduced to the halting problem and so if the halting problem is recursively enumerable then the blank halt problem is also recursively enumerable?

I'm confused about the reduction flow.


texts:
Is there a DFA that accepts no string, but has at least one final state?

I think it would be possible to make a DFA that accepts no string only by creating no final states or by making sure that the final states are not accessible. But how can a state not be accessible if a DFA has all of its transitions defined?


texts:
Let $T$ be a complete binary tree of height $n$ and root $r$.

A random walk starts at $r$, and at each step uniformly at random moves on a neighbor.

There are $m$ random walkers all starting at $r$ and let denote with $H_1,\dots,H_m$, the heights reached by the walkers after $n$ steps.

Show that, for some constant $C$ which do not have to depend on $n$
 and $m$, it holds that

$\mathbb{P}\left(\underset{i \in [m]}\max\left|H_i - \frac{n}{3}\right| \le C \sqrt{n\ln m}\right) \ge 1 - \frac{1}{m}$

I have been trying several strategies, to appropriately define $H_i$ as sum of random variables and similar, but no one turned out to work. Do you have any idea/suggestion to attach this problem?

Thanks in advance!


texts: What is a best known algorithm for finding diameter of undirected graph?

texts:
What is best (in terms of time complexity) known algorithm (approximate or exact) for finding diameter of a large undirected graph?

The diameter is defined as longest of shortest paths between any two nodes.

I know that naive solution takes O(nm) steps and is basically taking pairs of all vertices and finds distances between them.

This is very slow for large graphs, 2^20 nodes or more.

An example graph

http://snap.stanford.edu/data/com-Orkut.html


texts: RSA cryptosystem: Encrypting a signed message

texts:
I've started to read the section about the RSA cryptosystem in CLRS (page 958) and I don't understand the way it describes how to encrypt a signed message.

If Bob wants to send a message $M$ to Alice:

Bob takes $M$ and encrypts it (using Alice's public key): $P_A(M) = C$.
Sends $C$ to Alice.
She decrypts it using her private key: $S_A(C) = S_A(P_A(M)) = M$.

If Alice wants to send a signed message $M'$ to Bob (page 961):

She computes the digital signature of $M'$ (with her private key): $\sigma = S_A(M')$.
Sends the pair $(M', \sigma)$ to Bob.
Bob receives the pair and check the message authenticity by comparing $M'$ and $P_A(\sigma)$.

If Alice want to send an encrypted, signed message $M'$ to Bob.

In cursive is what I think (I don't know how) it goes.

Alice first appends her digital signature to the message. I guess we get $M'' = M'\sigma$, where $\sigma = S_A(M')$.
Encrypts the resulting message/signature pair with the public key of Bob (the recipient):
Is that $P_B((M'', \sigma))$? What does this mean: $(P_B(M''), P_B(\sigma))$ or $(P_B(M''), \sigma)$?. If the former, then what is the point of encrypting the digital signature?.
The recipient decrypts the received message with his or her secret key to obtain both the original message and its digital signature. I don't how this is done, since I don't know how steps 2 is performed.

Thanks!


texts:
I wonder how to check availability property from CAP theorem.
Consistency check is conceptually easy: if at least once somehow same query at the same time returns different results, then the system may be considered inconsistent (or under some circumstances eventually consistent).

But what about availability? If it takes 1 millisecond for the system to respond, it probably should be considered available. If 1 second for a huge query - probably also available. But what about 50 seconds for a simple query?.. Where is the threshold - how much time should the system take to respond in order to consider it unavailable?

Well, one possible threshold is to consider system unavailable only if it throws some error immediately or doesn't respond at all. But with such definition we may consider available any system that lets the user wait for a long time until all inconsistencies and partitions are resolved.

So my questions are:

1) How do we check if system satisfies availability property as defined in CAP theorem?

2) How do we distinguish the following cases:

System is available, but it may take 10 minutes to process some
huge query.
Actually system is not available, but there is some
wrapper (user calls it instead of the original system) that each time when original system is not available simply waits
until it becomes, so to the outside user it looks like the system is
available and is simply processing the query.


texts: How to convert this recursive algorithm to an iterative form?

texts:
Let us assume there's a folder structure as shown below: The letters a-d represent folders and the number 1-5 represent video files where for the file n, size(n)=n. So, 1 = 1MB, file 2 = 2MB, etc.

a
├── 1
├── b
│   ├── 2
│   └── 3
└── c
    ├── 4
    └── d
        └── 5

3 directories, 5 files

I want to write a script that takes as input a directory (e.g., a), and tells us the total video duration in that folder (iT=immediateTime) and the total video duration in that folder and all its sub-folders (tT=totalTime).

My pseudocode is:

function calcTime(dir)
{
    tT = iT = singleLevelCalcTime(dir);
    foreach(subdirectory in dir) {
        t+= calcTime(subdirectory);
    }
    echo iT;
    echo tT;
    return t;
}

Now, according to the Crunch-Turing thesis, essentially, every recursive function is mathematically proven to have an equivalent iterative version. My problem is I can't find any way to do this using just loops. I've read that explicit stacks (instead of the implicit ones generated by the nature of recursion) can solve this, but I can't figure out how.

For example, the first part of the algo is simple - iT can be calculated by the same method as in the original algorithm. Now, the program must enter each sub-directory and perform the same task again. However, without using recursion, I'd have to provide multiple levels of nested loops (unknown number of levels) to loop through each file/folder in each level. Please tell me where my approach is lacking. I can't really comprehend how to build an explicit stack that can solve this!


texts: Whats the logic between MAR, MBR and Control Bus

texts:
Control Unit has MAR and MBR registers. so MAR emits instruction to address bus so that the specific cell in the memory is activated. MAR also emits READ or WRITE command to control bus. MBR emit data for WRITE actions to data bus.

Question is how does the control bus communicate between MAR and MBR to know whether it is a write or read command. And once the cell is activated, how does data is being written or read?

I know CPU is smart... and computer bus is smarter... but there has to be logic to it...


texts: Number of ways painting graph in two colors, such that two nodes of same color are linked by edge

texts:
We are given undirected graph of $N$ nodes and $M$ edges, we want to count the number of possible ways to paint this graph in $2$ colors such that for each two nodes having the same color, there must be an edge between them.

I tried some examples on paper and I always got numbers of the form $2^x$, however I couldn't see a valid way to find such $x$ or I couldn't prove why this is the case.

Does this problem become easier if we are given directed acyclic graph instead of undirected one?


texts: Complexity-theoretic difficulty of checking the value of $\pi(x)$?

texts:
The prime-counting function, demoted $\pi(x)$, is defined as the number of prime numbers less than or equal to $x$.

We can define a decision problem from $\pi(x)$ as follows:

  Given two numbers $x$ and $n$, written in binary, decide if $\pi(x) = n$.

A friend and I were talking about this problem earlier today. There's a pseudopolynomial-time algorithm for this problem - just count up to $x$, using trial division at each step to see how many of the numbers are prime, and check if that's equal to $n$. The problem is also in PSPACE, since the algorithm I just described can be implemented to use only polynomial auxiliary space.

However, I'm having trouble finding a way to place this problem into a lower complexity class. I can't see how to build a polynomial-time verifier for the problem, so I'm not sure whether it's in NP, and I can't think of a way to get it into the polynomial hierarchy at all.

What is the most appropriate complexity class for this problem?

Thanks!


texts:
I was thinking about developing a daily production work plan algorithm for an enterprise. The problem is as  following:

There are various tasks that needs to be completed, each has a deadline, a duration and a set of requirements for resources. It is mandatory that no task is expired, but if that's not possible, we will settle for a plan with earliest completion time.

From there, these tasks will be divided into daily work plan which allows maximum 8 hours of task execution.

I think I'll start from looking at job-shop scheduling algorithms and bin packing algorithm but it that correct? You guys have any idea about how this could be done?


texts: How to properly calculate the order of growth of an exponential algorithm?

texts:
I'm reading SICP, and I'm a little bit confuse about this statement:

  Consider the problem of computing the exponential of a given number.
  We would like a procedure that takes as arguments a base b and a
  positive integer exponent n and computes b n . One way to do this is
  via the recursive definition

b n = b ⋅ b n − 1 ,
b 0 = 1

  which translates readily into the procedure

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

  This is a linear recursive process, which requires Θ ( n ) steps and Θ
  ( n ) space.

I did a tree illustrating the process generated by the procedure:

(expt 2 2)
|
|
|
(expt 2 1)

Which makes the statement "This is a linear recursive process, which requires Θ ( n ) steps and Θ ( n ) space." true. But when I use a substitution model, it seems that requires 0 ( n ^ 2) steps and space:

(expt 2 2)
    (* 2 (expt 2 1))
    (* 2 2)
4

Thank you.


texts: Formal languages: constructing * for a linear set

texts:
Right now, I'm working on a computer verified proof in Agda, showing that the Parikh images of regular languages are semi-linear (i.e. a limited form of Parikh's Theorem).

Right now, I'm trying to construct the equivalent of *-closure for a linear set. (Once I have this, it's easy to find for semi-linear sets).

More formally:

A linear set is a set of the form $\{ v_0 + c_1 \cdot v_1 + c_n \cdot v_n \mid c_i \in \mathbb{N}\}$. i.e. a linear combination of vectors from $\mathbb{N}^k$.
A semi-linear set is a finite union of linear sets

For a linear set $L$, I'm trying to construct $L^*$, the semi-linear (possibly linear?) set $L^* = \{ u_1 + \ldots + u_m \mid u_i \in L, m \geq 0 \}$, i.e. the infinite sum of L with itself.

I know that this set must be semi-linear, from Parikh's theorem. It basically corresponds to the case where, if $R$ is a regular languages with a linear Parikh image $L$, then $L^*$ is the Parikh image of $R^*$. (From this I know how to build up the case where R has semi-linear Parikh image).

I'm wondering if someone can either point me to a proof that Regular Expressions are semi-linear languages that doesn't rely on Parikh's theorem for context-free languages, or can point me in the right direction for constructing $L^*$ myself.


texts: Checking if several sets of pairs covers a given set of pairs

texts:
Suppose we have $N$ arrays of pairs, e.g. for $N=3$:

$A_1 = [ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]$,

$A_2 = [ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]$ and

$A_3 = [ [4,1], [5,1], [5,2], [7,1] ]$.

We can assume that the pairs in every array are sorted by the first number, and then by the second number. Also, the same pair won't appear in the same array more than once (same pair can appear in multiple arrays, as you can see above).

The numbers in every pair are arbitrary integers $\geq 1$.

How could I find all the $k$'s that satisfy:

$\exists \{ p_1, p_2, ... , p_N\}\subseteq [1..N]\ \forall n \in [1..N]: [k,n]\in A_{p_n}$

The expected result for the example above is: $[5, 7]$.

Note: Speed is the most critical factor of the algorithm, then memory. If it helps to optimise for speed/memory, assume that $N\leq 10$. The number of pairs in an array can be ~50000.


texts: Representation of -40 in 8bit computer using 2's complement

texts: What is the representation of -40 in a 8bit computer using 2's complement intiger?


texts: Construct a proof tree in Hindley-Milner with function overload

texts:
I'm reading Wadler's paper called "How to make adhoc polymorphism less ad hoc".
I'm trying to understand the given rules for function overload (over and inst) and I want to create a small example of a proof tree using them. All deductions rules are in Figure 9 and Figure 10.

I decided to proof the following expression/type: $(over\: eq:: Eq\: \alpha\: in\: inst\: eq :: Eq\:Int \:=\: eqInt\: in\: eq\:1\:2)::Bool$.

Some people gave me a tip: construct the tree in bottom-up.

So here is what I did:

I think I'm stuck. I have no idea how to go up in the tree. And I'm not sure if I can, at some point, discharge the assumption about $eqInt$.

I would like to know what I'm doing wrong and how to finish this proof.

EDIT:
As said in the paper, $Eq\: \tau$ is a abbreviation for $\tau \rightarrow \tau \rightarrow Bool$.


texts: Reducing a system of two boolean algebra assertions to a single one

texts:
Given a system of two Boolean Algebra equalities

a = b.
c = d.

one can exhibit a single equation

F(a,b,c,d) = 0.

which is equivalent to the former system. (Symmetric difference is pivotal for constructing such quaternary operation F(a,b,c,d)).

Questions:

Is there binary operation x ? y (infix notation) such that

a ? c = b ? d.

is equivalent to the original system?
Is there binary operation x ? y  such that

a ? b = c ? d.

is equivalent to the original system?

Edit (June 13): The question is more subtle than I managed to convey. Boolean algebra is a finitely definable variety. I was wondering if we can get a single axiom system by combining identities. Padmanabhan proved in 1968 that every definable class of lattices (such as BA) can be defined by a single identity within the class of lattices. The key observation in his method is equipping the identities

a = b.
c = d.

with disjoint sets of variables. Then, simple disjunction

a v c = b v d.

would do.


texts:
Design a Monte Carlo algorithm that checks in constant time if a given element $x$ is in a $n$-dimensional vector $V$. Calculate the probability for a correct answer. Then suppose $n=10$, how many times the algorithm must be executed so the probability for a correct answer is greater than $0.9$?

Thats what I tried. Lets pick an arbitrary index $i$ which make sense in $V$, then check if $x=V[i]$ and return true or false as the equality holds or not.

My doubt comes at the time of calculating the probability of a correct answer as the statement gives no more details. Is it even numerically doable without additional asumptions?

I guess the probability of $x\in V$ once $x\not=V[i]$ is $$p=p_1+p_2+\dots+p_{n-1}$$ (following law of total probability) being $p_j$ the probability of $V$ having $j$ times the element $x$. But this probabilities are unknown. Or $$p=1-p'$$ being $p'$ the probability of $V$ not having $x$ as an element (also unknown).

Am I forced to suppose $V$ is a vector of elements of a certain finite set $X$ of $m$ elements or something similar?


texts: Proof or refute $n^n = \Omega(n!)$ with the help of Stirling's approximation

texts:
I'm trying to proof/refute the following equation:

$$n^n = \Omega(n!)$$

Generally I would try to use Convergence Criteria and or l'Hôpital's rule to solve such a problem.

$$\lim_{n\to \inf}{{f(n)}\over{g(n)}} = K$$

However, in this case $n!$ is somewhat of a party-stopper. I found Stirling's approximation which states that:

$$n! \approx \left(\frac{n}{e}\right)^n\sqrt{2πn} $$

My idea was therefore:

$${n^n}\over{(\frac{n}{e})^n\sqrt{2πn}}$$
$${n^n}\over{\frac{n^n}{e^n}\sqrt{2πn}}$$
$${e^n}\over{\sqrt{2πn}}$$
$$\lim_{x\to \infty}{{e^2n}\over{2πn}} = \infty$$

$$ 0 < K \leq \infty $$

therefore the original equation is true.

Is that approach "ok", did I understand Stirling's approximation correctly?


texts:
Are there any proofs that BQP is not in P?  In laymen's terms, I am asking if there is any formal proof separating the complexity class that quantum computers are presently assumed to solve efficiently from the complexity class that non-quantum computers are presently known to solve efficiently.

Obviously I'm not talking here about black box/oracle proofs that show they are nonequivalent if we have access to some theoretical oracle.  Just talking about regular, normal equivalence.


texts: How is the set of functions from ${\{a,b\}}$ to $N$ countable?

texts:
Assume a set of functions from ${\{a,b\}}$ to $N$

Where $N$ is the set of Natural numbers.

Let us assume that the size of $N$ is $n$.
i.e $|N|=n$

The first element $a$ have $n$ choices for mapping.
The second element $b$ have $n$ choices for mapping as well.

So the number of functions = $n.n$ = $n^2$.
which  is strictly greater than $n$ and hence the size of $N$.
So "Set of functions from ${\{a,b\}}$ to $N$", should not be countable. But it is. I am just a beginner in discrete maths, so this might be a stupid question for some. But please explain.


texts: Are compilers able to detect alternating accesses to arrays and interleave them in memory?

texts:
Is it possible to design a compiler which optimizes a loop in which arrays are accessed in alternate fashion? For example like this:

// int[] a,b
int sum = 0;
for(int i = 0; i < n; i++)
{
  sum += a[i] + b[i];
}

With the usual sequential array storage, a[i] and b[i] may be far away from each other in memory. Therefore, I think a good compiler optimization would detect that a[i] and b[i] are always accesses at the "same" time, and store the arrays interleaved, that is a[0] b[0] a[1] b[1] ... so that one memory access may retrieve both a[i] and b[i].


texts:
In text books, for instance in the 3rd edition of Introduction to Algorithms, Cormen, on page 625, the weights of the edge set $E$ is defined with a weight function $w:E\rightarrow \mathbb{R}$.

Why is it defined in this way? Why do we need a function? I mean, we all know when working with a graph, that the meaning is just that an edge $(u,v)$ has a weight $w$. So, why is it written with a function? I remember the first time I saw this definition I was very confused. Only after actually going through an algorithm and reading it again, I realized that it really just means that every edge has its weight.

So, I still don't fully understand why it is written in this complicated way and what exactly it means though, and it would be very nice if someone could tell me that in a understandable language.


texts: How to find the largest power of two divisor of a given integer?

texts:
Given an integer $x$, I need to find the largest power of two $p = 2^n$ that divides $x$ such that the remainder is zero.
When $x$ is zero, the algorithm should return zero. For odd numbers, it should return one, since the largest power of two that divides these numbers is $2^0$.
How to write an algorithm for this? (any programming language would do, or pseudocode)


texts: What does sublinear space mean for Turing machines?

texts:
The problem of deciding whether an input is a palindrome or not has been proved to require $\Omega(\log n)$ space on a Turing machine. However, even storing the input takes space $n$ so doesn't that mean that all Turing machines require space $\Omega(n)$?

Of course, there's no contradiction here, since any function that uses at least linear space also uses at least logarithmic space. But writing $\Omega(\log n)$ does suggest that it's possible for a Turing machine to use less than linear space – after all, why would people spend all that time proving $\Omega(\log n)$ if that was exactly the same thing what seems to be a trivial $\Omega(n)$ bound? So what does it mean for a Turing machine to use less than linear space?


texts: Is this language regular or non-regular: {ww : w ∈ {a,b}* }

texts:
This is a question from a text book that's giving me some trouble.  The question is:

  Determine whether or not this language is regular. Justify your answer.
  $$L = \{ww : w \in \{a,b\}^* \}$$

I think this language is not regular because $w$ can be of arbitrary length and adheres to no pattern.  So, therefore, it cannot be determined whether $ww$ is part of the language using a finite number of states.  Am I correct in this assumption, and does my explanation make sense?  Thanks for any help you can give me!

My answer, after reading the comments below:

Let $w = ww = (a^p)(b^p)(a^p)(b^p)$.  Then consider the Pumping Lemma.  Since $|xy| \leq p $ and $|y| \geq 1$, then the $y$ part of the string must be a's.  But if we pump up, we'll have more a's in the first part than the second, and $w \neq w \in             ww$.  Hence, the language can't be regular.


texts:
I saw in this video that computing clustering coefficient of central node  of a star graph using the following algorithm is $\Theta(n^2)$ and for a clique it is $\Theta(n^3)$. is that correct?

def clustering_coefficient(G,v):
    neighbors = G[v].keys()
    if len(neighbors) == 1: return 0.0
    links = 0.0
    for w in neighbors:
        for u in neighbors:
            if u in G[w]: links += 0.5
    return 2.0*links/(len(neighbors)*(len(neighbors)-1))


texts: Relation between problems and algorithms

texts:
From Wikipedia

  a computational problem is understood to be a task that is in principle amenable to being solved by a computer (i.e. the problem can
  be stated by a set of mathematical instructions). Informally, a
  computational problem consists of problem instances and solutions to
  these problem instances. For example, primality testing is the problem
  of determining whether a given number is prime or not. The instances
  of this problem are natural numbers, and the solution to an instance
  is yes or no based on whether the number is prime or not.

  ... A key distinction between analysis of algorithms and computational
  complexity theory is that the former is devoted to analyzing the
  amount of resources needed by a particular algorithm to solve a
  problem, whereas the latter asks a more general question about all
  possible algorithms that could be used to solve the same problem.

So a problem can be solved by multiple algorithms.

I was wondering if an algorithm can solve different problems, or can only solve one problem? Note that I distinguish a problem and its instances as in the quote.


texts: Reducing minimum vertex cover in a bipartite graph to maximum flow

texts:
Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim holds).

Intuitively: for each flow, pick one endpoint, then it is a minimum vertex cover in bipartite graph. But can it be shown rigorously?


texts: Determine deadline for periodic task that enter ready queue in RTOS

texts:
I am currently trying to optimise the scheduler of FreeRTOS and in general Real-Time Operating Systems as a Project.

In FreeRTOS, and I suspect other RTOS as well, we don't specify the deadline for the tasks, not to mention the tasks would mostly be periodic.

How can we, if possible, generate the deadline for them?

Maybe a constant added to the time task reached the ready queue? Where the constant depends on the priority.

How should I go about it? Looking for suggestions...

In short, how can we implement something like Earliest Deadline First?

I am actually trying to implement Ant Colony Optimisation.

Edit: In FreeRTOS the API of OS doesn't need deadline to create Task, only Priority can be set.


texts: Is concept of virtual memory about memory isolation or about ability to swap? Or both?

texts:
Most reading I found about virtual memory, such as http://www.linux-tutorial.info/modules.php?name=MContent&pageid=89 or https://en.wikipedia.org/wiki/Virtual_memory always state that virtual memory is a concept that allows operating system to make it "appear as though you have more memory than you really do".

But isn't that what overcommit is about? Isn't whole virtual memory concept primarily about the fact that each process has an isolated virtual memory pool, thus being unable to read or modify other process memory?

If not, what is this technology of memory isolation within own virtual memory pools called?


texts: Which one of these two sets is computably enumerable?

texts:
M is a turing machine description, L(M) is recognized by M, |L(M)| is the size of this language.

{M : |L(M)| <= 330}
{M : |L(M)| >= 330}

I don't quite understand what this question is asking. Does the first question mean  M accepts at most 330 inputs?

My thoughts:

co-CE
CE (Construct a M to check the input, if >= 330 inputs are accepted, halt)

I am not sure if I am correct, and can I prove the first question is not CE by decribing TM may never halt?


texts:
A code is (statistically) self-synchronizing if, given that the transmitted string is long enough, the receiver is guaranteed to eventually synchronize with the sender, even if bit flips or slips have occurred.

Do Huffman codes have this property in general? In case not, is there a criterion for testing if a Huffman code is self-synchronizing or, equivalently, is there a modified construction of a Huffman code which guarantees self-synchronization?


texts:
I'm having trouble understanding and solving the problem.
Suppose we have a program which is composed of 3 portions A, B and C and that each portion takes $t_A$, $t_B$ and $t_C$ respectively to run on a single-core CPU.
Assume that $t_A$ < $t_B$ < $t_C$
Assume we parallelize only the portion C of the code and that we run the whole program on a cluster that has up to $N$ cores. The speedup we achieve is linear to the number of cores.
I have to plot the execution time vs the number of cores
What I don't understand is, how can you have a linear speedup ? I've tried playing around with Amdahl's formula to find a way to have a linear speedup to the number of cores. I might be mistaken, but I've realized that this is only possible if the speedup is equal to the number of cores (so I don't understand how you can achieve a linear speedup).
If you could explain this to me, that would be very helpful, thank you.


texts: Card Shuffling, Bounding Mixing time using Paths and Flows

texts:
I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2).

To paraphrase, we are supposed to use paths and an encoding scheme in order to bound the mixing time of a Markov Chain composed of state space $\Omega$ where a given state consists of a permutation of cards labeled {1,...,$n$}. Further, a valid path $\gamma_{x,y}$ between two states $x,y \in \Omega$ can be formed using no more than $n$ transitions (i.e. we can go from state $x$ to state $y$ in $n$ transitions) as follows: for each $k$ in 1 thru $n$, move card $x_k$ (i.e. the card labeled $k$) from its current position to its final position (the one occupied by the card in state $y$). So in effect, each transition step (which I will label $z_i$) in the aforementioned path is also in the form of a valid permutation, where at most two cards have swapped their positions from the previous step $z_{i-1}$.

Furthermore, to the best of my knowledge, the "flow encoding technique" and "appropriate injection" that the question mentions have to do with showing that there exists no significant "bottleneck" or "congestion" in any path between any two states $x,y$, and this in turn proves that the Markov Chain has a rapid mixing time.

So the primary difficulty I'm having is how to devise an encoding scheme $e_i$ for each stage of the transition so as to prove that, given some step of the transition $z_{i-1} \rightarrow z_i$, there exists an injection between the pair of states $x,y$ and the encoded data $e_i$. If my understanding is correct, $e_i$ itself has to be in the form of a valid permutation on {1,...,$n$} (and so $e_i \in \Omega$), and it must be possible to get back $x$ and $y$ (i.e. derive the permutations of $x$ and $y$) if all you're given is the encoding along with the transition step $z_{i-1} \rightarrow z_i$.

My understanding of the problem of course could be incorrect in some way as I'm just learning this material, in which case I'd appreciate a correction. Regardless, how might I go about devising an appropriate encoding scheme? Thanks a lot.


texts: Name of an Exact Cover by 3 sets variant

texts:
Exact cover by 3-sets is $\sf{NP}$-complete:

Instance: Given a finite set $X = \{ x_1,x_2,...,x_{3n}\}$ of $3n$ elements and a collection $C = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \}  $ of $m$ 3-elements subsets of $X$;
Question: Find a subcollection $C'$ of $C$ such that every element in $X$ is contained in exactly one member of $C'$.

The problem remains NPC even if we add the following condition:

every element of $X$ appears exactly in three subsets of $C$

Has this variant an "official" name?


texts:
Suppose I have the following Functional Dependencies for a Relational Model:

$A \to C$
$B \to C$

According to the composition rule for functional dependencies we have:
If X → Y and Z → W, then XZ → YW

For the case above would it be correct to say:

$AB \to CC$

Leads to:

$AB \to C$

Would the composite $CC$ be the same as just $C$? And for a relational model would it be proper to separate $C$ into a relation such that $AB$ is the Primary Key? Or should I simply drop either of the relations $A \to C$ or $B \to C$?
I was told by my database professor that $AB \to C$ is wrong and I should dropped one of them when I have created a Logical Data Model. But I don't understand how what I said above is wrong.


texts: How can I compute logarithm when comparison is undecidable?

texts:
In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively:
newtype ArbReal = ArbReal {approximate :: Word -> Integer}
data ArbComplex = ArbReal :+ ArbReal

For the ArbReal type, the ArbReal constructor labels a function that, when fed an integer $n$, computes the encoded real number to $n$ decimal digits below the decimal point, rounded. For example, when ArbReal f = pi, f 0 = 3, f 1 = 31, f 2 = 314, and so on.
Note that there is no guarantee to the direction of rounding. Given ArbReal g = 0.5, g 0 can be either 0 or 1. This is inevitable, for if there were, an interval would be decidable.
ArbComplex encodes a complex number by specifying its real part and imaginary part.
I've successfully implemented addition, subtraction, multiplication, and division on both types. Division by 0 falls in an infinite loop, though.
I also implemented nth root function of real numbers, square root function of complex numbers (where branch cut doesn't exist, hence multivalued), and $\pi$.
Now it's time to implement natural logarithm (on complex numbers, without a branch cut). And that's where a problem emerged. I was implementing the algorithm (namely, AGM iteration) in this paper, but:

Finally, if $0< x <1$, we may use $\log(x) =−\log(1/x)$, where $\log(1/x)$ is computed as above.

This paragraph forces a comparison, which is undecidable. So it's impossible to implement the algorithm directly. Indeed, in my current version of implementation, $\log 1$ falls in an infinite loop.
Is there a tweak on the algorithm that makes the algorithm computable? Or must I implement a completely different algorithm?


texts: Synchronizing sequence and Synchronizable DFA, how come states repeat if synchronizing word length is $>|Q|^{2}$?

texts:
I am trying to prove problem 1.59 in Sipser's book: Introduction to the theory of computation , 2nd Edition.

Let $M=(Q,\Sigma,\delta,q_0,A)$ be a DFA and let $q'$ be a state of $M$ called its "home". A Synchronizing sequence for $M$ and $q'$ is a string $s\in \Sigma^*$ where $\delta (q,s)=q'$ for every $q\in Q$. (We actually have extended $\delta$ to strings so that $\delta(q,s)$ equals the state where $M$ ends up when $M$ starts at state $q$ and reads input $s$).
Say that $M$ is Synchronizable if it has a synchronizing sequence for some state $q'$.
Prove that, if $M$ is a $k$-state synchronizable DFA, then it has a synchronizing sequence of length at most $k^3$.

This problem was already attempted here. I don't understand the answer though:

The proof of this a standard shrinking argument: if such a word is longer than $k^{2}$, then during the runs from $q1$,$q2$ a pair of states repeats, and we can shrink $w$.

How come a pair of states repeats?
I don't see a problem with runs from $q1$ and $q2$ reaching separate states. I don't so how I could be sure that I could shrink to word without disturbing both routes.


texts:
In Categories, Types and Structures, authors talk about exponential objects in section 2.3.1.

  Let $C$ be a Cartesian category, and $a,b \in Ob_C$. The exponent of $a$ and $b$ is an object $b^a$ together with a morphism $eval_{alb}: b^a \times a\rightarrow b$ (evaluation map), and for every object $c$ an operation $\Lambda_c : C[c\times a,b]\rightarrow C[c, b^a]$ such that for all morphisms $f: c\times a\rightarrow b$, $h:c\rightarrow b^a$, the following equation holds:
  $\beta. eval_{a,b} \circ (\Lambda (f)\times id_a )=f$
  $\eta. \Lambda_c(eval_{a,b}\circ(h\times id_a))=h$

Can you please show me the steps to derive the last two equations?


texts: Can a machine choose whether or not to accept a state in a FSM

texts:
We were given a question in class with this FSM and had a debate over what the regex would be and the corresponding accepted strings. Does this FSM make sense as on state 1 there seems to be a choice between going to state 3 or looping on state 1 with the input of b.

![enter image description here][2]

Please forgive the bad drawing as we were given the question on paper.


texts: Is Post's Correspondence Problem decidable with fixed word size?

texts:
So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$.

I'm wondering, can anything similar be said for when there is a fixed word length?

To be precise, here's the problem:

  Given fixed $m$ and $n$, with $n \geq 7$, and words
  $u_1, \ldots u_n$ and  $v_1 \ldots v_n$ such that $|u_i| \leq m$ and $|v_i| \leq m$,
  is there an index sequence $i_1, \ldots i_k$ such that
  $u_{i_1} \cdots u_{i_k} = v_{i_1} \cdots v_{i_k}$.

For what values of $m$, if any, is this known to be undecidable?

Note that this is similar to this question, but none of the 8 linked papers seemed by their titles to answer my question, and I haven't fully read all 8 of them yet.


texts: Best-Case Running Time For Binary Search Tree Insertion

texts:
The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is:

  The term best-case performance is used in computer science to describe the way of an algorithm behaves under optimal conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list.

According to this definition, the best case running time for BST insertion should be $O(1)$ [consider that we are inserting to the root node]. But different resources says different things, some claim that it is $O(\log n)$ [perfect balanced tree] and some others claim that it is $O(1)$ which one should I believe?


texts: Maximum independent set in progressive k-partite graphs

texts:
I am working on the famous maximum independent set problem on a graph class called progressive $k$-partite graph, and it is defined as follows.

Given a graph $G = (V_1, V_2, \dots, V_k, E)$, where $V_i\ |\ i \in \{1,2,\dots, k\}$ are the partitions and $E$ is the edge set. We assume that the vertices of each partition is ordered. The order of the vertices in each partition is determined by a function $f: \mathbb{N} \rightarrow \mathbb{N}$, which takes a vertex as the parameter, and returns the order of that vertex in its partition.

The progressive rule is, if a vertex $v$ in some partition $V_i$ is adjacent to a vertex $u$ in another partition $V_j$, it must be also adjacent to vertices that have higher precedence, or lower precedence in $V_j$ w.r.t. the function $f$.

Moreover, there exists another function $g(V_i,V_j)$, that takes a pair of partitions as input, and outputs whether the progressive rule is applied forwards or backwards. If $g(i,j) = 0$, then an edge $uv$ from a vertex in $V_i$ to a vertex in $V_j$ means $u$ is also adjacent all $x$ vertices such that $f(x) < f(v)$. Otherwise, if $g(i,j) = 1$, then u is also adjacent to all $x$ vertices such that $f(x) > f(v)$.

To write formally,

$$ uv \in E \Leftrightarrow ux \in E\ \text{s.t. }  u \in V_i, v,x \in V_j \begin{cases}
       f(u) < f(x), & \text{if} & g(i,j) = 0 \\
       f(u) > f(x), & \text{if} & g(i,j) = 1
   \end{cases}
$$

also, $$ f(i,j) = 0 \Leftrightarrow f(j,i) = 1$$

So, basically, vertices are ordered in each partition, and for each pair of parititions, the progressive rule is dictated by another function.

You can interpret this scenario as a leveling system in a game. There are $k$ teams with arbitrary number of players in each, and each team hands in an ordered list of their players. To compete with a player in a partition, one must also compete all the players that are listed either below or above that player. The function $g$ determines, for each pair of teams, in which order they have to compete.

So, my question is,

  Given $G, f, g$, is finding maximum independent set NP-hard?

I think it is not, because we can use a quadratic-time algorithm, which checks a local independent set for a pair, and iterates by adding other pairs that are connected to them. However, I don't have a concrete algorithm.


texts: When and what must be present on the left-hand side of the turnstile in metalogics?

texts:
Let me show the problem on an example...
An actual task from one of the former exams:

Consider a simple functional language:
$$e::= x|n|e_1e_2|\lambda x.e$$
With typing rules:
$$\tau ::= \mathtt{int} | \mathtt{foo} | \tau_1 \rightarrow \tau_2$$
$$\Gamma \vdash n : \mathtt{int}$$
$$\Gamma (x : \tau) \vdash x : \tau$$
$$\begin{array} {c} \Gamma(x : \tau) \vdash e : \rho \\ \hline \Gamma \vdash \lambda x.e : \tau \rightarrow \rho\end{array}$$
$$\begin{array}{c} \Gamma\vdash e_1:\tau\rightarrow \rho\quad\Gamma\vdash e_2:\tau \\ \hline \Gamma\vdash e_1e_2 : \rho\end{array}$$
$$\begin{array}{c}\Gamma\vdash e:\tau \\ \hline \Gamma\vdash e: \mathtt{foo}\end{array}$$
Where the environment $\Gamma$ is a partial function from the set of variables into the set of types and $\Gamma(x:t)$ denotes an environment that assignts the type $t$ to the variable $x$ and works like $\Gamma$ for all other variables.
Derive types for the following expressions:
(omitted for brevity)
Example: Type derivation for $\lambda x.\lambda y.x$:
$$\begin{array}{c}x:\alpha,\;y:\beta\vdash x:\alpha \\ \hline x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha \\ \hline \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha) \end{array}$$

It is this example that perplexes me. Why is it necessary to put $x:\alpha$ on the left-hand side of $\vdash$ in the second step of the derivation? My thinking is that $\lambda x.y : \beta\rightarrow \alpha$ results from both $x:\alpha$ and $y:\beta$ so there's no reason to put $x:\alpha$ on the lhs of $\vdash$ but not $y:\beta$.
But $\begin{array}{c}x:\alpha,\;y:\beta\vdash x:\alpha,\; y:\beta \\ \hline x:\alpha,\; y:\beta\vdash \lambda y.x:\beta\rightarrow\alpha \end{array}$ is a tautology that brings in nothing, so we should instead simplify this to $\begin{array}{c}x:\alpha,\;y:\beta \\ \hline \vdash \lambda y.x:\beta\rightarrow\alpha \end{array}$. Note that this is precisely what the third step of derivation seems to be doing: $\begin{array}{c} x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha \\ \hline \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha) \end{array}$ They simply put nothing on the left-hand side of the $\vdash$.
What am I missing here? Is this related to the form of the axiom that seems to be used here - $\begin{array} {c} \Gamma(x : \tau) \vdash e : \rho \\ \hline \Gamma \vdash \lambda x.e : \tau \rightarrow \rho\end{array}$ - where the environment used above the vertical line contains the assignment $x:\tau$ while the environment used below the vertical line is devoid of this assignment? Which is why in $x:\alpha\vdash \lambda y.x:\beta\rightarrow\alpha$ the assignment $x:\alpha$ must be present before the $\vdash$, but the assignment $y:\beta$ must not? Is my reasoning correct? But if it is, then why does the third step seem to differ and is of the form $\vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha)$ and not $\lambda y.x : \beta\rightarrow\alpha \vdash\lambda x.\lambda y. x : \alpha \rightarrow (\beta\rightarrow\alpha)$?
Or am I splitting hairs here? But my thinking is that I'm not certain what degree of accuratness is required by this professor so I wouldn't like to loose points on something of this sort... Could you clear my confusion?


texts: How to find 5 repeated values in O(n) time?

texts: Suppose you have an array of size $n \geq 6$ containing integers from $1$ to $n − 5$, inclusive, with exactly five repeated. I need to propose an algorithm that can find the repeated numbers in $O(n)$ time. I cannot, for the life of me, think of anything. I think sorting, at best, would be $O(n\log n)$? Then traversing the array would be $O(n)$, resulting in $O(n^2\log n)$. However, I'm not really sure if sorting would be necessary as I've seen some tricky stuff with linked list, queues, stacks, etc.


texts: How to prove that context sensitive languages are closed under intersection and complement?

texts:
This is a question from the exam of our "Automata and Formal Languages" course. There is a question where asked to prove or disprove that any "relative complement" operation between two context sensitive languages will also produce a context sensitive language.

From the context sensitive closure properties Wikipedia, and princeton.edu.
I know that those languages are closed under intersection and complement.

I have spent too much time on finding the formal prove of those statements. Where / How can I find the proofs? Or how to prove them by myself? Can anyone point me to a reference ? Can any one post here the proofs ?


texts: What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale?

texts:
Background:

The pool ball weighing problem is a classic CS question thrown at students, typically to demonstrate a binary search (alternative to ripping phonebooks in half).

Pool Ball Problem: Given $n$ pool balls where exactly 1 weighs more than the rest, find that pool ball using a scale.

The common approach is to split the balls into two groups, then weighing each group. You can narrow it down to one ball in roughly $\log_2(n)$ rounds. You can modify the algorithm to change the resulting base of the logarithm. This can be done by changing how many groups the scale can weigh. For example, if you had a scale that determined the heaviest of 4 groups (plus sign shaped on a pivot), then you would only need roughly $\log_4(n)$ rounds.

Problem: Consider the pool ball weighing problem but allow us to grow the number of groups we can split the set of pool balls into.

Instead of using a scale that compares a predetermined constant number, $k$, of pool ball groups, suppose we are allowed to vary and modify it during execution. For example, you are allowed to start with a split into 2 groups, then 3 groups next round, then 4, etc. It is not bounded apriori. Let's say that comparing $k$ groups takes $O(k)$ time. As a result, we know the heaviest of the $k$ groups or know if they weigh the same. If we grow the number of splits with each successive round, then we would require much fewer than $log(n)$ weigh-ins. There are divisibility issues that come up when doing the splits, but assume they are trivial to resolve.

$f(i) = \text{# of splits in $i^{\text{th}}$ round}$
(This is a positive, increasing function. We are required to spend the time/space to compute this.)

Let $t_f(i)$ be the time complexity of computing $f(i)$ given $\langle f(1), \dots, f(i-1)\rangle$ or subset of.

$N(i) = \begin{cases} n  & \text{if } i = 0 \\
\frac{N(i-1)}{f(i)} & \text{if } i \geq 1 \end{cases} = \text{# of pool balls after round $i$}$

We narrow our search down to one ball in $j$ rounds when:
$N(i) = 1 \geq \frac{n}{f(1)\cdot f(2)\cdot \dots \cdot f(j)}$

Or alternatively:

$\prod_{k=0}^{j}f(k) \geq n$ for some $j(n)$ dependent on $f$

Question: What can we say for the optimal time complexity of this algorithm? What are some properties of an optimal $f(i)$ we should expect? I realize this heavily depends on which models of computation we use (computing a fast growing $f$ can be expensive on some models while cheap on others). I'm willing to be reasonably flexible and not picky about it. Perhaps you guys could suggest a fruitful/interesting choice. For instance, the undergrad version of the problem trivializes the complexity by ignoring the complexity of grouping the balls together and probably considers $+, \times$ to take constant time.

The tricky part here is to pick a fast growing $f(i)$ that does not end up becoming too expensive to compute. The faster a chosen $f$ grows, the more that the time complexity decreases. On the flip side, the longer $f$ takes to compute, the longer the algorithm ends up running. We're looking for ways to balance these two.

Example:
I could simply increment the number of groups I split the pool balls into each round. Here, $f(i) = i + 1$. The total number of uses of the scale is $O(\Gamma^{-1}(n))$ (inverse factorial). The overall asymptotic time complexity is $(2+3+\dots+\Gamma^{-1}(n)) + \Gamma^{-1}(n) = O\left( \binom{\Gamma^{-1}(n)}{2} \right)$ (this takes into account the time complexity of handling the k-scale and incrementing the number of rounds each time). I'm assuming integer addition is a constant time operation.


texts: Barendregt's Variable Convention: what does it mean?

texts:
Barendregt's Variable Convention: If $M_1,...,M_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables.

This convention appears a lot in papers and I always wonder what does it mean. I want to know exactly what it is saying. I have two ideas about it

when you working on the theory

always keep a bound variable's name different from the names of variables at a particular time (Note:two bound variables may have same names)
always keep a bound variable name different from name of other bound variables name and all free variable names (every name is distinct)

Variable convention does not mention about if we can have two bound variables  with same names, but I feel variable convention also implies such distinctiveness of bound variables.

So anyone clarify it to me?

Thanks in advance!


texts: Strongly connected and completely specified Moore equivalent of a Mealy Machine

texts:
Problem: Prove that if a Mealy machine is strongly connected and completely specified, the corresponding Moore machine will also be strongly connected and completely specified.

My approach so far:

As the Mealy Machine is completely specified, we have 2 cases for each state:

All transitions coming into this state have the same output.
At least 2 transitions coming into this state have different outputs.

For case 1:
The equivalent for this state would simply be changing the notation, i.e. mark all transitions into this state simply by the input symbols and just mention the output with the state as is.

Now, as the machine is completely specified, each such input transition and it's corresponding output will be defined, and the states resulting due to such states will also have completely specified transitions.

For case 2: The equivalent for such a state requires the 'splitting'/addition of new states such that each 'split' state corresponds to the different outputs that can be generated. We split a state into a 2 corresponding states.

Now, as the machine is completely specified, each such input transition and it's corresponding output will be defined, and the states resulting due to such states will also have completely specified transitions.

Strongly Connected Machine: If for any two states $S_i, S_j$ of the machine, there exists a finite sequence of input characters that can make the machine transition from $S_i$ to $S_j$, the machine is strongly connected.

Completely Specified Machine: Consider $M = (I,O,S,F,Z)$

$I:$ Input Symbols
$O:$ Output Symbols
$S:$ Set of States
$F:$ Transition function $F: S\times I \rightarrow S$
$Z:$ Output function
$Z: S \rightarrow O $ (Moore)
$Z:$ $S\times I \rightarrow O$ (Mealy)

Now, if for every $(p,x)$ such that $(p \in S, x \in I)$ there exist some $q \in S$ and $y \in O$ such that $F(p,x) = q$ and $Z(p,x) = y$ (Mealy), $Z(p) = y$ (Moore)

My Question:

I'm having a hard time trying to formally prove the above while I can see it is true with the above intuition. I can similarly say that if the mealy machine was strongly connected, even after replacing it with 1(or 2) states, it would most definitely still be strongly connected. I was looking for help on formalising this above approach or a more solid proof on this.


texts: Why the Call instruction in the x86 architecture saves the return address as EIP+5 instead of 4?

texts:
In 'The Computer Organization and design book' it illustrates the call instruction as

Decrementing the stack pointer by 4.
saving the EIP+5 into the stack.
Jumps to the new address specified.

What I know already is the instructions in this architecture are not typically all 4 byte in length, Hence.

How do we standardize the EIP to be added by 5 to the next instruction ?

normally in the MIPS architecture throughout the rest of the book the EIP is incremented by 4 which is intuitive as all the instructions are 32 bits.


texts: Trouble Replicating Proof of The Lambda Calculus Fixed Point Theorem

texts:
From pg. 35 of Lambda Calculus and Combinators An Introduction:

  Corollary 3.3.1 in $\lambda$ and $CL$: for every $Z$ and $n \ge 0$, the equation

  $$ xy_1 \ldots y_n = Z $$

  can be solved for $x$. That is, there is a term $X$ such that

  $$ Xy_1 \ldots y_n =_{\beta, w} [X/x]Z. $$

  Proof: Choose $X \equiv \mathsf{Y} (\lambda x y_1 \ldots y_n.Z)$.

Note: In the book, we assume that $\mathsf{Y} \equiv (\lambda ux. xuux)(\lambda ux. xuux)$. Further, for ease of notation, let $V \equiv (\lambda x y_1 \ldots y_n.Z)$.

The problem is that when I check this with my own examples, I'm not getting this result.

For example, suppose that neither $x$ nor any of $y_1, \ldots , y_n$ is in the free variables of $Z$ (to make it easy). Then this theorem asserts that if $X \equiv \mathsf{Y}(\lambda x y_1 \ldots y_n . Z)$, then

$$
Xy_1 \ldots y_n =_{\beta, w} Z
$$

When I check whether this true, I get

$$
(\mathsf{Y}(\lambda x y_1 \ldots y_n . Z))y_1 \ldots y_n = (\mathsf{Y}V)y_1 \ldots y_n = (V\mathsf{Y}V)y_1 \ldots y_n =_{\beta, w} Zy_n
$$

Am I doing something wrong?


texts:
The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following:

  For a recurrence of the form $T(n) = aT(\frac{n}{b})+f(n)$
  with constants $a \ge 1$ and $b>1$,

  Case 1: if $f(n) = O(n^{\log_b(a-\varepsilon)})$ for some $\varepsilon > 0$, then $T(n) = \Theta(n^{\log_b(a)})$

  Case 2: if $f(n) = \Theta(n^{\log_b(a)})$, then $T(n) = \Theta(\log n \cdot n^{\log _b(a)})$

  Case 3: if $f(n) = \Omega(n^{log_b(a+\varepsilon)})$ for some $\varepsilon > 0$, and if $a f(\frac{n}{b}) \le c f(n)$ for some
  constant $c<1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

I have seen proofs of this theorem which go through the algebraic derivation of these results and I understand how to apply it but I don't have a very strong intuitive understanding of why it works. Here's what I understand so far, using these explanations of the Master Theorem on Quora as a starting point:

The first answer frames the three cases in terms of the relative amount of work done at each level (either increasing geometrically, staying the same, or decreasing geometrically). At a high level, I understand this intuition and if the Master Theorem were given to me I could explain it using this reasoning, but I'm unconvinced that I could take this idea of geometric growth/decay and then derive the theorem.
I think the second answer is closer to the kind of intuition I'm looking for. It explains the $aT(\frac{n}{b})$ term and the $f(n)$ term as opposing forces of replication and merging, respectively. However, I'm having trouble understanding how the intuitive cases (the replication step winning, the merging step winning, and the forces being equal) actually translate into the three different cases of the Master Theorem.

This explanation also follows a similar argument and simplifies the Master Theorem in the following way:

  If $T(n) = aT(\frac{n}{b})+f(n)$ then compare $n^{\log_b a}$ with $f(n)$

  If $f(n) < n^{\log_b a}$, then $T(n)=n^{\log_b a}$
  If they are equal, then $T(n)=f(n)\log n$
  If $f(n) > n^{\log_b a}$, then $T(n)=f(n)$

While I see the connection with the Master Theorem cases here, there isn't an intuitive explanation for where the $n^{\log_b(a)}$ term comes from. That is, if I were just looking at the recurrence relation $T(n) = aT(\frac{n}{b})+f(n)$, how would I know to compare $f(n)$ with $n^{\log_b(a)}$? Perhaps there is some connection between $n^{\log_b(a)}$ and $aT(\frac{n}{b})$ that I'm missing?

In summary, I'm looking for something of the form "here is a high level concept/understanding (eg. geometric growth/decay, competing forces), and now here is how you can derive the Master Theorem from that idea." I would be satisfied with an explanation of how to get from the replication and merging intuition posed in the second bullet point above to the three different cases of the Master Theorem but I'm also interested in any other more intuitive perspectives.


texts: How to understand definition of $\Pi_k$ in arithmetical heirarchy

texts:
Am reading a text about computability theory, and according to the text, at each level $k$ of the arithmetical hierarchy, we have two sets, $\Sigma_k$ and $\Pi_k$, where $\Pi_k$ is defined as:

$$
\Pi_k=co-\Sigma_k
$$

So that for $k=0$, we have the class of decidable sets and $\Sigma_0=\Pi_0$, and for $k=1$, we have $\Sigma_1$ as the class of computably enumerable (c.e.) sets and $\Pi_1$ as the class of not computably enumerable sets (not c.e.)....

Let $L(M_e)$ denote the language recognized by Turing Machine $M_e$ with Godel number $e$. I came across the following language $E$, where:

$$E=\{e|L(M_e)=\Sigma^*\}$$

i.e. $E$ is the language of all Turing Machine codes $e$ that are computably enumerable. By a diagonalization argument, it can be shown that $E$ is not c.e. This implies that:

$$
E \in \Pi_1
$$

However, if $E \in \Pi_1$, it means that $E = co-A$, for some $A \in \Sigma_1$, using the definition in the above statement... However, the complement of $E$ is:

$$
\overline{E}=\overline{\{e|L(M_e)=\Sigma^*\}}
$$

which (I guess) means that $\overline{E}$ is the language of all Turing Machines $e$ such that on some inputs, $e$ diverges... However, it has been shown that $\overline{E} \equiv_m K^{2}$, i.e. $\overline{E} \equiv_m K^K$, so that, where given two sets $A$ and $B$, we have $A \equiv_m B$ iff $A \leq_m B$ and $B \leq_m A$, and $\leq_m$ refers to a many-to-one reduction:

$$
\overline{E} \equiv_m K^K \in \Sigma_2
$$

Given that $\Sigma_2 \neq \Sigma_1$, it looks like that $\overline{E}$ is not computably enumerable... But doesn't this contradict the definition of $\Pi_1$ which states that the complement of a not c.e. set is c.e. ?

I think am missing something in my understanding of the definitions ...


texts: How to Track Connected Components in a Graph when Deleting Nodes

texts:
Suppose you have a graph G, and you want to support the following operations:

addNode(Node n)
addEdge(Node n1, Node n2)
deleteNode(Node n)

Now I want to track after every operation what the connected components of my graph are. If I only had to support addNode and addEdge, I would use a Union-Find data structure to maintain this information after every operation.

However, how does one support deletion operations? My current thought is that I must run several BFS operations on my graph to recompute all the connected components of the graph again.

Is there a more efficient way to support the delete operation?


texts: A condition for $\emptyset \neq S\subset RE$ under which $L_S \notin RE$

texts:
I read some computation theory lecture notes and after citing and proving the proposition: $\emptyset \in S \Rightarrow L_S = \{\langle M \rangle : L(M)\in S\} \notin RE$ it says that $\emptyset\in S$ is not a sufficient condition, i.e $L_S \notin RE$ doesn't yield $\emptyset \in S$, by giving the counter example $L_{\Sigma ^*}:= \{\langle M\rangle : L(M) = \Sigma^*\}\notin RE$ . However it says that there is a necessary and sufficient condition under which $L_S\notin RE$. I searched in Sipser's book for this condition but couldn't find it. I would really appreciate a reference for this condition.

Edit : given the answer by @dkaeae , I wish to know what is the stronger property one can deduce about a non-trivial $S\subset RE$ in case $L_S \notin RE$.


texts: Is there a low degree vertex in planar graphs?

texts:
A book I read states "Since $G$ is planar, $G$ has a vertex $v$ of degree at most 5".

Is this true?
Why?
Does this theorem have a name?


texts: NP-completeness of triangle removal problem

texts:
Triangle removal problem states that, given an undirected graph G, can you pick a subset
S of vertices such that removing S will remove all triangles from the old graph and |S| <= k. I was trying to use reduce from vertex cover problem, but every construction I attempted has failed. Here's what I've done:

1) Add extra edges to the graph such that every pair of distinct vertices is connected by an edge (In other words, create a complete graph Kn)

2) Create a subgraph of G, but only composed of vertices with degree at least 2 from the original graph

I found a counter example for each construction, and I can't fully grasp the starting point. The goal is that I want to build some graph out of an old graph such that the every triangle should use at least one vertex in S(solution returned by black box for "triangle removal problem"), but it has to be a vertex  cover for the old graph at the same time. How should I approach this?

Edit:
Current attempt - for every existing edge (u,v) in E in a graph, add a new vertex w and add two new edges (u,w) and (w,v) so that it forms a triangle


texts: Inherent complexity of testing line segment intersections with aligned and oriented bounding boxes?

texts:
It is well known that in practice, a substantial difference in run-time between algorithms for testing intersection of a line segment with aligned or oriented bounding boxes (in computer graphics parlance AABB/OBB) does exist. Nevertheless, I wonder if anybody has ever tried to find a lower bound on the run-time for a deterministic algorithm for either problem and found that this lower bound is actually different.

I have been conducting several searches on both Scholar and naked Google and either (1) I don't know how to formulate the question in a format such that Google algorithms return a relevant answer, or indeed (2) nobody has looked into this problem.

I do think that (1) is way more likely than (2). So I would appreciate if anybody here is aware of a result like the one I am trying to find, or if it has been discussed in some (formal) way that I can cite, could provide me with some pointers.

Thanks!


texts: We can make all the gates using nand or nor gates. My teacher told us that nand gates are cheap too, then why do we need other gates at all?


texts:
I just learned about recurrences and I just can't solve this problem. I have this recurrence relation:

$$
T(n) = \begin{cases}
k\cdot T(\frac{n}{k}) & n > 0\\
1 & n = 0\\
\end{cases}
$$

where $k$ is a constant number.

I tried drawing a recurrence tree or replacing for lower $n$s but no success. I hope you can help me with an idea!


texts:
I was reading the other day about this problem, refreshing it, and on a couple of places over the internet I read somebody explaining something in the line of '..does not matter as long as is polynomial, a N^20 or N^30 will do it, we know that maybe the solution does not make the problem tractable but if we can produce an algorithm having polynomial time complexity that will be good enough..."

My educated guess makes me think, that, if we can have a polynomial tractable algorithm , with today's computing resources, then that will be great, because we can use the solution, but looks like for P vs NP question as long as is polynomial that would be all.

How accurate are the comments I found on the internet?


texts:
I have a BNE-instruction (32 bits), which contains 16 bits for the jump field:

Opcode A[31:26]
RS A[25:21]
RT A[20:16]
Immed A[15:0]

Assuming the BNE-instruction will now be written in 64 bits format, what would be the (new) max jump distance this instruction can make?

I really have no clue, what to do, so I hope someone can help me. Thanks in advance.


texts:
For finding out whether two Turing machines accept any words in common
(ie. whether L(M1)∩L(M2) = ∅), would this question be computably enumerable? co-computably enumerable? neither CE nor coCE?


texts: Is a perfect matching's weight less than MST of a metric graph?

texts:
This is part of a bigger proof I'm trying to solve, which eventually came down to one thing:

Let $G=(V,E)$ an un-directed, complete, metric graph (maintains the triangle inequality) with an even number of vertices. Let $PM$ denote a minimum-weight-perfect matching on $E$ and let $MST$ denote a minimum-spanning-tree of $G$.

Is it true that $w(PM) \leq w(MST)$ ?

I'm not sure if the fact that the graph is metric is useful, but I have pointed that out any way.

I know $PM$ and $MST$ do not necessarily share all edges, but maybe some of them? I was trying and couldn't find a counter-example to disprove this.

My gut says it's true, but I cannot find a definitive way to prove it.


texts: Are there name and literature for this SAT-like problem?

texts:
Given $f : \{0,1\}^* \to \{0,1\}$ and $n \in \mathbb{N}$,
we define $\textsf{Prob}(f,n)$ as the following problem:

  Find an $x \in \{0,1\}^n$ such that $f(x) = 1$.

A machine solving $\textsf{Prob}(f,n)$
would have $f$ encoded as a bit-string representing another machine computing $f$
and would have $n$ encoded in binary.

$\textsf{Prob}(f,n)$ generalizes some problems. For example:

If $f$ is a Boolean logical proposition with $n$ variables,
then $\textsf{Prob}(f,n)$ would be the search problem that corresponds to the SAT of $f$.
If $f$ is the decider for a language,
then $\textsf{Prob}(f,n)$ would be the problem of finding
an $n$-bit string in that language.

Has $\textsf{Prob}(f,n)$ been studied in the literature (presumably with another name)?
Is there already a name for this problem?
What would be a good starting point to find papers on this problem in the research literature?

What problems are similar to this problem?

Is there linear-time $f$ such that
$\textsf{Prob}(f,n)$
has no better algorithm than brute force?
Formally, is there $f$ such that
evaluating $f(x)$ is in $\textsf{DTIME}(O(\lvert x \rvert))$
and $\textsf{Prob}(f,n) \in \textsf{DTIME}(\Omega(2^n))$?


texts: Subset of $k$ vectors with shortest sum, with respect to $\ell_\infty$ norm

texts:
I have a collection of $n$ vectors $x_1, ..., x_n \in \mathbb{R}_{\geq 0}^{d}$. Given these vectors and an integer $k$, I want to find the subset of $k$ vectors whose sum is shortest with respect to the uniform norm. That is, find the (possibly not unique) set $W^* \subset \{x_1, ..., x_n\}$ such that $\left| W^* \right| = k$ and

$$W^* = \arg\min\limits_{W \subset \{x_1, ..., x_n\} \land \left| W \right| = k} \left\lVert \sum\limits_{v \in W} v \right\rVert_{\infty}$$

The brute-force solution to this problem takes $O(dkn^k)$ operations - there are ${n \choose k} = O(n^k)$ subsets to test, and each one takes $O(dk)$ operations to compute the sum of the vectors and then find the uniform norm (in this case, just the maximum coordinate, since all vectors are non-negative).

My questions:

Is there are a better algorithm than brute force? Approximation algorithms are okay.

One idea I had was to consider a convex relaxation where we assign each vector a fractional weight in $[0, 1]$ and require that the weights sum to $k$. The resulting subset of $\mathbb{R}^d$ spanned by all such weighted combinations is indeed convex. However, even if I we can find the optimum weight vector, I am not sure how to use this set of weights to choose a subset of $k$ vectors. In other words, what integral rounding scheme to use?

I have also thought abut dynamic programming but I'm not sure if this would end up being faster in the worst-case.

Consider a variation where we want to find the optimal subset for every $k$ in $[n]$. Again, is there a better approach than solving the problem naively for each $k$? I think there ought to be a way to use the information from runs on subsets of size $k$ to those of size $(k + 1)$ and so on.
Consider the variation where instead of a subset size $k$, one is given some target norm $r \in \mathbb{R}$. The task is to find the largest subset of $\{x_1, ..., x_n\}$ whose sum has uniform norm $\leq r$. In principle one would have to search over $O(2^n)$ subsets of the vectors. Do the algorithms change? Further, is the decision version (for example, we could ask if there exists a subset of size $\geq k$ whose sum has uniform norm $\leq r$) of the problem NP-hard?
Suppose we now know that our vectors $x_i$ all come from $\{0, 1\}^d$. Does anything change?


texts: Longest Path Problem on Graphs of Bounded Clique-Width

texts:
The wikipedia article mentions:

For graphs of bounded clique-width, the longest path can also be solved by a polynomial time dynamic programming algorithm.

However there are no references and I wasn't able to find anything relevant in literature. Nor was I able to come up with a naive algorithm that would achieve this.
Would appreciate some pointers. If it's important for the algorithm -- I do have constructions of the graphs in terms of the node/union/join/rename operations.


texts: I have a data set with two classes: one class has at most 2000 members while the size of the second class is unlimited, though it is typically in the hundreds of thousands.  I have read that it is problematic to use a decision tree to naively classify this data.  My question is, how how I modify the data or the classification scheme to classify such data, using a decision tree at some point?


texts:
According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite ..

that's mean it may be infinite language is regular ?

my example is L = {a^n b^n+1, n >0 } is it regular ?
it generate infinite set of strings
how to represent it as DFA or a regular expression (can represent this language using RegExp ?).. i can guarantee the exact number, how to automata to maintain the exact number of a's or b's

i tried some grammar, i do not get the regular grammar ..
my grammar looks like

S -> AB

A -> aA | e

B -> bbB | e

final question, how the language is regular and infinite in the same time ?


texts: How to convert a grammar with finitely many ambiguous strings into a new, unambiguous grammar?

texts: Suppose $L$ is an infinite CFL, and $G$ is a grammar with finitely many ambiguous strings which generates $L$.  Is it possible to convert $G$ into an unambiguous grammar which also generates $L$?  If so, how would I go about doing this?  One starting approach I see is to have rules of the form $S \longrightarrow w $ in the new grammar, where $w$ is a string that was ambiguous in the original grammar.  I'm not sure; however, how I'd go about modifying the original grammar to a further extent.  Of course, we'd like to keep much of $G$ for our new grammar, insofar as $G$ unambiguously generates strings of sufficient length.


texts: Assume a map-reduce program has $m$ mappers and $n$ reducers ($m > n$). The output of each mapper is partitioned according to the key value and all records having the same key value go into the same partition (within each mapper), and then each partition is sent to a reducer. Thus there might be a case in which there are two partitions with the same key from two different mappers going to 2 different reducers. How to prevent this from occurring? That is, how to send all partitions (from different mappers) with the same key to the same reducer?


texts: Compiler implement power method with syntax graph

texts:
We learn how to write compiler. I know that we can use grammar to construct a parser for compiler or otherwise use a syntax graph to represent grammar and generate code when move on it's node. our teacher use second approach. a simple graph for only expression (limited) is:

You can see that when we see a sub graph, we go inside that to complete it. in this example, "T", "E" and "F" are sub graphs. after getting to final node of sub graph, if there is no token that can be matched, we comeback to upper graph and move on that edge. if there is code generation on a graph, we generate it too like "genSum" and etc.
If you examine it, you will see that it works perfect. however I don't know how to implement "power" syntax with this syntax graph because of it's associativity.  Is it impossible?  out teacher doesn't answer that and ask us to think about it.
Thanks and sorry for bad English.


texts: Clique decision problem restricted to a subgraph

texts:
I know that the clique problem is NP-complete.

However, what if we change the problem a little bit?

For example,

Given a graph $G(V,E)$, an integer $k$ and a subset $S$ of $m$ vertices, we are given a decision problem to find a clique with size $k$ contained within $S$.

A real world example would be something like a social networking graph. Where each node is a person and an edge represents that they are friends with each other. Now what if we were to find clique with size $k$ amongst the set of teenagers.

Does that change the complexity? Since we are only looking into a subgraph, e.g. less vertices to look for?

Thanks!


texts: Edit distance for huge strings with bounds

texts:
My question is simple but I don't know if the answer is.

  If you have two strings of length 10 million each, is there an algorithm that would allow you in
  practice to compute their edit distance (Levenshtein) if you are told
  it is at most 100?


texts: Complexity for merging 3 sorted arrays using this specific algorithtm

texts:
During an interview I was asked to calculate the big theta complexity for the following algorithm that receives 3 sorted arrays of variable size and returns a new array which has the elements of the original 3 arrays.

The algorithm is pretty basic: we set indexes at the beginning of each array and use such indexes for accessing the elements, in that fashion  we find the minimum element for the 3 arrays (at the position given by the indexes) and then we insert the element into the resulting array and we increase such index. We repeat until we are done processing every element.

My answer was that the complexity was linear because we are processing n elements and we are doing a constant number of comparisions for finding the minimum element out of the 3 arrays (at the given index position). Yet, I was told that the complexity is not linear but it is higher than nlogn.

I have a few ideas but could someone explain  the actual complexity of this algorithm for me?

Thanks for your time.


texts: Information loss of a 9-input majority gate

texts:
According to information theory, the logic gates AND, NAND, OR, NOR all lose 1.189 bits of information each with two bits of information at their inputs and with all inputs being independently and uniformly distributed.

When gates are used in combination with other gates in a circuit, to calculate the entropy loss for the entire circuit you have to use what are called "mixture probabilities" or "mixing distributions" to calculate the entropy loss, the loss for each gate being dependent on the entropy loss history of the preceding gates.

Can anyone calculate the entropy loss of a majority gate with 9 inputs, all equally likely $\{1,0\}$?


texts: Simulating a multi-network environment in one device using Python

texts:
I am deploying a blockchain on a localhost where all nodes can communicate with each other using ports and APIs; however, a node/group of nodes can leave the main blockchain group.
Some questions came up as I was working on it:

When a group splits, can we reassign new ports for the split such that the nodes can communicate among themselves and prevent the split from communicating with the main blockchain group?
Are there any Python tools that can facilitate the simulation of the network environment?


texts: How to convert a Turing Machine program to a tiling using Wang Tiles?

texts:
This is a cross-post from a post on MathSE due to lack of answers.

To illustrate my question I provide the following example.

The website Online Turing Machine provides a Turing Machine simulator. The following program adds 1 to any binary number.

q0,1  =>  q0,1,>
q0,0  =>  q0,0,>
q0,_  =>  q1,_,<
q1,0  =>  q3,1,>
q1,1  =>  q1,0,<
q1,_  =>  q3,1,>

A program line has the following format:

state, character read => new state, character written, direction tape

In the program above q0 is the initial state and q3 is the accepting state.

In Tilings and Patterns by Gruenbaum and Shephard, 11.4 "Computing By Tiles" I read that it is possible to convert any turing machine program to a tiling of the plane using Wang tiles. The book contains an example tiling which calculates the Fibonacci numbers. The procedure, recipe, to convert a Turing machine program to a set of Wang tiles is not entirely clear to me.

Question: What is the algorithm to convert a Turing Machine program line by line to a set of tiling of the plane using Wang Tiles? And how does it work on the Turing machine in the given example?

Update:

Image is that of a Wang tile that adds 1 to a binary: 111 + 1 = 1000 where 1 is red, 0 is cyan. Aiming to generate tiles like this from any Turing Machine. First row 111, last row 1000.


texts: Finding MST for connected graph with $|E|=|V|+87$

texts:
Given $G=(V,E)$ undirected, connected graph and weights given by $w:E \to \mathbb R$. We also know that $|E|=|V|+87$.

Find Minimum spanning tree of $G$.

Obviously we can use Prim in $O(|V| \cdot \log |V|)$.

But can we do better by using the fact that the graph is connected, and use the sets sizes? Like removing the lightest edge from each cycle and keeping the connectivity of the graph?


texts: Computing farthest pair of points in d dimensions

texts:
Question: Given $n$ points in metric space, find a pair of points with the largest distance between them.

If we restrict ourselves to $d$-dimensional Euclidean space then, a naive algorithm of finding distances between all pairs of points in a space of dimension $d$ and selecting the maximum requires $O(dn^2)$ time.

However, finding a farthest pair for points in a plane can be done in time $O(n\log n)$. This is done by restricting our search to pairs of antipodal points on the convex hull. But, this approach does not scale well with higher dimensions.

Is there any solution better than the naive one either for the case $d=\Omega(n)$ (i.e., high dimensions) or for the case $d=O(\log \log n)$ (i.e., low dimensions)?


texts: How does one simulate continuous gravity using a discrete timestep?

texts:
While gravity in real life is continuous, computers are limited to discrete calculations.

Therefore, a seemingly correct projectile simulation inevitably drifts off.

For example:

// Repeat once per frame
position += velocity * deltaTime;
velocity += gravity * deltaTime;

Graphed, compared to the actual projectile formula


texts: Min-entropy of a random pre-image of a random function

texts:
I am facing hard time understanding min-entropy.

Fix $v \in \{0,1\}^{n/2}$, let $F\colon \{0,1\}^n \to \{0,1\}^{n/2}$ be chosen randomly, and let $X_v$ be a string chosen uniformly at random among $F^{(-1)}(v)$ (or a special string $\epsilon$ if $F^{(-1)}(v) = \emptyset$). We want to compute the probability that $H_\infty(X_v) \leq n/4$ (over the choice of $F$), where $H_\infty(X_v)=-\log(\max_{x}\{\Pr[X_v=x]\})$ is the min-entropy of $X_v$.

It's not obvious what approach is needed to solve such things! It would be helpful if one could explain where to start...


texts: From Whence the Randomization in Randomized Quicksort

texts:
Cormen talks briefly about the advantages of picking a random pivot in quicksort.  However as pointed out here(4th to the last paragraph):

  Using a random number generator to choose the positions is relatively
  expensive

So how is picking a random pivot actually implemented in practice, and how random is it?  It can't be too expensive, since from what I understand one of quicksort's main advantages over other $\cal{O}(n \lg n)$ sorts is the small constant factors, and spending allot of cycles picking pivots would undermine that advantage.

EDIT

As an example, the C code from "Three Beautiful Quicksorts" actually calls the C library rand function:

int randint(int l, int u) {
    return rand()%(u-l+1)+l;
}

void quicksort(int l, int u) {
    int i, m;
    if (l >= u) return;
    swap(l, randint(l, u));
    m = l;
    for (i = l+1; i <= u; i++)
        if (x[i] < x[l])
            swap(++m, i);
    swap(l, m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}

While the pivot picking code here is clearly $\cal{O}(1)$, it would seem that the hidden $c$ here is relatively high.


texts:
I've heard of (structural) induction. It allows you to build up finite structures from smaller ones and gives you proof principles for reasoning about such structures. The idea is clear enough.

  But what about coinduction? How does it work? How can one say anything conclusive about an infinite structure?

There are (at least) two angles to address, namely, coinduction as a way of defining things and as a proof technique.

  Regarding coinduction as a proof technique, what is the relationship between coinduction and bisimulation?


texts: How can I make the variance of a multiple sum of set of fixed number of variables minimum?

texts:
Here is the problem:
There are $MN$ people, where there are $M>1$ seeds and $N>0$ people are in each seed.
We have to make $N$ teams of $M$ people where everyone in the team have different seeds.
Each person have their own value; values are positive integers.
Assume there are no two people with same values.
For two distinct seeds $I$ and $J$, we say $I<J$ if for all $x\in I$ and $y\in J$, $x<y$ holds.
It is guaranteed that for any two distinct seeds $I$ and $J$ in the problem, $I<J$ or $J<I$ holds. In other words, we can set $M$ seeds $I_1,I_2,\cdots,I_M$ in the problem to satisfy $I_1<I_2<\cdots<I_M$.
I am interested in two versions of this problem:

There are no paired people. This means in process of making $N$ teams, there is no restriction except given above.
There may be some paired people. This means a set of paired people that cannot be split is given, so that if a team contains one person from some pair, the team should also contain the other person from that pair. It is provided that every pair contains exactly two people from different seeds.

For each version, the task is to design an algorithm to make the variance of the sum of values of people in each team to be minimum.
Since this problem is NP (complete?), I would accept heuristics.
I hope that the heuristic method gives the solution with variance at most $25\%$ larger than the optimal solution, as I don't want to harm the balance of the team.
Could you please give an algorithm or heuristic that can solve this problem? Also, adding a time complexity would be highly appreciated!


texts:
I'm now to problem solving, and I need some help and insight on the following problem from HackerRank:

Given a sequence $p(1),\ldots,p(n)$ of distinct numbers from $1$ to $n$, find numbers $y_1,\ldots,y_n$ such that $p(p(y_1))=1,\ldots,p(p(y_n))=n$.

My approach was to perform a double index lookup on each element in the provided input: for each $i \in \{1,\ldots,n\}$, I find an index $z_i$ such that $p(z_i) = i$, and then an index $y_i$ such that $p(y_i) = i$.
Is there a more efficient way to solve this problem?


texts: To find median of k sorted arrays of n elements each in less than O(n*k*log(k))

texts: How to find median of k sorted arrays each of length n? Note that total elements would be n*k. I know it can be done in O(n*k*log(k)) using merge technique. I am looking for a better time efficient solution..Like for 2 arrays it can be done in O(log(n)) time..I am trying to use the same logic here but couldn't apply..


texts: Drawbacks of repeating a single pattern matching procedure for many patterns

texts:
One naive approach in solving multiple pattern matching problem is to call single pattern matching procedure on each of the pattern.

There must be some drawbacks in this approach, given the variety of multiple pattern matching algorithms such as Aho Cornsick algorithm, which prove to be more efficient.

So what are the drawbacks on this straightforward yet naive approach? In what scenario is this algorithm doing unnecessary works?