texts: Are there NP COMPLETE problems that are "easy" in practice?

texts:
NP COMPLETE problems are hard in the worst case (assuming $P \neq NP$). What that means is that for every polynomial $p$, sufficiently large integer $n$, and algorithm $A$, there is an instance $x$ of size $n$ for which the algorithm takes more than $p(n)$ time. But this is one instance for every (sufficiently large) $n$. In principle, this could be the only hard instance for that value of $n$, and all other instances for that $n$ could be easy. So how hard are NP COMPLETE problems in practice?

I'll refine that question to: Are there NP COMPLETE problems that are somehow easy in practice?

The definition of "easy" is left open. One definition may be given by average-case complexity, another one could be given "smooth complexity", another could be given by Fixed Parameter Tractability, efficient approximability, polynomial-time solvability with an advice oracle, efficiency in practice without a mathematical definition etc. I'm hoping that by leaving the definition of "easy" open, I can get a wider range of answers. Any definition of "easy" should imply that the problem is easy "in real life" or "in practice". Also, don't assume I know any of that stuff I just listed in any detail.


texts: Post Correspondence problem provable instance

texts:
Let the Post Correspondence problem with input

$$K = ((x_1, y_1), . . . ,(x_n, y_n)), x_i, y_i ∈ \Sigma^*$$

for $$ i = 1, . . . , n $$

Find a concrete solution for the input

$$K = ((001,0), (01, 011),(01, 101),(10, 001))$$

The Post Correspondence problem is undecidable so it's really hard to find a concrete solution. I've tried brute forcing it but it gets frustrating after a few tries.

Is there a logical way to deduce that K is a solution, rather than finding a pattern that works?


texts: Why is my run time calculation of selection sort different?

texts:
This is the pseudocode I used:

Their calculation seems to be different from mine. Can someone explain how they derived it? Here is mine in comparison:

Line 1: $c_1 \cdot (n-1)$
Line 2: $c_2 \cdot (n-1)$
Line 3: $c_3 \cdot n $
Lines 5-6: $c_4 \cdot \frac{n(n-1)}{2}$ (the if statement executes with an arithmetic progression)
Line 9: $c_5 \cdot n$

Altogether,
$$T(n) = c_1(n-1) + c_2(n-1) + c_3n + c_4 \frac{n(n-1)}{2} + c_5n,$$
which simplifies to
$$ T(n) = \frac{c_4}{2} n^2 + c_1n + c_2n + c_3n - \frac{c_4}{2} n + c_5n - c_1 - c_2. $$


texts: Nodes in a binary search tree that span a range

texts: I have a binary search tree of height $h$ with an integer in each leaf.  I also have a range $[\ell,u]$.  I want to find a set of nodes that span the range $[\ell,u]$, i.e., a set $S$ of nodes such that the leaves under $S$ form all (and only) those leaves containing integers in the range $[\ell,u]$.  How large does $S$ need to be, in the worst case, as a function of the height $h$?  How do I find such a set explicitly?


texts:
Suppose $x \in \mathbb{R}^d$ and $M \in \mathbb{R}^{d \times k}$.

Why $xx^TM$ requires $O(dk)$ operations?


texts: What does the intersection symbol (∩) mean when applied to two non-set elements?

texts:
I came across a piece of literature in which I saw the intersection symbol (∩) being used on two non-set elements in the definition of an equivalence relation; I have posted it below for reference. The elements in question are meant to represent different files on a computer. What could that intersection symbol mean in this context?

  Let $x_1$ and $x_2$ be two files and let v be a given computer virus. We then define the equivalence relation $R_v$ as follows:

  $x_{1}\!\mathit{R_{v}}\,x_{2} \;\; if \;\; x_{1} \cap x_{2} \in \left \{ x_{1},x_{2},v \right \}.$

  This is an equivalence relation and any equivalence class of a
  given element $x$ is defined by $C(x) = \left \{ y |y\in S \;\; and \;\; x \mathit{R_v} y \right \}$.
  The class $C(v)$ contains every file infected by $v$. Every class
  which is a singleton contains an uninfected file.

This text appears in the paper just before the excerpt above and may provide more context:

  Most of self-reproducing codes that exist at the present time
  are worms and thus a single copy of the malware is present
  in the system. But it is not the case as far as virus are considered
  (many copies exist in the system at the same time). In
  order for our model to be general, we will consider that all the
  different copies of a malicious codes are in fact a single one,
  e.g. the viral code. In the very special case of k-ary viruses,
  the viral code is the disjoint union of k different files.

  From a mathematical point of view, it is equivalent to consider
  the following equivalence relation, which is defined on
  a set S (the file system).

And even earlier, the text the author describes the $x_i$ variables as boolean variables:

  In order to define
  the working context, let is consider an operating system containing
  $n$ files ($n$ is of arbitrary size). These are all possible
  files that exist or may exist in the system at a given time.
  Each of these files are described by a Boolean variable $x_i$ ,
  $i = 1, 2, . . . , n$. No particular assumptions is made about the
  status of any of these files (executable or not, data. . .).

Source for the paper: https://link.springer.com/article/10.1007/s11416-007-0044-2


texts:
So I fully understand the how the RSA algorithm works, but now I am trying to reason with the formula. I want to know:

  why the public key e and the private key d in the RSA encryption have
  to satisfy the equation ed = 1 mod (p − 1)(q − 1)?

Is it because of the standard modular arithmetic rule where 1 mod anything is 1, or is there a more to this answer?


texts: Are statecharts with parallel states NFA, DFA, or none of the above?

texts:
I'm looking for formal statements and proofs that I can make when using SCXML statecharts. As such, I'm trying to categorize it properly.

SCXML supports hierarchical states. I believe that any hierarchical state machine can be converted into an equivalent non-hierarchical state machine. And I believe that a "simple" non-hierarchical state machine can be considered a DFA (deterministic finite automata).

SCXML is not a "simple" state machine, however:

Transitions between states may be guarded by arbitrary code conditions. Only one transition from an active state will be taken as a result of a single event, but which transition is taken may vary. Given this, I believe that SCXML should be considered (for certain configurations) an NFA (non-deterministic finite automata).
Certain transitions may be taken not in response to an event, but as soon as a condition is valid. Given this, I believe that SCXML may at times be considered an NFA with ε-moves.
SCXML supports not just hierarchical states, but also "parallel" (orthogonal) states. These allow the runtime to be in more than one atomic ("leaf") state simultaneously.

This last detail gives me pause, as I have not found any formal statements classifying parallel state machines. Does the introduction of concurrent parallel states break any NFA definition?

I think that it doesn't. I think that you can convert any parallel state machine into an equivalent non-parallel machine via combinatorial explosion. But I'd like to know it for sure.


texts: Context-free grammar for $a^ib^ic^id^{3i}$

texts:
I'm trying  to make a context-free grammar for $L=\{a^ib^ic^id^{3i}\mid i>0\}$.
I could make a grammar for $a^ib^jc^jd^{3i}$. But I can't make the grammar for the special case that $i=j$ as it is in $L$.


texts:
I am having trouble with some homework regarding proving that DCONN is NL-Complete. As part of the exercise, the fact that RCH is NL-Complete can be assumed.
Problem definitions:

RCH: Given a directed graph G and nodes x, y , is there a path from x to y?

DCONN: given a directed graph G, is it connected?

To my understanding we have have to prove two things:

$ DCONN \leq RCH$
$RCH \leq DCONN$

Reduction $\leq $ in this case is defined as:
$L$ is logspace-reducible to $L^{'}$ ($L \leq_{log} L{'})$ iff there is a LOGSPACE function f such that: $x \in L$ iff $f(x) \in L{'}$.
To be honest I have no idea where to even start. The following is my naive attempt to tackle the first issue.
For the first part I thought that running $n^2$ RCH questions to see if node $y$ is reachable from node $x$ for all $x,y \in G, x \neq y$ will be sufficient to prove that $G$ is connected or not. But I am not sure if that is sufficient to be considered a reduction.
When it comes to the second part I have no idea where to even start. Any help or pointers would be appreciated.


texts: Measuring entropy for a table (e.g., SQL results)

texts:
We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of the benchmark. However, the results often contain a lot of redundancy, so just counting results seems coarse.
Consider the following table containing results for a query like "for the US, give me its states and its car manufacturers":
================================
|| ?us_state | ?us_car_manu   ||
||============================||
|| Alabama   | Chrysler       ||
|| Alaska    | Chrysler       ||
|| ...         ...            ||
|| Wyoming   | Chrysler       ||
|| Alabama   | General Motors ||
|| Alaska    | General Motors ||
|| ...         ...            ||
|| Wyoming   | General Motors ||
|| Alabama   | Ford           ||
|| Alaska    | Ford           ||
|| ...         ...            ||
|| Wyoming   | Ford           ||
===============================

All 200 (50 × 4) results are of course unique. However, given that there is an inherent Cartesian product, the number of results flatters the amount of "information content" or "entropy" of the table: every additional car manufacturer adds fifty results for the fifty US states. (Again, this is just an example; I'm not interested in better ways to represent or run this particular query.)
As such, we're looking for a metric that will give an indication as to the (loosely speaking) redundancy-free content in the table for better comparison of content across different results for different queries. Other result tables may contain a mix of different types of Cartesian products (e.g., consider generalising the query to any country, where each country itself has its own product of states and car manufacturers, etc.).
Currently we're working off a simple metric which just counts unique term–position combinations: for the above example, the metric gives 50 + 4 = 54. This may be sufficient for comparison, but is not sensitive to the combination of terms for individual results.
Thanks to Wikipedia, I'm aware of—but not familiar with—the notion of entropy in information theory. However, I'm unclear on how the concept of entropy could be applied to this use-case. (I'm not interested in the entropy of the result strings; each term can be considered a "symbol".) Roughly speaking, each query variable could be considered as a free variable with the result terms in that column providing a set of possible outcomes and their frequency of occurrence being used as a probability mass function. This way I could compute the Shannon entropy for each column. But thereafter, I don't know how columns can be combined, or how tuples or results can be considered ... if a notion of conditional entropy would be better, etc.
And so ...

Does anyone have pointers to related material on the measure of entropy/redundancy/etc. in tables or similar structures?
Otherwise, does anyone have any ideas on how to use Shannon entropy in a convincing way for tabular data?


texts: Algorithm for splitting array into subarrays with sums close to the target value

texts:
I have an array of positive integers, $A = (a_1, a_2, ..., a_n)$.
Let $s(A)$ denote the sum of elements of array $A$.
I also have an integer $t$, such that $1 < t \le s(A)$.

I want to split the array $A$ into $m$ contiguous subarrays $(A_1, ..., A_m)$, for which I'll get a minimum of function $f$, defined as

$$
f(A_1, ..., A_m) = \sum_{1 \le i \le m}{(s(A_i) - t)^2}.
$$

Please note that I'm talking specifically about arrays, so the order of elements does matter.

Here is a simple example.

Let $t = 13$ and
$$
A = (1, 6, 7, 10, 3, 2, 10).
$$
With the following subarrays
$$
A_1 = (1, 6, 7)\\
A_2 = (10, 3) \\
A_3 = (2, 10) \\
$$
the value of $f(A_1, A_2, A_3) = (14-13)^2 + (13 - 13)^2 + (12 - 13)^2 = 2$.

I don't need an exact solution. Good heuristic would be sufficient.


texts: Data structure to use for a consumable message queue where it's safe for messages to overwrite one another

texts:
I have a queue of messages representing filesystem operations that need to be processed in order. A message may succeed or fail when it's sent. A change message, for example, is generated when a user creates or saves a file.

Delete Foo.txt message sent
Delete Bar.txt message sent
Change Baz.txt message sent
Change Foo.txt message sent

In the most common case, I pop the top item from the queue and send it off for processing, which succeeds.

But suppose this happens:

Delete Foo.txt message attempted (FAIL)
Delete Bar.txt message attempted (OK)
Change Baz.txt message attempted (OK)
Change Foo.txt message attempted (OK)

What should I do in this case?

I want to move on and process the next item in the queue, but it's not that simple. In this case, "Delete Foo.txt" must be processed before "Create Foo.txt", otherwise we're deleting Foo.txt from the search index (see "more details" below), even though it exists.

One approach I had considered: a key-value store, where the document path is the key, and the Message is the value. In the context of a filesystem, the only operation that matters is the most recent, so overwriting the Message associated with a file if it hasn't been sent might work.

What kind of data structure and algorithm is right for this situation? I don't want to reinvent the wheel.

A few more details:

New items are constantly arrive in the queue, from multiple producer threads
The messages are consumed from the collection by a single consumer
A message is a serialized object, sent to a RabbitMQ broker
This queue exists in case the RabbitMQ broker goes down or a Publisher Confirm fails
Messages are consumed from the endpoint by a different service which performs various actions to keep a search index incrementally up to date
C#, if it matters

Update 1:

Big picture

I am sending messages about filesystem operations that have occurred. These messages are used to keep a search index (elasticsearch) up to date. A few minutes behind is perfectly acceptable. If a user makes three saves in rapid succession, I don't need search index updates for the first two saves. (If it happens, that's fine, but it's not required.)

CRUD operations are done by users working with their files on a busy network share. Each write operation triggers a message that has to be sent to a persistent work queue (the RabbitMQ broker). An example message might contain data that boils down to "File F has been deleted" or "File Y has been changed". (No file contents are contained therein.)

(These messages are consumed by another component downstream that performs an action based on the contents of the message, which is outside the scope of this question.)

Because messages represent filesystem actions that were performed in a sequence by users they either:

Have to be sent in order so they can be processed in order OR
The message associated with the most recent write operation on File F should overwrite any queued message associated with File F that hasn't been sent yet

In my example above (second unordered list), it's safe for the message representing "Change Foo.txt" to overwrite a failed "Delete Foo.txt", because the Change message was triggered after the Delete message. (The time where Foo.txt didn't exist isn't important.) Hence my thought of a using key-value store of  as a holding area in case of a Message send failure.


texts: Decidability of dependent typing on primitive recursive languages

texts: With a dependent type system in a normal functional language type checking may never halt. This is partially because dependent typing removes the isolation between types, and code. My question is this: would an implementation of dependent typing for a primitive recursive language(not Turing-complete) be guaranteed to halt? Thanks!


texts: Asymptotic complexity of Combination sum problem vs Coin change problem

texts:
I've been looking at the following combination sum problem:

Given a set of candidate numbers (candidates) (without duplicates) and a target number
(target), find all unique combinations in candidates where the candidate numbers sums to
target.

The same repeated number may be chosen from candidates unlimited number of times.

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Most of the solutions I encountered for this problem were some variant of the following backtracking solution:-

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int
remain, int start){
    if(remain < 0) return;
    else if(remain == 0) list.add(new ArrayList<>(tempList));
    else{
        for(int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}

Most of the comments of these solutions implied an asymptotic complexity of O(2^N) due to this code potentially building up all subsets in the worst case.

However, this problem statement seems very similar (if not identical) to the Coin change problem

You are given coins of different denominations and a total amount of money. Write a function
to compute the number of combinations that make up that amount. You may assume that you have
infinite number of each kind of coin.

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

The most common solution I've found to this problem is the following O(N*amount) dynamic programming solution:

class Solution {
  public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;

    for (int coin : coins) {
      for (int x = coin; x < amount + 1; ++x) {
        dp[x] += dp[x - coin];
      }
    }
    return dp[amount];
  }
}

It seems to me that the first solution is just the top down variant of this algorithm.

I can't seem to figure out why the first solution is exponential and the second one is not.
Where have I gone wrong in my understanding?

Is it actually printing the subsets vs counting that makes the difference here?

Is there any way print all combinations whilst preserving polynomial time?


texts:
$L = \{ \langle M \rangle \mid L(M) = \Sigma^∗ \}$

Is above problem R.E ?

I found an explanation in one of the websites and I have doubt in few lines of paragraph.

The explanation was

Now, given a halting problem $(\langle H \rangle, w)$, we proceed as follows: We make a new TM say $A$, which on input $x$, just simulates $H$ on $w$ for $|x|$ steps. If $H$ halts on $w$, $A$ goes to reject state. Otherwise it accepts. So, $L(A)=\Sigma^*$ if $H$ does not halt on $w$ and $L(A) =$ a finite set if $H$ halts on $w$. So we can reduce non halting problem to this problem. Hence given language is non R.E

Can someone please explain me how is $L(A) = \Sigma^∗$ if $H$ does not halt on $w$ ? It says if $A$ doesn't halt within $|x|$ steps then $L(A)$ is infinite. How can we say that ? What it TM $A$ halts on $|x+1|$ th  step? Even then it will be finite but this explanation considers it as infinite.

I understand how is it finite set if $H$ halts on w but I am not able to understand the non halting part.


texts: Is there a problem which can be solved in $O(f_k(n))$ time for any $k$ where $\lim_{k \to \infty} f_k(n) = 0$ but no constant time solution is known?

texts:
So Fibonacci heaps can perform insertions in amortized constant time, and I came up with a sequence of heap data structures $H_k$ such that insertions can be performed in amortized $O((\log n)^{1/k})$ time where $n$ is the size of the heap. If we didn't know insertions could be performed in constant time, then my result would suggest it, since we can get arbitrarily close to constant running time asymptotics with my solution.

This led to me to wonder, is there an example of a family of algorithms or data structure operations, that are all functionally equivalent, and can be performed in $O(f_k(n))$ time, where $f_k$ is a sequence of functions such that $\lim_{k \to \infty} f_k(n) = 0$ for all $n$, but no constant time alogorithm/data structure operation can be found? Or at least where no constant time solution is currently known? I suspect the answer is yes but probably hard to prove. It would be very surprising if the existence of such family of algorithms with $O(f_k(n))$ running time would imply a constant time algorithm exists.


texts:
Given: $n$ tasks with accomplishment times $t_1, t_2, \ldots , t_n$. There is no such task that its accomplishment time is greater than the overall accomplishment time of other tasks.

Question: How to distribute these tasks between two workers in a such way that $|T_1 - T_2|$ is minimum ($T_i$ - the overall accompl. time for the $i$-th worker accordingly).

We will use the local search algorithm, starting with a random distribution and redistributing one task on every step only if it leads to reducing $|T_1 - T_2|$ as long as it's possible.

Does this algorithm find the optimal distribution or is there any counterexample?


texts: Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$

texts:
I need to construct a CFG for the following language$$L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$$
I know that the two middle position should always be the same. E.g. $11,00,0\underline{11}0,0\underline{00}0,\dots$ Each position on the opposite sides of the middle points should also be the same.
So these are the production rules of the CFG I came up with
$$
S\rightarrow00$$
$$S\rightarrow11$$
$$S\rightarrow ASA$$
$$A\rightarrow1$$
$$A\rightarrow0$$
$$A\rightarrow \epsilon$$
Is this solution correct?


texts: Recursive functions from O(n) complexity to O(log n)

texts:
For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each time?

For example, take this recursive reverse_string function ...

    def reverse_string1(s):
        if len(s) < 2:
             return s
        return reverse_string1(s[1:]) + s[0]

... compared to this function that does the same string reversal:

   def reverse_string2(s):
       if len(s)<2:
             return s
       mdpt = len(s)/2
       r1 = reverse_string2(s[:mdpt])
       r2 = reverse_string2(s[mdpt:])
       return r2 + r1

Does the latter function successfully reduce the runtime complexity from linear to logarithmic?


texts:
I've read this part like 3-4 times and I'm not understanding what is going on.

Let G6 be the following CFG and convert it to Chomsky normal form by using the conversion procedure just given. The series of grammars presented illustrates the steps in the conversion. Rules show in bold have just been added. Rules shown in gray have just been removed.

Specific steps/instructions from the book

1.The original CFG G6 is shown on the left. The result of applying the first step to make a new start variable appears on the right.

S→ASA|aB         S0→S
A→B|S             S→ASA|aB
B→b|ε             A→B|S
                  B→b|ε

2.  Remove ε rules B→ε, shown on the left, and A→ε, shown on the right.

S0→S              S0→S
 S→ASA|aB|**a**        S→ASA|aB|a|**SA|AS|S** from?
 A→B|S|**ε**           A→B|S|ε
 B→b|**ε**             B→b

3a. Remove unit rules S→S, shown on the left, and S0→S, shown on the right.

S0→S                  S0→S|**ASA|aB|a|SA|AS**
 S→ASA|aB|a|SA|AS|S    S→ASA|aB|a|SA|AS
 A→B|S                 A→B|S
 B→b                   B→b

3b. Remove unit rules A→B and A→S

S0→ASA|aB|a|SA|AS     S0→ASA|aB|a|SA|AS
 S→ASA|aB|a|SA|AS      S→ASA|aB|a|SA|AS
 A→B|S|**b**           A→S|b|**ASA|aB|a|SA|AS**
 B→b                   B→b

4. Convert the remaining rules into the proper form by adding additional variables and rules. The final grammar in Chomsky normal form is equivalent to G6, which follows. (Actually the procedure given in Theorem 2.9 produces several variables Ui, along with several rules Ui→a. We simplified the resulting grammar by using a single variable U and U→a.)

S0→AA1|UB|a|SA|AS
 S→AA1|UB|a|SA|AS
 A→b|AA1|UB|a|SA|AS
A1→SA
 U→a
 B→b

I don't understand why they added the "bold" (** **) items. I also don't understand 4. Can someone please explain this to me. Thank you!


texts: Does Rice's theorem apply to sequential logic circuits?

texts:
I am wondering if Rice's theorem (or something similar to that) applies also to sequential circuits. I.e. given any finite sequential circuit, can there be an algorithm that can formally verify any property of this circuit? I'm thinking yes, because the number of latches is bounded, so is the number of states. Even if the input is unbounded, at some point you have to arrive at a state that you've already seen before.
What are the limits of model-checking sequential circuits?


texts: Fastest Algorithm to find shortest path between two edges in a graph

texts:
If I just want to find shortest between a single source and destination, can I do better Dijkstra (which finds from one source to all destinations)?

I am trying to answer a question in the EPI book.  The question is as follows:  Suppose you are given a N*N matrix in which some of the cells are greyed out and two non-grayed out cells(source and destination), find the shortest path between the two.  Greyed out cell means -> A path cannot traverse through that cell.

The book recommends DFS or BFS but this takes O(V + E) which in this case is O(N^2) since both number of Edges and vertices are O(N^2).  Same as Dijkstra.  Wondering is we can do better.


texts: Generalization of Horn clauses in logic programming?

texts:
As far as I understand, Prolog and related languages are restricted to inference rules of the form
$$ p_1 \land \dots \land p_n \rightarrow q$$
which is equivalent to the Horn clause
$$ \neg p_1 \lor \dots \lor \neg p_n \lor q$$
I'm wondering if there are languages that relax this constraint to allow arbitrary disjuctions as clauses in the knowledgebase, and if so what the downsides of this would be. For example, the rule
$$ p \rightarrow q_1 \lor q_2 \equiv \neg p \lor q_1 \lor q_2$$
is not a Horn clause and is not allowed in Prolog, but it seems to me that it would be possible to run a resolution algorithm for such clauses as well. For example, if $p = \top$, then we can prove $q_1 \lor q_2$ by contradiction: we assume the converse $\neg(q_1 \lor q_2) = \neg q_1 \land \neg q_2$ and resolve
$$ (\neg p \lor q_1 \lor q_2) \land (\neg q_1 \land \neg q_2) = \neg p$$
which then yields a contradiction $p \land \neg p$.

Why should such arbitraty disjuctions not be permitted? Is it somehow related to the satisfiability problem (HORNSAT) ?  Or is it due to the closed world assumption (where the statement $q_1 \lor q_2 = \top$ is paradoxical) ?

p.s. I am a hobbyist in logic programming, so simple informal explanations are appreciated :)


texts: Can we construct a Karp reduction from a Cook reduction between NP problems?

texts:
We have had several questions about the relation of Cook and Karp reductions. It's clear that Cook reductions (polynomial-time Turing reductions) do not define the same notion of NP-completeness as Karp reductions (polynomial-time many-one reductions), which are usually used. In particular, Cook reductions can not separate NP from co-NP even if P $\neq$ NP. So we should not use Cook reductions in typical reduction proofs.

Now, students found a peer-reviewed work [1] that uses a Cook-reduction for showing that a problem is NP-hard. I did not give them full score for the reduction they took from there, but I wonder.

Since Cook reductions do define a similar notion of hardness as Karp reductions, I feel they should be able to separate P from NPC resp. co-NPC, assuming P $\neq$ NP. In particular, (something like) the following should be true:

$\qquad\displaystyle L_1 \in \mathrm{NP}, L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1 \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$.

The important nugget is that $L_1 \in \mathrm{NP}$ so above noted insensitivity is circumvented. We now "know" -- by definition of NPC -- that $L_2 \leq_{\mathrm{Karp}} L_1$.

As has been noted by Vor, it's not that easy (notation adapted):

  Suppose that $L_1 \in \mathrm{NPC}_{\mathrm{Cook}}$, then by definition, for all languages $L_2 \in \mathrm{NPC}_{\mathrm{Karp}} \subseteq \mathrm{NP}$ we have $L_2 \leq_{\mathrm{Cook}} L_1$; and if the above implication is true then $L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$ and thus $\mathrm{NPC}_{\mathrm{Karp}} = \mathrm{NPC}_{\mathrm{Cook}}$ which is still an open question.

There may be other differences between the two NPCs but co-NP.

Failing that, are there any known (non-trivial) criteria for when having a Cook-reduction implies Karp-NP-hardness, i.e. do we know predicates $P$ with

$\qquad\displaystyle L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1, P(L_1,L_2) \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$?

On the Complexity of Multiple Sequence Alignment by L. Wang and T. Jiang (1994)


texts: PDA to accept language with more a's than b's and c's

texts: My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of the b's and higher than the amount of c's, so for example the word "abcacba" would be accepted.


texts: Reference request: Practical string algorithms

texts:
I think I have quite a good understanding of string algorithms. However, a couple of days ago, I came across this post: Find all pairs of strings in a set with Levenshtein distance < d

I was wondering, whether there are more string algorithms which do not have good worst-case guarantees but are good in practice. I guess these are not taught at some university string algorithms courses, as the professors want to teach algorithms with good theoretical running times


texts: Class of the language only containing the empty string?

texts:
$L = \left \{ \epsilon  \right \}$
Clearly this language is finite so this must be a regular language.
Now since every regular language is Context Sensitive, $L$ is a CSL.
We can define the grammar for $L$ as :
$S\rightarrow \epsilon$
Now since $L$ is a CSL, this grammar must be a Context Sensitive Grammar.
But from the definition of a Context Sensitive Grammar:

  A Context sensitive grammar is any grammar in which the left side of
  each production is not longer than the right side.

But here
$\left | S \right | > \left | \epsilon  \right |$
This is contradictory.
I am unable to figure out what's wrong here.


texts: How to detect intersecting segments based on length of the segments

texts:
As part of a larger problem, I am trying to detect based on the distance matrix which segments intersect in the original 2D space that originated the matrix. I don´t have coordinates (lat/long, x/y or any other for the points).

As an example, on the image below, the answer to the question for the top graph would be: AD, BC. While for the bottom graph would be AC, BD.

The information that we have is just the distance matrix:

DISTANCE MATRIX TOP

$
\begin{align}
 && A && B && C && D \\
A&& 0 && 1 && 1 && \sqrt{2} \\
B&& 1 && 0 && \sqrt{2} && 1 \\
C&& 1 && \sqrt{2} && 0 && 1 \\
D&& \sqrt{2} && 1 && 1 && 0
\end{align}
$

DISTANCE MATRIX BOTTOM

$
\begin{align}
 && A && B && C && D \\
A&& 0 && 1 && 1 && \sqrt{2} \\
B&& 1 && 0 && \sqrt{2} && \sqrt{5} \\
C&& 1 && \sqrt{2} && 0 && 1 \\
D&& \sqrt{2} && \sqrt{5} && 1 && 0
\end{align}
$

I have tried so far to use the triangular inequality and some other (probably) naive geometric knowledge but I can´t figure out what conditions must be met.


texts: A question about an input in a Halting Problem proof

texts:
Here is my Halting Problem proof, that largely mirrors other (non-diagonalizing) proofs that I've seen.

$H(p,i)$ returns $1$ if program $p$ halts on input $i$.
$H(p,i)$ returns $0$ if program $p$ does not halt on input $i$.
Let $f(t,t)$ be an interface for any program that returns a $0$ or a $1$.
$g(x)$ is $0$ if $f(x,x)$ is $0$, infinite loop if $f(x,x)$ is $1$
Now use $H$ in place of $f$:

4b. (modified)  $g(x)$ is $0$ if $H(x,x)$ is $0$, infinite loop if $H(x,x)$ is $1$

Run $g(g(i))$ which runs $H(g(i),g(i))$
        If $H(i,i)=0$, then $g(i) = 0$
        If $H(i,i)=1$, then $g(i)$ is undefined
If $g$ halts, then $H(g(i),g(i))$ must return $1$ (line 1).

But then $g$ won't halt. (line 4b)
If $g$ doesn’t halt, then $H(g,g)$ must return $0$ (line 2).

But if $H(g(i),g(i))$ is $0$, then $g$ halts. (line 4b)

My issue is with $g(g(i))$.  I understand that the idea of the proof is to  feed the machine into itself, but what, exactly, is the contents of the $i$?


texts: What does every root is at the same level mean

texts:
My textbook says a "complete binary tree" is a "full binary tree" where every root is at the same level.

My conceptual understanding:

All this time, I was led by my textbook to believe a root is the "top-most vertex" in which all the other vertex are led away from it. So basically I am led to believe there can be only one root in a tree.

Questions:

What does "where every root is at the same level" even mean?

Isn't a root suppose to be at level 0 all the time?


texts: Difficulty understanding the use of arbitrary function for the worst case running time of an algorithm

texts:
In CLRS the author said
"Technically, it is an abuse to say that the running time of insertion sort is $O(n^2)$,
since for a given $n$, the actual running time varies, depending on the particular
input of size $n$. When we say “the running time is $O(n^2)$,” we mean that there is a
function $f(n)$ that is $O(n^2)$ such that for any value of $n$, no matter what particular
input of size $n$ is chosen, the running time on that input is bounded from above by
the value $f(n)$. Equivalently, we mean that the worst-case running time is $O(n^2)$.
"
What I have difficulties understanding is why did the author talked about an arbitrary function $f(n)$ instead of directly $n^2$.
I mean why didn't the author wrote
"When we say “the running time is $O(n^2)$,” we mean that for any value of $n$, no matter what particular input of size $n$ is chosen, the running time on that input is bounded from above by
the value $cn^2$ for some +ve $c$ and sufficiently large n. Equivalently, we mean that the worst-case running time is $O(n^2)$".
I have very limited understanding of this subject so please forgive me if my question is too basic.


texts: FInding the combination with the least number of elements from and array of integers, given an integer sum

texts:
I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm which doesn't find the optimal solution, however I'm having problems finding the optimal solution using dynamic programming.

The gready algorithm I've written is:

Function min_comb(array, value)
    min = 0
    for i in 1:length(array)
        if array[i] <= value
            min += floor(value / array[i])
            value = value % array[i]
        end
    end
    return min
end

which works fine for Example 1 below, but of course not for Example 2.

Example 1: If given an array $A=[1000,500,100,20,5,1]$ and a sum $S=1226$, the least number of combinations would be $N=6$ ($1000+100+100+20+5+1$).

Example 2: If given an array $A=[4,3,1]$ and a sum $S=6$, the least number of combinations would be $N=2$ ($3+3$).

How should I go about solving this problem?


texts: Simple Uniform Hashing Assumption and worst-case complexity for hash tables

texts:
Is the Simple Uniform Hashing Assumption (SUHA) sufficient to show that the worst-case time complexity of hash table lookups is O(1)?

It says in the Wikipedia article that this assumption implies that the average length of a chain is $\alpha = n / m$, but...

...this is true even without this assumption, right? If the distribution is [4, 0, 0, 0] the average length is still 1.
...this is a probabilistic statement, which is of little use when discussing worst case complexity, right?

It seems to me like a different assumption would be needed. Something like:

  The difference between the largest and smallest bucket is bounded by a constant factor.

Maybe this is this implied by SUHA? If so, I don't see how.


texts: How to the examples for using the master theorem in Cormen work?

texts:
I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples

$3T( \frac{n}{4} ) + n\log(n)$
$2T( \frac{n}{2} ) + n\log(n)$

For the first example we have $a=3$ and $b=4$  so $n^{\log_4
(3)}=n^{0.793}$ and Cormen says that if we choose $\epsilon = 0.207$ then $f(n) = n\log(n) = \Omega(n^{\log_4(3)  + \epsilon})$

How? As I understand it if $\epsilon = 0.207$ then $\Omega(n^{\log_4(3)  + \epsilon})= \Omega(n)$ so we have $n\log(n) = \Omega(n)$  but it's not true; But he proves that $n\log(n) = \Omega( n^{\log_4(3)  + \epsilon} )$

And then he proves that for the second case $n\log(n)$ does not apply to masters method 3-rd case the same way as I prove above.

So could somebody explain me in detail how  the third case of the master's theorem applies to  $3T( \frac{n}{4} ) + n \log(n)$  but not to $2T( \frac{n}{2} ) + n\log(n)$.


texts: why do CPU architectures use a flags register (advantages?)

texts: Some CPUs have a flags register (ARM,x86,...), others don't (MIPS,...). What's the advantage of having a CMP instruction to update the flags register followed by a branch instruction instead of using a zero register and conditional branches to check for sign, overflow etc?


texts: can virtual address map any on virtual memory on disk?

texts:
I was reading a textbook which says that:

If the valid bit is set, the address field indicates the start of the corresponding physical page in DRAM where the virtual page is cached. If the valid bit is not set, then a null address indicates that the virtual page has not yet been allocated. Otherwise, the address points to the start of the virtual page on disk.

My question is, does each page tabe entry(PTE) need to be match the same offset one in disk? for example, PTE 1 has VP 1 in physical memory, but can PTE 1 originally mapped to VP 3? or PTE 1 has to map VP 1,  PTE 2 has to map VP 2,  PTE 3 has to map VP 3 and so on?
if PTE x has to map VP x, then why when valid bit is not set then the address points to the start of the virtual page on disk? can't we use the offset x in PTE x to infer that it maps to VP x?


texts: How to find the pumping length of a context-free language?

texts:
Please help me understand, and if possible, tips, to determine a pumping length $p$.

Suppose I have the example :

Let $G$ be a Context-Free-Grammar with a set of variables $\{S,A,B,C\}$, set of terminals $\{0,1\}$, start variable $S$, and rules

$S \to ABA \mid SS$
$A \to S0 \mid 1C1$
$B \to S1 \mid  0$
$C \to 0$

Now given the above, how do I find the pumping length $p$?
Please explain how you actually got it from the grammar.


texts:
While exploring about the 2-core system. The voltage decreases linearly with the frequency. The voltage may not decrease below 75% below the original voltage.This voltage is referred to as the voltage floow and any voltage lower than that will lose the state. What % of parallelization gives you a voltage at the voltage floor?
I solved the question as  :-
Vnew=0.75Vold that leads to fnew=0.75fold ; Since f is inversely proportional to the Texe, so we can say -
Told=0.75Tnew. So speed up S= Told/Tnew which leads to 0.75 . Now applying Amdahl's law to find the parallelization by using the formula S=1/((1-F)+F/S). Here I have considered S as 2 as 2 core system,but I am getting the parallelization as negative. Could you please help here?


texts: Find minimal spanning tree of graph with edge values from 1 to 5 integers

texts: How can I find the minimal spanning tree of graph with edge values from 1 to 5 integers (no need to be unique) most effectively? I know I can use Kruskal algorithm, but how can I modify the algorithm to find it faster when I know there are edges with values only 1, 2, 3, 4 or 5? I cant figure it out how it could be faster when I know this limitation on edges.


texts:
According to the concepts of Pipelining,

In a single cycle different stages of different instructions are
executed.

Now I have a bit of confusion here, that if a single processing element is there and can perform one processing at a time ,
then -
Do the preemption occurs multiple times in a single cycle in order to complete the different stages of different instructions inside the pipeline ?
If so, then does this mean that clock cycle duration is larger than the time quanta assigned to execute each stage of an instruction ?
For Example -
In Cycle 2 - below given stages of different instructions is to be executed -

IF of instruction5, ID of instruction4, EX of instruction3, MEM of
instruction2,
WB of instruction1

OR the pipelining works only when there are multiple processing elements ? If I am missing something ?
Please explain or provide some helpful links for me to clear my doubts.
Thanks in Advance !


texts: Understanding Hamiltonian Path, NP vs Co-NP

texts:
I am having difficulty understanding the distinction between NP and Co-NP.

According to my textbook (Sipser), the HAMPATH problem is in NP. That is, for the language: HAMPATH = { (G,s,t) | G is a directed graph with a Hamiltonian path from s to t}, there exists a nondeterministic Turing Machine M that can decide this problem in polynomial time. I understood this to mean that for some input (G,s,t), M accepts if G has a Hamiltonian Path from s to t, and M rejects if G does not have a Hamiltonian Path from s to t, both in polynomial time.

However, the book also says that !HAMPATH =  { (G,s,t) | G is a directed graph with no Hamiltonian path from s to t} is in Co-NP, so it is not known to be in NP.

Why couldn't the same NTM for HAMPATH be used to decide !HAMPATH, except that it returns the opposite state?


texts: Algorithms that solve a practical problem but have not been proven correct

texts: Are there any known famous and usable algorithms that seem to solve some famous problem but which haven't been proven to be correct?


texts: Is there a method to compress all data without loss (lossless compression)?

texts: I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I continue? Why is it impossible to compress all the data without loss?


texts: With respect to differential privacy what should be the qlobal sensitivity for regression in non interactive mode?

texts: I need to make a dataset differentially private on which regression, which in more general sense could be extended to learning any model, is to be performed. I need to calculate the global sensitivity for adding noise. How do I calculate global sensitivity in such cases.


texts: Decision problem such that any algorithm admits an exponentially faster algorithm

texts:
In Hromkovič's Algorithmics for Hard Problems (2nd edition) there is this theorem (2.3.3.3, page 117):

  There is a (decidable) decision problem $P$ such that for every algorithm $A$ that solves $P$ there is another algorithm $A'$ that also solves $P$ and additionally fulfills
  $\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n)$

$\mathrm{Time}_A(n)$ is the worst-case runtime of $A$ on inputs of size $n$ and $\forall^\infty$ means "for all but finitely many".

A proof is not given and we have no idea how to go about this; it is quite counter-intuitive, actually. How can the theorem be proven?


texts: How can we describe the similarity between trees?

texts:
For example, I have a program generates two ASTs, and I want to compare the two trees.

I've tried to treat the trees as graphs, but I think it doesn't show the particularity of trees.


texts: Is it allowed to do a binary search with an oracle when proving NP-completeness?

texts:
In https://cs.stackexchange.com/a/45524/28999, they do a binary search using an oracle for an NP-Complete problem. They show that the original problem can be reduced to that NP-Complete problem, implying that the original problem is in NP.

Why is that allowed? Why are you allowed to continue after the oracle returns false? Doesn't this defeat the whole idea of NPC versus co-NPC? You could then simply use an oracle for a NP-complete problem to show that NPC = co-NPC?

I would think that the whole reduction is wrong and that the original problem is probably not in NP. Or aren't they implying that?


texts:
Say you have a (context-free) grammar, and you wish to mathematically model the magnitude of the ambiguity possible under this grammar, across the space of all possible** input strings.

Practically, one can feed in a large number of inputs strings to a parser of the grammar, and get a distribution over that set of inputs. This may be useful if one assumes the set of inputs to somehow represent a more general case, but for the sake of exercise, let us arbitrarily assume, that this approach does not generalize, or that we cannot a-priori come up with a sufficiently representative set of strings.

Can you suggest a mathematical model for the magnitude of ambiguity allowed by a given grammar? differently phrased, how would you creatively model the combinatorial magnitude of possible parses?

** this is of course ill-defined, but it takes some creativity to come up with a definition for "reasonable" input strings, or think of a measure for the length or complexity of a string, that can serve as a useful parameter in the model.


texts: Is it possible to use a space-filling curve to index a 2D grid which is not $2^x$ by $2^y$?

texts: I am working on a project which needs to traverse a 2d spatial grid, and would like to use a space-filling curve indexing scheme.  Unfortunately, I have no guarantee that the input grid will be a power of two along either dimension.  In fact, it may be just barely over a power of two in some cases.  Virtually extending the grid to be a power of two in size may use too much memory (it is a very large grid).  Is it still possible to use a space-filling curve, such as a Morton curve, to index this grid?


texts:
Consider this example (taken from this document: Showing that language is not regular):

$$L = \{1^n \mid n\text{ is even}\} $$

According to the Pumping Lemma, a language $L$ is regular if :

$y \ne ε$
$|xy| \lt n$
$\forall k \in N, xy^kz \in L$

In the above example, $n$ must be even. Suppose we have $n = 4$, we can express: $$xy^kz$$ such that: $x = 1$, $z = 1$, and with $k = 2$, we have $y^k = y^2 = 11$, so we get the string $1111$. However, since all $k$ must be satisfied, if $k = 1$, the string is $111$, it does not belong to $L$. Yet, I was told that the above example is a regular language. How can it be?


texts: Two Turing machines $M_1$ and $M_2$ with $L(M_1) \subseteq L(M_2)$

texts:
Suppose $M_1$ and $M_2$ are two Turing machines such that $L(M_1)\subseteq L(M_2)$. Which of the following is true?

(A) On every input on which $M_1$ does not halt, M2 does not halt
(B) On every input on which $M_1$ halts, $M_2$ halts too
(C) On every input which $M_1$ accepts, $M_2$ halts.
(D)On every input which $M_2$ accepts, $M_1$ halts.

I am confused between B and C. This was an online practice test question.

For (B) my claim is that when $M_1$ is able to decide the language (i.e., $M_1$ halts on every input), then, since it is given $L(M_1) \subseteq L(M_2)$, $M_2$ should also halt and be able to decide on every input.

However, option (C) also looks convincing. If for every input $M_1$ says "yes" in the language, then $M_2$ should also be able to decide for that input.

Please let me know how to approach this correctly.

EDIT:
After reading the discussion, am I correctly interpreting the problem If I imagine the figure below

SO, (B) must be the wrong choice according to this right?


texts:
So I am trying to find the recurrence for this problem but I feel like it is missing something.

An ice cream shop is looking to minimize their operation costs, under the given constraints:
They are faced with costs of purchasing ice cream from a local distributor, where each order has a (potentially large) fixed delivery cost $shipping_cost$ as well as the price $price$ for each pint
To minimize delivery costs, they can buy more ice cream than needed for a given day, and keep it stored in their freezer overnight.
Their freezer can store $max capacity$ pints of ice cream at any time (includes both the shipment as well as any pints stored overnight)
However, storing extra ice cream overnight is not free, and it costs them $overnight cost$ dollars per pint (per night) to keep any additional ice cream frozen if they buy in advance.
Given a list of $daily demand$ (in pints) of ice cream for the next $num_days$ days, what is the minimum cost for the shop to be stocked up ready to meet their demands each day?
Inputs:

An integer $num\_days$, for the number of days
A list of $n$ integers demands, separated by a space, for the pints of ice cream demanded each day
An integer $max\_capacity$, for the capacity of their freezer
An integer $shipping\_cost$ , for the fixed cost of each shipment taken
An integer $price$, for the price they pay for each pint of ice cream
An integer $overnight\_cost$, the cost of storing a pint of ice cream for a day
.
$minCost[n]$ = the minimize cost on the nth day.
$iceCream[n]$ = the pints of ice cream demanded on the nth day

So this is what I thought of:
The whole price of ice cream should be the sum of pints * price, it will never change.
On day 1, the shop must pay shipping fee. minCost[0] = shipping_cost.
If the remaining ice cream cannot satisfy the demand on that day, the shop has to ship more, cost = shipping_cost + overnight_cost, so they should avoid this situation. Therefore, we only compare shipping_cost with overnight_cost.
$minCost[n] = min { shipping\_cost + minCost[n-1], overnight\_cost * iceCream[n] + minCost[n-1] }$
However, when max_capacity is not big enough, the remaining ice cream cannot satisfy the demand on next day, they have to ship.
if( ( max_capacity - iceCream[n-1] ) < iceCream[n] )
    minCost[n] = shipping_cost + minCost[n-1]

What is this missing?


texts: How to minimize diffusion in undirected weighted graph

texts:
I've got a work that has to do with networks, where each edge has a weight ($w\in(0,1)$) and some random set of nodes are 'infected'. I don't know which nodes are (or how many). The diffusion spread is according to linear threshold model (with some random threshold $\theta\in(0.3,0.5)$. I'm allowed to delete only $10\%$ of edges from the original graph, before the parameters are set (I don't know the initial infected nodes, nor the threshold a-priori).

I've tried multiple methods like:

removing highest weighted edges first - that results good performance when only small amount of initial infected nodes is given.
removing local-bridges - I've sorted the edges by neighbourhood overlap, and then removed by weight. - This works good for low thresholds.
Multiple variations of vertex cover, edge cover, centrality, betweenness etc - all underperformed the "naive" remove by weight approach (presented in (1)).
Clustering heuristics - tried to construct clusters and remove cutting edges (by weight, etc).

I find it hard to "accept" that approach (1) which seem to be very naive - outperforms all other.

Also, went over several papers and implemented some of the suggested ideas - none outperformed that naive approach.

I will appreciate if anyone with similar experience has anything to suggest.


texts: How exactly do you calculate the hidden layer gradients in the backpropagation algorithm?

texts:
I have been going through the description of the backpropagation algorithm found here. and I am having a bit of trouble getting my head around some of the linear algebra.

Say I have a final output layer $L$ consisting of two visible units, and layer $L-1$ consists of four hidden units. (this is just an example to illustrate my problem)

my understanding is that the weight matrix for this final layer ($w^L$) should be a 4 x 2 matrix.

the reference says to calculate the output error $\delta^{x,L}$ given by:

$\delta^{x,L} = \nabla_a C_x \odot \sigma'(z^{x,L})$

where:

$z^{x,L} = w^La^{x,L-1} + b^L$,

$a^{x,L} = \sigma(z^{x,L})$, and

$\odot$ is the hadamard product.

evaluating $\delta^{x,L}$ gives a 1 x 2 vector, as it should given there are two output units.

my problem is when calculating the hidden layer gradients (eg. $L-1$) given by:

$\delta^{x,L-1} = ((w^L)^T\delta^{x,L})\odot\sigma'(z^{x,L-1})$

now if $w^L$ is a 4x2 matrix and $\delta^{x,L}$ is a 1x2 vector then wouldnt $(w^L)^T\delta^{x,L}$ be a multiplication of a 2x4 matrix and a 1x2 matrix, which is impossible?

i feel like i have missed something vital in my understanding, but i cant work out what it is.

is it just as simple as making it $\delta^{x,L}(w^L)^T$? this would be a 1x2 matrix multiplied by a 2x4 matrix, which is perfectly legal. but the formula has it around the other way.

can anyone see where my understanding is flawed? any help would be greatly appreciated


texts: Why does the square root of n! grow exponentially faster than exponential functions?

texts:
I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.

In the proof of the theorem $6$ of the paper on page 632, the authors go on proving the difference between the probabilities of sampling all irreps, $|p - q|_1$ of a subgroup inside the symmetric group $S_n$.

$$
\begin{align}
|p - q|_1 &=  \Sigma_{\rho} \mid p_{\rho} - q_{\rho} \mid \\
          &\le \Sigma_{\rho} \frac{d_{\rho}}{n!} 2^{O(n)} \sqrt{n}^{n / 2} \\
          &\le \Sigma_{\rho} \frac{\sqrt{n!}}{n!} 2^{O(n)} \sqrt{n}^{n / 2} \\
          &\le \frac{2^{O(n)} \sqrt{n}^{n/2}}{\sqrt{n!}} \\
          &= 2^{O(n)} \frac{\sqrt{\sqrt{n}^n}} {\sqrt{n!}} \\
          &\le 2^{O(n)} \frac{1}{\sqrt{\left( n / 2 \right)!}} \lll 2^{-\Omega(n)}
\end{align}
$$

How is $2^{O(n)} \frac{1}{\sqrt{\left( n / 2 \right)!}} \lll 2^{-\Omega(n)}$?


texts: LinkedList: Remove the kth node form the end

texts:
Question: Write a function that takes in the head of a Singly Linked List and an integer k and removes the kth node from the end of the list. The removal should be done in place, meaning that the original data structure should be mutated (no new structure should be created). Furthermore, the input head of the linked list should remain the head of the linked list after the removal is done, even if the head is the node that's supposed to be removed. In other words, if the head is the node that's supposed to be removed, your function should simply mutate its value and next pointer. Note that your function doesn't need to return anything. You can assume that the input Linked List will always have at least two nodes and, more specifically, at least k nodes.
Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null. if it's the tail of the list.
The Solution:
class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function removeKthNodeFromEnd(head, k) {
  let first = head;
    let second = head;
    let i = 1;
    while(i <= k){
        second = second.next;
        i++
    }
    if(second == null){
        head.value = head.next.value; // Why can't I do: head = head.next
        head.next = head.next.next;
        return
    }

    while(second.next !==null){
        second = second.next;
        first = first.next;
    }
    first.next = first.next.next;

}

I have understood the above algorithm for the most part. Except why I need to have:
        head.value = head.next.value;
        head.next = head.next.next;

Why can't I just replace the above lines with a single:
head = head.next


texts: Suppose G is simple graph with n vertices. Prove that G has twice as many edges as vertices only if $n\geq 5$

texts:
I just didn't understand the second part of the prove

"G has twice as many edges as vertices only "... what do I actually have to prove ?

I understand it like $n=2e$ , is it right ?

then isn't it's just similar to the degree equation ??


texts: Generating cyclical dependency graphs from k-way partitions of DAGs representing boolean networks

texts:
My question stems from something mentioned in the following paper*:

Acyclic Multi-Way Partitioning of Boolean Networks by Jason Cong, Zheng Li, and Rajive Bagrodia

Given a DAG representing a Boolean network, $N$, where each node represents a logic gate, define a k-way partitioning solution as $S = (A_1, A_2, ..., A_k)$ satisfying $$A_i \cap A_j = \emptyset \quad{\text{and,}}$$ $$\bigcup\limits_{i=1}^{k} A_i = N$$

Then define a dependency graph $D(S)$. This is a directed graph with $k$ nodes where each node represents a block, $A_i$, and has an edge $(A_i,A_j)$ if and only if there exists an edge $(x,y)$ in $N$ such that $x \in{A_i}$ and $y \in A_j$ (in other words, the edges are the edges removed when forming the partition).

The authors note that it is possible to get dependency graphs that are cyclic after some k-way partition. My question is, how is this possible? I can't seem to come up with an example where partitioning a DAG would ever produce a cyclic dependency graph. As I see it, a cyclic dependency graph would require a an edge to be "reversed" somehow, which would produce a cycle in the original DAG. Perhaps it has something to do with the fact these graphs are representing boolean networks?

*Link to pdf may be paywalled

**Note the authors also have a balance constraint on the partitions which I didn't describe but I don't think that's relevant to my question.


texts:
I understand that a big advantage of round robin scheduling over non-preemptive schedulers is that it dramatically improves average response times. By limiting each task to a certain amount of time, the operating system can ensure that it can cycle through all ready tasks, giving each one a chance to run, and the length of the quantum and the number of processes in the run queue.

How do time slice duration and context switching affect each other in a round robin scheduling algorithm?


texts: How to evaluate a Kleene's Closure through CFG and attribute grammars

texts:
For a CFG with the production rules that can represent a regular expression. How can one calculate all the set of strings that regular expression would produce.
For T = {a, b,*,(,)}
and an arbitrary production rule I created to represent a simple regular expression
S->SS | S* | (S) | a | b | ∅
What would be an attribute grammar which can calculate the set of all strings that the regex can evaluate.
For example if we generate b(a)*
Then the output generated by regular expression would be a set of infinte strings {b,baa,ba,baaa......}
using set valued expression in the attribute grammar.
I am not sure how to represent set valued concatenation and Kleene closure.


texts: How does the CPU receive, process and output information?

texts:
I was studying the I/O process of a PC...and I think I understood it..but not very much so I will type what I understood giving an example..and I hope that I got it right

e.g. typing with a keyboard

First: The Input, and that is done simply by the keyboard..

Second: The information gets to the CPU in binary, but the logic unit doesn't understand it so the Control Unit gets the Instructions saved in the RAM by the CU it self..
then the instructions is sent to the Logic Unit through the CU

Finally:The Logic Unit understands it that time and do some operations that produces some Outputs.
The outputs are saved in the RAM, and viewed on the screen

So, please tell me if that's right or if I missed the whole thing..
Thank you very much in advance.


texts: Arden's rule expressed as matrix algebra

texts:
The following theorem is (in the context of languages) known as
  Arden's Lemma: Given a linear system $X = B+AX$ and the matrix A is
  quasiregular, then we have a solution which is unique and which
  preserves rationality. In the next lemma we show the converse: For
  every rational series we can find a linear system such that the first
  component of its solution vector is exactly the given series. With
  these two results we have already done most of the work for proving
  the Theorem of Schutzenberger, which teaches us that the families of
  rational and recognizable series coincide.

  Theorem 2.2.1

  Let $B \in \mathbb{K}\langle\langle\Sigma^*\rangle\rangle^{n,1}$ and $A \in \mathbb{K}\langle\langle\Sigma^*\rangle\rangle^{n,n}$ a quasiregular matrix. The linear
  system

  $$
X = B + AX
$$

  has the unique solution $X = A^∗B$. Moreover, if $A$
  and $B$ are $\mathbb{K}-rational$ then the solution $X$ is $\mathbb{K}-rational$.

  Proof:

  First we show that $X = A^∗B$ is a solution:

  $$
B + AX = B + AA^∗ B = (I + AA^∗)B = A^∗B = X.
$$

My question is as follows: what does asterisk mean in this context (when it is used with matrices)? I know what Arden's Lemma is, but I don't understand the proof given here.

To credit the author of this paper: Regular Languages And Their Generating Functions: The Inverse Problem by Christoph Koutschan.


texts:
Ok, I really need help because I have read in so many books but still don't understand the complexity class NP.

These are the books:

Theoretische Informatik; Katrin Erk, Lutz Priese (german)
Grundkurs: Theoretische Informatik; Gottfried Vossen, Kurt-Ulrich Witt (german)
Theoretische Informatik; Ingo Wegener (german)

Links:

https://de.wikipedia.org/wiki/NP_(Komplexitätsklasse) (german)
https://www.ibm.com/developerworks/community/blogs/jfp/entry/no_the_tsp_isn_t_np_complete?lang=en (english)

And I actually have more links but I can't post them here because I don't have enough reputation

So far I know:

A problem L is in NP when there exists a nondeterministic algorithm which solves problem L in polynomial time.
NP includes decision problems. If there exists a solution for these problems, it should be possible to check with a deterministic algorithm in polynomial time whether the solution is indeed a solution.

To 1.: is the calculated solution an exact match or is it just an approximation? To 2.: is it just necessary to be able to check in polynomial time? For example: the solution is not indeed a solution but I was able to check it in polynomial time. Is the problem still in NP?

For a problem to be in NP, I must have a nondeterministic algorithm which solves the problem in polynomial time. The solution is an exact match and I must be able to check in polynomial time with an deterministic algorithm that the solution is indeed a solution????????????????

Can someone please help me to understand.

Further thoughts:
Let's take the TSP as an example.
Question: Does a tour exist <= k ?

Let's assume I wrote a nondeterministic algorithm, which calculates a tour <= k. So my answer would be: Yes, a tour like that exists.

However Vladimir wrote in his answer: If this question can be answered by a polynomial time nondeterministic algorithm, then the language L is in NP.

So I gave an answer 'yes'; that means the TSP is in NP?! However what about if my answer would be: No, a tour like that does not exist! ? Then the TSP would not be in NP?

And looking on the other definition: Further I answered: Yes, a tour like that exists, because my nondeterministic algorithm calculated a tour like that. Now if I can check with a deterministic algorithm in polynomial time that the calculated tour is indeed verified to be correct, then TSP is in NP !?


texts: Is it always possible to convert a k-tape Turing machine to a single-tape one without increasing its running time complexity exponentially?

texts: I am studying the past exam paper of course Theory of Computation. I know it is always possible to convert a k-tape Turing machine to a single-tape one, but how will the running time complexity be changed?


texts: Understanding tables in Dynamic programming

texts:
I came across this problem that asks you to implement a regular expression matcher with support for '.' and '*', where

'.' Matches any single character.

'*' Matches zero or more of the preceding element.

isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

While I was able to solve this in a linear fashion, I came across lots of solutions that used DP, like the one below,

class Solution {
    public boolean isMatch(String text, String pattern) {
        boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
        dp[text.length()][pattern.length()] = true;

        for (int i = text.length(); i >= 0; i--){
            for (int j = pattern.length() - 1; j >= 0; j--){
                boolean first_match = (i < text.length() &&
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
                if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                    dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                } else {
                    dp[i][j] = first_match && dp[i+1][j+1];
                }
            }
        }
        return dp[0][0];
    }
}

I'm having a hard time understanding this. I've solved a few DP problems that involved grids (shortest path in 2d grid, largest square in binary 2d grid),  using a DP table there made perfect sense to me. However here I'm completely lost, I'm unable to understand how traversing a 2d table helps in solving this problem. Further more it appears we know when the characters don't match in the loop, so I don't understand why we don't terminate the search there (this is also probably due to my lack of understanding of how a table traversal leads to a solution). Is there a clear intuitive explanation for problems like these?


texts: Is Binary Search Related to Binary Search Tree?

texts: I was reading binary search and suddenly realized that it would be very difficult for a binary search tree to find the middle value and then split in two. Are these related at all?


texts:
Let L1 = L2 union L3
find values such that L1 is context free and L2 and L3 are not.

So far I have:
L1 = $a^nb^n$
L2 = $a^*b^*$
L3 = $a^+b^+$

Is this acceptable?? Since L2 covers everything including epsilon and L3 is the same but does not include epsilon?

I know L2 is regular so I guess that is also not a CFL.
Another problem is that the a's and b's aren't linked in L2 and L3, so either one can always have more a's than b's and vice versa.


texts: Environment detection - How to detect "city" versus "landscape" background environment in computer vision?

texts:
I'm searching for computer vision or machine learning algorithms/methods that are used to classify or differentiate two outdoor environments. Given an image with vehicles, I need to be able to detect whether the vehicles are in a natural open landscape (desert, in particular), or whether they're in the city.

I've searched but can't seem to find relevant work on this. Perhaps because I'm new at computer vision, I'm using the wrong search terms.

Any ideas? Is there any work (or related) available in this direction?


texts: An NFA with no equivalent DFA with fewer than $2^n$ states: Example and Proof

texts:
I have been following the book Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft and Jeffery D. Ullman.

I came across the following topic titled Bad Case for Subset Construction (2.3.6). I cannot follow the example given over there, about NFA N that can accept strings with 1 at the $n^{th}$ position, and that the DFA formed from that NFA thereafter will have no equivalent with fewer than $2^n$ states.

  They argue that The DFA $D$ must be able to remember last n symbols it
  has read. Since any of the $2^n$ subsets of the last n symbols could
  be 1, if D had fewer than $2^n$ states, then there would be some state
  $q$ such that $D$ can be in state $q$ after reading two different sequences of n bits, say $a_{1}a_{2}...a_{n}$, and $b_{1}b_2...b_n$.

Here is an extract from the book itself:

I have been trying to comprehend the proof, including this line and the subsequent paragraph that follows, but I have not been able to.

Can someone please explain the approach ?


texts: Is the number of coin tosses of a probabilistic Turing machine a Blum complexity measure?

texts:
I read that the number of coin tosses of a probabilistic Turing machine (PTM) is not a Blum complexity measure. Why?

Clarification:

Note that since the execution of the machine is not deterministic, one should be careful about defining the number of coin tosses for a PTM $M$ on input $x$ in a way similar to the time complexity for NTMs and PTMs. One way is to define it as the maximum number of coin tosses over possible executions of $M$ on $x$.

We need the definition to satisfy the axiom about decidability of $m(M,x)=k$. We can define it as follows:

$$
m(M,x) =
\begin{cases}
k & \text{all executions of $M$ on $x$ halt, $k=\max$ #coin tosses} \\
\infty & o.w. \
\end{cases}
$$

The number of random bits that an algorithm uses is a complexity measure that appears in papers, e.g. "algorithm $A$ uses only $\lg n$ random bits, whereas algorithm $B$ uses $n$ random bits".


texts: Recurrence Relation for Column Major Form of multidimensional array

texts:
A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[0][n_2-1]...A[n_1-1][n_2-1]$$

The left most index varies most rapidly if we look at the looping changes.

For a particular element $A[i_1][i_2]...[i_m]$ of an $m$ dimensional array $A[n_1][n_2]...[n_m]$ if we denote $e_m$ as the number of elements stored in memory before the given element, we can see the following

$$ e_1 = i_1$$
$$ e_2 = i_1 + i_2 \times n_1$$
$$ e_3 = i_1 + i_2 \times n_1 + i_3 \times n_1 \times n_2$$

How to show that generally

$$ e_m = e_{m-1} + i_m \times \prod_{j=1}^{m-1}{n_j}$$

If we look at the two dimensional array, the number of elements stored before a particular array location can be calculated as the column number of the element we are looking for summing with the $row \times column$ number of elements. How does the above recurrence relation work?


texts: Binary 2s Compliment Applied Twice Gives Original - How?

texts:
At the moment the maths behind binary 2s compliment seems like voodoo to me.

If I take 0011 (+3) and "flip and add 1", I get 1101 (-3)

If I apply the same process to 1101, ("flip and add 1"), I get back to the original positive value.

How is this so?


texts: Prove that $SEQ_{DFA}$ = {⟨A,B⟩ | A,B are DFAs and L(A) ⊆ L(B)} is decidable

texts:
Consider the following language $$EQ_{DFA} = \{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A) = L(B)\}$$

Given the fact that $EQ_{DFA}$ is decidable, how can I prove that the language $$SEQ_{DFA} = \{ \langle A, B\rangle: A \ and \ B \ are \ DFAs \ and \ L(A)\subseteq L(B)\}$$ is also decidable?

Thank you in advance


texts:
I'm trying to find complexity class of finding winning strategy for first player in following game:

Intance of 'Stones' game is:

finite set $X$
relation $R \subseteq X^3$
set $Y \subseteq X$ and node $f \in X$

At the beggining we place stone in every element of $Y$.
Every player in his turn can move stone from $x$ to $z$ iff. $\exists y.R(x, y, z) \wedge y\ has\ stone\ placed\ in\ it$.
Player who places stone in $f$ wins.

I think it's $PSPACE-complete$, but I was trying to proove this for some time, and I run out of ideas.

I won't lie, it's homework assignment for my complexity class. Any help will be highly appreciated.


texts: Find the fixed point of a recursive functional?

texts:
A functional is a function which takes another function as a parameter.
The fixed point of a function is an input such that
F(x) = x

Given an example functional,
T(F,x,y) = if x = 0 return 0
           else return y + F(x - 1,y)

what is the fixed point of the functional?

The functional looks similar to a recursive implementation of x * y given the if x = 0 return 0 and function call with x - 1, but I don't see where to go with this. To find a fixed point in a normal mathematical equation you'd just set T(f,x,y) = f(x,y) and solve, but given the format that doesn't really work. I can't see how the RHS can be simplified to allow that.


texts: Categorization of Binary search as Divide and Conquer

texts: Why do we call binary search as 'Divide' and 'Conquer' strategy? It does not combine the results unlike other Divide and Conquer strategies.


texts: Fantasy premier league dream team algorithm?

texts:
For those of you who are not familiar with FPL, here's a short version. You have players playing as either Goalkeeper, Defender, Midfielder or Forward. Each player has some price (either rounded to .5 or .0), and based on their real life performance you earn points. You have a budget of 100£ and you need to build a team, keeping in mind you have a limit for players on each position.

Now, the problem is: If you have all players prices, their positions and total number of points they scored in a season, how do you find the highest scoring team (team score is equal to sum of all players' individual points) with, for example, 4-4-2 formation? (1GK, 4DEF, 4MID, 2FWD)

I guess this is a variation of knapsack problem, where you have limitations to have exactly 11 players, and exactly 4-4-2 formation.
So is that the best way to solve this problem and how would you solve it with these modifications/limitations, or is there a better solution?


texts: To what does typing correspond in a Turing Machine?

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


texts: How do two H gates act on two entangled qubits?

texts:
In this circuit, if the two qubits are initialized at state 0, then after the oracle they are entangled and in the state:
$$\frac{1}{2} (|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$
My question is, how do the two $H$ gates act on them? Do they act like:
$$\frac{1}{4} [(|0\rangle+|1\rangle)\otimes(|0\rangle+|1\rangle) + (|0\rangle+|1\rangle)\otimes(|0\rangle-|1\rangle) + (|0\rangle-|1\rangle)\otimes(|0\rangle+|1\rangle) - (|0\rangle-|1\rangle)\otimes(|0\rangle-|1\rangle)]$$
which in the end nothing has changed. My intuition tells me that it's wrong.
Update: The figure above is from a circuit to implement Grover's algorithm. The whole figure is given below:

The state is indeed not changed after the two $H$ gates, so why do they add them here?


texts: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (proofs, etc.)?

texts:
I'm a student, so I apologise if this is an idiotic question: Is there a fundamental reason/limitation, such as $P \not = NP$, that prevents computers from being able to do mathematics (posing conjectures, proofs, etc.)? Why or why not?

I have heard arguments that computers will never be able to do mathematics close to the ability of humans, and these arguments are sometimes justified with reference to P vs NP (assuming that $P \not = NP$). It is said that, since these problems are NP rather than P (?), the solutions (proofs) could either be so lengthy as to not be understandable and/or verifiable by humans, or the solutions (proofs) would take so much time that the task practically becomes impossible. Are these statements true? Why or why not?


texts: Why classes implicitly derive from only the Object Class?

texts:
I do not have any argument opposing why we need only a single universal class. However why not we have two universal classes, say an Object and an AntiObject Class. In nature and in science we find the concept of duality - like Energy & Dark Energy; Male & Female; Plus & Minus; Multiply & Divide; Electrons & Protons; Integration & Derivation; and in set theory. There are so many examples of dualism that it is a philosophy in itself. In programming itself we see Anti-Patterns which helps us to perform work in contrast to how we use Design patterns. I am not sure, but the usefulness of this duality concept may lie in creating garbage collectors that create AntiObjects that combine with free or loose Objects to destruct themselves, thereby releasing memory. Or may be AntiObjects work along with Objects to create a self-modifying programming language - that allows us to create a safe self modifying code, do evolutionary computing using genetic programming, do hiding of code to prevent reverse engineering.

We call it object-oriented programming. Is that a limiting factor or is there something fundamental I am missing in understanding the formation of programming languages?


texts: Proving Turing Completeness by creating a compiler to a Turing Complete language

texts: Given a programming language A unknown to be Turing Complete, if one can create a compiler for a TC programming language B using A does this imply that A is itself Turing Complete? If so, what is the formal thinking behind the idea?


texts: I have seen the term "approximation oracle" in computer science papers, sometimes parameterized with the letters $\alpha$ and $\beta$. What is an approximation oracle? How are such oracles used? I am somewhat familiar with the idea of an "oracle machine" in complexity theory.


texts: Big-O Notation of Anagram solution algorithm

texts:
In Solution 1: Checking Off of Problem Solving with Algorithms and Data Structures, just beneath the ActiveCode: 1 extract (included at the bottom of this post for reference), it is stated:

  each of the n characters in s1 will cause an iteration through up to n
  characters in the list from s2.

...which to paraphrase (less succinctly), means "each character in s1 could result in all characters in s2 being inspected".

The following sentence states:

  Each of the n positions in the list will be visited once to match a
  character from s1.

Firstly I'm unsure which list is being referred, I think it means the variable alist, i.e. s2. Is this correct?

  The number of visits then becomes the sum of the integers from 1 to n.

Secondly (and the real point of this post), if each item in the list (variable alist) is inspected for each character in s1, then why is this not simply O(n) = n^2 as per "nested loops"?  If n=5, then then sum(n) = 15, where as n^2 = 25.

I'm fine with simplifying the equation for summing 1 to n integers to get n^2, but I'm confused about how sum(5) = 15, whereas O(n) = n^2.

ActiveCode: 1 Checking Off (active5)

def anagramSolution1(s1,s2):
    alist = list(s2)

    pos1 = 0
    stillOK = True

    while pos1 < len(s1) and stillOK:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 = pos2 + 1

        if found:
            alist[pos2] = None
        else:
            stillOK = False

        pos1 = pos1 + 1

    return stillOK

print(anagramSolution1('abcd','dcba')

Edit to add

Having written this out it struck me that perhaps dropping the (1/2) and (1/2)n from the formula to sum(n) is the reason for the difference of actually summing n, as opposed to just doing n^2.

To be absolutely clear, I understand the formula for summing n is n^2 when dropping the non-dominant terms. What I don't understand is why we're summing n and not immediately and directly stating it is actually n^2 as a result of the nested loop and this sentence:

  each of the n characters in s1 will cause an iteration through up to n
  characters in the list from s2.


texts: How to determine the maximum RAM capacity for an operating system?

texts:
I was curious to know what limits the max RAM capacity for an OS while reading about microprocessors being 32-bit and 64-bit. I know that limit for 32-bit OS is 4GB and for 64-bit OS is 16 Exabytes, but my question is how do we get there? I found this calculation:

$\qquad 2^{32} = 4\,294\,967\,296$

and

$\qquad \frac{4\,294\,967\,296}{1024 \cdot 1024}\,\mathrm{B} = 4\,096\, \mathrm{MB} = 4\, \mathrm{GB}$.

It's different for 64-bit:

$\qquad 2^{64} = 18\,446\,744\,073\,709\,551\,616$

and

$\qquad \frac{18\,446\,744\,073\,709\,551\,616}{1024 \cdot 1024}\mathrm{B} = 16\,\mathrm{EB}$.

What I don't understand is how the calculation of bits turned into bytes and reached the results 4GB and 16EXB?


texts: How to solve a problem about balancing parentheses with smileys?

texts:
I'm new to dynamic programming and find a problem about balancing parentheses and smileys ":)" and "(:" at HackerRank, which is impossible to do.
I've been trying to solve it by 3 days now. The main issue with this problem is that the input string size is in range of 10^9 (creating a dynamic programming 2d array of size 10^9*10^9 takes forever) and no matter what I try the execution time out. Someone please help.
Here is the problem about balancing parentheses and smileys ":)" and "(:"


texts:
I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash?
One reason to rehash seems to be load factor or hash table size. When I want to lower the load factor and increase hash table size, then I need to rehash. Any other reasons, especially in real database development? Thanks!


texts: How do you check if two algorithms return the same result for any input?

texts:
How do you check if two algorithms (say, Merge sort and Naïve sort) return the same result for any input, when the set of all inputs is infinite?

Update: Thank you Ben for describing how this is impossible to do algorithmically in the general case. Dave's answer is a great summary of both algorithmic and manual (subject to human wit and metaphor) methods that don't always work, but are quite effective.


texts: Why is fully homomorphic encryption so slow?

texts:
What are the reasons that FHE is so slow? Is it possible to make the FHE algorithm so fast that it can be used in practice (say, the practical FHE algorithm should be slower no more than 10 times compared to conventional calculations)?

Or there is some fundamental limitation and any FHE implementations will always be millions of times slower than usual calculations?


texts: What is the time complexity of this аlgorithm? O(n * r)

texts:
Given function rand7 returns random integer in interval [0, 6]. Your task is to implement function rand5 which should return random integer in interval [0, 4] using function rand7.

This is a question from my book. So, this is how I solved it (the algorithm is written in C):

int rand5(void){
  return (int)(rand7() * 4. / 6. + .5);
}

Basically, I just scaled the interval to [0, 4]. The + .5 part is to properly round to nearest integer (not just to truncate decimals). However, this is not correct solution.

Solution in my book is very weird to me. This is how they did it:

int rand5(void){
  int a;
  while((a = rand7()) > 4);
  return a;
}

The book says that the algorithm I came up with works only when interval is significantly large (so the probability will not change a lot). For smaller intervals (like this one) there is no other solution.

Well, it sounds pretty weird that there is no other solution. What is the time complexity of this algorithm? For my algorithm, time complexity is O(r) where r is time complexity of rand7. But what is the complexity of their algorithm?

The complexity should be O(r * n) where n is, according to the definition of the time complexity, the largest possible number of loop iterations. But what is the largest possible number of iterations? We know nothing about function rand7 and the way it is implemented, so the largest possible number of iterations is infinity. So, the complexity of this algorithm is O(infinity) which doesn't make any sense.

Of course, if rand7 if properly implemented, it will for sure return at lest one time number in interval [0, 4]. But, theoretically, it can return any number of consecutive numbers which belong in interval [5, 6]. Is then complexity indeterminate?

Also, how is that possible that "there is no other solution"? To generalize, is there any algorithm which can give an integer random number (with equal probability for all numbers) from interval [0, k] for given number k using only rand2 (for example), such that the algorithm should work in finite time complexity?

Edit

Ok, if I need to summarize this, the question is as title says, what is the complexity of this algorithm?


texts: Efficient Algorithm to Find the n-th Odious Number

texts:
An odious number is defined as an integer that has odd binary Hamming weight. I need an implementation of algorithm that finds the nth odious number, preferably recursive. Any ideas? A python script is also wanted, but I can write it myself once the algorithm is found.
More description can be found on formula section in OEIS: A000069.


texts: Understanding Alpha Beta Pruning: Why do we ignore the values of a unsearched tree after the first leaf, can they not include acceptable values too?

texts:
So this is my question.

I am trying to understand this part of the book:

At d) why do we stop looking at the other nodes in that branch? There could be a acceptable value next to the 2? I am just trying to understand alpha beta pruning for a while.


texts: Relations of some exponential functions -- which is correct?

texts:
Consider the following functions

$f(n) = 3n^{(n^{1/2})}  $
$g(n) = 2^{(n^{1/2}) \log n }$  // here base of $\log n$ is 2
$h(n) = n !$

Which of the following is true?

$ h (n)$ is $O (f (n) )  $
$h (n)$ is $O (g (n)) $
$g (n)$ is not $O (f (n) )  $
$ f(n)$ is $O(g (n))$

I tried this way :

To check which function is large :

$3n^{(n^{1/2})}$ = taking log

$n^{1/2} \log 3n $

$g(n) = 2^{(n^{1/2}) \log n }$

by taking log :

$((n^{1/2})\log n )\log 2$ => $0.3 (n^{1/2})\log n  $

$h(n) = n !$ => $n^n  $

by taking log :

$n \log n $

So now comparing all these 3 functions I got following equality :

$f(n) < g(n) < h(n)  $
So answer should be (4) but actually answer is (1).
Could anyone explain me where I am wrong ?


texts: Single machine job scheduling to minimize weighted sum of completion time

texts:
Given $n$ jobs, schedule them such that the weighted sum is minimum.

weighted minimum sum S  for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :

$S = \sum_{1\leqq i \leqq n} w_i C_i$ where $C_i\ = \sum_{1\leqq j \leqq i} t_j$ and $w_i$ is the weight of job $J_i$,  $t_i$ is the time $J_i$ takes to complete.

I think the solution is to schedule the jobs in shortest weighted processing time i.e. to arrange them in the increasing order of  $ t_i/w_i $.

But how to prove this.


texts: How does recursion works when there are 2 or more consecutive recursive calls?

texts:
I was learning about recursion and i came across the following pseudo code for quicksort.

QUICKSORT(A,p,r)
1   if p < r
2      then q := PARTITION(A,p,r)
3           QUICKSORT(A,p,q-1)
4           QUICKSORT(A,q+1,r)

In this code there are two consecutive statements that recursively call quicksort function. It confuses me. I want to know how these statements gets executed. Does the partition of left half of the array happens recursively or does both left and right of the array gets partitioned at the same time?


texts: Correctness proof for finding weighted maximum independent set for a tree

texts:
The maximum weighted independent set for a tree can found out using the following dynamic programming approach.

Min[u] = wt(u) + Σ Mout[v] where v ∈ children(u) Mout[u] = Σ max { Min[v], Mout[v] } where v ∈ children(u)

where Min[u] and Mout[u] computes the total weight of the maximum independent set for the sub tree rooted at u by including or excluding u respectively.

I tried to proof the correctness of this algorithm. Suppose the independent set ( say I ) generated from this algorithm is not of maximum weight. Let the maximum weighted independent be I'. Then there must be a vertex V'∈ I' and V' ∉ I. And also there can be 2 cases. Either parent(V')∈ I or parent(V') ∉ I. I tried both the cases to solve furthur but could not proceed. Is this approach correct or there is some alternative way to prove the correctness.


texts: Randomized vs deterministic approach for multiset equality

texts:
Let $S_1$ and $S_2$ are two multi sets. We want to find, Is $S_1 =S_2$?

Algo 1:

Sort $S_1$ and $S_2$ and then check $S_1 = S_2$

Running time : $O(n \log {n})$, where $n$ is the size of the multi sets.

Algo 2:

Contruct two polynomials using $S_1$ and $S_2$ (example if $S_1 = \{1,1,2\}$ then polynomial will be $(x-1)(x-1)(x-2)$)

Let us say we have now two polynomials $p(x)$ and $q(x)$, do $p(x)-q(x)$, now using polynomial identity testing check whether $p(x)-q(x) =0 $ or not. If it is zero then $S_1$ equals to $S_2$.

Question : Which algorithm is better Algo 1 or Algo 2?


texts: Returning sorted lowest k elements in a binary heap

texts:
Given a binary heap of size $n$ and a number $k\le n$. How can I return an array with size $k$, which contains the $k$ lowest elements in the binary heap, so that it will be sorted in the end?

The problem is that the time-complexity needs to be $\Theta(k \log(k))$.


texts: A complete catalog of 2-state Turing machines?

texts:
For educational purposes, I'm about to start a research project that involves creating a complete database documenting and classifying all 2-state, 2-symbol Turing machines, according to a multiplicity of criteria. Including all rejecting and accepting transitions, there are $28.561$ such machines, a number big enough to make it interesting, and small enough to make it feasible.

How did I get this number? Using Tibor Radó's notation for the busy beaver problem, the number of machines for $n$ states is $[4(n+1)]^{2n}$. Adding all rejecting transition possibilities, you get $[4(n+1)+1]^{2n}$ machines.

I have briefly searched online and found nothing similar, so I am asking here if anybody knows if this has already been done, or not. I am aware that many simplifications are possible, but as I intend to explore every angle (what they generate, what they accept, if and when they halt, etc.), the resulting number of different machines will still be quite significant.


texts: Why can't DFS be used to find shortest paths in unweighted graphs?

texts:
I understand that using DFS "as is" will not find a shortest path in an unweighted graph.

But why is tweaking DFS to allow it to find shortest paths in unweighted graphs such a hopeless prospect? All texts on the subject simply state that it cannot be done. I'm unconvinced (without having tried it myself).

Do you know any modifications that will allow DFS to find the shortest paths in  unweighted graphs? If not, what is it about the algorithm that makes it so difficult?


texts: Karp hardness of a diameter-decreasing planted clique

texts:
A diameter-decreasing planted clique in an undirected graph $G(V,E)$ is a set of vertices $\mathcal{C}\subseteq V$ such that if we add all the missing edges between any pair of vertices in $\mathcal{C}$ to turn it into a clique, then the diameter of the obtained graph $G'$ is at most $2$.

Diameter-decreasing Planted Clique Problem:

  Input: An undirected graph $G(V,E)$ and a natural number $k$

  Output: YES if there exists a diameter-decreasing planted clique
  of size $k$ in $G$, otherwise NO

What is the complexity of this problem?


texts: Can we express the program to find last element of a list as a catamorphism?

texts:
So I've got a bit of category theory under my belt, and I am reading a few papers about calculating functional programs.  I've expressed  programs like summing a list as a catamorphism, and I've fused some catamorphisms, too.

I thought it might be interesting to see how far I could take what I now know about catamorphisms by applying it to 99 Haskell Problems .  It turns out that I can't take it very far at all because the first problems have me stumped.

I'm aware that the old saying "if the only tool you have is a hammer, then every problem looks like a nail" applies to me. But if we are asked to provide a program that finds the last element of a list, can we express that program as a catamorphism?  If not, then why?

Thanks in advance!


texts: Generating function of non-regular language

texts:
Let's say $\sum_{n \ge 1} a_{n}x^n$ is generating function for regular language $L$. $a_{n}$ is number of words with length $n$.

Find an example of generating function which isn't correspond for any regular language.

My attempt : I use the fact for any regular language there is exists $n_{0}$ $\lambda_{i}$ and $p_{i}$ : $a_{n} = \sum_{i} \lambda_{i}^{n} p_{i}$ and as example get language with $a_{n} = C_{n}$ , where $C_{n}$ is Catalan number. My teacher said that's not obvious and told me to get easier example. But I don't know useful criteria to find an example with contradiction about regularity. Any ideas?


texts: Prove the existence of regular $C$ so that: $A \prec C \prec B $

texts:
Given $A,B$ regular languages with $A \prec B$. Prove the existence of $C\in L_{\text{regular}}$ so that: $A \prec C \prec B$.

Here, $A\prec B$ stands for: $A\subset B $ and $B\setminus A $ is infinite.

I tried to go for: $C=\overline{B} \cup A$ and some other options but it didn't work out.


texts: Extending Thompson's NFA algorithm with backreferences

texts:
I'm looking for an algorithm as efficient as possible for a regex engine that supports submatch tracking (a.k.a capturing parentheses) and backreferences. What I mean by as efficient as possible is that the simple parts of the regex (like .*.*) should still be matched in linear time no matter whether the backreferences match immediately or go full exponential.

Thompson's NFA algorithm seems to be a very promising base algorithm as it can match a regex of size $m$ to a string of size $n$ with a worst-case time complexity $O(mn)$ and a worst case space complexity $O(m)$.

It could be easily modified to support capturing parentheses by embedding in the active states the set of captured substrings that lead to the current state. When a given state is reachable from two path, some rules is used to decide which set of substrings is kept (e.g. left-most longest). Correct me if I'm wrong, I don't think this method change the worst-case time complexity. However, the worst-case memory usage goes to $O(m^2)$ instead of $O(m)$ since each active state has to know at least one set of substrings for all the previous capturing parentheses.

Backreferences are where I'm stuck. I know a worst-case exponential time is unavoidable (unless P = NP). But the only solution I could think of takes an exponential amount of memory. The idea would be to take the algorithm above and keep all the combinations of matched substrings so that future backreferences could pick the ones that match.

I feel like there would be a way to make an algorithm that would save the regex engine state (which states of the NFA were active their associated data) when an active state exits a backreferenced capturing parentheses. So that we commit to the first match, and if later the backreference fail, it backtracks to the saved state and try the next match for that pair of parentheses.

The issue with that idea is that it doesn't allow to have some preference when several substrings could match. For instance we might want to choose the longest match when a greedy operator is used.

Any idea how this could be done?
Maybe there is already a known solution that didn't come up in my research.

Two notes:

I found a paper that propose an algorithm that either is wrong or that I didn't understand.

There's the Henry Spencer's hybrid regex engine that manage to mix Thompson's NFA (sometime called a DFA engine) with some backtracking (sometime called NFA engine). The only documentation I could find about it is posgres' README for a high level view, and Russ Cox on comp.compilers who explain that submatch extraction has an $O(n^4)$ worst-case. And I still have no information about how backreferences are supported or how they interact with the simple parts of the regex.


texts:
The most appropriate way to implement a heap is with an array rather than a linked list, why is this?

I don't completely comprehend why this is? is it because it is easier to traverse?


texts: shortest time based on traffic congestion data

texts:
I want to develop one algorithm which can predict shortest time to be taken to go to a destination from a source in a road network based on traffic congestion data.
Consider that I have a server which gives me real time traffic congestion data for all the path segments in a road network. Now I want to develop such an algorithm which can predict time to be taken based on these data. So in short:

time_to_be_taken_from_source_to_destination = function ( traffic_congestion_data ). And 'time_to_be_taken_from_source_to_destination' is proportional to 'traffic_congestion_data' as time increases when traffic_congestion increases.

Are there any such algorithm alraedy developed? Any idea? reference to any algorithm or theory will be appreciated.