texts: Is there any open-source tools for verifying TCTL formulae over timed automata can be imported into my project?

texts:
In my project, there is one important step to automatically verify a timed automata with TCTL formulae. I briefly surveyed the tool UPPAAL that provides a GUI to construct a timed automata and to specify CTL formulae. However, I didn't find the api to invoke.

Is there any tools with api provided for verifying TCTL formulae over timed automata can be imported into my project? Such that I can automatically send the timed automata and the TCTL formulae to the tool and get the satisfaction result.

And, the tool UPPAAL can only verify a CTL subset of TCTL over a timed automata. On this constraint, if I want to verify a TCTL formula with interval constraint $\Phi$ (such as $\exists (\Phi_1 U^J \Phi_2)$), I have to extend each location $l$ of the automata with an extra clock $z$, and verify each state $l\{z:=0\}\models \exists (\Phi_1 U (z\in J \wedge \Phi_2))$. And I have to wrap a CTL detection algorithm for nested formulae. Is there any tool can directly verify TCTL formulae over a timed automata?


texts: Cancellation of inequalities in floating point arithmetic

texts:
In finite precision floating point arithmetic the associative property of addition is not satisfied. This is, it is not always the case that $$(a+b)+c=a+(b+c)$$
Even $a=(a+b)-b$ is not always true.
To prove that $x+y<z$ is equivalent to $x<z-y$ with real numbers we can add $-y$ on both sides of $x+y<z$ to get $(x+y)-y<z-y$ and then from this $x=x+(y-y)<z-y$. But I can't repeat the last step for floating point.

Question 1: Are the inequalities $x+y<z$ and $x<z-y$ equivalent in finite precision floating point arithmetic?

Question 2: Are the inequalities $x+y\leq z$ and $x\leq z-y$ equivalent in finite precision floating point arithmetic?

I was too hasty and updated without checking properly. What I really indented to ask is if the breaking of the equivalence could be as drastic as:

Question 3: Could we have $x+y<z$ and $x>z-y$?

Possibly there are already answers below for this. If so, I will check them when I get a chance and select the answer.

Motivation: There is that interview problem that given an ordered array of numbers and a threshold it asks for the number of pairs of numbers of the array which sum is not larger than the threshold. Possible solutions aside, I wanted to understand the particular point of the dangers of switching between testing $x+y<z$ (and also $\leq$ depending on which variant of the problem is presented) and testing $x<z-y$ (or $\leq$).


texts: What are some quadratic run time tasks (algorithms)?

texts:
Are there problems, for which best algorithms have worst run time O(input_length^2) and it is proven, that this worst time cannot be substantially improved (better algorithms do not exist).

EDIT: This question is different from Are there any known lower-bounds for complexity on Non-determinsitic machines , because I have in mind deterministic machine. For example, simple one-processor computer. Question Problems that provably require quadratic time is more like this.


texts: Scheduling problem of average sums with condition

texts: Take a multiset $S=\{s_1,\ldots,s_n\} \subset \mathbb{N}$ and some $k \in \mathbb{N}$.  Take $T$ to be the set of all sequences of the form $s_{\pi(1)},\ldots,s_{\pi(i)}$, such that $\sum_{j=1}^{i-1} s_{\pi(j)} < k \leq \sum_{j=1}^{i} s_{\pi(j)}$ where $\pi$ is a permutation of the indices of $S$ and $i\leq n$ . Is there an efficient algorithm to compute the average of the sum of members of $T$?  This is of interest to me because of its application to scheduling.


texts: Minimum weighted arithmetic mean partion?

texts:
Assume I have some positive numbers $a_1,\ldots,a_n$ and a number $k \in \mathbb{N}$.

I want to partition these numbers into exactly $k$ sets $A_1,\ldots,A_k$ such that the weighted arithmetic mean

$$\text{cost}(A_i,\ldots,A_k)=\sum_{i=1}^{k}\frac{|A_i|}{n}c(A_i)$$

is minimal, where $c(A_i)=\sum_{a \in A_i}a$ is simply the sum of all numbers in $A_i$.

Is there actually a (polynomial) algorithm to do this or is this a (NP) hard problem?

I tried to reduce it to some NP-hard problems but didn't get anywhere, especially because the numbers are nonnegative and thus in an optimal partition big sets need to have smaller weight which seems to be some kind of balancing problem instead of a packing problem (which I am more familiar with).


texts: From the LR(1) parsing table, can we deduce that it is also an LALR and SLR table?

texts:
There is this question I read somewhere but could not answer myself.

Assume I have an LR(1) Parsing table. Is there any way that just by looking at it and its items, can I deduce that it is also a table for LALR and SLR?


texts: Permutation to maximise strings' common prefix

texts:
Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix.

Given a set $S=\{(s,w)\}$ of pairs of fixed length bit strings and weights and an integer k find a permutation p of {1..k} and bit string v of length k to maximise

$$
\Sigma \{ w_i | (s_i,w_i)\in S\land s_i[p(1)]=v[1] \land s_i[p(2)]=v[2]\land...s_i[p(k)]=v[k] \}
$$

I can think of an obvious greedy algorithm where we

pick the index i and value v which maximises the weights of the strings with $s[i]=v$
delete position i from all strings.
Repeat until we've chosen k bits.

Is it possible to do better?

The problem I'm trying to solve is a compression one where the bits in the data can be reordered and each compressed item can be either the original or the suffix from the original which is concatenated with a common prefix when decompressed.

I need to find a reordering and prefix which maximises the number of items which can use the second form. If p is the permutation and v the prefix

Compression for s:

sp = permute(p, s).
If sp[1..k]=v then      # Does the permuted s have the prefix v
    return sp[k+1..n]   # Compressed case, uses only n-k bits
else
    return sp           # Uncompressed case, uses all n bits

Decompression for s:

if len(s)=k then
    su = concat(v,s) # Compressed case, add the prefix.
else
    su = s  # Uncompressed case
return inverse_permutation(p, su)


texts: When you first start a system boot, are you in kernel mode or user mode? Why?

texts: I'm confused as to what mode computers boot in. My thought process was that since kernel mode is effectively the base layer of protection for the computer, it would boot in kernel mode and then load user mode. User mode is also effectively a subset of kernel mode? So you would have to load kernel mode before switching into user mode, right?


texts: Finding the (probable) maximum of a large set of integers *without* iterating over all of the values

texts:
As in the title, I am trying to find the largest (aka least upper bound) of a (very large) set of integers.  Importantly, I do not have direct access to the full list of integers, but I do have a function $f(n)$ which returns true/false if $n$ is in the set.  The function $f(n)$ is expensive and I would like to minimize the number of calls I must make to it.

The integers might or might not be consecutive, or have large gaps between them (i.e. might be sparse or dense).  There is no prior-known upper bound on the largest integer in the set, which can go off to infinity in theory.

Is there a well-trodden algorithm for doing this?  My inkling is to do some kind of random sample to determine the density, and then try to find the upper bound within some certainty.  I'm not sure how to bound my initial sample properly then though, or which distribution I might assume the integers have based on that sample.

Thanks.


texts:
Given a Problem $A$ that has an answer $true$ if and only if both (some) conditions $1$ or $2$ are $false$.

Whether condition $2$ is $true$ can be tested with certainty in polynomial time. Thus, we can say that answer to an instance of $A$ is $false$ in polynomial time (in case if $2$ is $true$). If condition $2$ is $false$, we still need to test condition $1$.

Checking if condition $1$ is $true$ on $A$ is an NPComplete problem (if we consider all possible instances of $A$).

Can we thus conclude that the original problem with both conditions is co-NPComplete?


texts: Why do we use the log in gradient-based reinforcement algorithms?

texts:
I've been reading some papers on reinforcement learning.

$$\Delta w=\frac{\partial ln\ p_w}{\partial w}r$$

I often see expressions, similar to the above one, where the weights (denoted by $w$) are updated following the partial derivative of the policy function (denoted by $p_w$) with respect to its weights.

But why do we take the $\log$? What is its purpose?


texts: Efficient data structure for multidimensional searching on intervals and keys

texts:
I am searching for a data structure that can capture a database, which is consisted of one column of intervals (like [0, 2], [4, 6]) and one/two columns of keys (like {'a', 'c'}).
I want to be able to do efficient indexing in both ways such as queries like the following are computationally balanced:

"give me the keys that appear in the interval frame of 1 and 5" or
"give me the intervals where 'a' exists"

“Computationally balanced” means that there is no 'hierarchy' e.g. from sorting and secondly to be as much redundant as possible.

Also I want to be able to efficiently union/intersect two databases based on intervals (and keys of course).

Here are some notes from approaches I've tried but do not seem to do the trick:

Interval-Set/Interval-Map (Boost): Information is not at all redundant:
(1, 5)->'A' and (4, 8)-> 'B', will be stored as
(1, 4)->{'A'}, (4,5)->{'A', 'B'} and (5, 8)->{'B'}.
It is also hierarchical.
R-trees (Boost): Everything is geometrical.
On the contrary key '1' is not closer to key '2' than key '3'.
Complicated search queries do not appear feasible.
Things are distinguished between keys and value.


texts: Minimum amount of rectangles to create a 2-dimensional matrix

texts:
From this codegolf question.

Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a rectangle of numbers within $N$ with any positive nonzero integer.

Valid "moves":

2 moves:
0 0 0 0      0 0 0 0
0 2 0 0  =>  1 1 1 1
0 2 0 0      0 2 0 0
0 2 0 0      0 2 0 0

2 2 0 0
2 2 0 0
0 0 0 0
0 0 0 0

Invalid moves:

0 0 0 0
0 2 0 0
0 0 0 0
0 2 0 0

2nd move invalid:
2 2 2 0      2 2 2 0
2 2 2 0  =>  2 0 2 0
2 2 2 0      2 2 2 0

A few examples of valid $M$ matrices:

1 2 3 4 5
5 4 7 0 5

0 0 0 0
0 0 0 0

0

The question is, how do you find the minimum amount of moves required to recreate $M$ out of $N$?


texts: Question about DFA for exact string matching

texts:
In the Handbook of Exact String Matching algorithms, it describes the transition set for a basic string matching automaton as:

for

q in Q (q is a prefix of x)
a in $\Sigma$
(q, a, qa) is in E if and only if qa is also a prefix of x
otherwise (q, a, p) is in E such that p is the longest suffix of qa which is a prefix of x.

I'm having difficulty understanding the last statement. Why would there be a state transition to a suffix?


texts: Is λx. a valid Lamda Calculus abstraction?

texts:
For demonstration purposes I was wondering about some very easy to grasp LC abstractions and I came to the idea of a function that simply eats its argument, and nothing more.

If you apply λx. (Yes no lambda term after the point) to an argument the abstraction reduces to nothing.

Although this isn't very useful for computation maybe, do you think the idea itself is valid or not?

Ok thanks everyone. Although I still like to tinker with the idea in my head, I understand it's simply not an option to use this throwaway function when dealing with LC.

Every application in LC returns an expression. There are no birds in the forest of Smullyan that can not sing.

Thanks again.


texts: How can there be stop and wait protocol for a simplex channel?

texts:
Doesn't the receiver have to send back an acknowledgement frame?
So how can it send back a frame, since a simplex channel only allows transmission in one direction?


texts: Which is the most similar NP classic problem, if any exists, to this one?

texts:
Consider a given set $W = \{w_1, w_2,...,w_N\}$ of weights, such that $\sum_{i=1}^N w_i = 0$. Consider the given set of mutually different elements $A=\{a_1,a_2,...,a_M\}$ with $M\leq N$. Consider the set $S$ as a length-N sequence in which all elements of $A$ appear (therefore some $a_i$ can be repeated).

Define the set  $G_{j} = \{k: s_k = a_j\}$ as the collection of positions within $S$ of element $a_j$ $\, j=1,...,M$. Similarly, $W_j = \{w_k \;\textrm{for } k \in G_j\}$.

Find all arrangements $S$ such that the sum of elements in $W_j$ is zero $\forall j=1,...,M$.

For example, for
$W=\{ -264, -132, -24, 60, 120, 156, 168, 156, 120, 60, -24, -132, -264\}$,
$A=\{a,b,c\}$,
the sequence
$S=\{a,b,c,a,a,c,a,b,a,a,b,c,a\}$ is a solution of the problem.
In fact
$G_a = \{1,4,5,7,9,10,13\}$, $G_b = \{2,8,11\}$, $G_c = \{3,6,12\}$
$W_a = \{-264,60,120,168,120,60,-264\}$, $W_b = \{-132,156,-24\}$, $W_c = \{-24,156,-132\}$. The sum of elements inside each $W_j$ is null, $\forall j$.


texts: Algorithm for difference of two semi-decidable languages

texts:
I have two algorithms

Algorithm 1:

if( Condition1(input)==true )
   print(input);
else
   loop forever;

Algorithm 2:

if( Condition2(input)==true )
   print(input);
else
   loop forever;

for any arbitrary fully-computable conditions 1 and 2.

We know both of these algorithms are partially computable.

I want to write a new algorithm (algorithm 3) like this:

if algorithm1 prints x and algorithm2 does not print x "if and only if" algorithm3 print x

Can I write algorithm3? And how?


texts:
So in my APCS class today we played around with generating pi, and approximating to a user defined number of places.  We used the Leibniz formula for π.  As we began playing around with it we tried throwing in 2147483647, the largest value for an int, but noticed it wasn't going to finish anytime soon.  I googled runtime analysis a bit and am wondering how I would graph the complexity of the program.  The function appears to be logarithmic, but I figure that as the complexity increases with each calculation, so would the complexity, but when i graphed it as a Riemann sum, it was a negative value with a slope of 0. Why would that be? I attached my code.

public class pi_calculator
{

public static void main(String [] args) {
Scanner scan = new Scanner (System.in);
int numberOfTerms = 0; {
numberOfTerms += scan.nextInt();
double startTime = System.nanoTime();
double piSum = 0;

if ( numberOfTerms > 0 && numberOfTerms <= 2147483647 ) {
   for( int i = 0; i <= numberOfTerms; i++ ){
        piSum += 4.0 * (Math.pow(-1, i)/(2*i+1));
   }
   double endTime = System.nanoTime();
   double duration = (endTime - startTime)/1000000;
   System.out.print( "Your pi estimate: " + piSum +"\n in: " + duration + "ms" );
}
else {

 System.out.print("ERROR");
}

}
}}


texts:
I'm very confused about the reasoning for these circuits being called 'full adders' and 'half adders'

I've read before that 'half adders' are called so, because two of them make up a 'full adder', and a 'full adder' is 'full' because you can get all the values $(0,0), (0,1), (1,0), (1,1)$.

But what irks me is that adding two bits would never get you $(1,1)$ in the first place, so why not call it a 2-bit adder, since that's exactly what it does. By extension, a 'full adder', in my mind, should be called a 3-bit adder.

If i think of full adders as '3 bit adders', would I ever run into any conceptual troubles? Same goes with '2 bit adders' and half-adders. Are there any historical insights as to why they are called such?

Cheers.


texts: Finding the required value of an algebric expression

texts:
I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$.

I want to find the largest integer value such that it is less than $T$ and not satisfied by $Ax+By+Cz$, how can I do it without using brute force.


texts: Is feasible learning using just one algorithm and just one class of functions?

texts:
Suppose that in an enterprise there is a section specialized in data prediction problems, and to make easier the software maintainance, the next decision is taken: it will be used only one algorithm and only one class of functions to approach solutions for any future problems. Will this decision benefit the enterprise?

I know that, for example, for non-linear models, it is possible to transform datasets using a transformation of the form $x \mapsto (x,f(x))$, in order to obtain a model that can be approximated by linear functions (as a particular example, we can transform quadratic datasets in $\mathbb{R}^2$ in linear ones using the mapping $(x,y) \mapsto (1,x,y,xy,x^2,y^2)$) but, is this enough to ensure that using only one algorithm and one class of functions will benefit the enterprise?


texts: Why can't a compiler create universal N-bit code (e.g. 32-bit, 64-bit, etc.)

texts:
It is my understanding from what I have read that you need to compile separate executables for 32 bit and 64 bit machines. So if I compile a C program for example I need to compile 2 different binaries for 32-bit and 64-bit machines.

However, it seems like intuitively a compiler should just be able to compile down to instructions that say "allocate N bits of space" and similar for other related instructions rather than "give me 32-bits of space" or "give me 64 bits of space"?

Why is this not the case (looking for some intuition at a high level)?


texts: Anonymization of dataset preserving unique identities

texts:
The $k$-anonymization paradigm (and its refinements) means to create datasets where every tuple is identical with $k-1$ others.

However I'm in a situation where people are in the dataset many times. And I want to follow their progress through the health care system, so I need to know who is who. If I give each person a unique ID, which is necessary in this situation, a linking attack from within the table is possible!

Does anyone know of any relevant theory or have attempted to deal with similar problems?

I'm inclined to think it is impossible to give any good guarantee of anonymity in this situation.

This will possibly be used for my MSc thesis topic.


texts: PDA of the language where the number of a's are NOT equal to the number of b's

texts:
I have this NPDA for language L = {w: num_a(w) == num_b(w)}
all loops in q1

a, $ -> 0$       b, $ -> 1$
a, 0 -> 00       b, 1 -> 11
a, 1 -> \lambda  b, 0 -> \lambda

       ------>q1-----------------\lambda, $ -> $------>q2

initial state: q1
final state: q2
What if I modified L such that the number of a's is not equal to number of b's.
That is L' = {w: num_a(w) != num_b(w)}.
What would be the modification I have to make in the original NPDA.


texts: Sub language is not Turing-recognizable, or could it be?

texts: Let A and B be languages with A ⊆ B, and B is Turing-recognizable. Can A be not Turing-recognizable? If so, is there any example?


texts: Lambda calculus: difference between contexts and evaluation contexts

texts:
Firstly, I'd like to say that my text below may contain errors, so feel free to point out any mistakes in my formulation of the question.

Consider an untyped lambda calculus with booleans and if-statements whose terms are given by this syntax:

 t ::= v | t t | if t t t | x
 v ::= \x.t | #t | #f

Contexts C in this case would be given according to this syntax:

C ::= [-] | \x. C | C t | t C | if C t t | if t C t | if t t C

Additionally, one could define evaluation contexts E according to this other syntax:

E ::= [-] | \x. E | v E | E t | if E t t

I split my question in three sub-points which I'd like to be addressed.

When are the two notions used? I know for example that evaluation contexts are used to define the semantics of the calculus, but the usage of contexts still somewhat eludes me. Also I'd like some confirmation of my knowledge here.
When is one to be preferred to the other and why?
Could you point to relevant articles that could help me sort out this matter?


texts:
I'm trying to prove that the recurrence $T(n)=2T(\left \lfloor \frac{n}{2} \right \rfloor) + n$ is in $\Omega(n \log_2 n)$.

Here's my attempt: Suppose there is some $c>0$ and a positive integer $n_0$ such that $n_0 \le k < n \implies T(k) \ge ck \log_2 k$.

Then

$$\begin{eqnarray*}
T(n) &=& 2T(\left \lfloor \frac{n}{2} \right \rfloor) + n \\
&\ge& 2c \left \lfloor \frac{n}{2} \right \rfloor \log_2 \left \lfloor \frac{n}{2} \right \rfloor + n \\
&\ge& 2c \left ( \frac{n - 1}{2} \right ) \log_2 \left ( \frac{n - 1}{2} \right ) + n \\
&=& c(n - 1) \log_2(n - 1) - c(n - 1) + n \\
&=& cn \log_2(n-1) - c \log_2(n-1) - c(n - 1) + n \\
&=& cn \log_2 \left [ n \left ( 1 - \frac{1}{n} \right ) \right ] - c \log_2(n-1) - c(n - 1) + n \\
&=& cn \log_2 n + cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n.
\end{eqnarray*}$$

I can't determine if there is a $c > 0$ such that $cn \log_2 \left ( 1 - \frac{1}{n} \right ) - c \log_2(n-1) - c(n - 1) + n$ is non-negative for $n$ large enough.

Also, I think this approach is too complicated given how easy it is to prove $T(n)=O(n \log_2 n)$. Am I missing some obvious estimate here?

Any help is welcome. Thanks.


texts: Journey of a process from compilation to execution

texts:
I am reading operating system, and after reading some topics (Processes, Main Memory management) I got somewhat confused. I have knowledge about certain things but I am not able to combine and visualize them. Let's take an example - I have a simple programme as follow:

#include<bits/stdc++.h>
using namespace std;

int add(int a,int b){
  return a+b;
}

int main(){
  int a=1,b=2;
  int c=add(a,b);
  cout<<c<<endl;
}

I want to know how this program will be loaded into the main memory and how will be getting the computation done.
I have certain points which I want to incorporate in the overall process.

At what stage and where will I be getting the 4 sections of memory .( Text, Data, Stack and Heap).
At what stage will the process be getting its PCB(Process Control Block.) Does PCB contains the 4 sections of process?
When and where is the role of CPU?
Address binding.
Loading
Linking.
Logical and physical address space.
Paging

Please explain how the process will be executed including the above steps and other steps which take place in general.
P.S. Please explain by assuming some memory addresses.


texts: Are there efficient probabilistic multiplication algorithms that use O(n log n) gates?

texts:
Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice completely silly because you only start to see advantages on numbers with an absurd number of digits.

But suppose that we only wanted a probabilistic multiplication circuit, which returned the wrong result with probability at most epsilon. Then maybe certain shortcuts could be taken, in order to avoid the most inconvenient parts of multiplying two numbers.

For a fixed acceptable failure rate epsilon, is there an O(n log n) multiplication algorithm that achieves this failure rate without being horrendously inefficient in practice?


texts: Why is {w | no prefix of w starts with b} = {w | the first character of w is a} ∪ {e}?

texts:
\begin{align} L &= \{ w \in \{a, b\}^* \mid \text{ no prefix of $w$
 starts with $b$}\} \\ &= \{w \in \{a, b\}^* \mid \text{ the first
 character of $w$ is  $a$} \} \cup \{e\} \end{align}

Why is it in union with an empty string? If an empty string from $b$ can also be a prefix.


texts: Given two total Turing machines, is it undecidable problem to detect whether they give the same output on all inputs?

texts:
See title. And by all inputs I mean providing the functions with the same input and checking whether they give the same output for each case.

EDIT

If it can be reduced to Halting problem, then how?

EDIT 2

@Ariel's answer doesn't satisfy me since given the concrete machine $T$ and input $x$ he states that there exists a computable function that is equal to $1$ everywhere except $x$ and indicates whether $T$ terminates on $x$, on $x$. Note: there is no algorithm for building such a function since it would answer the Halting problem immediately. He proceeds with noting that if that function coincides (by required in the question decision algorithm) with the constant $1$ (as a function) then $T$ terminates on $x$. Otherwise - it does not. So, Halting problem solved, a contradiction. Except there is no. We didn't build an algorithm for building that function ($f_{M_x}$, if I understood correctly), so we didn't build an algorithm for deciding whether arbitrary $T$ terminates on given $x$. @Ariel, correct me, if I'm wrong...

EDIT 3
@Ariel was correct!!! Since I did not mentioned that required decider algorithm must only accept not descriptions of computable functions but Turing machines implementing them, his answer was fully correct.
Now the thing - I just require for seeked algorithm to process only pairs of always halting Turing machines and testing them for equality on every input. @Ariel, I'm really sorry :-(

EDIT 4
And if somebody still wishes to answer this question, Rice's theorem for partial functions does not help, since I don't require the decider beeing searched for to be such over all partial function, only over total function, i.e. it may not halt on arbitrary not-always-halting Turing machine.


texts: Using Graphs to construct semi-supervised learning solution

texts:
I am currently trying to design a graph-based approach for content tagging. In principle I am trying to two two things:

Use an algorithm such as Latent Dirichlet Allocation (LDA) or some variant of it to discover terms in documents that relate to a certain topic, thereby allowing me to tag a document as relating to that topic. None of the documents are labelled yet, so this step is entirely unsupervised
Allow user feedback on whether the labels are correct. This firstly allows us to sharpen labels on specific documents (i.e. override the output from 1. if incorrect). And secondly, it allows us to use these user-defined labels in a semi-supervised learning algorithm, which might perform better than what is done in step 1 (though this part is out of scope for this question).

Step 1 I could represent with a simple graph as follows:

The LDA algorithm outputs the terms found in the document along with some weighting according to their frequency. In addition, it outputs a set of topics along with the terms that are associated with each topic (again, weighted according to how strongly the term is associated with the topic).

Now for point 2 I need to incorporate user feedback, so I need to link a user to a document to indicate that the user has read it and then link the user to the topic, indicating that the user believes the document is about that topic.

But this doesn't really work. "Document is_read_by User" correctly describes the relationship between the document and the user, but "User believes_document_related_to Topic" is not a valid relationship because it is contingent on a specific book - in this case 1984 by George Orwell.

My question is, how could I build this relationship with a graph? I.e for each user I want to be able to capture the following information.

According to User "Karl" the document "1984 by George Orwell" is about the topic "Surveillance"

(Of course, the idea is to allow multiple users to give feedback, thereby strengthening/weakening the relationship between the document and the topic).


texts: Can someone clarify Invariant 4.7 of the PBFT correctness proof paper?

texts:
I am reading the PBFT Correctness Proof Paper and I cannot make completely sense of the Invariant 4.7 and its proof:

Here are my concerns:

I assume that the symbol $\Leftrightarrow$ is used with the usual meaning of double implication.
$n\mbox{-}faulty$ is defined (Definition 4.3) as the number of faulty replicas, so I do not understand how it can be used as a predicate in Invariant 4.7.
When is $n\mbox{-}faulty$ true of false?


texts: a problem with Suzuki-Kasami mutex algorithm

texts:
I have some sort of a misunderstanding regarding the Suzuki-Kasami distributed mutex algorithm. I am writing my question here because I failed on gaining access to the original paper.

I will call processes sites for convenience.

My question

Why the token holder $j$ releases its token only when $RN_j[i]==LN[i]+1$ and not when $RN_j[i]>LN[j]$.

I mean, since we cannot assume anything on the quality of communication, maybe site $i$ had the time to increment his sequence number twice so that the token holder got a message with difference $2$ from $LN[j]$. In this case the token holder will not release his token and starvation will be applied.


texts: Improvement on djikstra's algorithm for shortest paths

texts:
We all know about the djikstra's algorithm for computing single source shortest path and the complexity for the same as O(m log n)
( m being the number of edges and n the number of vertices ), this complexity results from using the heap as a data structure for the algorithm

However I recently came across a statement which says this complexity can be improved to O( m + n log n) by using another exotic type of heap as a data structure. Does anyone has any idea about this data structure which is being mentioned?.


texts:
I want to create an algorithm to build a hex matrix with given:
- max n rows
- max m collumns
- min t rown
- min q collumns

containing the specific words from a list: "example", "test", "algorithm".

For example. To build a hex matrix with:

  - max n = 5 rows
  - max m = 6 collumns
  - min t = 5 rows
  - min t = 4 collumns
  - containg words: "orange", "test"

Can anyone point me in the right direction of how to build this type of algorithm? ( C++, C#, Swift, Objective-C)


texts:
Consider the augmented grammar G is:

S` -> S
S -> a
S -> (T)
T -> T,S
T -> S

I have tried to construct parse table. But, when I read '(' nonterminal Symbol (item 3), there is no action table elements either 'shift' or 'reduce'.

I3:
S -> (.T)
T -> .T,S
T -> .S

so I can't construe '(a,(a,a))' in this Parse table.
then is it ambiguous grammar? or I wrong the answer?


texts: Do we need recursion in programming language to solve any problem?

texts:
My question is simple: If we want to be able to solve every problem, that we can solve using recursions, do we need programming language to allow us use recursions?

Assuming we are allowed to use: conditional evaluation of blocks (if/else), cycles(for,while), dynamic allocation of memory.

I know, that we won't be able to implement everything the way we want. However, I'm asking whether we are able to solve everything, just by using different implementation - or by modification of algorithm to be non-recursive.


texts: Are functions that are equal to a constant as you take a limit to infinty O(1)?

texts:
The below function converges to a constant as you take n to infinity.
$f(n)=(1 + \frac{1}{n})^n$
$\lim \limits_{n \to \infty}(1 + \frac{1}{n})^n = e$
Would this imply that it is O(1) since you can just upper bound it with a constant?


texts:
I asked a (seed) question about sums of Landau terms before, trying to gauge the dangers of abusing asymptotics notation in arithmetics, with mixed success.

Now, over here our recurrence guru JeffE does essentially this:

$\qquad \displaystyle \sum_{i=1}^n \Theta\left(\frac{1}{i}\right) = \Theta(H_n)$

While the end result is correct, I think this is wrong. Why? If we add in all the existence of constants implied (only the upper bound), we have

$\qquad \displaystyle \sum_{i=1}^n c_i \cdot \frac{1}{i} \leq c \cdot H_n$.

Now how do we compute $c$ from $c_1, \dots, c_n$? The answer is, I believe, that we can not: $c$ has to bound for all $n$ but we get more $c_i$ as $n$ grows. We don't know anything about them; $c_i$ may very well depend on $i$, so we can not assume a bound: a finite $c$ may not exist.

In addition, there is this subtle issue of which variable goes to infinity on the left-hand side -- $i$ or $n$? Both? If $n$ (for the sake of compatibility), what is the meaning of $\Theta(1/i)$, knowing that $1 \leq i \leq n$? Does it not only mean $\Theta(1)$? If so, we can't bound the sum better than $\Theta(n)$.

So, where does that leave us? It it a blatant mistake? A subtle one? Or is it just the usual abuse of notation and we should not look at $=$ signs like this one out of context? Can we formulate a (rigorously) correct rule to evalutate (certain) sums of Landau terms?

I think that the main question is: what is $i$? If we consider it constant (as it is inside the scope of the sum) we can easily build counterexamples. If it is not constant, I have no idea how to read it.


texts: Are there FPTASs for the min cost flow problem?

texts:
In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs for the min cost flow problem?

Possibly, there is no need for an FPTAS here since an optimal solution can be computed very fast (using double scaling or the enhanced capacity scaling algorithm, for example). But from a theoretical point of view, this would be interesting to know.


texts: Can it be undecidable whether a problem is undecidable or not?

texts:
I've just started learning about the concept of undecidability and turing machines, and while I am finally beginning to grasp it, I'm still curious about one thing. Is it possible for a problem to exist for which it is impossible to prove whether it is undecidable or not? In other words, can the problem of "is it decidable" be undecidable itself?

There could be a serious contradiction that I'm not missing here, but I'm not sure. Are there any problems known like this?


texts:
I was following a discussion on a forum where a person has asked whether the following generates lexical errors or not,

  (1) char p="gate;

  (2) int /* n;

  (3) printf("%d, n);

When I tried to run them on my CPP compiler I got these errors respectively for the following 1, 2 and 3

When I looked them up on the internet they all are appearing to be Syntax errors.. Am I right? or are they lexical errors?


texts: Algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$

texts:
Let $A_1=(Q,\Sigma,q_0,F_1,\delta _1)$ and $A_2=(P,\Sigma ,p_0,F_2,\delta _2)$ a finite non determinustic automaons.

  Describe algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$

Hint: Intersection automaton

My try

To bulid the intersection automaton $L_1\cap L_2$ and check if $L_1\cap L_2 \neq \varnothing$ with $"\color{blue}{\text{emptiness problem algorithm} }"$  and if $L_1\cap L_2 \neq \varnothing$ so $\exists $ word $w$ such that $w \in \mathscr L(L_1\cap L_2)$


texts: What exactly is going on in a proof by induction of a recurrence relation?

texts:
In CLRS, it works through an example going through a recurrence relation proof using the "substitution method".

We have the recurrence $$T(n) = 2T(\lfloor n/2 \rfloor) + n \   \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \ \ \ \ \ \ \ \ \ \ \   (4.19)$$

It claims:

  We guess that our solution is $T(n) = O(n \lg(n)).$

We assume that $T(m) \leq cm\lg(m)$ for all $m < n$ (in particular, for $m = \lfloor(n/2) \rfloor$, and need to show that $T(m) \implies T(n).$

I'm fine with this; this seems like a standard case of strong induction, but what I don't understand is the explanation of the base case (which we also need to prove):

Could someone explain this paragraph to me?
More specifically:

What are boundary conditions?
How do we know the base case? We're only given $T(n)$ recursively; there's no initial case when $n$ is, for example, $1$. How, then, do we know that
"$T(1) = 1$"?
I don't understand what the paragraph is getting at.  How do we determine the base case in the general case?

Also, I've noticed that, in practice examples, the author has failed to mention the base case completely when doing these types of proof; that is, they assume the inductive hypothesis, and prove that (for all $m<n$), $T(m) \leq \text{something} \implies T(n) \leq \text{something}$, but they leave it at that, as though that were sufficient for the proof.
In fact, these proofs don't even explicitly state the inductive hypothesis. For example, in the case of (4.19), they would write something like:
$$ \begin{align} T(n)  \leq c\lfloor( n/2) \rfloor \lg(\lfloor n/2\rfloor) \end{align} \\  \leq \ ... \\ \leq cn\lg(n) \ .$$

Is this acceptable, or would that constitute a sloppy proof?


texts: If a problem is in P (ie 3-Clique or any Clique problem with a fixed k) does that mean it is also in NP and CO-NP?


texts: Design considerations for a language to support automatic parallelization

texts:
Automatic parallelization isn't a new thing by any means, and lots of questions have been asked about whether Java or C or C++ or a host of other languages or specific compilers (gcc 5 v 6, clang, Hotspot, etc.) support automatic parallelization. In many cases, the problem seems to be that compilers sometimes try to automatically parallelize code, but it's just a really hard problem due to memory guarantees (in a managed language) or pointer tracking (in an unmanaged one). The impression I get is that it's just tough to do in a language that was designed primarily for serial execution.

Let's say we were trying to build a programming language from the ground up specifically to simplify the task of automatic parallelization, vectorization, and distribution--from small loops/computations (SIMD CPU instructions, GPU kernels) up to large portions of code (threads, remote processes, cloud computing), we want to be able to automatically determine how a program could be broken up to be run in as parallel a manner as possible.

Some potentially relevant considerations might be:

Would it be easier with managed or unmanaged memory? (in particular, thinking of how Rust does unmanaged memory but has built-in thread safety)
Would it be easier with a purely (or mostly) functional language, or OOP, or imperative?
How to incorporate non-determinism, such as user input, network traffic, or PRNG's?

What characteristics would it be important for such a language to have to make this task as simple and robust as possible?


texts: Proving complexity of computing product of matrices

texts:
If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{8}{3}N^3+2pn^2+O(n)$ flops?

I have no idea where to start. It is assumed that we do not compute $A^{-1}$ directly, but, instead, we compute the $LU$-factorization of $A$, and use $L$ and $U$ to compute the product $A^{-1}(BC)$ using the method of solving of multiple right-hand sides (whatever this means).

I would appreciate some help with this.


texts: What is a continuous environment for an agent?

texts:
I know the environment of an intelligent agent is divided to discrete and continuous. But I think they are relevant to sensors and actuators of the agent itself. Moreover, environment may have many mutable factors,(some continuous, some discrete).

For example for an agent which is an expert system (computer program) to play the role of a physician, what is the environment, is it continuous or discrete?

Please give some examples of continuous environments.


texts: Is $E_{LBA}$ a Turing-recognizable language?

texts: I know that $E_{LBA} = \{\langle M \rangle ~ \mid ~ L(M) = \emptyset \}$ is an undecidable language, but is it recognizable (recursively enumerable)? It seems that it's complement is recognizable since we could construct a Turing machine that enumerates all strings and checks if any belong to the language. If both $E_{LBA}$ and its complement were recognizable, then $E_{LBA}$ would be decidable, but it isn't, which leads me to think it isn't recognizable. Is this true?


texts: The time complexity of finding the diameter of a graph

texts:
What is the time complexity of finding the diameter of a graph
  $G=(V,E)$?

  ${O}(|V|^2)$
  ${O}(|V|^2+|V| \cdot |E|)$
  ${O}(|V|^2\cdot |E|)$
  ${O}(|V|\cdot |E|^2)$

The diameter of a graph $G$ is the maximum of the set of shortest path distances between all pairs of vertices in a graph.

I have no idea what to do about it, I need a complete analysis on how to solve a problem like this.


texts: Sequence alignment with one to many characters

texts:
I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with one character beside allowing character substitution, deletion or insertion.

For example, if I have a set of similarly sounding characters, like

monir, monier, muneer, munir, mounir, mouneer

The alignment algorithm will produce the following output

m u n i - r
| | | |   |
m o n e e r

Is there a way to adapt these algorithms (or an alternative algorithm) to consider aligning/substituting character with more than one character in order to output something like

m u n i  r
| | | |  |
m o n ee r

Please note that, I'm using the standard java implementation for these algorithms and I don't have a predefined list of similarly sounding characters, so I'm trying to aligning the similar words together in order to extract these alignments.


texts: Analysis of the following integer program

texts:
So the knapsack problem has an integer programming formulation as follows,

$$ \max_x v\cdot x\\s.t \\x_i \in \{0,1\}\\w\cdot x \leq C$$

Now consider the second integer program which might be a variation of the knapsack integer program.

$$ \max_x v\cdot x\\s.t \\x_i \in \{0,L_i\}\\  x_i \leq R \cdot \delta_i\\ \delta_i  \in  \{0,1\}\\ \sum_i \delta_i = k$$
where $v_i$ is item's $i$ value, $L_i$ and $k$ are constants, and $R = \max{\{L_1,L_2,...L_d\}}$.

Is there a dynamic programming solution or an approximation algorithm
for the second integer programming problem ?
Is it possible to use the solution of the knapsack problem to warm
start or partially solve the second integer programming ?

Thanks!


texts: What is the difference between a collection of Turing Machines and a family of Circuits?

texts:
Given a Collection of Turing Machines $T_1, T_2, T_3,...T_n$ where $T_1$ denotes that the Turing machine can only take in an input of size 1. Is there any difference in computational power to a family of Circuits $C_1, C_2, C_3,...C_n$ ?

What if we assumed that each Turing machine, encoded special information for that specific input size to make each instance efficient?

If there is no difference in computational power, then maybe we could use this to define non-uniform algorithms instead of circuits?


texts: Why does the map function in MapReduce take two parameters?

texts:
I am playing around with MapReduce and wanted to ask why the map function takes two inputs (key, value)? Why not just pass along the value?

Specifically, if you look at the word count example on Wikipedia page you will see that the map function is:

function map(String name, String document):
// name: document name
// document: document contents
  for each word w in document:
    emit (w, 1)

However, the function never does anything with the parameter "name". Why even pass it in?


texts: Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?

texts:
If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get worst-case performance regardless of whether your 'already sorted' list is in ascending or descending order?

My thinking is that, if you always choose the smallest element for your pivot, then whether your 'already-sorted' input is sorted by ascending or descending doesn't matter because the subset chosen to be sorted relative to your pivot will always be the same size?


texts: How to determine(with some confidence) if two extremely long lists of numbers (terabytes) are similar?

texts:
I have two very large files with numbers seperated by commas. What is most efficient/fastest way to say with some confidence that these two files have same numbers.

The main rule if if two distributions are the same, also the order of data does matter for example:
A = {1 2 4 5 6}
B = {6 5 4 2 1}
C = {0.5 0.5 1 2 3 4 5 6}

in above case A and C are still similar but A and B are totally different

To be more clear lets split the question into 3 main tasks

Given large lists A,B find if lets say 50% of A is contained in B (Most efficient technique without comparing all numbers from list)
Given A,B match above condition check that the overlapping numbers have similar order as mentioned above i.e. if 2 in A is followed by 1 same should happen in B. The positions of 1,2 can be different in B.
Select two independent batches from A and B and test if those are from Poission distribution, binomial distribution.


texts: Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}

texts:
Can someone help with this:

$L=\{a^ib^j \mid i,j \ge 0 \text{ and } i \ne 2j\}$

I'm trying to write a grammar for this language?
I don't know how to do this.
I tried this:
$S \rightarrow aaAb \mid aA \\
A \rightarrow aA \mid a$


texts:
If $L1⊆L2$, and $L1\not∈RE$, is it possible that $L2∈RE$ ?

Also I find it hard to find languages that are not in RE at all, I've heard about Arithmetical hierarchy but we didn't really learnt it in class so I guess the solution shouldn't necessarily be correlated to Arithmetical hierarchy.

I know that the $A_{TM}=\{(〈M〉,w): M\ accepts\ w\}$ where M is a Turing machine
then $\overline {A_{TM}}\notin RE$, but it doesn't seem to help.


texts: Understanding the Broyden–Fletcher–Goldfarb–Shanno Algorithm to Select Weights for Neural Nets

texts:
I am trying to train and implement a Neural Network. I was reading a few articles, learning about their principles and the math that goes behind them. However, while I was trying to understand the math, specifically the optimization part (for selecting weights), I ran into a problem: I couldn’t understand the Broyden–Fletcher–Goldfarb–Shanno algorithm.
I understand that it (basically) uses newton's method, expect that it finds the zeroes of the derivative of the original function (to find the local minima of the original function).

However I was having trouble following the notation and math that is written on Wikipedia about it:

First of, I do understand that Bk is a Hessian matrix that holds the partial second derivatives and f(x) is the original function that we are finding the local minima of. Moving on to step 1, I do not understand why the search direction needs to be solved. (Is it because we need to figure out whether the zero of the derivative is a local maximum or minimum of f(x) aka perform the first derivative test). In step 2, I do not understand why line search needs to be performed. In step 3, I do not understand what the product of ak and pk means. In step four, (correct me if I am wrong), yk equals the change in y or f(x). Finally, I know step 5 is trying to approximate Bk+1, which is what newton's method does, but I do not understand why its trying to estimate another Hessian matrix, shouldn't it be estimating a point? Or is it estimating a matrix because the algorithm is supposed to work with a multidimensional space, but then how does the partial second derivative matrix lead to finding the local minima of the original function? Also, what does the right side of the equation mean with all the vector/matrix multiplication and division. (I know this is a quasi-netown method but do not really understand it).

I tried to search the internet for my answers, but I couldn't really find anything. I am only in high school and don't have anyone who can explain me this math. So I really appreciate your help. Thank you so much in advance.


texts:
As in, I have to design a determenistic (one-taped) turing machine that accepts that language (All strings made up of 0 and 1, where the j-th character from the end is a 0, and $j$ is a constant that we know what it is before running the machine) in less steps than the trivial steps.

In the trivial solution, I would first check if the starting point is a blank, if so the machine denies. If not, go to the last bit (first blank) then move $j$ steps to the left and check if it is $0$.
All of that takes $1 + n + j$ steps, but my professor says there is a better runtime that I should come up with.

Any hints would help!


texts: Size of constant depth circuit for digital comparator?

texts:
Is a lower bound of $\Omega(n^2)$ known for the size of any constant depth circuit expressing a digital comparator for two $n$-bit numbers?

Two $n$-bit binary numbers can be compared using a digital comparator circuit.
The straightforward way to implement such a circuit is to compare the high-order bits; if they are the same then continue to compare the second most significant bits, and so on.
This circuit has size (measured in the number of gates) that is roughly quadratic in $n$, with linear depth.
By standard arguments, this can be folded up into an equivalent circuit of roughly the same size that has logarithmic depth (in $n$).

In fact, constant depth circuits of size $O(n^2)$ are sufficient for a digital comparator, if unbounded fan-in gates are allowed: see Heribert Vollmer's Introduction to Circuit Complexity (Exercise 1.4).
Is a tight lower bound known?


texts: Generate all permutations of 1 to n with i stacks

texts:
Assume we have i stacks. the possible actions are:

push to first stack form input
pop from stack i and push it to stack i+1
pop from last stack to output

If we have numbers of 1 to n starting from 1 in the input, what is the minimum value of i which  can generate all permutations of 1 to n at the output?

The options are:

1
2
n-1
n

Option 1 obviously is not the answer, and also it's totally possible with n and n-1 stacks witch removes the option 4.

The real question is "is it possible doing with 2 stacks or we need n-1"?


texts: Checking if there is a single path that visits all nodes in a directed graph

texts:
Given a directed acyclic graph G, give a linear time algorithm to determine if the
graph has a directed path that visits every vertex.

You can assume you are given a list of nodes and two adjacency lists: Enter[v] which contains all the edges entering node v, and Exit[v] which contains all the edges leaving node v.
I was thinking that I could pick a node that doesn't have edges entering it and run DFS on it. During DFS, every time I get to a node with no children, I check if all the nodes have been visited. If not, I backtrack and explore a different path each time. If I make it back to the original node or if I hit a node with no children, I can check if I have seen all the nodes. If not, I return that there is no such path, else I have found a path.
Would this work?


texts: How can an LBA check legality of TM transitions without extra memory?

texts:
In Sipser's book there is a proof that an emptiness of LBA is undecidable, with the help of reduction to A_$_{\text{TM}}$.

The reduction is proposed in the following manner:
we receive a TM $M$ and a word $w$, and build an LBA $B$ that accepts if is fed an accepting computation history of $M$ on $w$.

At page 224, it describes how $B$ checks that the configuration $C_{i+1}$ is legal for M on $w$ at the step $i+1$, and states "then $B$ verifies that the updating was done properly by zig-zagging between corresponding positions of $C_i$ and $C_{i+1}$. To keep track of the current positions while zig-zagging, $B$ marks the current position with dots on the tape."

How can we know that $B$ does not need additional memory to check for legality of configuration change from $i$ to $i+1$? $B$ is an LBA, that says it has only the memory it got with initialisation and cannot go beyond it on the tape, so if it needs additional memory it has a problem.


texts:
I have a question:

Does for every NFA $N$ exist NFA $M$ that has maximum 3 final states and $L(N) = L(M)$.
I can answer no for DFA for below language and its minimal DFA that has 4 final states .

$L_1 = \{ax_1,bx_2,cx_3,dx_4 | x_1 \in \Sigma^* ,x_2 \in (a+b)^*,x_3 \in (b+c)^* ,x_4 \in (a+b+c)^*\}$ , $\Sigma = \{a,b,c,d\}$

but because there isn't any specific algorithm for finding minimal NFA,I don't know how to answer this question.can any one help ? it seems that answer is no.


texts: Method for finding correlation between data sets

texts:
Let's say that I have $N$ data sets where I have data points at some fixed frequency, such as "daily".

What would be a good method for finding correlation between any of the data sets, or choosing a single data set, and asking what other data sets are most correlated?

To make it less abstract, imagine that I'm logging how much water I drank a day in ounces, how much exersize i did a day in minutes, my mood level, and how bad of a headache I had that day from 1 (no headache) to 10 (bad headache).  I'd want to be able to see if my headaches were correlated (keeping in mind, it might not be causation) to me drinking less water perhaps, or doing less exercise.  However, it's possible that there may be a lag between cause and effect (or correlation), etc.

That's my basic question, but in case it's relevant to the answer, I'm also wondering how I might be able to handle missing data (maybe some days didn't get data?).

Also, I was wondering what if the data sets AREN'T at the same frequency?  Like one data set may be weekly while the others are daily.

My best guesses at how to approach this could be to use a discrete Fourier transform of each data set, and then do a dot product between the frequency histograms to find ones that had similar frequencies (even if different phases), and then I could use the phase information to figure out the kind of lag time there is.

Since I'm also interested in negative correlation, I'm thinking that when i do the dot product between the histograms and get my 0 to 1 answer, that i would report "correlation" as $abs(dotProduct-0.5)$ so that things close to either 0 or 1 were treated as important.

Is there a better way? Is my best guess a reasonable approach?

Thanks!


texts:
Let's say we have a directed graph in which each pair of adjacent edges has a weight; or, alternatively, each ordered triple of vertices A, B, C has a weight $W(A,B,C)$ of going A->B->C.
I am looking for a generalisation of a widest path in such graph, that is, a way to find a directed path between given two vertices, which has a maximal minimal weight of an intermediate step.
The naive solution is to generate a regular, directed graph which vertices contain ordered pairs of vertices of an original graph, connected by edges with weights $\hat{W}(IJ,JK)=W(I,J,K)$, and this way lower the whole problem to standard widest path, but maybe there is a better way?


texts:
By making use of the fact that sorting $n$ numbers requires
$\Omega(n \log n)$ steps for any optimal algorithm (which uses 'comparison' for sorting), how can I prove that finding the convex-hull of $n$ points is bounded by $\Omega (n \log n)$ steps?


texts: Can cantor pairing function prove that 2D Turing Machine can be represented by 1-tape TM?

texts:
I'm trying to figure out if a 2-Dimensional Turing Machine can be represented by any 1-tape TM. I came across the Cantor Pairing Function when doing some research. And based on my understanding and how the pairing function works, any 2D TM can be represented by a 1-tape TM if it uses that said function.

Am I right? Can someone elaborate a little bit more on that please.


texts: Shortest path in directed graph passing thru specific vertices

texts:
Given a directed graph $G$, vertices $s$, $t$ and group of vertices $U$, suggest a algorithm returning true if exists shortest path $P$ from $s$ to $t$, such that $P$ contains all $U$ vertices.

The graph is unweighted, we have to find shortest path in distance.

I was thinking about using reduction and BFS, But honestly I have no clue how to define the reduction graph.

The algorithm should run in linear time - $O(E+V)$.

Any suggestions?


texts: Reliability of information on large social networks like Wikipedia

texts:
I was going through the playlist of an online course on Social Network Analysis offered by the Indian Institute of Technology (Madras), when I came across the claim that "when a lot of people get together and start discussing and debating conflicting ideas, true knowledge is known to emerge"-- and thus implying that Wikipedia, as such a platform, would in general have accurate information. Here is the link to the video.
But the video just claims that and moves on, focusing more on selection, Social influence, similarity measure etc. So it does not tell us "why" this is true (theoretically) or what is the empirical evidence behind this claim (practically).
One possibility that comes to my mind is Robert Aumann's theorem claiming the impossibility of two perfect Bayesian thinkers "agreeing to disagree" -- famous in Economics, which is my home field. But I have no idea how this may connect to social network analysis, or if Aumann's theorem has anything to do with it at all or not.
I would want to know, theoretically why is the video's claim true, or true atleast approximately (any mathematical theorem or maybe reference to some reading material) and if possible, any empirical evidence to back it up.


texts: Is Loop Invariant Proof a form of Induction?

texts: As far as I see, what computer scientists refer to as loop invariant proofs are exact replicas of induction proof. Is it true? Can I state that loop invariant proof implies an induction? Is there a theoretical difference?


texts: How to get the expected running time of an algorithm

texts:
I have an algorithm which, basically given an array of $n$ numbers, checks if there is any repeated numbers in the array, and returns true if there is and false otherwise.

It uses a direct access table (hashing function $h(x)=x$), which makes the running time linear. So it creates a new array, initializes all values to false, then iterates through the given array, and since each value is an index to the hash table, it accesses that array location and changes it to $1$. If it is already a $1$, then you know that it is a repeated number.

But when getting the expected running time, you need to first define a probability space. This is the part I am confused about. How can you define a probability of a number being repeated in A, if you are just given an array with arbitrary numbers?


texts:
Is P/poly known to be in RE?
If yes what other classes is it known to be part of.


texts: Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

texts:
I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I am having trouble finding algorithms which perform well on a massively parallel architecture where there is no shared memory between CPU and GPU.

However, on the wikipedia page for the $\mathsf{NC}$ complexity class states that the determinant (and inverse) of matrices lies within this class, which makes me believe that there do exist algorithms which perform well on massively parallel architecture.

Can anyone provide me with a reference to such an algorithm, or is it just proved that the determinant and inverse of a matrix lies within $\mathsf{NC}$ without a current algorithm having been developed.


texts:
So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting correct regexes at least to my knowledge, I was having some weird issues with variables/state names. Please help me understand what my mistake is here in my process:

Consider the DFA that is governed by these equations and $\Sigma = \{a, b\}$:
$$Q_0 = bQ_2 \cup aQ_1
\\ Q_1 = bQ_2 \cup aQ_0
\\ Q_2 = aQ_2 \cup bQ_2 \cup \varepsilon$$

I'm sorry I don't have a picture of the graph, but I think this should be fairly simple to visualize. It is an unminimized DFA that pretty much accepts every string with at least 1 'b', as it bounces back and forth from $Q_1$ and $Q_0$ every time an 'a' is reached, both $Q_1$ and $Q_0$ have edges to $Q_2$ from 'b', and $Q_2$ is an accept state that stays at $Q_2$ no matter what character it sees. Now I attempt to do the reduction method we see in Raphael's post:

$Q_1 = bQ_2 \cup a(bQ_2 \cup aQ_1)
\\ Q_1 = bQ_2 \cup abQ_2 \cup aaQ_1
\\ Q_1 = (b \cup ab)Q_2 \cup aaQ_1
\\ Q_1 = (aa)^*(b \cup ab)Q_2$

$\\ Q_2 = a^*bQ_2 \cup \varepsilon
\\ Q_2 = a^*b^* \cup \varepsilon
\\ Q_2 = (a^*b^*)^*$

$\\ \\ Q_1 = (aa)^*(b \cup ab)(a^*b^*)^*$

Now I have two questions here:

Notice that at the end of my $Q_1$ manipulation I moved $(aa)^*$ to the front. This is something that I did out of common sense since thinking about the DFA, $(aa)^*$ has to be first since $Q_2$ doesn't have any outbound edges. Is there a way to formalize what I'm thinking/doing here?
Notice that at the end I have my valid regex equal to $Q_1$. That doesn't seem right, since we want to find the regex associated with $Q_2$! But a quick simulation through my head tells me that it actually is the regex associated with $Q_2$. So what is going on?!

Thanks so much for your help.


texts: What is the Number of Possible Nonequivalent Propositions with $P_1, P_2, P_3$ Using $\iff$ Operator?

texts:
A multiple choice question asks this:

Number of nonequivalent propositions that only consist of $P_1, P_2, P_3$ and use the $\iff$ logical operator is?$$A)7\text{ }B)8\text{ }C)1\text{ }D)16$$

I am really uncertain about what the question is asking. Is it asking me to find all the possible propositions using the $P_1, P_2, P_3$ terms and logical operators (e.g. $\land, \lor, \neg$...) and see which ones have the same value?


texts:
I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$

I know that I need to prove by induction on the length of the word but I am not sure how to do the induction step.

My try:

Anchor: After processing the only string of length zero, ε, the automaton is in state $q_0$ as claimed.

Hypothesis: After reading a string u the automaton is in state $q_1$ iff $u=xa$, and in state $q_2$ iff $u=xab$ and in $q_0$ iff $u=ε$ or $u=xb$. The claim holds for input fragments of length up to n.

Step: Any string $v$ of length $n+1$ is either $v=ua$ or $v=ub$

We split to cases:

$v=ua$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q_0$ or $q_2$ - there for if we call $a$ after that we get to $q_1$ so $ua$ is not accepted.
Also, if $u$ ends with $a$ then it must be in $q_1$ - there for if we call $a$ after that we get to $q_1$ so $ua$ is not accepted.
$v=ub$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q_0$ or $q_2$ - there for if we call $b$ after that we get to $q_0$ so $ub$ is not accepted.
Also, if $u$ ends with $a$ then it must be in $q_1$ - there for if we call $b$ after that we get to $q_2$ so $ua$ is accepted.


texts:
The Queen of England wants to organize a set of tables for n guests talking different languages. The tables have to be set in a way that every guest can speak to his neighbor on the right and his neighbor on the left.

Four possibilities come up :
1- One table for all guests.
2- One table for all guests, but we alternate between men and women.
3- Guests are grouped 2 by 2 (n/2 tables)

The problem seems to me similar to the Minimum Spanning Tree. The graph would have nodes of guests connected if the two guests can speak the same language. But there seems to be more than this to it. I'm going to continue trying to find a classic graph problem that can represent this problematic. Any help is greatly appreciated. I have an exam in graph theory next week. Wish me luck.


texts: Can a CD disk and the memory of a device have an infinite space storage?

texts:
I’m asking this because, I’m thinking that it is possible to make a CD or ps vita cd to have an infinite space storage so that new updates will come.

And, it is possible for the company Sony to make the new memory of ps vita to be infinite space storage?

Can anyone tell me if it is possible for a company to do that?

Out of curiosity.

Sorry if I have asked in a wrong site and for adding this tags, you can edit this post.


texts: Question on the paper ``Self-Testing/Correcting for Polynomials and for Approximate Functions''

texts:
I am having some trouble really getting to a precise understanding of some of Self-Testing/Correcting for Polynomials and for Approximate Functions and would greatly appreciate help. Here is my understanding of section 3, Self-Testing Polynomials.

My main problem is that the definition of the function $g$ seems to require a theorem that isn't cited. Details below.

One is given a program $P$. This program (supposedly) computes a polynomial function $f$. This polynomial $f$ is defined implicitly by saying that $f$ is the interpolating polynomial, over some finite field $F$, of data points $(x_0,y_0)$, $(x_1,y_1)$, $\dots$, $(x_n,y_d)$. In other words, $f$ is the lowest degree polynomial satisfying for all $i=0,1,\dots,d$, $f(x_i)=y_i$. In any case, $P$ ought to be very quick to compute, the best case scenario certainly being where $P$ is a list of (supposedly) all values of $f$ pre-computed.

One wants a quick way to verify that $P$ does its job as advertized, at least mostly.

During the proof that the program Polynomial Self-Test has the desired properties, one introduces the function $g$ defined as
$$\forall x\in F,\quad
g(x)=\mathrm{maj}_{t\in F}
\left\{\sum_{i=1}^{d+1}\alpha_i P(x+i\cdot t)\right\}$$
where the $\alpha_i$ are the field elements that satisfy, for any polynomial $Q$ of degree $\leq d$,
$$Q(X)=\sum_{i=1}^{d+1}\alpha_i Q(X+i\cdot T)$$
These exist and can be defined in terms of the inverse of a Vandermonde matrix, and the paper even tells us they are binomial coefficients up to a sign.

The goal is nicely summed up by the authors: prove that under certain circumstances, the function $g$ thus ``defined'' is indeed the interpolating polynomial of the data, and mostly agrees with $P$:

  It is not clear to me how to interpret the definition of $g$. There are two definitions one could come up with:

    1) $g(x)$ is the value that comes up most often from all the $\sum_{i=1}^{d+1}\alpha_i P(x+i\cdot t)$, but this would require us to break ties (probably arbitrarily). This is unacceptable considering a lemma further down that tells us that under certain conditions $g$ is precisely the function $f$ sought after

    2) If we consider the totality of values $\sum_{i=1}^{d+1}\alpha_i P(x+i\cdot t)$, for all $t\in F$, there always is a $50\%+\epsilon$ majority of one value. In which case the definition is unambiguous, but which would require a proof, likely saying that if $\delta$ is small enough (and hopefully ``small enough'' can entirely de defined in terms of $d$ and $\delta$, i.e. not using the cardinality $|F|$ of the finite field $F$)

    2') Or we could leave $g$ undefined in those cases where no $50\%+\epsilon$ majority arises, but that would surely make the analysis more complicated.

  It seems only the second one makes sense, and when considering a proof that comes afterwards, it seems this is indeed the definition they are using. However, it would require proof that with $\delta$ small enough, a  $50\%+\epsilon$ always happens.

Here $1-\delta$ is defined as (I believe there is a typo in the paper here):

When doing a similar analysis with $F_2$-linear maps $F\to F_2$ for a field of characteristic $2$, there is a very cute result from representation theory that tells us that if $f$ satisfies the defining equation of a linear map ``$f(x+y)=f(x)+f(y)$'' often enough, then it agrees with an actual linear map at least as often (in terms of Hamming distance). It seems the authors are aiming for a similar result here, but there is a piece missing as far as I can tell.


texts: Where do transformational grammars stand in the Chomsky Hierarchy?

texts:
From what I understand, natural language are too complicated to be generated by a context-free grammar, yet parsing a context-sensitive grammar is too computationally demanding for our brain to be continuously performing. So it seems that if our brain indeed has a "syntax" module to parse sentences as Chomsky claims it does, then whatever it's doing should sit somewhere between CFGs and CSGs in terms of computational complexity.

I'm really not familiar at all with Linguistics in general and even less so with Chomsky's work, but (correct me if I'm wrong) the point of transformational grammars was to explain this?

For those not familiar, a transformational grammar consists of a CFG to generate syntactically valid sentences, and also on top of this "transformational" rules, that transform these valid trees to form other valid trees. A common example is affirmative->question transformation ("John has eaten all the heirloom tomatoes." -> "Has John eaten all the heirloom tomatoes?").

It is not clear to me why such tree transformations couldn't be integrated into the CFGs by adding more rules (for example, question-form sentences can clearly be generated instead of being transformed from an affirmative sentence).

If I am right (in that transformational grammars sit between CFGs and CSGs), could someone give me an example showing both relations (that TGs are more expressive than CFGs but less expressive than CSGs). If I'm wrong, then please help me increase my knowledge of linguistics by pointing me towards valid readings.


texts:
Is there a nice way to give context free grammar for
$$\{a^nb^ma^kb^l:n+m=k+l\}?$$

From PDA point of view it seems we just push + on stack if we see a, push + on stack if we see b, pop + from stack if we see a, pop + from stack if we see b and accept if you have empty stack.


texts: Time-Sensitive Reductions for Undecidable Problems

texts:
I'm studying Comparability and Complexity, and through the course, a number of problems (namely, the halting problem for Turing Machines, etc.) have been proven undecidable through elementary proofs and reductions.
Next, the course discusses polynomial time reductions between several problems, which makes sense: it's reasonable to explore which problems are "about as hard".
Finally, we discuss such polynomial time reductions between a few undecidable problems. For example, we prove that $HALT_{TM}$ is polynomial-time reducible to $A_{TM}$, but that $ALL_{TM}$ is not polynomial-time reducible to $E_{TM}$.
This threw me off a bit - if two problems are undecidable, why it's interesting to investigate complexity properties of them?


texts: Algorithm to save state of array as it changes

texts:
There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be retrieved upon querying.

For ex -

Initially, the array is [7, 8, 9]. This is version 1.
Next, 90 was added. Version 2 is [7, 8, 9, 90].
Next, 23 was added. Version 3 is [7, 8, 9, 90, 23].
Next, 90 was deleted. Version 4 is [7, 8, 9, 23].

And so on.

I need to write a function, get_version(ver_num), which returns the state of the array for each version. So, running get_version(3) should return [7, 8, 9, 23].

I have thought of saving incremental changes to the array in each iteration, in the form of an array maybe.

For ex -

[("add", [7, 8, 9]), ("add", [90]), ("add", [23]), ("subtract",[90])]

This will save space but in order to recreate the array for a specific version, I have to iterate over this array until I reach the required version. Is there a way better than this?

Thanks


texts: Determining the intersections of a line segment and grid

texts:
Problem: Given a line segment on the cartesian plane, determine where and which order it intersects a regular grid.  This sounds simple, but is actually quite a tough problem.  It's related to, but distinct from, both Bresenham and supercover.
More specifically, consider:

A line segment with start $(x_1, y_1)$ and end $(x_2, y_2)$
A grid of cells, bounded by all lines $x = k$ and $y = k$ for all integer $k$
Each cell therefore has four boundaries, called North, South, East, and West

The example plot shows the segment from (0.6,0.4) to (-0.2, 2.2) crossing three boundaries.
For a given line segment, we wish to determine the cell boundaries it crosses:

For each boundary type, the number of crossing. {N:2 S:0 E:0 W:1} in the example.
The sequence of crossings. {N, W, N} in the example.
The grid position of each crossing, defined as $(x - floor(x), y - floor(y))$.  Approximately N: (0.35, 1), W: (0, 0.8), N: (0.8, 0) in the example.

I'll note that the problem as-is is not fully defined: line segments starting or ending on a boundary, coinciding with a boundary, and crossing a vertex all need definition.  We can accept any reasonable, consistent definition of these.
Solving #1 is easy:
number of east (west if neg) crossings = floor(x2) - floor(x1)
number of north (south if neg) crossings = floor (y2) - floor(y2)

Solving #2 and #3 is surprisingly hard.  I've come up with three approaches:

Direct.  The ideal would be to calculate this directly (that is, without iteration), similar to the formula for #1.  I have made no progress here.
Iterative.  Determine the next crossing (by trying both directions and determining which is crossed first).  Determine how far along the segment that is.  Repeat until done.  This works, though it lacks elegance or speed.  The other issue is that chopping the segment repeatedly, if not done carefully, can cause inconsistency with floating point calculations leading to missed or double crossings.
Mixed.  Use the calculation above to determine the total number of crossings of each type.  For each, one $(x,y)$ coordinate is an obvious integer, and the other can be solved using simple algebra, as can the length of the segment to that point.  Sort by segment length.

#3 is the best approach so far.  Is it possible to do better?


texts: Algorithm to partition students in two groups maintaining brotherhood (related to COVID19 pandemic)

texts:
I need to find an algorithm for the following problem. Any idea to which kind of algorithm to look for as starting point is welcomed. Should I look for a graph algorithm? Combinatorial problem? Mathematical or dynamic programming?

Objective:

I have a set of 48 classes with 25 students each. I need to divide each class in two groups, lets call them A and B. There are the following constrains:

Some students have brothers/sisters in other classes. I need that all brother/sister be in the same partition A or B. This
should be a hard condition that must be fulfilled by the solution.
A second constrain is that girls and boys should be equally divided in the both partitions of each class. If class 12 has 11 boys and 14 girls; the partition should be: partition 12A with 6 boys and 12 girls and partition 12B with 5 boys and 12 girls. This constrain is not hard, it may be violated by the solution slightly.

What if the number of constrains increases a lot.

In the comments, it is suggested to use a greedy algorithm, because it is easy to move students with no constrains (no siblings) from one partition to another.
What to do if the number of constrains is very high. For some reason we have a lot of constrains of the type: studentA can't be in the same partition of studentB, ... What algorithmic approach is best?

Some numbers:

There are around 1200 students, divided in 16 years. Each year has 3 classes. The ratio girls and boys is, as expected, 1:1.
There should be between 500 and 600 brother/sister relations.

Background:

Due to the COVID19 pandemic it is possible that next school year, students may be separated in two groups. These groups will alternate going to school and staying at home. To easy the logistics for parents, it may be desirable to have all siblings in the same group, going to school or staying at home.


texts: An algorithm to detect if the conversion rate growth acceleration rate is still rising or stopped

texts:
An example.

I have bought a currency while the rate was 1.0. As soon as the conversion rate has increased to 2.0 I would like to sell the currency. Now, that would be an easy task to do. But we are not searching for "easy" tasks, are we?

What if there was a way to determine, whether the rate is still growing or not? For example, what if the conversion rate was still growing at +0.5 per minute, in that case - I would be able to sell the currency at rate 3.0 if only I have waited for 2 more minutes. Alternatively, I would be able to sell the currency at an even higher rate, if it was determined that the acceleration rate either stopped, or became negative.

Here is a visual representation of what I want to accomplish:

black line - good, but too early to sell
green line - sell now
red line - better sell it now, before rate decreased

Is there an algorithm to accomplish this task?

At this point - it is not clear to me:

What would be the best time range to take into acceleration rate calculations. Should I consider the rate change during the last 10 minutes, 5 minutes or 20 seconds?
How do I determine that the "growth" (acceleration rate) has stopped or is close to being stopped?
Do I only need to know only the conversion rate, or also number of trades (buys/sells) at a given time frame?

Any advices are appreciated.


texts: What units should Shannon entropy be measured in?

texts:
The only examples I've seen use bits as a measurement of entropy, but all these examples happen to use binary code alphabets. If we wanted to see how well a coding with a code alphabet of length n works, would we measure entropy in units of n?

Or would it make sense to stay using bits if we're comparing codings with binary and n-length code alphabets?


texts: What TSP variant doesn't return to start point?

texts:
For my case I have starting point and several cities.

I want the shortest route to visit all cities without returning starting point.

I have read several TSP algorithm and all include the return a full cycle.

So what TSP variation should I look for to solve my problem?


texts: Clarification of definition of class $DisNP$

texts:
I an trying to learn about $DisNP$ Complexity class. I couldn't find this class in any book. But, regarding it, I found this definition in a paper:

Definition: A disjoint NP-pair (NP-pair for short) is a pair of nonempty sets $A$ and $B$ such that $A, B \in NP$ and $A \cap B = Empty$. $DisNP$ denote the class of all disjoint NP-pairs.

Now I am aware that when a problem like $SAT$ etc. is said to be in $NP$, it means that assuming we have a NDTM we can get the solution in polynomial time. Or in other words, if we can guess the solution, then the verification takes polynomial time.

But, what does it mean when we say a set $A \in NP$ or a set $B \in P$.

Does the elements of the sets represent the solution for which the corresponding $SAT$ instance for each set is true i.e. set $A$ and $B$ contain the solutions of some $SAT$ instances $SAT_A$ and $SAT_B$ such that $SAT_A$ is satisfiable iff its solution is in the set $A$?

I am not clear how we use sets (which I assume have binary strings) for defining $P, NP, NPC$?


texts: Maximum length path between any two nodes in a tree with possible negative edge weights

texts:
Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a graph with edge weights 1 but that won't work here.

All I can think of is going for a $O(N^2)$ approach with LCA but thats a glaringly bad approach for huge trees ($N \sim 100000$)


texts: How to do training & inference with denoising autoencoders?

texts:
Following the development in the Goodfellow book:
https://www.deeplearningbook.org/contents/autoencoders.html (sec 14.5)
I have 2 questions:

To me the text seems to imply that we are doing SGD only over the parameters of the decoder, and assuming a fixed encoder $f$. But this can't be true right? The original paper (2008) describes doing descent on both decoder and encoder.

Assuming we have trained a DAE using some noise corruption model $C$, when we use the model to create representations of inputs, we feed it the uncorrupted input $x$. But won't this take the encoder outside its training distribution? For example, suppose $C$ used salt-and-pepper noise, then the model is likely to create a representation that assumes that extreme values of input features are likely corrupted even if given extreme values in noise-less input. I suspect the manifold interpretation of DAE (fig 2 in the paper or fig 14.4 in the book) helps explain why the encoder still performs well on uncorrupted input, but I dont have a crisp argument.


texts: Show that a function belongs to grade of incline

texts:
This is a Data structures & Algorithms question. For instance I have the following grades of functions: $O(1), O(2^n), O(n \log n), O(e^n), O(n^3), O(n^{1/3})$ and $O(\log \log n)$

I need to show and proof to which of these function grades does the function: $n^7$ belong to.
I didn't get a chance to ask my professor on this topic so I'm not sure how to solve this problem.


texts:
When you learn programming they tell you choose data types that suffice for the concepts you're expressing, i.e. not too small because then your data won't fit and not too big because you don't want nonsensical values stored.

Table of unsigned integers

8-bit: 0 to 255
16-bit: 0 to 65,535
32-bit: 0 to 4,294,967,295
64-bit: 0 to 18,446,744,073,709,551,615

According to the table above, an 8-bit unsigned integers can store e.g. the number of weeks in a year (approximately 52) and a 64-bit unsigned integer can store e.g. astronomical values.

To get to the point of my question; how do the different variable sizes affect the performance of a program? I imagine that a 64-bit CPU internally handles all variables as 64-bit and simply ignores the highest bits, so an 8-bit variable, travelling across the system, would be handled as:

xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx yyyyyyyy

Where y is either 0/1 and x is ignored.

Would it make any difference performance-wise to only use the largest variable size on the platform and use business logic to enforce reasonableness in the values being processed and stored? Is there a performance hit when using variable sizes lower than the native variable size of the architecture?


texts: Strassen algorithm for matrix multiplication complexity analysis

texts:
I see everywhere that the recursive equation for the complexity of Strassen alg is:
$$T(n) = 7T(\tfrac{n}{2})+O(n^2).$$ This is not so clear to me.
The parameter $n$ is supposed to be the size of the input, but it seems that here it is one dimension of a matrix while the input size is actually $n^2$.
Also, each matrix of the input is divided to 4 sub matrices so it seems the recursive equation should be $$T(n) = 7T(\tfrac{n}{4}) + O(n).$$


texts:
$A$ is finite, $B$ is NPC - When there's a polynomial reduction from $A$ to $B$?

Basically, I've understood that if $A$ is finite, then there's a reduction for every $B$ which isn't trivial (empty or $\Sigma^*$).

BUT, if $B$ is NPC then $B\ne \emptyset, \Sigma^*$, so in which case there's is no polynomial reduction from $A$ to $B$?


texts: Algorithms for MinSat when all literals are positive?

texts:
I am given a set $U = \{1, \cdots, n\}$ and a set of subsets $C_1, \cdots, C_k$ of $U$; here the sets are all the same size.

The minimum set-cover problem of course is to find the minimum number of the $C_i$ such that their union is $U$.

I'm looking at the "opposite" problem: I want to find the minimum-size subset $K$ of $U$ such that every $k \in K$ has that $k \in C_i$ for some $i$.

Edit: I researched more and this is the Minimum Satisfiability problem. One can formulate the problem as a CNF SAT formula: the formula is the conjunction of $(c_{i,1} \vee \cdots \vee c_{i,m} )$ where the $c_{i,j} \in C_i$ for all $i$.

The MinSat problem is NP-complete in the general case, but here all of the literals are positive. Are there faster algorithms for this case?


texts:
Given a two-dimensional data set where each point is labeled $ \{0,1\}$, I want to implement a sparse classifier with $L_p \ \text({ 0<p \leq 1) }$.

I have been reading on logistic regression and regularization. Let me give you an example of what I have been working on.  The concrete example is:  Let $\left((x^{(i)},y^{(i)} )\right)_{i\in \{1,\dots, m\}} $ be my data set with  $y^{(i)}\in \{0,1\} $ and $x^{(i)}\in \mathbb{R}^2$. And the cost function I minimized is

$ J(\theta) = - \frac{1}{m} \cdot \sum_{i=1}^m \large[ y^{(i)}\ \log (h_\theta (x^{(i)})) + (1 - y^{(i)})\ \log (1 - h_\theta(x^{(i)}))\large] + \frac{\lambda}{2m}\sum_{j=1}^n \theta_j^2$.

where $h_\theta(x) = \frac{1}{1+e^{-\theta^{T}x}}$.  I thought that this would be a good introduction to sparse.
Currently I use a neural networks and was wondering if I am heading in the right direction in understanding sparse methods.

That leaves me with the question:

What is the definition of sparse classifiers? What would be an example?


texts: Can someone help me come up with a formula for calculating the difference in time?

texts:
So my assignment is to write a program that prompts the user for two different times on the same day (with 0 being midnight, 0700 being 7:00 am and 2200 being 10 pm) and then returns the difference between the two times with the amount of hours and amount of minutes elapsed. For example, if the user inputted 1255 and 1305, the program should return 0 hours and 10 minutes. I'm fine with how to find the number of hours but I cannot come up with a formula for finding the difference in minutes. Here is what I have so far:

    Scanner keyboard1 = new Scanner(System.in);
    System.out.print("Train A departs at: ");
    int a = keyboard1.nextInt();

    Scanner keyboard2 = new Scanner(System.in);
    System.out.print("Train B departs at: ");
    int b = keyboard2.nextInt();

    int difference = Math.abs(a - b);
    int hours = difference / 100;
    int minutes = (I need help here);

    System.out.print("\nDifference: " + hours + " hours and " + minutes + " minutes");


texts: Converting regular language to regular expression by replacing commas with union

texts: I know that regular languages are those that can be described by regular expressions. For the language {0,1}*, is the corresponding regular expression (0∪1)* ? If so, does replacing braces with parentheses and commas with union always work when converting from regular language to regular expression?


texts: Find a list of actions that result in desired state

texts:
I have a problem that I need to solve, and I'm looking for which area of computer science (algorithms. etc) would be appropriate to solve this problem.

In the system we have a list of actions that a user has previously taken. The possible actions are:

User creates item of type A.
User creates item of type B.
User creates item of type C.

The date and time the action was taken is also recorded.

We have a function passesRules which takes the list of all actions the user has previously taken as input, and applies a set of rules and returns a boolean. The boolean is true if any of the rules are true, and false if none of the rules are true.

There are many possible rules, but in general they take the form of:

Has user created 5 items of type A in the last 10 days?
Has user created 2 items of type B in the last 3 days?
Has user created more than 6 items of type C in last 5 days, AND
created 3 items of type A in the last 10 days?

What I want to do is to create a function predictActions which predicts the actions the user must take so that passesRules returns true.

Obviously with the rules described above there are multiple different sets of actions that could make passesRules return true. I would like predictActions to return an array where each element in the array is a list of actions the user could take to make passesRules return true.

predictActions should take the following parameters:

The list of actions the user has previously taken.
The list of rules.
The current date.

I'm not asking for a solution, but I don't know what area of computer science to investigate further to model and solve this problem. Something from graph theory, or some type of constraint solver?

Thanks!


texts: Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

texts:
So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces are inserted into each sequence and how many times each possible pair of aligned characters appears in the alignment. Just like longest common subsequence, finding the optimal alignment of two strings under an arbitrary linear scoring scheme can be solved in quadratic time using dynamic programming. (Needleman-Wunsch algorithm). The longest subsequence problem and variants that use linear scoring schemes and ask for the optimal multiple sequence alignment are NP-hard when the number of input strings is not fixed.

However, in biology, there is a probabilistic generative model that generates related DNA sequences. Starting with an unknown root ancestor DNA sequence, bifurcations occur that create two daughter sequences (species) that are independently derived from the ancestral sequence by potentially adding some characters in random locations, deleting some characters, and changing some characters. Then the bifurcations continue with additional changes at each level until the modern day DNA sequences of extant species are obtained. Then we want to align the modern day species' sequences (e.g. find the longest common subsequence in the simplest case) without knowing the exact ancestral sequences. In this case, fossil records can help identify the bifurcation events and estimate the sequence mutation rates after each bifurcation. So a reasonable estimate of the generative model that generated the related modern day DNA sequences can sometimes be obtained.

Now, my question is, for such an NP-hard optimization problem with a well-defined probabilistic generative model that generates input data, has anyone studied the hardness of finding either an optimal or nearly optimal solution, where either the worst-case or expected running time depends on the parameters for the model that generates the input data? For example, if DNA mutation and insertion/deletion rates are very low for a particular group of species, then it should be fairly easy to get at least a nearly optimal alignment of all the DNA sequences using partial alignments and pruning and heuristics, without resorting to a full-blown exponential time solution.


texts: On the diamond property for $F_{\omega}$ in TAPL

texts:
In page 455, of Pierce´s TAPL and page 560, the single-step diamond property of reduction:

  $S \Rrightarrow S' \land T \Rrightarrow T' \implies \exists V. T \Rrightarrow V \land U \Rrightarrow V$

is proved. The argument goes by induction on the total sizes of the given derivations, with a case analysis on the final rules of both. I think this is a bit of an overkill since I think I have a proof by induction on $S$.

If $S = X$ then $T=U=X$ and we can take $V = X$.

If $S = S_1 \to S_2$ then $T = T_1 \to T_2$ and $U = U_1 \to U_2$ where $S_1 \Rrightarrow T_1, S_2 \Rrightarrow T_2, S_1 \Rrightarrow U_1, S_2 \Rrightarrow U_2$. By induction hypothesis, $\exists V_1,V_2. T_1, U_1 \Rrightarrow V_1, T_2,U_2 \Rrightarrow V_2$ and by the rule QR-Arrow $T \Rrightarrow V_1 \to V_2, U \Rrightarrow V_1 \to V_2$.

The rest of the cases are similar with the help of lemma 30.3.7:

  $S \Rrightarrow S', T \Rrightarrow T' \implies [Y \mapsto S]T \Rrightarrow [Y \mapsto S']T'$

for the case QR-AppAbs.

Could you help me understand what's wrong with my proofs?


texts: During a technical interview I was asked about ways to make sure code/software design is functional before deploying to any servers and the only thing I could think of was unit testing. My interviewer pressed me for other ways but I couldn't come up with any alternatives.


texts: What is the difference between "strict schedule" and "cascadeless schedule"?

texts:
In database transactions theory, what is the difference between a strict schedule and a schedule that is merely secured against cascade aborts?

Could you give an example of a schedule that is secured against cascade aborts but is not strict?

I found these slides that give definitions but it's still not clear to me where is the difference (they just seem differently worded).


texts: Finding the best poker hand in a connected grid structure where order matters

texts:
I am trying to find the best poker hand in a connected grid, where order matters. An illustration is the best way of explaining the situation.

This grid has 12 random cards, in random positions. Each card is connected to the vertically, horizontally and diagonally adjacent cards.

The hands are standard poker hands but no extra cards are allowed – only the cards which constitute the hand. So, a pair is only two cards connected, four of a kind is just four cards connected, etc.

The best hand for this grid highlighted:

Order matters, so a straight must be in the correct order (e.g. 10, J, Q, K, A is valid but 10, A, J, Q K is not). There is no straight in this particular grid, the 10s are not connected to the Jack directly.

I am looking for an algorithm that finds the best hand for a random grid. The grid isn’t ever going to be much larger than this grid of 12.

I am also looking for an algorithm that finds out if there are no moves at all – this would alert the player to this fact to save them searching for too long…


texts:
Is there a list of implications of $P=NP$?

Presumably, a proof of $P \ne NP$ will be by contradiction, for which a list of consequences of $P=NP$ would be useful.


texts: How is this equation (involving a recurrence and $\phi(N)$) derived?

texts:
As in another question, let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\
T(\phi(N)) + \lg(\phi(N))^3 & \text{otherwise}
\end{cases}$$

where $\phi(N)$ is Euler's totient function.

Tasse kindly reasoned that we can write

$$T(N) = T(\phi(N))+\log(\phi(N))^3 = T(\phi(\phi(N)))+\log(\phi(\phi(N)))^3 + \log(\phi(N))^3$$

I can't at all see why this is true.  How is this equation derived?  I do understand his proof that $\phi(\phi(N)) < N/2$.


texts: How are useless states created NFA to DFA

texts: So I understand how to convert an NFA to a DFA, however my question is, on a conceptual level, how and why are useless states created, and how can you (if there is a way) convert an NFA to a DFA without creating any useless states?


texts: Can a non-regular language $L$ have a non regular $L^*$?

texts: I have been looking around and i cant seem to find an example of such case that a non-regular $L$ has a non regular $L^*$. Is it possible? If so, can you provide an example of such case please?


texts: sum of max flow in residual graph and value of flow

texts:
My teacher today explained us this . Consider a network and suppose that at any stage during the application of the Edmonds Karp algorithm to find the max flow, let

f = value of flow in the network at this stage
t = value of the max flow in the residual graph of this flow
F* = max possible value of flow in the original graph [which will be finally outputted by the whole algorithm]

He claimed that

f+t = F*.

I am not able to prove this. Can someone please help?

EDIT : I am certain that if we prove that each time we augment the flow , the value of the max flow in residual graph decreases by the amount by which we augment the original flow , then we would be done , since in the beginning

f = 0
t = F*


texts: Is Phong shading a pixel-first computational model?

texts:
Wikipedia says that:

  If a mesh covers more pixels in screen space than it has vertices, interpolating colour values from samples of expensive lighting calculations at vertices is less processor intensive than performing the lighting calculation for each pixel as in Phong shading.

Why does it matter that there are more pixels than there are vertices? In the quote it also says that Gourand shading performs lighting calculation "at vertices" while Phong does it in pixels.

I have always thought that both shading schemes are the same, just that Gourand interpolate colours along vertices, while phong creates a reflection vector to interact with the light sources for specular reflection. Is this correct?


texts: Difference between IO threads and worker threads

texts: I have read that NodeJs is able to support hundreds and thousand of concurrent calls because the worker threads do not wait on the IO calls to complete. They use event driven IO.  Similarly in .NET we have Async keyword which allows the worker thread to be returned to perform other tasks while the "IO" call is executing. How does that all work.  There has to be some thread monitoring for the IO to complete and notify when its ready?


texts: Runtime of algorithem when the internal for depend on the external for

texts:
I'm trying to find the running time of this pseodocose:

int x=0,i,j
for (i=1;i<=n;i++)
    for(j=1;j<=n+r;j=j+i)
       x=x+j;

What I did: First I checked  what happened on the first iteration of the external for:

$i=1:$ the internal for will run $n+r$ times, so $j\in\{1,2,3,4,\dots,n+r\}$ so $\color{blue}{a_n=n}$
$i=2: $ the internal for will run from $j=1$ to some $k\leqslant n+r$ such that $j\in\{1,3,5,7,\dots,k\}$ so $\color{blue}{a_n=2n-1}$
$i=3$: the internal for will run from $j=1$ to some $k\leqslant n+r$ such that $j\in\{1,4,7,10,\dots,k\}$ so $\color{blue}{a_n=3n-2}$

So the runnig time should be $\color{blue}{\underbrace{n+(2n-1)+(3n-2)+(4n-3)+\dots}_{ n+r \text{ times}}}$

But what should I to now? I should find the running time in $\Theta$ terms, I am trynig to find the runnig time without using any calculator