texts:
This question follows
Unique 3SAT to Unique 1-in-3SAT

Consider an AND gate such that (A ∧ B) = C. It can be trivially expressed in 3SAT with 4 clauses and no extra variables.

$$
(A ∨ B ∨ \overline{C}) \wedge
(A ∨ \overline{B} ∨ \overline{C}) \wedge
(\overline{A} ∨ B ∨ \overline{C}) \wedge
(\overline{A} ∨ \overline{B} ∨ C)
$$

| A | B | C |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 0 | 1 | <-- Eliminated by (A ∨ B ∨ !C)
| 0 | 1 | 0 |
| 0 | 1 | 1 | <-- Eliminated by (A ∨ !B ∨ !C)
| 1 | 0 | 0 |
| 1 | 0 | 1 | <-- Eliminated by (!A ∨ B ∨ !C)
| 1 | 1 | 0 | <-- Eliminated by (!A ∨ !B ∨ C)
| 1 | 1 | 1 |

Using the resolution rule, you can even reduce it to 1 clause of size 3 and 2 clauses of size 2.

$$
(A ∨ \overline{C}) \wedge
(B ∨ \overline{C}) \wedge
(\overline{A} ∨ \overline{B} ∨ C)
$$

The OR gate is analogous because if (A ∧ B) = C then (!A ∨ !B) = !C. In other words, you just need to flip all the literals.

For the XOR gate, we could express it using 2 ANDs and 1 OR, or 2 ORs and 1 AND, but that would be a waste of space, especially in a circuit with many XORs. In fact, from observing the truth table again, we can do it again with 4 clauses:

$$
(A ∨ B ∨ \overline{C}) \wedge
(\overline{A} ∨ \overline{B} ∨ \overline{C}) \wedge
(\overline{A} ∨ B ∨ C) \wedge
(A ∨ \overline{B} ∨ C)
$$

Now I want to reduce the circuit to 1-in-3SAT instead of 3SAT.

While a 3SAT clauses states "at least one of the variables is true", a 1-in-3SAT clause states "exactly one variable in this clause is true and the two other are false".

In the previous question, to reduce an AND gate to 1-in-3SAT, Steven introduces 4 new variables D,E,F,G per gate and expresses the gate using four clauses:

$$
(A, D, E) \wedge
(B, F, G) \wedge
(\overline{A}, F, C) \wedge
(\overline{B}, D, C)
$$

The reduction is parsimonious because D,E,F,G are entirely determined by A,B.

The OR gate can be obtained by flipping A,B,C.

Question:

How can we do the same with XOR ?

The goal is to obtain a list of 1-in-3SAT clauses that ensures that A xor B = C, with as few new variables as possible, such that the values of the new variables are fully determined by A and B.

A trivial solution is to express A xor B using AND/OR gates, ((A ∧ !B) ∨ ( !A ∧ B)), but doing so introduces 14 new variables (3 gates * 4 variables + 2 intermediate output variables) and 12 clauses which makes XOR gates way more expensive than AND/OR gates.


texts: Is it possible to easily reduce 0/1 subset sum to subset sum with multiplicities?

texts:
So both the 0/1 subset sum problem (find a subset of given numbers that add up to a target sum) and the subset sum problem with "multiplicities" (find non-negative integer coefficients for the set elements so that the linear combination of set elements equals a target sum) are NP-complete. Is there some fairly easy reduction from 0/1 subset-sum to subset sum with multiplicities? This seems perhaps non-trivial, because just because there is a solution with multiplicities doesn't mean there is a 0/1 solution.

Some ideas I had that don't seem to work: For element $s$, solve the subset sum with multiplicity problem both for total sum $S$ and $S-s$ with element $s$ removed from the set. Then try to argue that $s$ either is or is not included in the 0/1 solution depending on the answer.


texts: Interpreting the accuracy of solutions to the correspondence problem

texts:
I have two pictures of the same object, taken by a car travelling down the road like shown on the right side of the image below. I want to find pixels of the object in each frame that correspond to each other.
Now, in the description of the Middlebury Stereo Evaluation v.3 dataset it says

Maximum disparities range from 200 to 800 pixels at full resolution.

This leads me to my two questions:

Do I understand correctly that algorithms working with the Middlebury dataset had to match pixels that were a distance of 200 to 800 pixels apart, like shown on the left side of the image?
Consider the leaderboard for the Middlebury Stereo Evaluation. Does an average absolute error metric of 1.4 mean, that above problem could be solved for the images in the dataset with an average accuracy of 1.4 pixels?


texts:
I have a set of points A in my space (geo points but I can assume they are on a 2D plane).

I have another set of points B.

For every point in B I want to find every point in A inside a radius R with center in the considered point from B set.

I did it with KDTree, this provide me a very fast and easy algorithm to create the data structure and find neighbours but it doens't find every point in a radius because it could avoid a path which contains element in my radius but not in the same subset of the radius center.

Minimal example of KDTree failing:

While exploring KDTree the target point (red) is under the line of point number 1. This will proceed to exploration of point under the line, this will miss the real point inside the red point radius.

What algorithm or data structure allow 100% correctness?

I know for sure I will performe worse but I am look for a balance between search speed and full correctness.


texts: Does Reverse Polish Notation have an LL grammar?

texts:
Let L be the language of all arithmetic expressions written in Reverse Polish Notation, containing only binary operators. $\Sigma(L) = \{n, o\}$, n := number, o := operator.

Is there an LL grammar G so that L(G) = L?


texts:
In exactly a month I will face a Java exam. My problem is that even if I know all Java theory (the exam won't face GUI), I have problems creating programs: sometimes I can't understand how to make a fast program or how to implement what I want my program to do. So how can I improve my Java habilities? What kind of exercises should I work on? Should I follow some guides or tutorials? Should I re-study all the theory till I understand better?

P.S. If this isn't the right Stack to post this on I will just close the question and look better for the right one


texts:
We are given a graph $G=(V,E)$ with positive edge weights $w_{i}$ and numerical {0,1,-1} labels $l$ for all vertices . We know that $G$ has a subset $G'$ with all vertices labeled 0. The problem is to assign labels to the vertices in $G'$ in such way that this sum is maximized $\sum_{e_{u,v}\in E} w_{i}l_ul_v.$ The question is whether this problem is NP-complete or not. If it is not then what is the polynomial algorithm?

Personally I believe that this problem is essentially a form of 3-Coloring. The challenge is to chose the labels {1,-1} depending on the neighbors. Say the boundary between $G$ and $G'$ has a lot of 1s  then it is better to chose 1s for the labeling of vertices in $G'$, similarly if the boundary has lots of -1s then it is better to chose -1s for labeling because $-1*-1=1$. So essentially this becomes some sort of reverse 3-Coloring problem where the neighbors have to have matched color.

Can you help reduce this problem to 3-Coloring (or vice-versa) ? Or perhaps there is polynomial time algorithm ?


texts: What is the purpose of erasing a type application to a term-application in parametric polymorphism?

texts:
From Types and Programming Languages by Pierce

  23 Polymorphism

  23.7 Erasure and Evaluation Order

  in a full-blown programming language, which may include side-
  eﬀecting features such as mutable reference cells or exceptions, the
  type- erasure function needs to be deﬁned a little more delicately
  than the full era- sure function in §23.6. For example, if we extend
  System F with an exception- raising primitive error (§14.1), then the
  term

let f = (λX.error) in 0;

  evaluates to 0 because λX.error is a syntactic value and the error in
  its body is never evaluated, while its erasure

let f = error in 0;

  raises an exception when evaluated.

  What this shows is that type abstractions do play a signiﬁcant
  semantic role, since they stop evaluation under a call-by-value
  evaluation strategy and hence can postpone or prevent the evaluation
  of side-eﬀecting primitives. We can repair this discrepancy by
  introducing a new form of erasure appropriate for call-by-value
  evaluation, in which we erase a type abstraction to a term-abstraction

erasev (x) = x
erasev (λx:T 1 . t 2 ) = λx. erasev (t 2 )
erasev (t 1 t 2 ) = erasev (t 1 ) erasev (t 2 )
erasev (λX. t 2 ) = λ_. erasev (t 2 )
erasev (t 1 [T 2 ]) = erasev (t 1 ) dummyv

  where dummyv is some arbitrary untyped value, such as unit.

Is the purpose of "erase a type abstraction to a term-abstraction" to prevent the body of a type abstraction from being evaluated?
What is the purpose of erasing a type application to a term-application by adding dummyv?
What is the evaluation rule for an application when the argument is unit?  (I can't find it in the section for type Unit.)

Thanks.


texts:
Here I have created 2 classes , $A$ is the super class of $B$ , i.e , $B$ inherits the features of class $A$.

Now I don't know exactly what statement (1) does but I am speculating as follows ,kindly correct me if I am wrong ,

An object of $B$ is created whose address has been assigned to the variable $ob$ of class $A$.

Now when statement (2) is called the $add$ function of the class $B$ is executed , but when statement (3) is executed it gives an error saying $e$ doesn't belong to $A$. Why is that ?

With my understanding , I thought statement (1) creates an object of class $B$ via its parent class $A$. Then why its object can't access its data member ? Can anyone explain ?


texts: Expected number of retransmissions for a packet

texts:
In a communication link out of p packets one packet will be lost. If stop and wait protocol is used then expected number of retransmissions for a packet?

(A) P/(1-P)

(B) P

(C) 1/(1-P)

(D) 1/P

This has already been answered here Stop and Wait retransmission of packets? but I dont have enough reputation to comment there, hence posting this as a separate question.

According to the expected answer,

  the expected number of packets you need to send is $\frac{1}{(1−1/p)}=\frac{p}{(p−1)}$

But this seems a bit absurd because this is a negative number. Is the solution incorrect?


texts: Using the features embedding of the output from a transformers to represent probabilities of categorical data

texts: I was considering using a transformer, on input data which can be represented as an embedding, so I can use the attention mechanism in the transformer architecture. As my data is of variable input and output length and the input is sequential. My question is that my output data is suppose to be either numerical or probabilities for each output variable. The output was originally supposed to 13 numerical outputs but I decided to use a probability score as way of normalizing the output. My question is can I use two output vectors with 7 features each instead of 13 numeric outputs. Each feature would map to one of the original output vectors and the the last feature would always be 0. As PyTorch expects your output to be the same number of features as your input. My input variables are embedded as 7 features. Should this approach work, as I am unsure of how the loss function works or is there a loss function that would allow for this.


texts:
I'm working through a Database Design textbook, and one of the problems involving ER Diagram design is giving me some trouble.

The diagram is for a UNIVERSITY database with the following rules:

  1)    The university keeps track of each student’s name, a unique student number, a unique Social Security number, address (split into street address, city, state, and zip code), phone number, birth date, sex, level (Freshman, etc.), major department, and degree program (BS, MS, PhD).

  2)    Each department is described by a unique name, a unique department code, office phone number, and the college it belongs to.

  3)    Each course has course name, a unique course number, description, number of credit hours, and offering department.

  4)    Each section has an instructor, semester, year, course, and section number. The section number distinguishes sections of the same course that are taught during the same semester/year, its values being 1, 2, 3, …, up to the number of sections taught during each semester.

  5)    A grade report has a student, section, a letter grade (F, D, C, B, A), and a numeric grade (0,…, 4).

  Specify key attributes of each Entity Type, and structural constraints (using max-min notation) on each Relation Type. For incomplete specifications, if any, make appropriate assumptions, and document them precisely.

This is what I've got so far:

A few questions I couldn't find answers to in the text:

1.) Can a Weak entity type have multiple partial keys?

2.) Can a Weak entity type serve as the identifying entity type for another Weak entity type (at the time of writing this, I'm guessing the answer is "no", but when I was making the draft I thought it might be possible)

3.) The text says it's possible for an entity to have multiple private keys, but is there some "best practice" limit to how many private keys an entity should have?

4.) The problem specifies that the SECTION and GRADE_REPORT entities should have a Course and Section attribute, respectively. However, the Section entity type is already in an identifying relationship with the Course entity type (and the Grade_Report type with the Section type, though as stated above I'm not sure if that's legal), so that seems a little redundant. Should these attributes be deleted, or am I maybe supposed to make them the partial keys of their individual types?


texts: Balanced Binary Search Tree Two-Sum with Constraints

texts:
My question spawns from this question. The question is straightforward:

  Can we find whether there exist 2 values in a balanced binary search tree where their sum equals a given target value?

Now the constraints:

Constant additional space in regards to $n$, the size of the tree. By this I mean you can use a constant number of $O(\log n)$ bit words however you wish. Assume references to nodes also take $\log n$ bits to store.
Read-only access to the tree. No modifications are allowed. This prevents a threaded traversal.
A node n has the following attributes: n.left, n.right, n.value. This means we have no access to a node's parent. This prevents a successor and predecessor traversal.
The algorithm must run in worst-case linear time in regards to $n$, the size of the tree.

It's worth noting that if we remove any one of the four constraints, we can satisfy the the other three relatively easily.

My initial thought is that this is not possible. Simply because we can have no memory of where we are in the tree when traversing it.

We could however implement a successor and predecessor in-order traversal using binary searches to find successors and predecessors. This would take $O( n \log n)$.

Another thought was that we could use a non-deterministic algorithm. Possibly a Monte Carlo algorithm with repetition or a Las Vegas algorithm. This randomized algorithm could be used to do a random walk along one path, then have another path search for a compatible node based on the random walk's nodes. I'm not entirely sure if this would work, but these are just some thoughts.

If this is indeed not possible, as I am suspicious, I would also be interested in the following additional modification:

The algorithm must run in average-case linear time.


texts: Proof that $(L_{all})^C$ is not recursively enumerable

texts:
The problem:

We have the language $L_{all} = \{\operatorname{Kod}(M) | M \text{ is a turing machine and } L(M) = \Sigma ^*\}$

Hence, $L_{all}$ is the set of all encoded Turing machines (the $\operatorname{Kod}()$ is the encoding function) which accept all words as input.

One needs to show that $(L_{all})^C$, the complement of $L_{all}$ is not in $\mathcal{L}_{RE}$, that means it is not recursively enumerable.

By definition, in $(L_{all})^C$ we have all strings which do not represent correctly encoded Turing machines as well as encoded Turing machines which reject at least one word from the alphabet.

What have I tried so far:

One idea was to use the diagonalization argument that can be used to prove that $L_{diag}$, the diagonal language is not recursively enumerable. This however doesn't seem to work.
I tried to prove that the statement is wrong (i.e. $(L_{all})^C)$ is recursively enumerable: The proof would more or less go like this (not very formal): Let $A$ be a Turing machine deciding if $x \in  (L_{all})^C$. We first check if $A$'s input is a correctly encoded Turing machine ($x = \operatorname{Kod}(M)$), if not we reject. If it is, we associate every word from $\Sigma^*$ with a prime $p$ and then use this to simulate all words on $M$ at once, (in the $p^i$th step of $A$ we simulate the $i$th step of $M$ on the $p$th word). This is where my counter proof fails. Since there are uncountably infinitely many words in $\Sigma^*$ and only countably infinitely many primes. However I do not see a way how I can use this fact to prove the original statement.

Any suggestion or hints would be greatly appreciated since I am genuinely interested how one approaches such a proof.

Full disclosure
 This was a bonus question on an old exam (not connected to homework) and I am curious how one can prove this, especially since it seems to be somewhat counter intuitive.


texts: Decidability over finite graphs of small degree

texts: Suppose $\sigma$ is a vocabulary of First Order logic consisting of one binary relation $E$ and let $\phi$ be a $\sigma$ sentence (FO formula with no free variables). Is it decidable whether there is a finite directed graph $G$, with all in- and out-degrees $0$ or $1$, such that $G\models \phi$ ?


texts:
I think some of the log properties are flying over my head but I'm trying to understand how the depth of mergesort is...

$1 + \log_2 n$

I understand that to get the depth, you would have to divide $n$ by $2^x$ but I don't how this leads to the above.

It's probably some simple log principal but I'm not sure.


texts: When are some (relatively) basic (think first year college level CS student) instances when one would use recursion instead of just a loop?


texts:
As there is an untyped lambda calculus, and a simply-typed lambda calculus (as described, for example, in Benjamin Pierce's book Types and Programming Languages), is there a simply-typed combinatory logic?

For example, it would seem that natural types for the combinators S, K, and I would be

S : (a -> b -> c) -> (a -> b) -> a -> c
K : a -> b -> a
I : a -> a

where a, b, and c are type variables ranging over some set of types T.  Now, perhaps we could get started with a single base type, Bool.  Our set of types T is then Bool along with whatever types can be formed using the three patterns

(a -> b -> c) -> (a -> b) -> a -> c
a -> b -> a
a -> a

where a, b, c in T.

There would be two new constants in the language.

T : Bool
F : Bool

So, this language consists of the symbols S, K, I, T, and F, along with parentheses.  It has one base type Bool, and the "function types" that can be made from the S, K, and I combinator patterns.

Can this system be made to work?  For example, is there a well-typed if-then-else construction that can be formed from only S, K, I, T, F?


texts: A language which is neither r.e. nor co-r.e

texts:
First, consider $$L_\exists=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts some input}\}$$
is RE. I tried to construct a Turing machine:

Input: Code(M);
L_e_TM(Code(M))
    for all words w of binary strings
        simulate M on w,
            if M accept w then return true;
    end for
end

Since we do not have to care about whether it halts or not, so we can use it to recognize $L_1$. But surely, this is language is not recursive which can be shown by reduction from the halting problem or by Rice's theorem.
But when we consider the complement of this language (for simplicity, we think all binary strings are valid Turing machine codes, otherwise we can just add a decider to check whether it is one recursively which will not affect the main result),
$$L_{\emptyset}:=L_\exists^\complement=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts no input}\}.$$
Similar we can just change the code above inside the for-loop:if M accept w then return false. Then both are in RE. Then they are in R? What was wrong? I thought there must be something wrong with the Turing machine code, but we are not talking about recursiveness, so I don't think the machine will not do the job to check whether it is in $L_\exists$ or not.
Somewhere, I have seen $L_\exists$ is RE. Hence,

Furthermore, consider

$$L_\forall=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts all inputs}\}$$
and
$$L_\forall^\complement=\{\langle M\rangle \mid M \text{ is a Turing machine and accepts not all inputs}\}.$$
Are they both non-RE or one is RE and the other not?


texts: Algorithms that are similar to Dynamic TIme Warping

texts:
Dynamic time warping (DTW) is an algorithm in time series analysis for measuring similarity between two temporal sequences which may vary in time or speed. Here are some explanations of DTW:

Dynamic Time Warping by Wikipedia
Dynamic Time Warping by M Müller (2007)

Is there any algorithm that can replace DTW for measuring similarity between two temporal sequences which may vary in time or speed?


texts: Can well-formed formulas in predicate logic for a given signature be recognized in LOGSPACE?

texts:
I read that visibly pushdown languages are supposed to model the typical simple formal languages like XML better than deterministic context free languages. The visibly pushdown languages can be recognized in LOGSPACE. I wonder whether the well-formed formulas in predicate logic for a given signature are a visibly pushdown language, or can at least be recognized in LOGSPACE.
Here is a typical well-formed formula in predicate logic, for the given signature $(f(\cdot,\cdot), g(\cdot))$:
$\forall x (f(x,y)=z \land g(z)=x)$
A corresponding context free grammar would be

$P \to T=T$
$P \to (P \land P)$
$P \to (P \lor P)$
$P \to \lnot P$
$P \to \forall V P$
$P \to \exists V P$
$T \to V$
$V \to x$
$V \to y$
$V \to z$
$T \to f(T,T)$
$T \to g(T)$

Some people prefer to use reverse polish notation:
$xyfz=zgx=\land x\forall$
A corresponding context free grammar would be

$P \to TT=$
$P \to PP\land$
$P \to PP\lor$
$P \to P\lnot$
$P \to PV\forall$
$P \to PV\exists$
$T \to V$
$V \to x$
$V \to y$
$V \to z$
$T \to TTf$
$T \to Tg$

Because I have now written down two explicit grammars, let the question just be whether these two grammars generate visibly pushdown languages, or can at least be recognized in LOGSPACE.


texts: Understanding validation based database concurrency control protocol

texts:
Database book by Korth explains validation protocol as follows :

To perform the validation test, we need to know when the various phases of transactions took place. We shall, therefore, associate three different timestamps with each transaction $T_i$:

Start($T_i$),the time when $T_i$ started its execution.

Validation($T_i$), the time when $T_i$ finished its read phase and started its validation phase.

Finish($T_i$),the time when $T_i$ finished its write phase.

The validation test for transaction $T_i$ requires that, for all transactions $T_k$ with $TS(T_k) < TS(T_i)$, one of the following two conditions must hold:

Finish($T_k$) < Start($T_i$). Since $T_k$ completes its execution before $T_i$ started, the serializability order is indeed maintained.

The set of data items written by $T_k$ does not intersect with the set of data items read by $T_i$, and $T_k$ completes its write phase before $T_i$ starts its validation phase Start($T_i$) $<$ Finish($T_k$) $<$ Validation($T_i$)). This condition ensures that the writes of $T_k$ and $T_i$ do not overlap. Since the writes of $T_k$ do not affect the read of $T_i$, and since $T_i$ cannot affect the read of $T_k$, the serializability order is indeed maintained.

Doubt
How second point says "writes of $T_k$ do not affect the read of $T_i$"?
Start($T_i$) is the timestamp when $T_i$ started its execution.
Validation ($T_i$): is the timestamp when $T_i$ finishes its read phase and starts its validation phase.
I believe that mean read phase start at Start($T_i$) and ends at Validation($T_i$) ?
Also Finish($T_k$) is timestamp when $T_k$ finished its write phase.
So, I believe Start($T_i$) $<$ Finish($T_k$) $<$ Validation($T_i$) means write of $T_k$ overlaps with read of $T_i$ and hence write of $T_k$ can affect read of $T_i$.
Am I missing something stupid?


texts: VC dimension of 1-NN classifier for discrete metric space?

texts: We know VC dimension of 1-NN classifier is infinite for continuous metric space. Is there any proof of VC dimension of 1-NN classifier if the metric space is discrete?


texts: Can I notate time complexity depending on the result of an algorithm?

texts:
I have a program that calculates the first year some two events happen on the same day. I have not calculated any upper limit for the year. The time complexity of the program would be equivalent to O(Years), where Years is the result of the algorithm.

Is such a notation possible?

If yes, can I call the algorithm "linear"?

If not, what would be the correct way of notating the complexity?


texts: Confusion in Banker's Algorithm: How resources are allocated?

texts:
I have seen examples about Banker's Algorithm from this Wikipedia link, this book and many other places. In all these examples some processes are allocated resources less than their Max Need.

For example, consider the state of system as shown in below given image taken from Wikipedia link:

Here you can see that the process P1's Max Need is 3  3  2  2 and the total available resources are 6  5  7  6. But the system allocates 1  2  2  1 resources to P1. Although it could allocate all the requested resources to P1 and P1 would have completed.

So my questions are:

Why does the system allocate partial / incomplete resources even when it has the resources available
If the allocation of partial / incomplete resources is allowed, then why does the system / algorithm enforce that the number of requested / needed resources should be less than the available resources (at the time of request)?. The system could allocate some resources (available at the time of request) to process(es) and the remaining would have been assigned when released by other processes.

OR

The process has to tell the number of resource types (and their instances) in advance, but does not need to be assigned all resources at a time; rather it is assigned resources when actually needed?

Please correct me if I am wrong.


texts: Big-Oh vs Theta in recurrence tree method

texts:
I am solving this problem from here.

The given relation is

$$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$

The solution via recurrence tree method is given as:

  The zeroth level has a single node with cost $n^2$. The first level has two nodes, each with cost $(n/2)^2 = n^2/4$. The third level has
  four nodes, with cost $(n/4)^2 = n^2/16$.

  In general, you can get the cost of a node by taking the subproblem size and squaring it. At the $i$th level, this cost is $n^2/4^i$. On the other hand, the $i$th level has $2^i$ nodes, so the total cost of each level is $n^2/2^i$.

  The height of the tree is $\log n$.

  Hence, summing the costs at each level we get

  $$\sum_{n=0}^{\log n} \frac{n^2}{2^i} = n^2\sum_{n=0}^{\log n} \frac{1}{2^i} \leq 2n^2$$ by the sum of an infinite geometric series. Therefore the total cost of the algorithm is $\Theta(n^2)$.

As far as I understand, we use Big-Oh to give an upper bound i.e it cannot get worse than this and we use Theta to prove a tight bound i.e when we have proved a lower and an upper bound.

However, here we have only proved an upper bound, so shouldn't the answer be $O(n^2)$?

Is this a specific case when it doesn't matter if we interchange Big-Oh and Theta?


texts: On the probability of randomized testing covering all combinatorial testing interactions

texts:
I'm interested in how fuzz testing and something called combinatorial testing. Combinatorial testing attempts to forgo exhaustive testing in favor of trying to test all possible "interactions" of a certain size. It's an interesting result that all interactions of a certain small size can be tested in far far fewer tests than the whole test space.
Define $V_n$ to be the set of binary vectors of size $n$, in other words $V_n = \{0,1\}^n$. This is intuitively the set of inputs that the tester might generate.
Define a $(k,n)$-template to be a subset of $\{0, ..., n-1\}$ of size $k$. Denote the set of $(k,n)$-templates as $I^k_n$. The intuition is that a $(k,n)$-template picks out $k$ variables out the $n$ variables.
Given a vector $v \in V_n$ and a $(k,n)$-template $T$ define $v[T]$ to be a new vector such that: $$v[T]_i = \begin{cases}
      v_i & i \in T \\
      2 & i \not\in T
   \end{cases}$$
The intuition is that $v[T]$ is the specific $(k,n)$-interaction that $T$ picks out from $v$. The $2$ is needed to account for a "don't care" value. Without it $[1,1,1,1][{1,3}] = [0,1,0,0][{1,2}]]$ despite those tests sharing no two way interactions in common.
The set of $(k, n)$-interactions of a subset $X_n \subset V_n$ is $X_n[I^k_n] = \{ v[T] \mid v \in X_n \land T \in I^k_n\}$. Ideally when testing we want to pick $X_n$ such that $X_n[I^k_n] = V_n[I^k_n]$ as this would be we have tested all $(k, n)$-interactions
If I sample $N$ vectors uniformly from $V_n$ to form a subset $X_n$ what is the probability that $X_n[I^k_n] = V_n[I^k_n]$?
Some values I've worked out partially so far (case 2 determined using inclusion-exclusion) but I think there might be a bug in what I wrote so forgive me if these aren't accurate.
$$p(X_{n}[I^1_{n}] = V_{n}[I^1_{n}]) = \prod_{i=0}^{n-1} 1 - 2\cdot\frac{1}{2^{N-1}}$$
$$p(X_{n}[I^2_{n}] = V_{n}[I^2_{n}]) = \prod_{i=0}^{n-1} \prod_{j=0}^{n-1} 1 - 4\cdot(\frac{3}{4})^{N} + 6\cdot\frac{1}{2^N} - 4\cdot\frac{1}{4}$$
The general form seems to be something with roughly the following form
$$p(X_n[I^k_n] = V_n[I^k_n]) = \prod^{n} \ldots \prod^{n} \sum_{i=0}^{2^k-1}(-1)^i{2^k \choose i}(\frac{2^{k}-i}{2^k})^N$$
I have a few questions about this

Is this conjectured formula correct? If not what is the correct formula?
This conjecture is essentially a probability exponentially close to 1 multiplied by itself a tower of exponential number of times. I just have no intuition for how on earth this scales. Is there some way to get an idea for how this scales with $n$, $k$, and $N$? Can we maybe lower and upper bound this by something more intuitive?
(bonus) Here I've assumed uniform random sampling from $V_n$ with replacement but many fuzz checkers will actually bias their sampling in various ways. For instance you might keep sampling until $|X_n| = N$ by sampling without replacement. It seems intuitively clear to me that sampling with replacement yields a lower $p(X_n[I^k_n] = V_n[I^k_n])$ than sampling without replacement but not by much. How can we tell if a given set sampling technique will be higher or lower than the assumed default of sampling without replacement?
(bonus) Is there some related area of math or theory I should take a look at that might give further insight?


texts: Calculus for Communicating Systems vs. Calculus of Communicating Systems

texts: Robin Milner uses both terms: Calculus for Communicating Systems and Calculus of Communicating Systems and, AFAIK, writes CCS for both. Is there any difference between the two? Is there a difference in semantics? Or is it simply British English vs. American English?


texts: Which part of the computer allocates memory in RAM?

texts: When we declare a variable there will be a random part of memory will be allocated in RAM. Which component will allocate the memory? Is the processor or any other specific hardware doing the allocation?


texts: What exactly would stop me from registering a domain from my own nameserver?

texts: Can I just make a nameserver and claim away? Are there implemented measures to stop this from happening?


texts:
Lets say Problem A,B are in NP.

Can we reduce Problem A to B? Meaning A $≤_p$ B? or A $≤_t$ B

Is there a difference in "hardness" of a Problem even in NP?

Or must Problem B at least be NP-Complete?


texts: Pagination of results from different sources merged by a unified scoring function

texts:
Assume a Hotel reservation scenario, given $m$ ranked lists of attribute values such as distance, price, amenities (normalized between $0$ and $1$), and a unifying linear score function $F(\cdot)=\alpha_1*score_1+ \alpha_2*score_2+ \alpha_3*score_3$, the Threshold Algorithm (TA) is optimal in finding top-$k$ results that have higher $F$ values.

However, consider a pagination scenario with page index $p$ and page size $k$. Indeed, instead of asking for top-$k$ that can be obtained from indices [0,k] in the final ranked list, we ask for [pk, (p+1)k]. What is the best solution to obtain this window of the results?

You may consider this problem as the pagination of the merged results over a unified scoring function when there are multiple data sources that each contains a score value but the merged results have a combined score value as a (linear) function of individual score values.

Some solutions:

Totally naive: given the multiple ranked results, compute the unified score, sort them, slice it as needed.

Potentially better but inefficient when asking lower-ranked results (farther pages):
Execute Threshold Algorithm and ask for top-(p+1)k, return the [pk, (p+1)k] from it.


texts:
Consider directed graphs. We call a node $v$ superstar if and only if no other node can be reached from it, but all other nodes have an edge to $v$. Formally:

$\qquad \displaystyle $v$ \text{ superstar } :\Longleftrightarrow \mathrm{outdeg}(v) = 0 \land \mathrm{indeg}(v) = n-1$

with $n$ the number of nodes in the graph. For example, in the below graph, the unfilled node is a superstar (and the other nodes are not).

[source]

How can you identify all superstars in a directed graphs in $\mathcal{O}(n)$ time? A suitable graph representation can be chosen from the usual candidates; please refrain from using representations that move the problem's complexity to preprocessing.

No assumptions regarding density can be made. We don't assume the graph contains a superstar; if there is none, the algorithm should recognize it.

Notation: $\mathrm{outdeg}$ is a node's number of outgoing edges, $\mathrm{indeg}$ similar for incoming edges.


texts: Will hardware/implementation affect the time/space complexity of algorithms?

texts:
I’m not even a CS student, so this might be a stupid question, but please bear with me...

In the pre-computer era, we can only implement an array data structure with something like an array of drawers. Since one have to locate the drawer with corresponding index before extracting the value from it, the time complexity of array lookup is $O(log(n))$, assuming binary search.

However, the invention of computers made a big difference. Modern computers can read from their RAM so fast that we now consider the time complexity of array lookup to be $O(1)$ (even it’s technically not the case, because it takes more time to move the register over a greater distance, etc)

Another example is Python dictionaries. While one might get a dictionary access complexity of $O(n)$ with an ill-written overloaded __hash__ magic method (or ridiculously bad luck, i.e. keys having lots of hash collisions), it’s usually presumed to be $O(1)$. In this case, time complexity depends on both the hash table implementation of Python dictionaries, and the keys’ implementation of the hash functions.

Does this imply that hardware/implementation can affect the time complexity of algorithms? (While both examples are about data structures instead of algorithms, the latter are built on the former, and I've never heard of time complexity of data structures, so I'm using the term "algorithms" here)

To me, algorithms are abstract and conceptual, whose properties like time/space complexity shouldn’t be affected by whether they’re implemented in a specific way, but are they?


texts: Why Shannon's Entropy is said to be a measure of information?

texts:
I got a bit of how Shannon explained to find the number of bits required to represent a message and Shannon's Entropy.But it's natural to know that to code alphabet letters you need 5 bits of information starting from 0000 to 11001.

Is that because at his time no one knew how to represent bits in information that Shannon came with looking at the unpredictability of the message to determine the number of bits needed to represent a message?

It's really getting confusing why would one need to consider terms like entropy,probability etc as said in Coding Theory to get the number of bits to represent a message when we already know that to represent 32 letters we need 5 bits.

Is there really any other reason behind why did Shannon came with these terms in the field of communication other than finding the number of bits required to represent a message?


texts:
By Burhman, Fortnow and Thierauf result Paper Link, we know that $MA_{EXP} \not\subset P/poly$.

Also, we know that $MA \subseteq P^{NP}$ (or $\Delta_{2}^{P}$ in some literatures).

By using the padding technique, we can conclude from this $MA_{EXP} \subseteq EXP^{NP} \not\subset P/poly$ and hence yielding a circuit lower bound for $EXP^{NP}$.

What is wrong with this argument?


texts: Why Do Computers Use the Binary Number System (0,1)? Why don't they use Ternary Number System (0,1,2) or any other number system instead?


texts:
Someone in a discussion brought up that (he reckons) there can be at least continuum number of strategies to approach a specific problem. The specific problem was trading strategies (not algorithms but strategies) but I think thats beside the point for my question.

This got me thinking about the cardinality of the set of algorithms. I have been searching around a bit but have come up with nothing. I've been thinking that, since turing machines operate with a finite set of alphabet and the tape has to be indexable thus countable, it's impossible to have uncountable number of algorithms. My set theory is admittedly rusty so I am not certain at all my reasoning is valid and I probably wouldn't be able to prove it, but it's an interesting thought.

What is the cardinality of the set of algorithms?


texts: Insertion sort on small arrays in Merge Sort

texts:
Quick question on the wording of the question from CLRS Ch2 Problems. The question goes as follows:

Although merge sort runs in $\Theta(n\lg n)$ worst-case time and insertion sort runs in $\Theta(n^2)$ worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which $n/k$ sublists of length $k$ are sorted using insertion sort and then merged using the standard merging mechanism, where $k$ is a value to be determined.

My question is: shouldn't there be $k$ sublists each of length $n/k$? The other way around is stated in the question. Because in merge sort, we keep halving the array, thus producing twice the number of arrays as in the previous level. Hence, each sublist is of length $n/k$ and we have $k$ of such sublists. Why does the question mention this the other way around?


texts: Can the lambda string be generated in any grammar?

texts:
I'm still quite new to regex, and I've seen topics online of people talking about removing lambda productions, but that has yet to be discussed in the class and the only formal definition of the rules in a grammar that I was given by my teacher:
$rule ∈ V$ $\times$ $(V ∪ Σ)^*$
where V is the set of variables and Σ is the set of terminals. Going strictly from this definition, I would assume I should be able to generate an empty string since V and Σ are both sets and that I believe the empty string can be generated from either of those sets.
For an exam I was given this definition of a grammar G:
$S \rightarrow  aS | Sb | a$
and I was later asked to write a regex that would represent this grammar. I figured that $S \rightarrow λ$ should be implicit. In other words, I should be able to generate the string 'b' from $Sb \rightarrow λb$
The regex I gave was $a^*b^*$
The T.A. marked it as incorrect because my regex can generate b, but the grammar G cannot, and because G does not have $S \rightarrow λ$
Can someone explain why $S \rightarrow λ$ would not be included in this grammar based on the definition of $rule ∈ V$ $\times$ $(V ∪ Σ)^*$?
Thank you!


texts: Graph algorithm to group nodes by level and group size

texts:
I have a directed graph representing some topics organized as follows (below screenshot is a subset of the graph):

I'm looking for an algorithm to group a set of nodes (in blue in the diagram) following this logic:

Groups as evenly sized as possible: we don't want groups with very few nodes and others with lots of nodes
If multiple groups have the same nodes, take the most specific group ie the group that's the closer successor

Now I know multiple solutions may exist for the same problem (eg 4 groups of 2 or 2 groups of 4?) but if there are existing algorithms similar to what I'm looking for I would be greatly if you can share their names so I can start testing them and see what works best for me and tweak them if needed.
Q: Do you know algorithms designed to perform similar types of node grouping?


texts: how to interpret the coefficients of binary logistic regression?

texts:
I'm working on a kNN classifier to classify whether a text is written by a man or a woman on the basis of the most frequent words. However, a kNN doesn't show which features were the most important in the classification. I got the suggestion to fit a logistic regression on my training data and labels to see which words were the most important in the classification task.

Now I have a list of the top 20 positive words and coefficients and top 20 words with negative coefficients. I do not know how to interpret these. I can see that the logistic regression has the classes F and M (don't know which one is 0 and which is 1), but is it possible to argue that the positive coefficients belong to the F class and the negative belong to the M class?


texts: Importance of contiguous allocation on flash disks

texts:
All file systems I know make significant efforts to try and allocate files in contiguous blocs on a disk.

But if the disk is an SSD using flash technology underneath, is there any benefit to contiguous allocation?  The only benefit I can see is in file systems like ext4 which use extents, in which case contiguous allocation is beneficial simply because it lets us describe the file's layout more succinctly, but it seems like a fairly minor advantage.

I guess another way to write this question is: do modern SSDs still perform better on sequential reads and writes than on scattered reads and writes?


texts:
There have been some nice papers about simple type inference for System F: "HMF: Simple Type Inference for First-Class Polymorphism", "Practical type inference for arbitrary-rank types", and "Complete and Easy Bidirectional Typechecking
for Higher-Rank Polymorphism". These algorithms require varying amounts of annotations from the user in order to do the type inference.
I am unable to find any papers on how to do type inference for System F-omega though. My questions:

Can the above algorithms be extended to handle System F-omega (maybe with some more required annotations)? Or do the type lambdas require a different approach?
Given that explicitly typed (Church-style) System F-omega is easy to type check, could we use one of the above algorithms to do type inference on the System F subset while requiring explicit types for the type lambdas, or do the type lambdas "infect" the other parts so that we cannot do this.
Is type inference for System F-omega simpler than type inference for dependent types or do they basically need the same techniques (higher-order unification)?


texts: How to do pixel array rotation whose angle not a multiple of 90 degree?

texts:
It is easy to rotate pixel array if the angle is a multiple of 90 degree.

For example, (quote from Computer Graphics with OpenGL)

  We can rotate a two-dimensional object or pattern 90' counterwise by
  reversing the pixel values in each row of the array, then
  interchanging rows and columns.

But I could not understand how to rotate pixel array when the angle is not a multiple of 90 degree from the textbook.

  Each desitination pixel area is mapped onto the rotated array and the
  amout of overlap with the rotated pixel areas is calculated.

Why does this means?


texts: MATLAB script to model biological branching process

texts:
I took an introductory MATLAB course a couple of years ago (and since then have only taken a basic C++ course) and am presently stumped as to how to start with a project I am undertaking. As part of this, I need to simulate the formation of branching structures using a branching annihilating random walk (BARW).

I am starting off with the 2D case. As a base, I have written a functioning basic script for a random walk (I really am starting with the basics!) and am trying to conceptually figure out how I will approach my task. The current idea I have is:

Create a large array which initially has null entries, except for the first entry which is the first 'growing tip'
Write a 'for' loop which essentially increments the time steps
For each time step, generate a random number. Divide the values consistently with the observed branching rate (the bifurcation rate vs elongation rate can be a variable parameter here) so that if the number is, say, less than 0.5, the tip continues to grow in its current direction. Otherwise, allow the tip to bifurcate with the branches going off in different (possibly random?) angles. The array will keep track of the tips (i.e. bifurcation will update the next zero row to a non-zero row)
I feel like it will be necessary to keep track of tip velocities here, probably in the array, and update tip propagation based on this. In this case, it no longer seems like a 'random walk'...
I also obviously have not yet accounted for the inability of tips to cross each other, but it already seems like the steps above have problems!

Again, I apologise I do not have a code to share. I am not yet proficient enough with programming to write code as I go, and have to have a conceptual plan of what I intend to do. Of course, this doesn't help if my steps are difficult/not possible to translate into code!


texts: Parity games and acceptance conditions of automata on infinite words

texts: I would like to understand the ideas behind parity games and their winning conditions. Where do they come from?


texts: Finding the minimum subset within a cycle

texts:
Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers defined in the interval $[c,d]$. Assume no two values are identical. For $(a,b)$, if $a > b$, the range is $[a,d] \cup [c,b]$; otherwise, it is $[a,b]$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

There exists an $O(n \log n)$ algorithm to find the smallest subset when, for any pair, $a$ is strictly less than $b$. I can run this algorithm for each pair to determine my solution. However, what is a more efficient algorithm to obtain the smallest subset?


texts: Why does the total credit associated with a data structure must be nonnegative at all times for the accounting method?

texts:
I was reading CLRS and it said in the chapter for the accounting method (for amortized analysis):

  the total credit associated with the data the structure must
  be nonnegative at all times.

where total credit is defined as:

  The total credit stored in the data structure is the difference between the total amortized cost and the total cost.

It also mentions the following:

  If we denote the actual cost of the ith operation by $c_i$ and the amortized cost of the ith operation by $\hat{c}_i$, we require:

  $$ \sum^n_{i=1} \hat{c}_i \geq \sum^n_{i=1} c_i$$

  for all sequences of n operations.

CLRS does provide an explanation of why it requires it but I am not sure I understand it. I will paste its explanation and explain my confusion:

  If we ever were to allow the total credit to become negative (the result of undercharging early operations with the promise of repaying the account later on), then the total amortized costs incurred at that time would be below the total actual costs incurred; for the sequence of operations up to that time, the total amortized cost would not be an upper bound on the total actual cost. Thus, we must take care that the total credit in the data structure never becomes negative.

So this is what I am confused about. When it says it requires $ \sum^n_{i=1} \hat{c}_i \geq \sum^n_{i=1} c_i$ to hold for all operations, does it implicitly also mean that it requires it for all $n \in \mathbb{N}$? i.e. its for all sequences of $n$ operations for all $n$?

What would be the deal if it didn't hold for all $n$? I tried reasoning this and I think it means that there exists some sequence that overall, is undercharged if we were to stop doing stuff at the end of that sequence. Thus, we wouldn't actually have a valid run-time analysis for this specific sequence of $n$ operations. Right?

I do think that it does mean for all natural numbers $n$ too. The reason I think this is because the way I think of the accounting method is that we have credit for later operations. If it was ever negative it means that some operation on the data structure at some point doesn't have actual enough "prepaid work" for some operation. Is this right or am I missing something?

Is the goal just that at all times for any sequence of any time that we always have an upper bound on the cost of $n$ operations? Regardless weather its charging, accounting, potential method etc, the goal is that always we have an upper bound on the cost of a sequence of $n$ operations?

So in this line of thought, if we do the potential method with:

$$ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$$

then because of the telescoping property, do we require for all sequences of operations that:

$$ \Phi(I_n) - \Phi(I_0) \geq 0$$

Since:

$$ \sum^n_{i=1} \hat{c}_i =  \sum^n_{i=1} ( c_i + \Phi(D_i) + \Phi(D_{i-1}) ) =  \sum^n_{i=1} c_i +  \Phi(D_n) - \Phi(D_{0})$$

since we need: $ \Phi(I_n) - \Phi(I_0) \geq 0$


texts: Regular expression for words over $\{0,1\}$ containing at least one 1

texts:
I had an exam on Theory of Computation, and one of the questions was to write down a regular expression for the language over $\{0,1\}$ consisting of all words containing at least one 1. My answer was:

$$ 0^* 1 0^* (0^* 1 0^*)^* \, . $$

My teacher gave me one mark out of 5, yet I can't find a possible string that will give false output here! His answer, which was $(0+1)^*1(0+1)^*$, was better, but mine works as well, I believe.

  Is my answer correct?


texts: Do all Cellular Automata have some kind of information boundary? Can all Cellular Automata be modelled with the Bekenstein Bound?

texts:
Since they are discrete models, do they have some kind of information boundary? Can all Cellular Automata models be related to the Bekenstein Bound?

https://en.wikipedia.org/wiki/Bekenstein_bound


texts: Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

texts:
I'm trying to reproduce the synthetic networks (graphs) described in some papers.

The topic is the same as a previous question of mine, but with a different focus.

It is stated that the Erdos-Renyi model was used to create $2$ networks with average degrees $\langle k_a \rangle$ and $\langle k_b \rangle$.

In the first paper, the average degree is $k = 4$ , while the number of nodes $n$ is 50000.

In the second paper the average degree is not called $k$, but it's stated that the mean degree is $1.999$ for $n = 200$ (in Fig. 2), while it is $2.45$ for $n = 4000 $ and $ n = 6000$ (in Fig. 7).

I looked for libraries implementing the Erdos-Renyi algorithm and they seem to require different parameters than average degree. One is NetworkX, another is igraph. They work in similar ways and ask for:

$n$ - number of nodes
$0 \leq p \leq 1$ - the probability for drawing an edge between two arbitrary vertices
$m$ - the number of edges in the graph (in alternative to $p$, only in igraph)

How can I calculate the settings to generate a graph with the same average degree as the ones described in the papers?

Here are the references:

Catastrophic cascade of failures in interdependent networks, Buldyrev et al. 2010, with a separately provided Supplementary Information
Small Cluster in Cyber Physical Systems, Huang et al. 2014
Catastrophic cascade of failures in interdependent networks, Havlin et al. 2010, this is on the Arxiv and somewhat clarifies the first

Note that these papers used generating functions to analytically study some properties of those graphs. However, they also run simulations on those models, so they must have generated those networks somehow.


texts: Are these three subset sum problems hard? How to solve them?

texts:
After asking this question I was thinking about some variants of subset sum problem (SSP).

The usual subset problem is the following.

Instance: Given a set of $n$ integers and an integer $\sigma$.
Question: Is there a non-empty subset that sums to $\sigma$?

The three variants of subset sum that I thought about are (I assume that all integers are positive):

SSP1:

Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
Question: Is there a non-empty subset of cardinality at most $k$ that sums to $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i=\sigma$ and $|S|\leqslant k$?

SSP2:

Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
Question: Is there a non-empty subset of cardinality at most $k$ that sums to at most $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i\leqslant\sigma$ and $|S|\leqslant k$?

SSP3:

Instance: Given a set of $n$ integers $\{a_1,\ldots,a_n\}$, an integer $k\leqslant n$ and and integer $\sigma$.
Question: Is there a non-empty subset of cardinality at most $k$ that sums to at least $\sigma$? That is a subset $S$ for which $\sum_{i\in S}a_i\geqslant\sigma$ and and $|S|\leqslant k$?

My question is: Are these problems (SSP1, SSP2 and SSP3) hard?

My claim is the following: SSP1 is NP-complete but SSP2 and SSP3 are polynomial-time solvable.

My Proof (intuitive and incomplete):

For SSP1, if I can find a subset $S$ of cardinality at most $k$, then $S\neq\emptyset$ and hence I have solved SSP.
For SSP2, sort $\{a_1,\ldots,a_n\}$ in the ascending order. Select the first $k$ elements. If their sum is less than $\sigma$ then we are done. Else remove the biggest elements of the selected $k$ elements and see. Continue.
For SSP3, sort $\{a_1,\ldots,a_n\}$ in the descending order. Select the first $k$ elements. If their sum is greater than $\sigma$ then we are done. Else output no.

Is my work correct?


texts: Distributed parallel computing algorithms for content dependent data

texts: I have implemented group of pictures parallelism for hevc encoding on distributed platform. In this we have to send different video chunks to different machines, these machines encode data in parallel and send data to master node. Here linear improvement in encoding is seen as number of nodes are increased. But now I want to further optimize this algorithm to get better results. Chunks I send to different machines might take different amount of time for encoding depending on content in that video chunk. So which algorithms in distributed parallel processing can be used here to optimize this process? To implement his system I am using OpenMPI framework.


texts: numeric stability of map reduce operations

texts:
I am building a small library for computing information retrieval metrics for classifiers (precision, recall, f1, accuracy, whatever). Typically each metric is built by calculating a single value for each object being classified (each metric will have its own formula there) and then calculating a single value (an average) aggregating all those single values; hence a mapper and a reducer.

With little formal training in numeric stability, I wonder what would be the most numerically stable way to calculate the average, and what might be the most interesting trade-offs between stability, avoidance of overflow, and computational complexity (performance).

Also any reference to a mathematical reading in this vein would be entirely welcome, for this, as well as for as similar future cases.

Thanks in advance!


texts:
I have this language

$L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$.

I have to determine a free context grammar that generates L.
Looks easy BUT i have a question about the grammar I found.
First things first, this is my grammar:

$S \Rightarrow BC$

$ B \Rightarrow aBbbb\ \backslash \ abbb $

$ C \Rightarrow Ccc \ \backslash \ cc$

Looks easy and clean to me. I already tested it with strings of different lengths and seems working just fine. Also it does indeed create only strings contained in L and no other strings.

My question is:

This is the first time I generate a grammar without any production containing $S$ itself (An example would be adding $S \Rightarrow B$ and I would solve my problem, because B generates only $a$'s and $b$'s and the number of this chars is dipendent between one another but indipendent with the number of $c$'s inside the string).

Recursively speaking, this works just fine but using $S$ would induce me to create a noncontracting language (because I'd be forced to invert some Non Terminals in order to produce both $a$'s and $b$'s correctly if something is wrong in my grammar).
Is this way of creating grammars correct? Can I describe what I wrote as an actual "grammar"? Is it context free?

Also, can I actually derivate $a$ through $B$ without a nonterminal $A$ and without generating it with the $S$ production?


texts: Is it possible to train a neural network to solve NP-complete problems?

texts:
I'm sorry if the question is not relevant, i have tried to search for articles about it but i couldn't find satisfying answers.
I'm starting to learn about machine learning, neural networks etc ... and i was wondering if making a neural network that takes a graph as input, and output the answer of an np-complete problem (e.g. the graph is hamiltonian / the graph has independant set superior to k, and other decision problems) would work ?
I haven't heard of any np complete problems being solved like this, so i guess it does not work, are there theoretical results stating that a neural network cannot learn np-complete language or something like this ?


texts: How the kernel works in a LCF theorem prover

texts:
I heard that there is some mechanism in LCF-based theorem provers that only allows some functions to create values of type theorem. I believe these are based on abstract data types.

Could someone sketch in pseudo-code how does this work? (in case the above is correct)


texts: “Left identity” of Monad laws in Haskell is wrong

texts:
Monad laws in Haskell

Left identity:  return a >>= f ≡ f a
Right identity: m >>= return ≡ m
Associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

is widely known, and I think the "Left identity" rule does not make sense.

In category theory, it is true that Monads corresponds to Monoid, but this "Left identity" is twisting things around.

the binary operator >>= is a notation, so is f a or f(x) etc..

f(x)
f a
m >>= f
monad.bind(f)

In program semantics, all are the same, especially, when we define f always returns a monad value.

It's like "1" and "One" means the same entity in mathematics.

1 ≡ "One"  // Some Identity!
// this rule must be satisfied in terms of category theory!??

So-called "Left identity" in Haskell Monad law: return a >>= f ≡ f a is nothing to do with category theory but simply notation.

On the other hand "Right identity": m >>= return ≡ m makes sense because according to the notation replacement, it can be rewritten to return m ≡ m, and surely this defines one of monad feature or a rule of identity.

(edit)

TTX = TX
unit(unit(a)) = unit(a)
return m ≡ m

whatever, the semantics is the same.

In the later part of [Monad laws in Haskell][1], it makes an excuse saying

  Not in this form, no. To see precisely why they're called "identity laws" and an "associative law", you have to change your notation slightly.

then, it introduces "Kleisli composition operator" : >=>.

What?? The different operator is introduced, then they concluds:

  This is a very important way to express the three monad laws, because they are precisely the laws that are required for monads to form a mathematical category.

The widely known "Haskell monad laws" are based on the bind binary operator: >>=, but in fact, the "left identity" rule is nothing to do with catrgory theory but merely programming notation replacement, then later, by replacing the bind operator to "Kleisli composition operator" : >=>, it claims the notation replacement is based on category theory.

I think this fools the readers and is the source of confusion of Monad concept to beginers or all of us.

Probably, I also need to mention that this Monad laws are firstly fomalized  in Monads for functional programming by Philip Wadler

EDIT:

Well, I do not deny return a >>= f ≡ f a is a binary operator definition. It's a replacement of notation, and here is the thing.

notation replacement is nothing to do with category theory or "Left identity"  `


texts: Deciding whether CFG generates the empty word

texts:
Give an algorithm to decide the following problem: given
a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it
generate the empty word? How can I make sure my algorithm is decidable?


texts: For which level of PH is $\operatorname{VALID}$ complete

texts:
I have the decision problem $\operatorname{VALID}$ which is the set of all valid propositional formulas (tautologies), I know that $$\overline{\operatorname{SAT}}\equiv_m^p \operatorname{VALID}.$$
This can easily be seen by changing instances of each problem into their logical negation, then a formula is a tautology iff its negation is not satisfiable.

My question is now, for which level of the polynomial time hierarchy PH is $\operatorname{VALID}$ complete. Here a quick definition of PH

$$  \Sigma_0 = \Pi_0=\operatorname{P},\quad \Sigma_{n+1} = \operatorname{NP}(\Sigma_n),\quad  \Pi_{n+1} = \operatorname{co}-\Sigma_{n+1},\quad \Delta_{n+1} =  \operatorname{P}(\Sigma_{n}).$$

I made the following observations: $\overline{\operatorname{SAT}}\in \operatorname{co}-\operatorname{NP}$, so that by the reduction given earlier we have that $\operatorname{VALID}  \in \operatorname{P}(\operatorname{co}-\operatorname{NP})= \operatorname{P}(\operatorname{NP}) = \Delta_2$. So my quess would be that the first level of PH for which $\operatorname{VALID}$ is complete is $\Delta_2$.

If $\overline{\operatorname{SAT}}$ is hard for $\operatorname{co}-\operatorname{NP}$ then I think the result follows, but I cannot seem to corroborate this with solid arguments.

Also, the reduction given seems so simple ($\phi \mapsto \lnot \phi$) that it seems that the class $\operatorname{P}(\operatorname{co}-\operatorname{NP})$ might be a bit overkill.

I would be grateful for any shared insights into this problem.


texts: Testing whether a tetrahedron lies inside a Polyhedron

texts:
I have a tetrahedron $t$ and a polyhedron $p$. $t$ is constrained such that it always shares all its vertices with $p$. I want to determine whether $t$ lies inside $p$.

I would like to add one detail to the problem in case it may contribute to the solution: $t$ is a Delaunay tetrahedron and faces of $p$ are triangular and are strongly Delaunay both with respect to vertices of $p$. A tetrahedron is Delaunay if circumsphere of its vertices contains no other vertex inside it. A face is strongly Delaunay if there exists a circumsphere containing vertices of that face on its surface but no other vertex on or inside it.

Following figures show the same problem in $2D$ space:

The original polygon $p$:

Delaunay triangulation of vertices of $p$:

Result of inside/outside test over triangles $t$(Shaded triangles are inside $p$ and rest are outside):

Desired result(pruning outside triangles):

My original problem is in 3D space so triangles $t$ in above figures translate to tetrahedrons and polygon $p$ translates to an arbitrary polyhedron $p$. I have figured out some formulations of this problem:

Formulation 1
The only parts of $t$ which can be outside $p$ are its edges and triangular faces but in general there may exist a $p$ which has edges of all outside $t$'s on its surface, so alternatively, this problem may also be formulated as to test whether for a tetrahedron $t$ there exists a face which lies outside $p$?

Formulation 2
I have another possible perspective towards this problem but lacking any formal idea:
Geometrically, if $t$ is outside then it will always be sticking on the outer surface of $p$. So if we can compute the contours(informally, the outer boundary)  $C_{V}$ and $C_{V_{p}}$ such that $V=V_{t}\cup V_{p}$ and $V_t,V_p$ are sets of vertices in $t,p$ respectively, then $C_{V}=C_{V_p}$ iff $t$ lies inside $p$.

I would like to know:

How can I solve either of Formulation 1 or Formulation 2?
Or, is there any completely different approach to solve this?

Update:
I now realize that this problem can be reduced to Point in polyhedron problem. Since an outside tetrahedron $t$ will have at least one face which lies outside $p$, so any arbitrary point on that face(except its vertices,in general) will always lie outside $p$. Therefore, for each face of $t$, I need to take an arbitrary point and test if that point lies outside $p$.

From point in polygon article I came to know about Ray casting algorithm and Winding number algorithm. Ray casting is not numerically stable for cases where point lies on the surface of $p$. But numerical robustness of Winding number algorithm has not been addressed there.

Based on above, my core problem now seems to be(please suggest if it should be asked as a separate question):
Is there any numerically robust algorithm for point in polygon problem?


texts: How can I prove that for every NFA with $\epsilon$ moves if $q_0 \in F$ then $\epsilon \in L(A)$? I can't think of any technique since it seems so trivial.


texts: Does the complexity of strongly NP-hard or -complete problems change when their input is unary encoded?

texts:
Does the difficulty of a strongly NP-hard or NP-complete problem (as e.g. defined here) change when its input is unary instead of binary encoded?

What difference does it make if the input of a strongly NP-hard problem is unary encoded? I mean, if I take for instance the weakly NP-complete Knapsack problem, it is NP-complete when binary encoded but can be solved in polynomial time by dynamic programming when unary encoded. Maybe it has some implications for hardness of higher levels of the polynomial time heirarchy?

Does the notion of strongly ...-hard also hold for other complexity classes, e.g. higher classes of the polynomial time hierarchy?

I previously asked this question at stackoverflow.com but it was pointed out that it is more appropriate here.


texts: Problems with proven complexity but no algorithm yet found

texts:
Does there exists a computable problem P such that:

Is proven that P can be solved with an algorithm that has a certain complexity.
The best algorithm know unluckily is still slower (greater complexity) than the proven bound.

Example:

A problem that we have proven can be solved in worst case in $O(n^2)$ operations.
The best algorithm that's currently known runs in $\Omega(n^3)$ time.


texts: LALR(1) parsers and the epsilon transition

texts:
I am having trouble getting my head wrapped around epsilon transitions while creating an LALR(1) parse table.

Here's a grammar that recognizes any number of 'a' followed by a 'b'. 'S' is an artificial start state. '$' is an artificial 'EOS' token.

0.    S -> A $
1.    A -> B b
2.    B -> B a
3.    B -> epsilon

Itemsets:

i0: S -> . A $
    A -> .B b
    B -> .B a
    A -> B . b  ! because B could -> epsilon
    B -> B . a  !    "

i1: S -> A . $

i2: S -> A $ .

i3: A -> B . b  ! from i0
    B -> B . a

i4: A -> B b .  ! from i0 or i3; the LALR algorithm compresses identical states.

i5: B -> B a .  ! from i0 or i3: the LALR algorithm compresses identical states.

I previously had a description on how this would work to parse a simple string. I removed it because I know less now than I did before. I can't even figure out a parse tree for 'ab'.

If someone could show me how I have mis-constructed my itemsets and how I'd reduce the epsilon transition I'd be grateful.


texts:
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which are decided by deterministic or nondeterministic log-space Turing machines, respectively. The two-way Turing machines may move their head on the input tape into two-way (left and right directions) while the one-way Turing machines are not allowed to move the input head on the input tape to the left.

Hartmanis and Mahaney have investigated the classes $1L$ and $1NL$ of languages recognizable by deterministic one-way log-space Turing machine and nondeterministic one-way log-space Turing machine, respectively. They have shown that $1NL \subseteq L$ if and only if $L=NL$.

See the paper here(it is free to download):

https://ecommons.cornell.edu/handle/1813/6253

I wonder this question:

Is $L \subset 1NL$ when $L \neq NL$?

Moreover, I wonder this another question:

Is there any reference that shows whether at least one of the options $L \subset 1NL$ or $1NL \subset L$ or $L = 1NL$ should be true?

Thanks in advance!!!


texts: How do learn the most important nodes in a tree?

texts:
I have a list of 20000 words and how often they appeared in a set of 500 newspaper articles.  I am trying to build a stemmer which chops off suffuxes from each words, so walked, walking, walks are the same word.

In English, the Porter Stemmer is a rule-based system where you repeatedly chop off suffixes:

    CONNECTIONS
    CONNECTION
    CONNECT

I am concerned if I do this for my collection of Spanish words and articles, I may not have a complete list of rules or it may be prone to other forms of error.  So I had proposed to learn the suffixes.

Right now, I just count the appearances of each suffixed up to 4 letters.  Here is the result the most common last letter in my vocabulary list:

 u'a': 58189
 u'd': 3183
 u'e': 62971
 u'i': 1725
 u'l': 26374
 u'n': 37823
 u'o': 46786
 u'r': 16833
 u's': 57396
 u'u': 2639
 u'y': 2212
 u'z': 1968
 u'\xe1': 1813
 u'\xf3': 6722

The last letters a and o are obvious things to stem since they indicate masculine and feminine.  However o could also be the 1st person singular of a verb.  a could be the 3rd person singular.

e and s are also obvious choices to stem.  Let's look at the last 4 letters:

 u'ados': 1826,
 u'ales': 1633,
 u'ando': 1291,
 u'ante': 1062,
 u'aron': 1027,
 u'ci\xf3n': 5355,
 u'ente': 3084,
 u'ento': 1690,
 u'erto': 1061,
 u'idad': 1749,
 u'ncia': 1362,
 u'ntes': 1511,
 u'ones': 2845,
 u'ores': 1050,
 u'si\xf3n': 1127

These are very common Spanish suffixes, appearing more than 1000 times in my corpus.  Should I stem them?

How do I choose a data set which handles the suffixes of different sizes and decides which ones are the most "significant" ?


texts: Why was R designed as a 1-starting indexes language?

texts:
Spawning from here:

  We usually don't care whether indices start at $0$ or $1$ (except in the sense we'd rather start with our favourite if it doesn't matter, and the old joke is that set theorists start at $0$ and non-Peano number theorists start at $1$). I say usually, because there are a few cases where we do:

  [...]
  [...]
  If there's programming involved, use the same indexing for your mathematical exposition as in the code itself, which varies by language. For example, Python starts at $0$, whereas R starts at $1$.

Why did they choose to start from $1$?


texts: Is there a faster than O(n^2) solution for Box stacking problem?

texts:
The Box Stacking problem is as follows:

  You are given a set of $n$ types of rectangular 3-D boxes, where the
  $i^{th}$ box has height $h_i$, width $w_i$ and depth $d_i$ (all real
  numbers). You want to create a stack of boxes which is as tall as
  possible, but you can only stack a box on top of another box if the
  dimensions of the 2-D base of the lower box are each strictly larger
  than those of the 2-D base of the higher box. Of course, you can
  rotate a box so that any side functions as its base. It is also
  allowable to use multiple instances of the same type of box.

Is there a solution faster than the $O(n^2)$ solution given here?


texts: Natural Language Parser that can handle syntactic and lexical errors

texts:
I have some background in natural language processing and I know that all parsers (top down or bottom up, or mix), at least when I studied just about a few years ago, cannot handle any error. A small error like a grammatical one or a spelling one will result in unexpected parsed tree.

This is unacceptable in natural language in most cases. Thus I have been trying to find a way to make a new one with a different approach.

The basic general abstract idea is that I will use a top down dynamic programming approach.
Given a string of text with $n$ tokens, several top down fillers will be generated. These fillers will look at the tokens to see if they can find and fill constituents that they are missing. Because of this, these fillers might leave gap after they have found everything they need. This is supposed to make the parser more robust.

An example will be best to illustrate this idea:

Given the sentence: I saw the ordinary thing.

One top down filler can be. $S \rightarrow Subj - Verb - Object$.
This filler will try to look for span that it can use to fill its expectation of seeing a $Subject$ followed by $Verb$ and $Object$. This means it will deployed three other fillers in sequence. The first one is $Subj$. This filler will scan and add to the cache three possible subjects which are $I$, $saw$, $thing$. $I$ is put in span $[1,1]$, $Saw$ in span $[2,2]$, $thing$ in span $[5,5]$. This will result in a total of three potential pending parse trees. Then with each of these pending parse tree, $Verb$ filler is deployed to scan the span after each possible subject. $Object$ filler is deployed to scan the rest.

With the above approach, sentences such as I .. eh... saw the big thing
or similar constructs do not cause problem because fillers look for what they need and fill them into the tree. This problem is dealt with when all fillers have completed. Fillers that leave lot of gaps (unused tokens) will not generate parses having high score compared to parses generated by fillers that use up all tokens.

This is also my approach to deal with subject-verb agreement and male-female as well as singular-plural agreement. You deal with them at the ranking stage so that you can give your parser much better error tolerance. Sentences such as Maybee they ehh can get something can still be parsed. One resulting parse will just not use Maybee. The top parses will then be used again, this time to look for unused tokens. Unused tokens will be processed with spelling correction, did-you-mean style. One can see how it works with incorrect sentences like This is a valide argument. Even incorrect sentences like They did got it are still parsed ok.

There will be other fillers which cannot find all they need such as conditional sentence filler. $CondS \rightarrow "If" - S - ["then"] - S$. Some filler such as imperative $ImpS \rightarrow ["Please"] - Verb - Object$ will complete most of the times because it can find all it needs abeit leaving gaps, but then it is a ranking problem to make sure that the correct one is returned.

So my Question is:

Has anyone ever thought of this approach? Any reference papers?
If nobody used it before what may be the potential problem?


texts:
Here sum of a geometric, where c is a positive real number.

$g(n)=1+c+c^2+...+c^n$

$\theta(1)$ if $c<1$

Any idea to solve this?


texts:
I am a bit confused on how I can show the finiteness problem is undecidable using Rice’s Theorem.

So I’ve got something like B = { | M is a TM and L(M)- finite}. I thought I could reduce A TM (determine whether a TM accepts a given input which I already know is undecidable) to B but then I’m not sure how I would construct/ describe a new Turing Machine that decides my A?


texts: A special case of the SUBSET SUM problem

texts:
Consider the following special case of SUBSET SUM

Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary.
Encoding: These inputs (compactly) encode a list $L$ of length $2^k$ where there are exactly $\binom{k}{i}$ terms of the form $a^{k-i}b^{i}$, for $i=0, \dots, k$.
Output: Is there a subset $D$ of $L$ whose sum is precisely $t$?

A certificate for this problem is a list $(n_0, \dots, n_k)$, where $n_i$ is the number of terms of the form $a^{k-i}b^{i}$ that exist in $D$. Assuming that $k$ is given in unary, such a certificate can be verified in polynomial time.
Any thoughts on whether this problem might be NP-Hard?
The setup is quite strange since even though the problem is closely related to subset sum, the inputs $a,b,k$ encode a list $L$ that is long, so it is not entirely clear how or if a connection exists.


texts: Measuring difference between two sets of neural network weights?

texts:
Suppose that we take a neural network of a given topology, and run it through two training processes, obtaining two different sets of converged weights at the end of the training.

What is a good way to measure the difference between the two sets of weights?

If this were a curve-fit where the parameters were largely orthogonal, we could simply treat the parameters as a cartesian space and compute the length of the vector difference between the sets.

However, the weights in a neural network are often not at all orthogonal.  There are trivial redundancies, in that we can reorder nodes within a layer, or multiply the input weights to a given node by a constant factor and the output weights by its inverse.  Even if we remove these by putting the weights in some canonical form (normalizing and sorting them, for instance), I can't see any reason to assume that we won't have plenty of remaining non-orthogonality.  As a result, two sets of neural-network weights that have a large vector-difference length may be essentially equivalent in practice.

An alternate conceptual approach would be to numerically integrate the difference between the output values over the entire input space, but for typical neural networks this space has high enough dimension for such an integration to be intractable.  So we'd need to do some sort of sampling-based approach, which introduces more handwaving about whether it's a meaningful measure.

Is there any existing consensus on what's a good measure?  Or, for that matter, any existing practice for what other researchers have used?


texts:
A recent exam question went as follows:

  $A$ is an infinite recursively enumerable set. Prove that $A$ has an infinite recursive subset.
  Let $C$ be an infinite recursive subset of $A$. Must $C$ have a subset that is not recursively enumerable?

I answered 1. already. Regarding 2., I answered affirmatively and argued as follows.

Suppose that all the subsets of $C$ were recursively enumerable. Since $C$ is infinite, the power set of $C$ is uncountable, so by assumption there would be uncountably many recursively enumerable sets. But the recursively enumerable sets are in one-to-one correspondence with the Turing machines that recognize them, and Turing machines are enumerable. Contradiction. So $C$ must have a subset that is not recursively enumerable.

Is this correct?


texts: How To Solve TSP With Multiple Routes, Visits And Constraints

texts:
I've got an TSP problem which I can't seem to solve somehow. It consists of about 1200 addresses for which all distances (measured in seconds) between them, a frequency (once a week, twice a week, 3 times a week etc...) and cargo-weight are given.

I've looked into TSP solutions, but they only seem to offer ways to calculate the shortest route, not divide addresses over multiple routes.

I should divide these addresses over 5 days based on their frequency. Then for every day I should devide the adresses over 2 routes for a cargo-truck to drive.

Furthermore there are 3 constraints:

All routes should start and end at the same given address.
There is a maximum distance which all routes must not exceed.
A truck has a maximum cargo-space which it should not exceed, if it does the truck should go back to the starting point to pick up the rest of the cargo and then continue with its route.

I've tried solving this problem by constructing a TSP algorithm that consists of greedysearch as an initial route, and then proceeds with localsearch to find a local optimum. Then I'm trying to swap addresses between routes and checking whether the total distance has decreased afterwards.

I can check (optimize and find its distance) one set of routes in about 10-20 seconds, by using multi-threading. I could potentially reduce this by only checking the distance between the nodes that have changed (instead of the entire route), but even then I don't think it would affect the execution-time much since there are only ~120-130 nodes in every route and dictionary-lookups aren't that slow after all). And as you can probably imagine by now, this is so incredibly slow that it won't seem to solve the problem at all.

So far I haven't been able to find a solution that comes anywhere close to the target distance (I've managed 8000 without the constraints whereas it should be below 6000 with constraints) . This has all been WITHOUT implementing the constraints mentioned earlier (which should probably be done by applying certain penalties for constraints that aren't met).

What would be a smart/good way to approach this problem?

Thanks in advance!


texts: Solving the recurrence $ T(n) = \dfrac{T(n-1) + T(n-3)} {T(n-2)} $

texts:
What's the (asymptotic) solution of the following recurrence?
$$ T(n) = \frac{T(n-1) + T(n-3)} {T(n-2)}. $$
I tried to solve this with generating functions to find an accurate bound.


texts:
I've been reading about how the kernel manages memory in x86 from this popular blog post(https://manybutfinite.com/post/how-the-kernel-manages-your-memory/) and had a few questions.

There is a part where the author describes page table entries and their associated fields. To quote "This lack of a PTE no-execute flag illustrates a broader fact: permission flags in a VMA may or may not translate cleanly into hardware protection. The kernel does what it can, but ultimately the architecture limits what is possible.".

I looked into the kernel source and found that the NX bit in modern systems is actually the most significant bit. Is this because modern hardware now supports NX?

If I tried to execute code on the stack with NX enabled, I crash, but what actually happens? Does the kernel check the page permissions on every execute? That seems really slow. Is it the hardware that knows if I can/cannot execute? If so, how does the hardware know. Does this have anything to do with the CS segment selector?


texts: If $\{ww^R \mid w \in L\}$ is regular, is $L$ itself regular?

texts:
If $L$ is some language and
$\{ww^R \mid w \in L\}$
is a regular language then does $L$ have to be a regular language?


texts: Simulating extensible sums with dependent types?

texts:
ML-style languages have a concept of "extensible" or "open" sum types, where variants can be declared at any point, and there's not a fixed number of constructors for the type. They're usually used to model exceptions and handling, where users can declare their own exception types.

I'm wondering, is there a way that we can encode an extensible sum type using dependent types (lacking a primitive for extensible sums?) This seems like the sort of thing we could get away with when we mix types and terms, but I haven't been able to find any references.

Thanks!


texts: Doubt regarding address calculation in two-dimensional arrays

texts:
I am reading about the address calculation formulas for one and two-dimensional arrays.             I have two related doubts concerning it.

In one of the problems, we are asked to calculate the location of B [1700] for an array B [1300....1900].
Now, I understand that B [1700] is actually the 401th element in the array (correct?), so we can calculate its address.

But in another problem, we are given an array X [-15....10,15.....40] and are asked to determine the location of X [15][20] but I don't see how it is even a part of the array since the "row" subscript(i.e. 15) is not contained in (-15....10). (According to me the last element of this array is X [10][40]).

My second doubt is: In another question, we are given the array M[-3......18,-8......7] (stored column-wise where width of element = 8 bytes) and are asked to calculate the base address given that the address of element M [5][10]=4000.

The solution proceeds as -

  M [5][10] = BA + W*(M*(j-Lc)+(i-Lr)) therefore, M [5][10]=4000 + 8*(22*(10-0)+(5-0))

i.e. my book answer takes Lc = 0 & Lr = 0 but I think it should be Lc = -8 and Lr = -3? So, which is it?
Also can I write a program in which I can verify this for myself (specifically, how can I declare an array in c++ whose subscript doesn't start at 0?)?
Thank you so much.


texts: Finding maximum-cardinality independent set with a particular oracle

texts:
We suppose we have a polynomial algorithm which receives a graph $G$ (any graph) and returns a stable set of $G, SA(G)$ with the following property:

$\alpha(G) − |SA(G)| \leq k$ , for every natural $k$ ($k$ is a constant)

$\alpha(G)$ is the stability number

I need to show that this algorithm can be used to find(in polynomial time) a stable set (of maximum cardinality) in a graph.

I discovered that if I give $k=0$ then we get to this relation. But does that mean that the algorithm finds the stable set with maximum cardinal.


texts: How do you find the union of the the unit squares contained in a polygon?

texts:
The Problem:

Suppose you have a simple polygon (edges don't cross).  Find the union of of all 1x1 squares that fit in the polygon.  To be clear, I am asking for the union of all points that are in some square that fits into the polygon.  Maybe the border of this union can be expressed as a shape whose edges are line segments and arcs of circles.

Motivation:

I am working on a computer vision project where I find beds in birds-eye-views of rooms.  I have a filter which fairly effectively removes the floor and the wall from consideration.

I would like to apply a filter on the remaining data that throws out points that cannot be in a bed-sized rectangle contained in the stuff that's left from my first filter, but does not throw out the bed.  It leaves some extra stuff as well.

I have written an iterative approximate solution.  Specifically, it discretizes the set of angles it tries.  I imagine that an exact solution could be faster as well as more precise.

To make the problem more appealing and perhaps more doable, I have only asked for fitting unit squares in the polygon.  I would be happy to know the solution to the more general problem of an arbitrary fixed-size polygon.

Thanks for any help you can provide!


texts: Comparing random access and sequential access

texts:
Assume that we choose randomly $k$ distinct numbers $N_1$, $\dots$, $N_k$ in $\{1, \dots, k\}$ and we have a file of $k$ parts. We have these two cases :

We read (or write) sequentially from part $1$ to part $k$.
We read (or write) the part indexed $N_1$, then the part indexed $N_2$, ..., and the part indexed $N_k$.

Have these two cases the same complexity in the RAM model?

In which model these two cases don't have the same complexity?


texts: Determine whether two collections of items can be paired

texts:
Given collections I (items) and S (slots), where I >= S.
And a pairing function that determines whether a slot can accept an item.

Is there an efficient way to find whether a "complete" pairing of items to slots exist, where "complete" means every slot is filled?

(More importantly for my use case... is there a way, other than trying every combination, to determine if no such pairing exists?)


texts:
I was watching the AI Stop Button Problem from Computerphile, and was very confused on the difference between two approaches.

Background: there is a barebones general intelligence running in the form of some robotic device. The device acts in accordance to optimize some utility function. The GI is asked to make tea, and this is the dilemma of how it will choose to press its stop button rather than make tea if the two are given the same reward, as pressing its stop button is easier and yields the same reward as making tea for the programmer.

One approach to try and get the GI to not care about the stop button is to set the reward function of pressing the button equal to what it's trying to achieve (let's say it gets 100 reward to make tea and 100 reward if the button is pressed).  Then, he explains how this will cause the robot to hit its own button immediately, because it's the same reward but easier than making tea  (explained 5 minutes in). If we tried making the button something only us humans can hit, then it would try to slap us immediately, threatening us into hitting the button, as slapping us to hit the button would also be easier and give us the same reward as getting the tea (explained 9 minutes in).

Then, at 10:00, it says that another, better approach is to define the utility function is set with an adjustment term to make the value of utility of the button being pressed and not being pressed would be, theoretically, exactly equal, so that it would be indifferent to the button being pressed.

I don't see how this second approach is different than the first approach. If, in the second approach, the utility function is defined so that the button being pressed and not pressed is equal, isn't that the same thing as giving 100 reward to make tea and 100 reward if the button is pressed? Wouldn't this supposedly better solution still cause the robot to either press its own button if possible, or slap you to threaten you to press its button? Because they both yield the same utility, but slapping or hitting its own button is easier than what it wants to achieve in life.


texts: What is the recurrence form of Bubble-Sort

texts:
I understand how bubble sort works and why it is O(n^2) conceptually but I would like to do a proof of this for a paper using the master theorem.

As an example: The recurrence form for merge sort is T(n) = 2T(n/2) + O(n) which, using the master theorem, gives us O(n log(n)).

I am unsure of how to do this process with Bubble sort. What equation allows us to see that it is O(n^2)?


texts: Infinite Boolean circuits as a model of computation

texts:
Boolean circuits are non-uniform models of computation in that they require a different circuit for each length of input. The typical way of uniformizing a family of Boolean circuits is to define a Turing machine that can output, for some input length N, the correct Boolean circuit for that N.

However, I wonder if it is instead possible, if not a bit abstract, to instead look at finite Boolean circuits that "converge" to some well-defined infinite circuit in the large limit of N, which can handle any input size of arbitrarily large but finite length, and get an equivalent model of computation.

My intuition is that this is often the case, because it is quite common for Boolean circuits to be able to handle not only their own input size, but all smaller input sizes as well. For example, an adder that works on inputs of N bits can handle inputs of length < N by zero-padding the highest undefined bits; this is equivalent to setting the undefined bits to zero by default. So we can easily imagine this series of circuits converging to something like ripple adder extending infinitely to the left, and for which we consider only those inputs with finitely many nonzero bits.

What I am really trying to understand is the simplest way to extend the notion of Boolean circuit to get something that is Turing-complete. For example, we can give a finite state machine an infinite queue and make it Turing complete. By looking at infinite Boolean circuits that can handle arbitrarily large input with finite support, can we likewise obtain Turing-completeness, with an analogue of the halting problem, etc? If not, how could we do it?


texts: Pumping Lemma for CFL - $ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $

texts:
I was making exercices about the Pumping Lemma for CFL, and I stumbled up on this language:
$$ \{ 0^{i} 1^{j} 0^{k} 1^{l} \hspace{0.2cm}| \hspace{0.2cm} i = l \hspace{0.2cm} \land j = k \} $$
I quickly made a CFG that represents that language (or so I believe):
$$ S \to 0S1 \hspace{0.2cm} | \hspace{0.2cm} A  \\
   A \to 1A0 \hspace{0.2cm} | \hspace{0.2cm} \epsilon
$$
The problem is that I began to think if the Pumping Lemma would hold (it should since I have a CFG for the Language, so it must be a CFL).
(Having the Pumping Lemma in mind) I chose a word, w = $ 0^{n}1^{n}0^{n}1^{n} $. I immediately stopped because this word will not pass the Pumping Lemma (it can be used to demonstrate that $  \{ ww \hspace{0.2cm}| \hspace{0.2cm} w \in \{0,1\}^{*}\}$, the language of duplicated words, is not a CFL, I have done it before)
Now I'm stuck with a Pumping Lemma that fails, and a CFG that produces the language and don't now what to do.
I tried to come up with a word that the grammar couldn't produce and failed, I tried to invalidate the PL but failed (there are no restrictions that tells that the word cannot have all segments of the same size, so $w$ is in the language).
As far as I know If the PL holds, the language doesn't have to be a CFL, but if it fails is absolutely unquestionable that the Language is not a CFL.
What I'm I missing?


texts:
Q) Consider the following program fragment:

var x,y:integer;
x:=1; y:=0;
while y < x do
begin
  x:=2∗x;
  y:=y+1;
end;

For the above fragment , which of the following is a loop-invariant ?

A) x=y+1
B) x=(y+1)2
C) x=(y+1)2y
D) x=2y
E) None of the above, since the loop does not terminate

Since, Loop-Invariant is something which is true before and after each iteration of a loop. So, according to the definition, I am getting answer as (D) but I have a doubt whether termination of that loop is necessary or not for the given code. One of the properties of algorithm says :- algorithm should always terminate after finite no. of steps. So, if the question is about Pseudocode then I will definitely mark answer as (D) but since it is program fragment, So I am confused between options (D) and (E).
So, My Doubt is definition of loop-invariant is also true for the loop in the code which is written in any language like C,C++ etc.
Please help.


texts: Calculate the computational complexity of multiplication AxAT

texts:
I need to implement an algorithm that calculates the symmetric matrix obtained by performing $A A^t$ being $A^t$ the transpose of $A$.

I did my analysis from two perspectives:

The first thing I notice is that it is not necessary to have more memory to have $A^t$ because it is the same as $A$, what changes is the "rotation". Therefore I not need store $A^t$ whether it can be "creative" and "intelligent" to iterate over the row / column properly in $A$.
The 2nd, what is known is that the symmetric matrices have the particularity that the elements of the upper and lower triangular (discounting the diagonal) are equal. Then, simply calculate the upper triangular and then "copy" the value of the position "transposed" in the lower triangular.

From what little I remember of the theory of computational complexity, traditional matrix multiplication $A B = (m\times n)\times (n\times p) = (m\times p)$, has complexity $O(mpn)$. If $A$ and $B$ are square everything is reduced to $O(m^3)$.

For my scenario where $A$  is $m\times n$ and recognizing that the symmetric matrix $S = A A^t$ is square, the expression reduces to $O(m^2n)$, but I can also be symmetrical save half the calculations: $O ((m^2n)/2)$. Until there more or less I think I'm doing OK.

The point is that I implemented two algorithms and can not remember as we proceed to analyze T() and thus see what could be more optimal. Hoping that one could guide me on how to estimate T():

Algorithm 1:

for i = 1..m do:
  for j = i..m do:
    if i = j
      then for k = 1..n do:
             S(i,j) = S(i,j) + A(i,k) * A(i,k)
      else begin
             for k = 1..n do:
               S(i,j) = S(i,j) + A(i,k) * A(j,k)
             S(j,i) = S(i,j)
           end

Algorithm 2:

for i = 1..m do:
begin
  for k = 1..n do:
    S(i,i) = S(i,i) + A(i,k) * A(i,k)
  for j = i+1..m do:
  begin
    for k = i..n do:
      S(i,j) = S(i,j) + A(i,k) * A(j,k)
    S(j,i) = S(i,j)
  end
end

Both by theory, do not exceed $O (m ^ 2n)$ obviously.
When I try to analyze iteration cycles for the variable j, is where I get confused.