texts: How are statistics being applied in computer science to evaluate accuracy in research claims?

texts:
I have noticed in my short academic life that many published papers in our area sometimes do not have much rigor regarding statistics. This is not just an assumption; I have heard professors say the same.

For example, in CS disciplines I see papers being published claiming that methodology X has been observed to be effective and this is proved by ANOVA and ANCOVA, however I see no references for other researchers evaluating that the necessary constraints have been observed. It somewhat feels like as soon as some 'complex function and name' appears, then that shows the researcher is using some highly credible method and approach that 'he must know what is he doing and it is fine if he does not describe the constraints', say, for that given distribution or approach, so that the community can evaluate it.

Sometimes, there are excuses for justifying the hypothesis with such a small sample size.

My question here is thusly posed as a student of CS disciplines as an aspirant to learn more about statistics: How do computer scientists approaches statistics?

This question might seems like I am asking what I have already explained, but that is my opinion. I might be wrong, or I might be focusing on a group of practitioners whereas other groups of CS researchers might be doing something else that follows better practices with respect to statistics rigor.

So specifically, what I want is "Our area is or is not into statistics because of the given facts (papers example, books, or another discussion article about this are fine)". @Patrick answer is closer to this.


texts: Improving QuickSort Algorithm with pivot as first element

texts:
I was trying to improve the algorithm since its the most effective and known algorithm among many others, I came across " Quicksort algorithm with an early exit for sorted subfiles 1987 by University of Tulsa, Roger L. Waiwright" check it out its interesting, do you guys know any other ways/researches ?
I think reducing the memory would work by reducing the amount of arrays and working on one array idk how I am going to do that.

doing bubble sort or selection sort for large arrays isn't helpful and checking if a big array is sorted using them would increase the complexity.
P.S: I am just learning and studying not doing a research etc.

Quicksort algorithm with an early exit for sorted subfiles


texts: Is $L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $ regular?

texts:
Suppose we have some regular language $L$, then can we say that $$L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $$
is also regular?

I have a 'feeling' that it is, but I can't sketch a proof for it.


texts: How can I quantify the number of swaps required for insertion sort?

texts:
Based on the Wikipedia implementation of insertion sort:

Given an input array $A$:

for i ← 1 to length(A)
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1

is there a way to quantify how many swaps are needed to sort the input list? It's $O(n^2)$, but I want a more precise bound. A perfectly sorted array clearly needs no swaps (so insertion sort is $\Omega(n)$), while a completely reversed array requires something on the order of $n^2$ swaps, but how do we quantify the number of swaps?


texts: How do POMDPs and Dynamic Influence Diagrams differ?

texts:
To give some perspective, first consider the following diagram comparing Markov Chains, HMMs, MDPs, and POMDPs (I'm not sure who to credit for it).

                    Fully observable          Partially observable
                _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
               |                         |                           |
    no actions |      Markov chain       |           HMM             |
               |_ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|
               |                         |                           |
    actions    |          MDP            |          POMDP            |
               |_ _ _ _ _ _ _ _ _ _ _ _ _|_ _ _ _ _ _ _ _ _ _ _ _ _ _|

Recall that an HMM allows us to model probability distributions over a sequence of observations. Bayesian networks (not pictured) are a generalization of HMMs which model conditional distributions over sets of random variables (see here for a description). When modeling a problem over time, one appends a time index to the model resulting in a dynamic Bayesian network.

A tool known as a dynamic influence diagram extends dynamic Bayesian networks to decision-making problems through the inclusion of actions that can effect the evolution of the problem.

My question is: how do dynamic influence diagrams and POMDPs compare? On the surface they seem like they are modeling the same problem type. What sort of problems are amenable to each tool?


texts: Programming languages for genetic engineering

texts: I'm interested in getting a Ph.D. and would love to work on a project such the GEC project at Microsoft Research, which studies the application of programming languages for synthetic biology and genetic engineering. What groups are doing work like this in a university setting?


texts:
What is an upper bound on formula size when converting 3-SAT to UNIQUE 3-SAT?

We can use the Valiant Vazirani Therom, also found here (in more detail).

Essentially, it is a randomized algorithm that converts a SAT formula into another SAT formula that has only 1 satisfying variable assignment (called UNIQUE-SAT) with high probability.

I'm wondering what the upper bounds are on the size of the formula.  The information I have proves that it is polynomial, but I hope we can get more specific.  Can anyone find a more exact upper bounds?


texts: Could my algorithm be considered Divide-and-Conquer?

texts:
So for my homework, I was supposed to design an algorithm which was divide-and-conquer that fulfilled the task of finding the two smallest numbers in an array of size n.

I recognize that my version is a bit cheap in that regard, in that it uses reference variables and only does work on the size 1 cases of the recursion. Is this still technically considered divide-and-conquer? Or is it practically too close to a linear search. If it is divide-and-conquer, how could you express the recurrence relation when the work is being done only on the "leaves" of the recursion.

   find_mins(int A[], int& min, int& sec_min, int l, int r){
    int pivot = (l+r)/2;

    if(l==r){
      if(A[l] < min){
        sec_min = min;
        min = A[l];
        return;
      }
      else if(A[l] < sec_min && A[l] > min){
        sec_min = A[l];
        return;
      }
      return;
    }

    find_mins(A,min,sec_min,1,pivot);
    find_mins(A,min,sec_min,pivot+1,r);

}

"Pseudocode"

FUNCTION(Array, min1, min2, left, right)
  Find pivot
  if(size of subproblem is 1)
    calculate mins
  function(Array,min1,min2,1, pivot)
  function(array,min1,min2,pivot+1,right)

Keep in mind, the code really isn't all that relevant, I just am curious if the structure fits divide-and-conquer description. My concern is that because work is only being done on the case where the size is 1, that it's more of a "linear search" than anything else.


texts: MULT in a RISC - should instructions take the same amount of time in a RISC system

texts:
I am studying computing  as part of my A level course, and my understanding is that all instructions in a RISC architecture should execute in roughtly the same, small number of clock cycles (ideally one).

This leads me to ask how multiplying two (possible very large) numbers takes (roughly) the same time as all the other commands, such as LOAD, STORE, ADD, etc.
I believe the most common way a computer multiplies numbers is using a Binary Multiplier, which requires multiple addition executions, meaning that a multiplication, or PROD command (from an example from Stanford University) will execute with many cycles per second and not be consistent with the speed/cycles of other commands from a reduced instruction set.


texts:
Assume a simple procedural language, where statements write and read from local memory via references and procedures accept arguments of n different scalar types (say floats, ints and strings) and tuples (or records or other structured monomorphic data).

When I try to embed such a language in a type-safe host language (say OCaml) I need to define the type of the memory. (Ok, I could encode it as a heterogeneous list as well, but that seems quite inefficient).

So my intuitive attempt would be to model it like this:

type mem = { floats : float array; ints : int array;
             structured : mem array}

type 'a ptr = { read : mem -> 'a; write : mem -> 'a -> unit }

let float_ptr i = { read = (fun {floats} -> floats.(i)) ;
                    write = (fun m a -> m.floats.(i) <- a) }

A float assignment would then require a float-pointer as target and so on. Since this seems quite useful, I assume that such an encoding has already been done somewhere, but without a useful name I am unable to search for it.

Is there any published work on such a memory encoding (and the required transformations etc.)?

p.s.: If someone could add the tags memory-model and embedding, I would be grateful, I had a hard time finding some adequate tags.


texts: Can you build a solver circuit from a verifier circuit?

texts:
Can you build a solver from a verifier?
I see that if you start with an NP-verifier TM the answer is yes, you can build a solver TM. How about for circuits? Can you go from a circuit that implements a verifier for instances of size n that is of size polynomial in n to a circuit that implements a solver for instances of size n?


texts:
I have been learning graph algorithms, and the concept of dynamic programming is quite succinct. However, I read that Bellman Ford is a form of dynamic programming. I am not sure why since given so many unnecessary re-computations, it is not exactly efficient in the likes of other dynamic programming that computes the sub-problems bottom up to the final problem. For example, FloyWarshall has a well defined sub structure of considering all other vertices up to k.
But for Bellman Ford, the implementation is not really relying on any computed sub problems, it is just a brute force algorithm that correctly returns the shortest path but it is not correctly computing the sub-problems in some correct order needed by a dynamic programming algorithm?


texts: Computational complexity of Doolittle's algorithm

texts:
I could not find a big-oh cost for Doolittle's algorithm for LU decomposition of a matrix online, so I took a pseudocode implementation from here
 and analyzed it to get $$\frac13n^3+\frac32n^2+\frac16n$$ operations.

However, the same document states here that there are in fact $$\frac23n^3+\frac12n^2+\frac16n$$ operations.

I triple checked my analysis, and couldn't see where I went wrong, so I ran the following Python code:

def doolittle_complexity(n):
   ops = 0
#  for i=1,⋯,n
   for i in range(1, n+1):
#     for j=1,⋯,i−1
      for j in range(1, i):
#        α=aij
         ops += 1
#        for p=1,⋯,j−1
         for p in range(1, j):
#            α=α−aipapj
             ops += 1
#        aij=αajj
         ops += 1
#  for j=i,⋯,n
   for j in range(i, n+1):
#      α=aij
       ops += 1
#      for p=1,⋯,i−1
       for p in range(1, i):
#         α=α−aipapj
          ops += 1
#      aij=α
       ops += 1
   return ops

print([(i, doolittle_complexity(i), i/6+((3*(i**2))/2)+i**3/3) for i in range(21)])

It defines a method that adds 1 to an operation counter every time the pseudocode algorithm would have done arithmetic or assignment. Then, it prints out a list containing tuples in the format (matrix size, # of operations counted, # of operations expected by my polynomial).

When run, it outputs:

[(0, 0, 0.0), (1, 2, 2.0), (2, 9, 9.0), (3, 23, 23.0), (4, 46, 46.0), (5, 80, 80.0), (6, 127, 127.0), (7, 189, 189.0), (8, 268, 268.0), (9, 366, 366.0), (10, 485, 485.0), (11, 627, 627.0), (12, 794, 794.0), (13, 988, 988.0), (14, 1211, 1211.0), (15, 1465, 1465.0), (16, 1752, 1752.0), (17, 2074, 2074.0), (18, 2433, 2433.0), (19, 2831, 2831.0), (20, 3270, 3270.0)]

Which seems to indicate that my polynomial was correct.

Regardless, and even though I understand that they have the same big-oh cost of $O(n^3)$, I would still like to understand how they arrived at their polynomial.


texts: I am looking for algorithms to classify words in a paragraph of text. I am particularly interested in a classification to determine if a certain word is noun, verb, etc., but also looking for any kind of word-classification algorithms. I am given a smaller input (e.g. 200 words) so there is no many options for machine learning but I would really appreciate algorithms involving machine learning.


texts: How to design xml schema for digital circuits?

texts:
how can i design XML Schema for logical and digital circuits?

i cant find any help or manual for this work

for example i have a digital circuits with AND OR NOR ,... gates

now i want design xml and schema for that

thanks for help

soryy for bad english


texts: Distance of a Graph node to a group of nodes?

texts:
Consider a graph where edges represent the similarity of two nodes. In general, the graph is sparse with edges existing between only similar nodes (I can achieve this by deleting edges with similarity values below a threshold). Now, let us say I have a group of nodes who are known to be similar (say determined by a clustering algorithm). I randomly pick a node from the graph and I want to measure some notion of distance of this node to the given group (or cluster). What are the different measures considered in this regard? I understand that one can plainly look at the number of edges in the shortest path between the node and the group. Are there more measures?

UPDATE: Upon comments from others, I have decided to give the application as well. Assume that we have been given a sparse graph. Now, we have uses who select nodes from this graphs. Typical users select nodes which are close to each other. Thus, they sample from a small neighborhood in the graph and they go far outside that range very rarely. Assume that you have a set of users like that and their past choices. Given this data, there are two problems now

Identify scenarios when the user selects a node far outside his usual neighborhood in future.
Identify spam users (or bots) which randomly sample from this graph.


texts:
I'm looking for some clarifications on an algorithmic task I've been trying to solve. This task is a part of Quiz 2 from the MIT 6.006 course.
The main idea of creating k-copies of a graph G is clear. What I'm really confused with is the final graph G':

Can you explain how the graph G' will look like?
How will the G' graph guarantee that all of the places {v0, v1, v2, vi} had been visited once we reached the destination vertex t?

I'm sorry if the community to post this question is wrong. Any suggestions are highly appreciated.
Input:

Solution:


texts: Get every possible (connected) subgraph containing x number of nodes

texts:
If I had a graph representing the USA with each node representing a state, and each edge linking adjoining states, is there a graph algorithm that would give me every possible unique group of 4 states that are linked (order of states is not important)?

By 'linked' I mean that all states in valid group should be reachable from every other state in the group either because they are adjoining (direct neighbours) or connected via another state in the group, eg :

One valid group is Kansas, Nebraska, Iowa, Missouri (since Nebraska, Iowa, Missouri are direct neighbours of Kansas)

But also Kansas, Colorado, Utah, Nevada is valid since Kansas is a neighbour of Colorado which is a neighbour of Utah which is a neighbour of Nevada (even though Kansas and Nevada are not direct neighbours)

It seems to make sense to me to represent this data in a graph or adjacency matrix since 'connectivity' is the key qualifier. Generating every combination of 4 states, then testing for connectivity seems wasteful and even more so if I wanted every combination of 5,6,7... states.

I don't have much knowledge in this area, but I thought this may be suited to a graph theory type problem, but cannot find anything that matches this type of problem, so I am probably looking in the wrong area.

Can anyone give any advice, areas for me to read up on ?


texts: Solving recurrence relation with minimum and factorial

texts:
I need to solve the following recurrence relation, where $T(n,m)$ is defined over $\Bbb N_+\times\Bbb N_+$.

$T(n,m)=\begin{cases}
1, & n=1\text{ or }m\leq 2(n-1)!\\
\min\limits_{a,b,c\geq 1,\ c\le n-1\\a\leq c!,\ b\leq(n-c)!}{T(c,a)+T(n-c,b)+T(n,m-ab)}, & \text{else.}
\end{cases}$

Note: This question is highly related to my previous question here, since $ab\leq\max\limits_{1\leq c\leq n-1}{c!(n-c)!}=(n-1)!$

I guess that the minimum is obtained at $c=\lceil n/2\rceil,a=c!,b=(n-c)!$, but I don't know how to prove it.

The first 10 values of the first n's are:

$T(1,*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots\\
 T(2,*)=1, 1, 3, 5, 7, 9, 11, 13, 15, 17,\dots\\
 T(3,*)=1, 1, 1, 1, 3, 3, 5, 5, 7, 7,\dots\\
 T(4,*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots$

Experiments show that

$$T(n,m)=\begin{cases}1 & n=1
\text{ or }f(n,m)\leq 0,\\ 3+2\Big\lfloor\frac {f(n,m)-1}{g(n)}\Big\rfloor & \text{otherwise},\end{cases}$$

for $f(n,m)=m-2(n-1)!$, and for some $g$ whose first values are: 1, 1, 2, 4, 12, 48, 240. I guess that $$g(n)=\begin{cases}1 & \text{if }n<3,\\ 2(n-2)! & \text{otherwise.}\end{cases}$$


texts:
I wonder if all the linear languages are in NL?

I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the language can be written in linear normal form, the machine accepts. The work tape only needs to store the current production, so that it works in logarithmic time.

Am I completely lost or is this a good start?


texts: Is there an Algorithm that can code itself?

texts:
Suppose there is algorithm that has a strong NLP module. Could it use the NLP module to read text books such as http://www.amazon.in/Artificial-Intelligence-Modern-Approach-Prentice/dp/0136042597 in text form, parse it, understand the semantics and then use the knowledge to improve the very code it's written in ?
Like a virtual computer scientist? Is any research group working on it or even thought of that idea?


texts: Need help with functional dependencies (Database Theory)

texts:
I'm trying to understand functional dependencies in databases.

Let's say, there are 3 tuples in an instance of a certain relation S as shown below.

I'm trying to determine if a certain functional dependency will hold over S. Please correct me if I'm wrong.

1) A -> B should hold because no 2 similar value of a give 2 different values in B.

2) B -> A should not hold because 3 -> 1 and then 3-> 5.

3) BC -> A should not hold because (3,3) -> 1 and (3,3) -> 5.

4) BC -> D should hold because (3,3) -> 1 and the second (3,3) -> 1 also.

I'm not sure if I understood it right.


texts: Time complexity of solving a set of 2-sat instances?

texts: Suppose I have a set of 2-SAT instances, the set is of size $2^{3C}$ for some constant $C$. What is the time complexity of solving all instances using the fastest known 2-SAT solver?


texts: Deciding which logical proposition is stronger

texts:
I am studying propositional logic and I am trying to solve some exercise related to the following definition:

Given two logical propositions $\alpha$ and $\beta$, we say that $\alpha$ is stronger than $\beta$ if and only if $(\alpha \implies \beta)$ is a tautology. Determine which of the two propositions is stronger in the following cases:

1) True, False

2) True, True

3) False, False

I am a bit confused with this problem. I've seen that for True we always assign the value $1$ and for False, the value $0$. So, (True $\implies$ False) has always value $0$ (actually, there is one possibility) and (False $\implies$ True) has always value $1$ (there is also one possibility). This means that (False $\implies$ True) is a tautology, so False is stronger than True.

I am not sure if what I've said above is correct and I am lost in 2) and 3), I would appreciate some help. Thanks in advance.


texts: Row-Column agnostic Matrix datastructure

texts: Due to the linear nature of computer memory, row-major and column-major matrices have different performance for row- vs. column access. The obvious solution would be to keep two copies of the same data sorted accordingly. Is there a DS with better space complexity?


texts: Understanding Time Series Data for Classification

texts:
I have collected data from numerous volunteers driving a simulator in 8 different scenarios (classes). A volunteer drives in a map for 4 minutes in one scenario (one experiment), then he drives in the same map for 4 minutes in a different scenario(second experiment).

Our current dataset has around 0.4 million rows of driving data.

Let us consider volunteer 1 (henceforth V1),
He drives in Day Non-distracted (DN) scenario producing N rows (say 1000).
He drives in Day Distracted (DD) scenario producing N rows ( say 1000).
.
.
.
For eight scenarios, thus producing around 8000 rows of driving data.

Volunteer 2 ( V2) produces 8000 rows of driving data.
And we have collected data from around 52 volunteers.
So we have 52 * 8000 rows of data rows in total.
The data looks like this.

In our current approach, we are saving the mode corresponding to each data points in the one hot format and we expect the deep neural network to crunch the numbers one data row at a time and form a relation between these 9 features and the 8 classes.

I would like to build a neural network model which will help me classify the data into 8 classes.

How do I proceed from here? Is this data a time series data? Does looking at each row of driving data make any sense? or should I be looking at the entire data rows of V1 in DN scenario as one input ?

Right now I am just doing a multi layer perceptron model, expecting the system to crunch the 9 features and find a relation to the mode. But somehow I feel that's not the way to look at this data.

I am very new to machine learning. Any help would be great. Thanks in advance.


texts: Graphs in space efficient representation

texts:
Let $G$ be a graph such that $V$ denotes a vertex set and $E$ is an edge set of the graph $G$. Let us consider that for the input graph $G$ it is the case that $|E| \le O(|V| \log |V|)$. Given a graph $G$, I want to answer whether $(u,v) \in E$. If the input graph is given by adjacency representation then I can answer whether $(u,v) \in E$ in $O(\log |V|)$ time with space complexity $O(|V| \log |V|)$.

Space complexity refers to the space taken by input in words. One word means $O(\log |V|)$ bits.

Question: Does there exists a representation of graph $G$ such that I can answer whether $(u,v) \in E$ in $o(\log |V|)$ time with space complexity $O(|V|)$?


texts: If the speed of electrical charge hasn't changed, how have computers become faster?

texts:
Everyone knows computing speed has drastically increased since their invention, and it looks set to continue. But one thing is puzzling me: if you ran an electrical current through a material today, it would travel at the same speed as if you did it with the same material 50 years ago.

With that in mind, how is it computers have become faster? What main area of processor design is it that has given these incredible speed increases?

I thought maybe it could be one or more of the following:

Smaller processors (less distance for the current to travel, but it just seems to me like you'd only be able to make marginal gains here).
Better materials


texts:
Given the root of a binary tree, for instance below, I am running the following tests in Python:
     1
    / \
   2   5
  / \
 3   4

Test 1:
cur = root
root = None
print(root, cur)
None, node 1

Test 2:
cur = root
root.left = None
print(root.left, cur.left)
None, None

In both tests cur and root point to the same memory location. In test 1, why changing root to None did not modify cur? But in test 2 when I assign root.left to None, cur.left is also changed?


texts: How does paxos algorithm handle partial failures of accept messages?

texts:
I've been reading the basic paxos algorithm from the "Paxos Made Simple" paper. I can't understand how paxos algorithm maintains the safety properties under partial failures of the accept messages, meaning cases where the proposer receives prepare responses from a majority, but the subsequent accept message does not reach all the acceptors. It seems to me this could lead in a violation of the safety properties, where there will be no majority that has agreed on the same value.

I created a contrived example of the use-case I am thinking about. In every round, the proposer sends a prepare message to a majority of nodes, gets a response from all of them, but then the accept message arrives only to one of them (the other ones get lost). More specifically, as shown in the image below:

in round 1, the proposer sends a propose (1) message. The acceptors haven't received any prepare message yet, so they all reply with a promise. The proposer gets a majority in phase 1, so sends an accept(1, A) message. This message reaches the first node that accepts it.
in round 2, the proposer sends a propose (2) message to a majority, which does not contain the node that has accepted a value. As a result, the proposes gets a majority and sends an accept(2, B) message, which reaches only the second node.
the round 3 is similar, where none of the selected acceptors during the first phase have accepted any value yet. As a result, the proposer picks a value and sends an accept(3, C) message, which reaches only the third node.
in round 4, the majority has to contain at least one of the acceptors that has accepted a value. Let's say this is the first node that has accepted the value A, which returns the number of the proposal (1) as a reply to the prepare(4) message the proposer sent. Since there's only one accepted value, the proposer uses this one and sends an accept(4, A) message, which reaches the fourth node.
in round 5, the proposer sends a propose(5) message to a majority that contains the first 2 nodes, which have accepted the values A and B. They both return the associated proposal numbers (1 and 2). The proposer picks the value corresponding to the highest one, B. The proposer then sends an accept(5, B) message, which only reaches the fifth node.

At this point, there is no way to satisfy the safety property, since we would need a majority (6/2 + 1 = 4) of acceptors to have accepted the same value.

Where is the flaw in my thinking ?


texts:
We receive a stream of $n-1$ pairwise different numbers from the set $\left\{1,\dots,n\right\}$.

How can I determine the missing number with an algorithm that reads the stream once and uses a memory of only $O(\log_2 n)$ bits?


texts: Modifications to speed up the AKS primality proving

texts:
It is clear that AKS primality proving is the newest one, but as the results show it is not the fastest one.

When I try the 9 digits long prime number it consume about 6 minutes to give you the result.

Are there any modifications to make it faster for large random primes in size above 200 digits?

The problems in the AKS are:

Euler phi function
Binomial congruence


texts: How to translate automatons (Turing machines) into programs of high level programming language?

texts:
Every program in high level ("industrial") programming language can be expressed as some Turing machine. I guess, that there exists universal algorithm for doing that (e.g. one can take the Cartesian multiplication of the domains of all the variables and the resulting space can be the state space of the Turing machine, though the handling of computer-representable floats can be tricky - is there such general algorithm or system that does that? https://github.com/Meyermagic/Turing-Machine-Compiler is an example for the programming language for Turing machine and for the transpiler that translates C programs into the language of Turing machines or see https://web.stanford.edu/class/archive/cs/cs103/cs103.1132/lectures/19/Small19.pdf for some kind of Turing assembler language). But what about the other direction - can Turing machine be rewritten in concise  program in high level programming language that uses functions, compositionality of functions and higher-order functions?
Of course, there can be infinite results to that conversion - starting from the naming of the variables and functions and ending with the data structures, content of functions, etc. But there are metrics for the quality of the software code and maximizing such metrics can result in more or less unique answer to this stated problem.
Such conversion is very actual in the current context of reward machines for the reinforcement learning (e.g. https://arxiv.org/pdf/1909.05912.pdf) - symbolic representation of the reward function (as opposite to tabular or deep neural representation). Such symbolic representation greatly facilitates skill transfer among different tasks and it introduces the inference during the learning process and in such way reward machines reduce the need for data and need for learning time.
One can say that the extraction of first order and higher-order functions is a quite hard task, but this task is being tackled by the higher order meta-interpretive learning, e.g. https://www.ijcai.org/Proceedings/13/Papers/231.pdf.
So - are there research trends, works, results, frameworks, ideas, algorithms about conversion of the Turing machine into program in high level programming language (and possibly back)? I am interested into any answer - be it about the functional, logic or imperative programming.


texts:
Optimization factoring:
Input: $N\in \mathbb{N}$
Output: All prime factors of $N$

Decision factoring:
Input: $N, k\in \mathbb{N}$
Output: True iff $N$ has a prime factor of at most $k$

How can I solve the optimization problem in polynomial time if the decision problem is polynomially solvable?


texts:
I'm following this explanation on the P3P problem and have a few questions.

In the heading labeled Section 1 they project the image plane points onto a unit sphere. I'm not sure why they do this, is this to simulate a camera lens? I know in OpenCV, we first compute the intrinsics of the camera and factor it into solvePnP. Is this unit sphere serving a similar purpose?
Also in Section 1, where did $u^{'}_x$, $u^{'}_y$, and $u^{'}_z$ come from, and what are they? If we are projecting onto a 2D plane then why do we need the third component? I know the standard answer is "because homogenous coordinates" but I can't seem to find an explanation as to why we use them or what they really are.
Also in Section 1 what does "normalize using L2 norm" mean, and what did this step accomplish?

I'm hoping if I understand Section 1, I can understand the notation in the following sections.

Thanks!


texts: Assume that SAT ∈ PSIZE, does it imply that NP = coNP?

texts:
Assume that $\mathrm{SAT} \in \mathrm{PSIZE}$, does it imply that $\mathrm{NP} = \mathrm{coNP}$ ?

I think that I've managed to show that if $\mathrm{SAT} \in \mathrm{PSIZE}$, then both $\mathrm{NP}$ and $\mathrm{coNP}$ are contained in $\mathrm{PSIZE}$, but I can't see how does help me. Any ideas ?


texts: Is there a language-independent, static analysis framework?

texts:
I'm looking for a generic static analysis framework that could be used to detect problems that aren't necessarily specific to a particular programming language; for example:

Variable taint checking / unvalidated user input
Detecting when a variable is unused
Detecting when an identifier shadows another identifier in the same scope
Detecting unsafe casting / direct assignment of variables of one type to another type

One way I imagine this might work would be for language-specific parsers to emit generalized information about identifiers and how they're used. Here are programs in three different languages that might have similar representations:

Intermediate Representation

This is not supposed to be an exhaustive list of properties / annotations that might be supported, and not all properties or their values would be supported for every language.

file: {
    scope: "global"
    path: "[...]"

    declarations: [
        {
            type: "variable"
            identifier: "SCRIPT_NAME"
            annotations: [
                "constant",
            ]
        },

        {
            type: "variable"
            identifier: "ARGV"
            annotations: [
                "untrusted-input",
            ]
        },

        {
            type: "function"
            identifier: "never_called"
        },

        {
            type: "function"
            identifier: "multiply"
            calls: [
                {
                    filename: "[...]"
                    line: 19
                }
            ]
        },

        {
            type: "function"
            identifier: "main"
        }
    ]
}

Python

#!/usr/bin/env python3
import os
import sys

ARGV = sys.argv
SCRIPT_NAME = os.path.basename(ARGV[0])

def never_called():
    pass

def multiply(a, b):
    return a * b

def main():
    result = multiply(int(sys.argv[1]), int(sys.argv[2]))
    print(multiply(result, int(sys.argv[3])))

if __name__ == "__main__":
    main()

C

#include <libgen.h>
#include <stdio.h>
#include <stdlib.h>

char *SCRIPT_NAME;

void never_called()
{
}

int multiply(int a, int b)
{
    return a * b;
}

int main(int argc, char **argv)
{
    int result;

    SCRIPT_NAME = basename(argv[0]);

    result = multiply(atoi(argv[1]), atoi(argv[2]));
    printf("%d\n", multiply(result, atoi(argv[3])));

    return 0;
}

BASH

#!/usr/bin/env bash
declare SCRIPT_NAME="$0"
declare -a ARGV=("$0" "$@")

function never_called()
{
    true
}

function multiply()
{
    local -i a="$1"
    local -i b="$2"

    echo "$((a * b))"
}

function main()
{
    local -i result

    result="$(multiply "${ARGV[1]}" "${ARGV[2]}")"
    multiply "$result" "${ARGV[3]}"
}

main

Notes / More Ideas

In the Python script, the analyzer could see that "int" is called on untrusted input, and it could record that the variables have effectively been sanitized by the "int" function. I imagine taint tracking would always maintain historical information to make it easy to assess why variable is considered untainted.
Similarly, the analyzer might have annotations for the type of validation that has been performed. For example, there could be annotations to indicate that a value has been confirmed to be an int and separate annotations that indicate that the range of the result has been validated.

So far I haven't been able to find anything like this. Perhaps something like this could be done with LLVM as a long as the language in question had an LLVM implementation. I don't think it would even necessarily need to be a completely working or perfectly correct implementation.


texts:
I want to know the speed of preorder traversal of  an tree. I do not mean its order of magntude which we know is O(n).
I want something like 27n  operations where an operation is precisely defined.
Thanks


texts:
I have a linear grammar $G$ and a string $s$.  $G$ is is not limited to right or left linear only but rather has a mix of rules of both types.
Is there an algorithm to determine whether $s \in L(G)$ in less than cubic time?
Converting to CNF and applying the CKY algorithm takes cubic time, and I am wondering if there is a more efficient algorithm.


texts:
A multi-user, multi-processing operating system cannot be implemented on hardware that does not support

Address translation
DMA for disk transfer
At least two modes of CPU execution (privileged and non-privileged)
Demand paging

My attempt:

Somewhere it explain as : Address translation is needed to provide memory protection so that a given process does not interfere with another.

We also need at least 2 modes of execution to ensure user processes share resources properly and OS maintains control. This is not required for a single user OS like early version of MS-DOS.

Demand paging and DMA enhances the performances- not a strict necessity.

    Can you explain it in a formal way, please?


texts: Formulating a recursion using mathematical notation

texts:
So I'm assigned a task that involves formulating a quite complex recursion of several variables using 'mathematical notation'. The assignment is quite sparse when it comes to additional information, but below is the code anyway;

int partDist(String w1, String w2, int w1len, int w2len) {
if (w1len == 0)
  return w2len;
if (w2len == 0)
  return w1len;
int res = partDist(w1, w2, w1len - 1, w2len - 1) +
(w1.charAt(w1len - 1) == w2.charAt(w2len - 1) ? 0 : 1);
int addLetter = partDist(w1, w2, w1len - 1, w2len) + 1;
if (addLetter < res)
  res = addLetter;
int deleteLetter = partDist(w1, w2, w1len, w2len - 1) + 1;
if (deleteLetter < res)
  res = deleteLetter;
return res;

}

The method calculates the amount of the following operations it takes to get from String w1 to w2 and vice-versa;

Adding a letter
Removing a letter
Change an already exisiting letter

I'm not really sure where to proceed from there. I've managed to write something along the lines of a mathematic formula with conditionals but it just looks really messy and with a lot of hand-written conditions.


texts:
Let $G$ be a directed graph, with a single source node $s$.  I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where each path must start at $s$.  The cost of a collection of paths is the sum of the lengths of the paths.

Is there an efficient algorithm to find the minimum-cost collection of paths?  This smells like it might be NP-hard to me (it sounds like a set cover problem), so I'm guessing not.  If it is NP-hard, are there any good approximation algorithms or heuristics for this problem?

This sounds a bit like some kind of network-flow problem.  Every collection of paths from $s$ to $t$ is an integral flow from $s$ to $t$, and every integral flow from $s$ to $t$ can be expressed as a union of paths from $s$ to $t$.  The difference is that (1) the objective function we are trying to minimize is different from the standard network flow problem, and (2) the starting point of each edge is fixed to $s$, but the ending point is not fixed.  So, I don't know if network flow like techniques would help.

Motivation: Suppose I have a DFA, and I want to find a testsuite that achieves full edge coverage.  A test is a word over the alphabet of the DFA; a testsuite is a collection of tests.  A transition is covered by this testsuite if there exists at least one test in the testsuite that causes the DFA to follow that transition at some point.  Suppose the cost of a test is its length, and the cost of a testsuite is the sum of the costs of the tests.

Then we can ask whether there is an efficient algorithm that, given a DFA as input, outputs a minimum-cost testsuite that achieves full transition coverage.  That's exactly the graph problem outlined above.


texts: The rules for Turing Machine ,equivalence?

texts: We have regular expression for DFA and NFA, at the same time, we have CFG for PDAs, What do we have for Turing Machine? If this questions is too obvious, please points me some reading, I am just learning Introduction to the theory of computation_third edition - Michael Sipser myself.


texts: Distance transform with variable "impedance"

texts:
The distance transform gives the distance of each pixel in a mask to the nearest zero.
E.g. lets take the Taxicab distance transform:
input       distance
1 1 0       2 1 0
1 1 1   ->  3 2 1
1 1 0       2 1 0

I'm looking for a generalized distance transform where each each element in the mask also has a "weight" or "impedance" quantifying "how much it costs to step into this square".  Weight would be undefined for zeros.
input     weight      distance
1 1 0     0 2 X        2 2 0
1 1 1  ,  3 2 3   ->   4 2 3
1 1 0     1 0 X        1 0 0

My questions are:

Is there a name for this transform?
Can it be done in O(N) like the traditional distance transform?
Is there a nice way to generalize this to euclidian distance?


texts: Graph algorithms for vulnerability and optimality of network

texts:
I am studying a research paper which is concerned with finding paths from a source nodes to a single sink node keeping in mind 2 things.

1.The security of the path.

2.The optimality of the path.

Research paper transmission cost minimization with vulnerability constraint

The vulnerability model of paper says that the link that is shared by greater number of paths is more vulnerable to be attacked by some attacker. For example if there are 5 source nodes and 1 sink node, and say there is a link shared by 3 out of 5 paths and a link shared by only 1 out of 5 paths, then the latter link is more secure.

It basically defines the vulnerability of a link by the value of $No(e)$, where $e$ is the edge and it applies a constraint that the link cannot be used by more than $No(e)$ paths for the link to be secure, other wise it is likely to get attacked.

Here are important points about the research paper.

  To guarantee network security, the constraint vulnerability for each
  link $e$ is set to $No(e)$, which is a positive integer.

  $s$ is the single sink node and $P$ is the set of sources.

  Definition 1: An $s-P$ cut (Ecut) is defined as the set of links
  satisfying that if these links are removed, node $s$ and nodes in set $P$
  are disconnected, meaning all the sources will be disconnected from
  the sink node. The weight of $s-P$ node cut is defined as

  $\sum{(No(e))}$ $\forall e \in$ cut $s-P$.

  The $s-P$ node cut with minimum weight is defined as $C_{min}$. This also
  serves as the upper bound for the number of sources allowed to
  transmit, or mathematically it means

  $$   |P| \leq C_{min}$$

Up to this point I have understood it completely. The upper bound on $|P|$ can be very easily derived, by analysing the boundary condition. Suppose we allow exactly $C_{min}$ number of sources to transmit and $C_{min} = \sum{No(e)}$ for all the edges in the cut with minimum weight. Now say $No(e)$ paths go through first edge in the cut, No(e) paths go through second edge in the cut and so on. But if anywhere $No(e)+1$ paths go through an edge keeping everything same(or in other words having sources $C_{min} + 1$) then vulnerability constraint is broken as link can at most be used by $No(e)$ paths.

Further the research paper is:Which I am not comfortable with is

  Proposed Algorithms

  Let us use a strategy to convert undirected to directed graph with the
  objective of devising an algorithm with the help of network flow
  theory.

  For each link $(u,v)$ in graph, replace it by two directed arcs, $(u,v)$
  and $(v,u)$, the cost of both arcs is same as cost of link in undirected
  graph. Let us denote the new network with $G(N,A)$, $E$ being replaced by
  $A$.

  Now for each directed arc $(u,v) \in A$, we define $f(u,v)$ as the current
  unit flow from node $u$ to node $v$. We initialize $f(u,v)$ as $No(u,v)$.

Algorithm 1: Computing the number of source nodes using each arc for the data transmission.

I understood that the number of source nodes using an arc for data transmission(or the number of times an arc is being used in various paths) is

$$r(u,v) = |No(u,v) - f(u,v)|$$

But my question is why was the need for arcs, we could have applied the dijkstra on undirected graph and then could have also got this, what is that I am missing.

Further the paper proposes that the cost $r(u,v)$ is added to each link in the undirected graph but does not specify whether both $r(u,v)$ and $r(v,u)$ is added

The second alogirthm, which i could not understand as to why the deletion of links is happening and also minimal explanation in paper of it is given.

Can somebody explain the second algorithm and its link with the first one and try to explain the bigger picture so that I can understand what is going on.


texts: Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$

texts:
In a hypothetical world, we have a machine that can find median of $n$
  numbers in $O(\sqrt{n})$. (Of course this machine is not real).

  Can we use this machine to sort an array in $O(n)$?

I don't know how can I approach these type of questions which have a wrong statement as given. I know if the machine also partitions the array when finding the median, we can sort the array in $O(n)$ using $T(n) = 2T(n/2) + O(\sqrt{n})$.

But the question didn't say anything about partitioning. So if we assume that it doesn't change the array in any way and just finds the median, Can we use this machine to sort the array in $O(n)$ or not?


texts: Compute lebesgue measure of set of intervals

texts:
Let $S = \{ [x_1, y_1], [x_2, y_2], \dots, [x_n, y_n] \}$ be a set of not necessarily disjoint intervals on $\mathbb{R}$. Is there an efficient way to compute the lebesgue measure of the union
$\displaystyle \bigcup_{i = 1}^n [x_i, y_i]$ ?

I present my ideas and approaches as following.

If all intervals of $S$ are disjoint (special case), the problem is trivial and may be solved in time $\mathcal{O}(n)$. The solution is obviously
$\sum_{i = 1}^n y_i - x_i$ .

In the general case, we can remove intersections as long as possible. After this procedure, we apply the special case described above. There raise up two questions:

How to find and remove intersections?
How efficient is this solution in terms of runtime complexity?

Another approach is to sort the intervals of $S$ by $x_i$ or $y_i$. It seems to be a good way to simplify the problem, but does it really help and how? There are several cases we must consider: disjoint intervals, overlappings, intervals completely contained in another, ...

It should be noticed that I am interested in an efficient solution. Can we do in time $\mathcal{O}(n)$ and why or why not?

I appreciate hints and references for further reading as well as solutions.


texts: 3-coloring a graph with propositional formulas

texts:
I am trying to tackle a specific problem so any help would be greatly appreciated:

Let $G = (V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. A 3-coloring of $G$ is a map $\chi:V\to \{R,G,Y\}$ such that if $\{x,y\}\in E$ then $\chi(x)\neq \chi(y)$. (Let $R,G,Y$ stand for red, blue, and yellow respectively).
Suppose $n > 1$ and let $V_n = \{0,1,\cdots,n-1\}$ and let $G_n = (V_n,E_n)$ be an undirected graph with vertex set $V_n$. For each $i$, $0 \leq i < n$ let $R_i,B_i,Y_i$ be propositional variables. We can think of $i$ being a node so $R_i$ says node $i$ has a color of red.
Give a propositional formula $A_n$ using the variables $\{R_i,B_i,Y_i | 0 \leq i < n\}$ such that $A_n$ is satisfiable iff $G_n$ has a 3-coloring. Do this in such a way that $A_n$ can be computed efficiently from $G_n$ (e.g. don't define $A_n$ to be $R_1$ if $G_n$ has a three coloring and ($R_1 \wedge \neg R_1$) otherwise).

My inclination for a question like this is to set up some sort of CNF formula, that is come up with a set of clauses that set out to take care of different properties. For instance I believe for something like this I need a clause that deals with the case that every node has a color, maybe one that deals with every node cannot have more than one color, and that every node cannot be the same color as an adjacent node? I am not really sure how to illustrate that last one or if there are cases that I am missing.


texts: Are the Confabulation Theories of Thaler and Hecht-Nielsen Isomorphic?

texts:
Both S. L. Thaler and R. Hecht-Nielsen have set forth neural-based theories of "confabulation" applicable to machine learning.

The essential mathematics of Hecht-Nielsen is set forth in his paper "Cogent Confabulation".  Briefly it is an inversion of Bayesian inference.  Bayesian inference is P(x|a&b&c&d...) where one is estimating the probability of x assuming a, b, c, d, etc.  Its inversion is P(a&b&c&d...|x), which RHN calls the "cogency" of x given the assumptions.

I haven't seen a similarly succinct description of Thaler's mathematics that would permit comparison to see if the theories are isomorphic.  Are they?


texts: Proving a language is not a regular language but a context free language

texts:
I have the languages $L_1$ and $L_2$ such that $L_1 = \{a^nba^n :n \in N\}$ and $L_2 =\{a,b\}^*\setminus L_1$.

I want to prove that $L_2$ is not a regular language. I know that to prove that $L_2$ is not a regular language I can use the pumping lemma but I'm unsure about the details.

I also want to prove that $L_2$ is a context free language. Do I need a Push Down Automaton that accepts the language to prove that $L_2$ is a context free language? If so, what would this Push-Down Automaton look like?


texts: Prove that L = { wu; wu in {a,b}* and |w| = |u| } is not regular

texts:
Prove that $L = \{wu, wu \in \{a,b\}^* \ \land  |w| = |u| \}$ is not regular.

I'm trying to approach this problem with the pumping lemma.

So I know I have to pick a string s, which can be split into xyz components in terms of the pumping length, p.

But I cannot seem to find an s.

For example using $ s = a^p b^p$ or $s = a^p a b^p b $, since $|xy| \le p  \land |y| > 0$, then y must contain some a's. So we can try to pump $x y^i z$ to see the new string is still in L.

The issue is that if y contains an even number of a's it can always be pumped because the resulting string will have even length so w can be the first half and u be the second half.


texts:
I ran into the following, deceptively simple problem, and I was wondering if there is a well-known algorithmic solution to it:

Given a set of points $S$ in $\mathbb{R}^d$ (or $\mathbb{R}^2$, for simplicity), find a $n$-sided polygon, such that

all points in $S$ are inside the polygon
the area of the resulting polygon is minimal.

Any references or hints towards a solution are greatly appreciated.


texts: United space-time complexity of finite strings

texts: Let's consider bit string as a program for some computational model. If after $k$ steps program represented by number $n$ halts and outputs bit string $s$, then complexity of s is (n+1)*k. For example complexity of result of program $101$ after 3 steps is (5 + 1)*3 = 18. Have this or similar complexity measure been studied somewhere? What's its name?


texts:
In the following loop

for i = 1 to n
    doSomething O(1)
    for j = 1 to k
        doSomething O(1)

Is the runtime still $O(nk)$ even with the expression in the outer loop? Because if I change the order of the loops and $n \neq k$ then doSomething is executed a different amount of times.


texts: Strong orientation graph algorithm with Robbins' theorem

texts:
I've been asked a question that goes something like this:

Using depth-first search and Robbins' theorem, design and analyze an efficient algorithm to construct a strong orientation of a given undirected graph G. If none exist, output a bridge in G.

Now, I can prove Robbins' theorem easily, which states that a graph is strongly orientable if and only if it has no bridges (i.e. it is 2-edge-connected). The example given to me is similar to what's given in Robbins' 1939 paper describing his eponymous theorem with the traffic problem and one-way streets.
Can we do something as follows:

run DFS from root vertex r
orient all tree edges away from r
orient all back edges towards r

I'm not sure how to prove that this creates a strong orientation, though.


texts: SimRank on a weighted directed graph (how to calculate node similarity)

texts:
I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that it applies to unweighted graphs.

It's easy to adapt the matrix representation of SimRank to use weighted edges:

$\mathbf{S} = \max\{C \cdot (\mathbf{A}^T \cdot \mathbf{S} \cdot \mathbf{A}),\mathbf{I}\}$

Just replace the entries in the adjacency matrix $\mathbf{A}$ with the edge weights. But I don't see how to derive the "iteration to a fixed-point" method from this formula.

$s_{k+1}(a, b) = \frac{C}{\left|I(a)\right|\left|I(b)\right|} \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j)$

Is the following method correct?

$s_{k+1}(a, b) = C \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j) \cdot w(i, a) \cdot w(j, b)$

My reasoning is that the original method is equivalent to this:

$s_{k+1}(a, b) = C \cdot \sum_{i \in I(a)} \sum_{j \in I(b)} s_{k}(i, j) \cdot \frac{1}{\left|I(a)\right|} \cdot \frac{1}{\left|I(b)\right|}$

so I replaced the trivially equal weights with the actual ones I have. Confirmation would be nice, though.

If there is a superior method to SimRank, I would like to hear about it. (I'm concerned with improvements to accuracy, not performance; this is a small data set.)

Edit: A different similarity metric that's nearly as accurate but performs a lot better would actually be useful too. My initial tests of SimRank are very slow, and the potential optimizations are not simple to code.


texts: Why does it take so long to prove optimality when warm-starting from optimal solution

texts:
So I'm solving bigger instances of some binary-linear-program using cplex.
The formulations of the problem I am using is integer friendly, meaning nearly all of my instances can be solved at the root node.
Additionally I have a pretty good heuristic for calculating solutions. The heuristic is quite fast and nearly always gives the globally optimal solution.

When combining cplex with the heuristic I do not achieve the performance gains I expected. I feed the globally optimal solution to cplex as a "warm-start-solution", but it still takes quite some time for cplex to proof its optimality (cplex chooses the dual-simplex for the relaxation).

I might lack some theoretical understanding, but why can't the dual-simplex just build a basis for the supplied optimal solution and show that there is nothing else to do?


texts: How to call an interval that has equal start and end point?

texts: For instance let's say that I have a Interval class, that has startPoint and endPoint fields, getter and setter methods (functions) accordingly. and I need to create a method that returns boolean value of startPoint == endPoint. And have a question regarding naming point. How to call this method? isEmpty() or isZeroLength(). I am beginner self-educated programmer, and truly I am not so good in math, so I don't know how it is called in math (empty interval or an interval with zero length), so that I use that determination.


texts:
I understand how the control, data and instruction buses form the system bus in von Neumann architecture but in the context of Harvard architecture, my textbook refers to "parallel data and instruction buses". The Wikipedia article for Harvard architecture also refers to an instruction bus: "TMS320 C55x processors, for one example, feature multiple parallel data buses (two write, three read) and one instruction bus."

What is an instruction bus? Based on its name, I'd guess it allows the processor to send instructions to components but in that case, how does it differ from a control bus?


texts: Algorithm for calculating regular divisions of lengths in easy-to-read form

texts:
I am creating some charts for elevation v distance data.

The original source of the data is GPX files and from them I have extracted...

The total route distance (km) and each point along the route as [lat, long, elevation, distFromStart]

The chart plots distanceFromStart (X-axis) v elevation (Y-axis).

The routes can be anything of length between 0.5km and 450km.

The issue I have is with calculating the divisions (the tick values) for the x-axis of the graph. The tick values should always be easy to read, rounded values. The number of ticks is flexible from 5 - 12 (or thereabouts).

So given

A distance (in km)
A list of acceptable tick values (0.1km, 0.2km,
    0.5km, 1km, 2km, 5km, 10km, 20km, 50km)

How can I calculate which acceptable tick value I should use and the number of ticks on the x-axis?


texts: How to find an algorithm's complexity from actual running times

texts:
I have a certain algorithm which I can run, but I do not have access to its code. Thus, it works as a black box. I would like to now the order of complexity of this algorithm on a certain set of instances, which grow in size as a function of $n$.

Now, I have collected running times from $n = 1$ up to $n = 5000$, which is as far as my computer can go in a reasonable amount of time.

I have plotted my data using Python and I have made some simple regression (exponential, cuadratic, cubic...), but I still can't get to decide which function best fits the algorithm. Obviously, if I try regression with a polynomial of higher degree, I will get a tighter curve, so in case the running time is a polynomial in $n$, I don't know how I could decide which is the one that really fits.

With instances up to $n = 1000$, it seems like the cubic polynomial is the best approximation. However, when I plot the instances up to $n = 5000$, things become less clear (in the second graph I compare the actual running times against the approximations obtained for up to $n =1000$, while the first one compares against the the approximations up to $n = 500$)

(in addition, I feel there is something off with float point calculations, as two of the curves below get really messy)

Any suggestions?

A bit of context: I am working on a particular class of hard Quantified Boolean Formulas (QBF) and I want to test their running times on different available QBF-solvers. These formulas verify a certain interesting property: they have linear size proofs in the QU-resolution proof system. However, QBF-solvers act as block boxes for me, and, altough I can see from data that they do not have the "predicted" linear running times, I would like to know how is the growth in complexity in these particular instances. Particularly, it would be great to give some approximate bound or even confirm that they do not seem to have an exponential growth. Thanks.


texts: Can we show that non-determinism adds no power, for some specific running time?

texts:
$NP = \cup_{k \in \mathbb{N}} NTIME(n^k)$

$P = \cup_{k \in \mathbb{N}} TIME(n^k)$

Can we show that $NTIME(n^k) = TIME(n^k)$ for a specific $k$?

For how large of a $k$ can we show the above statement to be true?


texts:
First and foremost, I would like an academic reference on how screen recording "works."
I have tried searching online, but I only get results for the software itself.

Exactly how does screen recording work, and to what extent does the content one records effect filesize?
For instance, if I were to record my screen playing an (x) resolution video, would the final output size be proportionally larger? Why or why-not?

If this question is closed, please, I would appreciate a reference, or a better way to phrase it (or a referral to a more appropriate sub-forum).
Thanks.


texts: Average solutions in infinite search tree

texts:
I have the following problem:

  Consider a balanced infinite search tree with branching number $κ$. Consider a
  search problem with solutions which may be located at any node of the tree.
  The search will not be terminated once a solution is found. The only information about solutions is that if you check a node at level $l$ the likelihood of finding a solution is $p^l$ (and $0 ≤ p ≤ 1$).
  a) Using breadth-first search, how many solutions will you find using an infinitely large tree?
  b) Using depth-first search?

I know the average number of solutions on a level $l$ is $l^k p^l$, and that I need to use geometric sequences to sum through the tree but I'm not sure how to proceed. How should I go about solving this problem?


texts: Is Levenshtein algorithm efficient for text similarity?

texts:
I searched on the net the different measures of text similarity. And I found many algorithms concerning this issue and there are classified into many categories such:

Token-Based Measure: Tf-idf, Euclidean, Manhattan, overlap coefficient, matching coefficient, cosine, etc.
Character-based: Levenshtein, Hamming, Jaro-Winkler, Jaro, etc.
Q-gram: Jaccard, dice coefficient, etc.
Mixed Measures: Monge-Elkan, Soft-tfidf

and other categories. In the article Similarity Measures for Title Matching they use different similarity measures and compare the results. But such a result they mention that Levenshtein could be one of the best algorithm for text similarities. Is it efficient with long sentences?


texts: 2-depth arithmetic circuits and VP vs VNP

texts:
the field of arithmetic circuit complexity is undergoing major discoveries in recent years as mentioned by Fortnow. am looking for a more layman-readable summary:

  is this new paper Sums of products of polynomials in few variables : lower bounds and polynomial identity testing / Kumar, Sarif essentially stating that a particular exponential lower bound on 2-depth arithmetic circuits ($\Sigma \Pi$) would imply VP$\neq$VNP?

(understood as cited by Fortnow the 4-depth case has been proved elsewhere by Kayal, Saha, Saptharishi.)

are the results proved in this paper or earlier papers? also if anyone knows of (introductory) textbook formulation(s) of this theory, most of which is contained in papers, please cite it.


texts: Should we consider number of surfaces in a disk while calculating effective data transfer rate?

texts:
Suppose a disk has

Number of surfaces: 8

Number of sectors per track: 20

Sector size: 4000B

Number of tracks: 10

It is rotating at 360 rpm.

So disk is reading data from one track at an instance. So I will only find for a single rotation how much data can be fetched & I will find how much data in 1 second.

In 60 seconds -> 360 rotations.

In 1 second -> 6 rotations

In 1 second ->  6*20*4000B OR 6*20*4000B*8

So should I multiply the number of surfaces. If I am not wrong, all the surfaces have separate R/W heads. So should I multiply?


texts: Bipartite graph minimal amount of vertices required

texts:
I have a bipartite graph made of two sets (SET 1 and SET 2) and I want to determine how many vertices from the SET 1 I can remove while still having
every vertex of the SET 2 connected to at least one vertex of the SET 1.

In this example, E and F can obviously be removed as D and C are connected 5 and 6.
But we could also remove B as A and C together cover more points. But so far I only have a very slow implementation of this which is to compare every vertex of SET 1 to every combination of vertices of SET1.
Is there any smart way to do this? I've been thinking about Kőnig's theorem but I didn't find a way to use it in this context as it seems to be made for undirected bipartite graphs.

Also, there are some constraints the input follows:
-Every element of SET 2 is connected to SET 1
-Every node of SET 2 is connected exactly to two vertices of SET 1


texts:
I am having a hard time understanding the quick sort partition operation.
I understand what partition is supposed to do, I just don't understand how partition does it. Specifically, I don't understand how the two subarrays (q-1, q+1) are constructed.
I have looked at various other SE articles, such as:

How does Hoare's quicksort work, even if the final position of the pivot after partition() is not what its position is in the sorted array?
Randomized Selection

I understand the notion of:

 1. Select a pivot (typically the last item in the array, at least in simplified methods)
 2. Create one subarray to the left of items smaller than the pivot
 3. Create one subarray to the right of items larger than the pivot
 4. Recursively call partition on each of the subarrays

However, in the following example, is where I get lost

8 1 9 3 5 7 6

Here, 6 is my pivot

7 is larger than 6, so my array now looks like:

8 1 9 3 5 6 7

Here is where I get lost. Does the rest of my sequencing look like:

8 1 3 5 6 9 7
1 3 5 6 8 9 7

Where:
1 3 5 is my smaller array and
8 9 7 is my larger array (where each then get partition recursively called?)

I am most confused by the proper construction of the larger and smaller arrays and in which order to put the numbers in. Any help is appreciated. I am happy to edit my post for clarity if I am unclear.

EDIT:
I tried using some base code from this address, and edited it slightly to create more print statements, but still don't understand why it would sort to:
1 3 5 6 9 7 8 and not 1 3 5 6 8 9 7 initially

Here is the code:

class QuickSort
{
    /* This function takes last element as pivot,
       places the pivot element at its correct
       position in sorted array, and places all
       smaller (smaller than pivot) to left of
       pivot and all greater elements to right
       of pivot */
    int partition(int arr[], int low, int high)
    {
        int pivot = arr[high];
        int i = (low-1); // index of smaller element
        for (int j=low; j<high; j++)
        {
            // If current element is smaller than or
            // equal to pivot
            if (arr[j] <= pivot)
            {
                i++;

                // swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i+1];
        arr[i+1] = arr[high];
        arr[high] = temp;

        return i+1;
    }

    /* The main function that implements QuickSort()
      arr[] --> Array to be sorted,
      low  --> Starting index,
      high  --> Ending index */
    void sort(int arr[], int low, int high)
    {

        printArray(arr);

        if (low < high)
        {
            /* pi is partitioning index, arr[pi] is
              now at right place */
            int pi = partition(arr, low, high);

            // Recursively sort elements before
            // partition and after partition
            sort(arr, low, pi-1);
            sort(arr, pi+1, high);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    // Driver program
    public static void main(String args[])
    {
        int arr[] = {8, 1, 9, 3, 5, 7, 6};
        int n = arr.length;

        QuickSort ob = new QuickSort();
        ob.sort(arr, 0, n-1);

        System.out.println("sorted array");
        printArray(arr);
    }
}
/*This code is contributed by Rajat Mishra */


texts: Are two elements always in a relation within a partially ordered set?

texts:
In a partially ordered set, am I always able to order two arbitrary elements out of the set? Or is it possible that two elements within the set have no order relation to each other?

For example if there are three elements $\{a, b, c\}$ and $a \leq b$ and $a \leq c$, does either $b \leq c$ or $c \leq b$ have to hold?

I need this to understand the fixed point theory for semantics of programming languages (denotation of while loops).


texts:
I wonder if there is a formal definition of lexical scope so that people can prove things with respect to it, for example, that an interpreter implements lexical scope. You may ask what level of formality I am talking about. For example, I deem the usual definition of the free variables of a lambda term formal: a variable $x$ is free in a term $N$ iff

$N$ is a variable $y$ and $x=y$, or
$N$ is the application $M M'$ and $x$ is free in $M$ or $M'$, or
$N$ is $\lambda y M$ and $x\neq y$ and $x$ is free in $M$.


texts: I have been looking at the wikipedia page for steiner trees, and I don't quite understand their 4-point solution. If the four  vertices are arranged in a rectangle shape wouldn't there be only one steiner vertex required in the middle to create the shortest length graph? The solution shows two vertices S1 and S2, but it seems that it would be shorter if there was only one vertex S instead, in between S1 and S2 and all of the vertices A, B, C, and D connect to S.


texts:
A parser is a procedure which decides if an input belongs to a certain language and produces a witness in the form of a parse tree.

Let a streaming parser be a parser which for any prefix $u$ can produce a partial parse tree corresponding to the productions that must be expanded to eventually accept any completion $uv$ of the prefix, for some completion $v$.

For example, if parsing the CFG
$$
\begin{array}{lcl}
S &\to& (a S+ b)
\end{array}
$$

then upon reading the prefix $aaa$, the streaming parser should report that any parse tree must consist of three top-level expansions of $S$.

Edit: I have two motivations for streaming parsing. The first is to provide a best-case constant bound on memory usage in the case where productions can always be resolved by a constant amount of lookahead. The second is to allow the consumer to lazily tear down the parse tree as the result is produced, e.g. by scheduling the execution of semantic actions associated with productions.

I am also interested in streaming parsing based on other foundations than context-free grammars, such as top-down parsing (parsing expression grammars, parser combinators, etc.).

Is there any existing work on such parsing algorithms?


texts:
In FIFO: when process get cpu time and then go to IO.
What happend in the time it is in IO? another process can run?
After finishing IO it continue or "loss its turn"?
Why FIFO give priority to cpu bound process?
In RR: assume slice time is s and after (s-2) for eample it get IO, what happend with the 2 other seconds? it loss them?

3.In preemptive SJF we look on the next cpu burst. What about non preemptive SJF? we lock on all the cpu in the process will need?And in genreal we look only on cpu? not on io?


texts: Stablishing termination of the construction of infinite stream with ranking functions

texts:
I'm working with Turing's paradigm to prove termination of programs by annotating functions with ranking functions and I encounter the following example:

def zeros: Stream[Int] = 0 #:: zeros

This is Scala syntax for contructing a stream made of an infinite number of zeros. In this case, the evaluation terminates but there is no (evident) measure that would prove it so?

Does this mean that the ranking functions paradigm is limited? Or is there a function stablishing termination of zeros?

Turing, A. Checking a large routine. In Report of a Conference on High Speed Automatic Calculating Machines, 1949.


texts: Prove disprove an existence of mapping reduction between 2 sets

texts:
I am currently studying mapping reduction in computational theory and finding it hard to grasp the concept fully.

For reference, consider the following given WHILE-Prog sets:

A = { (p.d) | p doesn't halt on input d } = Complementary HALT set.
B = { p | p halts on exactly one input (the input is unknown) }

Is A < B. meaning, is there a mapping reduction from A to B?

Can someone suggest a hint?

knowing that A belongs to coRE did not help much.
B doesn't seem to belong to either RE nor coRE.


texts: Recurrence Relations for Perfect Quad Trees (same as binary trees but with 4 children instead of 2)

texts:
I have to write and solve a recurrence relation  for n(d), showing how I arrive at the formula and solve the recurrence relation, showing how I arrive at the solution. Then prove my answer is correct using induction for perfect quad trees which are basically binary  trees but with 4 children at each node rather than 2 and the leaf nodes in the deepest layer have no children. Nodes at precisely depth d is designated by n(d). For example, the root node has depth d=0, and is the only node at that depth, and so n(0) = 1

Does this mean it would be
T(n)= 4T(n/4) + d ?
then prove

I'm really confused and would appreciate any help or resources.


texts: I was reading this answer about Turing machines and it refers to a bussiness-card-sized one, which claims to be a universal Turing machine, based on this paper. However, I don't understand the logic of that particular machine. I understand that in a universal Turing machine the "program" is just another machine encoded in the tape of the universal Turing machine. But, how is it encoded in this case? How would you write a program that adds two numbers for this machine, for instance?


texts: Red black tree - Insert/Delete proof of correctness

texts:
From the Cormen book I was studying the chapter focused on the red black tree. I was particularly interested in why the procedures for insert/delete fixup works (namely a formal proof).

I report both the algorithms, taken from the book:

The book gives a generic explanation of why they works, but doesn't give any formal proof. Could you suggest me how to prove the result, or could where I find the proof? For example if I focus on the insert, I would look at the node $z$ and I would assume by induction that one subtree has black height $h-1$ while the other has black height $h$, then I would show that after an iteration both subtree have black height $h$. I would try something similar for the delete procedure.

I'm not entirely sure that this is the best way to prove the correctness, and I can't actually find a formal proof of the result.

(The main reason is actually that every time I read the book and specifically such chapter I just try to memorize the procedures. Since this kind of tree implementation is quite common I think is time I understand why it works.


texts: Does intersecting the output of 2 programs give the output of another program?

texts:
Let $S$ be the set of all programs that take integers as input and return integers as output and halt on all inputs. Does there exist a pair of program in $S$, call them $P_1$ and $P_2$, such that there exists no program $P_3$ in $S$ for which the following hold for every integer $y$:

$P_3(x)=y$ for some $x$ iff $P_1(x_1)=y=P_2(x_2)$ for some $x_1$ and $x_2
$.


texts: In Round-Robin Scheduling with $n$ processes in ready queue and time quantum $q$, each process gets $1/n$ of CPU time in chunks of at most $q$

texts:
I was going through the Round-Robbin Scheduling Section of the dinosaur book by Galvin et. al. where I came across the following statement by the authors:

If there are $n$ processes in the ready queue and the time quantum is $q$, then each process gets $1/n$ of the CPU time in chunks of at most $q$ time units.
For example, with five processes and a time quantum of 20 milliseconds, each process will get up to 20 milliseconds every 100 milliseconds.

The meaning of the statement is not quite clear to me. I tried to make a rough justification of the same, but it did not quite satisfy me. Here is how I did it.
First I assume that all the processes have comparable CPU bursts. Or else the example which the authors give of each process getting up to 20 ms shall not be valid. [ Counterexample, suppose, we have $P_1,P_2,P_3,P_4$ with CPU bursts of $5$ ms each. And the CPU burst of $P_5$ is 80 ms, then if $P_1, P_2, P_3, P_4, P_5$ arrive in order, with in the first $20$ ms the first $4$ processes shall be completed, and then the ready queue shall be having only process $P_5$ and it shall get a total of $80$ ms out $100$ ms.]
Let $T$ be the CPU time and there being $n$ processes in the system with comparable CPU bursts we can assume that,
$$\text{Time for each process}\approx \frac{T}{n}$$
But in Round-Robbin scheduling, each process in its turn runs for at most $q$ time units. [ The process in its last turn might take less than $q$ time units if incase the $q$ does not divide the CPU burst of the process equally]
So this approximate quantity $\frac{T}{n}$ is made up of chunks of size at most $q$.
Is this approach appropriate?


texts: How to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$?

texts:
$T(n) = T(n-2)+T(n-3)+2T(n/3)$ and $T(n)=1$ for $n<4$.
I tried to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$ using the recursion tree but it's not clear enough for me to make a guess and demonstrate it by induction? also, it should be computed given both upper and lower bound.


texts: Relationship between an integer N and the number of bits n required to represent the integer

texts:
I'm trying to understand the time complexity of the following code in terms of n.

Pseudocode for trial division:

I understand that the time complexity of the algorithm is O(sqrt(N)). However, can someone explain how the person in the link below came up with O(e^(n/2)). In other words, what's the mathematical relationship between N and n? Thanks.

Time complexity explanation:


texts: What does does $O$ mean in this context?

texts:
I understand big O notation in computational complexity theory, but I don't see how it applies in the equation below.

From Pattern Recognition and Machine Learning:

  If we weren't familiar with the rules of ordinary calculus, we could
  evaluate a conventional derivative $dy/dx$ by making a small change
  to the variable $x$ and then expanding in powers of $\epsilon$, so that
  $y(x + \epsilon) = y(x) + \frac {dx}{dy}\epsilon + O(\epsilon^2)$

  and finally taking the limit $\lim\epsilon\to 0$.


texts: Scheduling a dependency graph for parallel computing

texts:
Background:

I have a dependency graph, i.e. a directed graph where the nodes are tasks and the edges are dependency relations. Moreover, nodes are assigned a weight since they take different amount of time to complete.

I have developed an algorithm that rearranges the graph by merging some nodes together that can be computed as one task instead of several separate tasks (this is not parallel computing), i.e. the algorithm reduces the number of tasks. However, this algorithm doesn't always give one rearrangement of the graph but can produce many, e.g. three graphs where all of them are in some sense the same graph but rearranged.

What I want to do is the following:

I want to determine which one of the different rearranged graphs is the "best" where "best" is determined by some type of grading criteria. I was thinking this criteria could be some type of measurement of parallel degree that takes the weights in consideration. I have tried just using a topological sort but I find this approach a bit to primitive. After picking a graph, I would also want to produce a scheduling list of the tasks. The weights can be seen as estimations on how long a given task will take to complete, but these are only rough estimations.

Questions:

What kind of measurement of parallel degree could I use and what algorithms are there for grading this and also for scheduling the tasks accordingly?


texts: The set of turing machine that stops with input zero is not recursive

texts:
If M is a Turing Machine, consider the subset of $\mathbb{N}$ defined as:
$$ \mathrm{ZTM} = \{ x \mid M_x(0)\downarrow \} $$

i.e. the set of 'indexes' of machines that halt on zero. It is possible to use Rice's theorem to prove that this set is r.e. but not recursive.

But I'd like to have a direct proof, using directly some diagonalization argument if possible.


texts: Is random access allowed in the Bit Complexity model, or is it just expensive?

texts:
In the RAM model, you're allowed to do unbounded indirect access (pointers can be arbitrarily large and still fit in a single machine word).

In the Bit Complexity model (no wiki article, sorry), machine words are constant sized. So storing the address of an entry in a table of size $N$ would require $O(lg(N))$ words.

This raises the question: Are you even allowed to do a multi-word random access into a table of size $N$ when using the bit complexity model? It's a bit of a strange operation, because the machine can't "hold the jump in its head" while making it. On the other hand, it could be allowed but cost $O(lg(n))$ time instead of the RAM model's $O(1)$ time.

I realize that this is basically just a definition, with interesting things on either side, but I'm wondering what the common definition is. Is bit complexity just another way of saying "multi-tape turing machine"?


texts: What is the significance of the vector dimension in semidefinite programming relaxations?

texts:
Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you.

So, we first write down an integer quadratic program that solves the problem exactly. For example, in the case of MAX-CUT we would write:
$$
\max \sum_{\{u,v\} \in E}{\frac{1 - x_u x_v}{2}}
$$
$$
x_v \in \{-1,+1\}.
$$

Then we relax the program by allowing the variables to take on vector values in the sphere $S^{n-1}$, and replacing products with scalar products, obtaining a semi-definite program that can be solved precisely.

Our approximation proceeds by solving the SDP and rounding the solution to obtain a legal solution for the original problem whose distance from the SDP solution can be bounded.

My question is: What is the importance of the dimension of the vectors? In all the cases I have seen, the analysis would stay the same if we assume that the vectors are all unit vectors in $\mathbb{R}^2$. So why do people always take vectors in $S^{n-1}$?


texts: What is the formal description of a Turing machine?

texts: I was asked to give a formal description of a Turing machine I have no experience with this, and was wondering what "formal description" entails.


texts:
Given a set of (propositional) formulae $\Phi$, two formulae $\phi$ and $\xi$, determine whether there exists $\Psi\subseteq \Phi$ such that $\Psi\models \phi$ and $\Psi\not\models \xi$.

Question: what is the (theoretical) complexity of this problem? Is it in DP?


texts: Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C

texts:
So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve this recurrence relation by expanding it out and here is what I have so far:

I'm not sure where to go from here and how to find the asmpytotic bounds.


texts: Facility location on a Sphere with great circle distance

texts:
I am looking for an algorithm to find the point that minimizes the sum of the great circle distances to a set of fixed points on a sphere.

In more detail: Given $x_1,\ldots, x_k$ fixed points in the $\mathbb{R}^n$ sphere. All of them have non-negative coefficients, i.e., $\|x_i\| = 1$ and $x_{ij} \geq 0$. I wish an algorithm to find the point $y$ such that $\|y\|=1$ minimizing $\sum_{i=1}^k d_{x_i}(y)$, where $d_{x_i}(y) = \arccos( \langle x,y \rangle)$.

I know this is considered a facility location problem but I can't find any algorithm that solves this particular problem.


texts: For any two regular languages A, B, show that {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free

texts:
Basically I'm wondering if the concatenation of two equal length string is context free. I've seen multiple proofs of this online using PDAs but we aren't covering them in my automata course and my professor says they aren't needed for the proof. Any help would be greatly appreciated!

This is the full question:

For any two languages $A, B$ over $\Sigma$, define
$A \diamond B := \{xy\mid x \in A, y \in B, |x| = |y|\}$.
Show that if $A, B$ are regular then $A \diamond B$ is context-free


texts: Distribution of $(X_1,X_2)$ if $X_1\pm X_2$ are two independent $N(1,4)$

texts:
$X_1+X_2$ and $X_1-X_2 $ are i.i.d. $N(1,4)$. What is the distribution of $X = (X_1,X_2)^T$?
I know i.i.d. is an independent and identically distributed random variable but I don't know how to use it to solve this problem that contains a column vector.


texts: Can you prevent a man in the middle from reading the message?

texts:
I have heard about all these Man-In-The-Middle Attack preventions and I am wondering, how this can possibly work if the man in the middle only listens to your stream and does not want to change the message itself.

Can the man in the middle not just take the keys swapped by the opponents, change the keys and then decrypt and encrypt the message again?

How can a certificate prevent this?

Edit:

I have heard that the certificate authority generally says: "Yeah, that is the other ones key". But how can I be certain, that the signature of the certificate is not fudged?


texts: Minimal number of unions of sets such that no union has more than N elements

texts:
I have some sets, and can combine them by taking their union. I can take unions of the unions, too. I want to take unions until the total number of sets is as small as possible, with one caveat: that none of the unions can have more than $N$ elements. (So that the problem always has a solution, none of the input sets will ever have more than $N$ elements.)
If the input to the problem is a set of sets $\{S_1 ... S_n\}$, the result should be disjoint partitioning of the input into subsets, such that the size of the union of the sets in each subset is always smaller than $N$, which might look something like $\left\{\left\{S_1,S_3\right\},\left\{S_2,S_4,S_5\right\},...\right\}$.
What's the best algorithm to do that? The brute force algorithm is exponential, and naively memoizing it is GL-complete (because so is the bipartite graph isomorphism problem). This question is similar in spirit, but it's about finding one set, instead of the smallest set of sets.


texts: What's the use of studying trigonometry in computer science? I mean, is it essential? Does it have a specific application in computer science? Because I can't seem to muster enough motivation for learning it.


texts: How is the definition of monads in category theory equivalent to the definition in functional programming?

texts:
In Haskell, Monad is a class of type constructors which act on types that have the following functions implemented:

(>>=)  :: m a -> (a -> m b) -> m b
(>>)   :: m a ->       m b  -> m b
return ::   a               -> m a

and they satisfy the following "laws:"

return a >>= f      = f a
m        >>= return = m
(m >>= f) >>= g = m >>= m >>= (\x -> f x >>= g)

I understand why a type with these functions implemented with those constraints is useful, because I've used them. But to be completely honest, I'm interested in pure mathematics over programming, so I want to understand the category theoretic origins of monads.

Monads in category theory seem very different, they are ordered triples $\langle T, \mu, \nu\rangle$. Where $T$ is an endofunctor on a given category $C$, $\mu : 1_C \rightarrow T$ is a natural transformation as is $\nu : T\circ T \rightarrow T$ such that they all satisfy conditions reminiscent of the one's for Haskell monads. It seems like return, which I understand to be the type constructor for an instance of monad, is the endofunctor $T$.

In essence I want to understand which functions are which natural transformations, and why, but I also want to understand why return is an endofunctor, acting on a category, even though it seems like most types in Haskell are treated as objects.

I was once watching Bartosz Milewski lecture and he said that monads can be thought of as "monoids on the category of endofunctors." I stopped watching because I didn't know what monoids were at the time. But now when I think "monoid on the category of endofunctors" I think "The set of endofunctors on a category under composition." But I don't see how an object like this could relate to the definition of a monad, so if someone could explain that as well it would be greatly appreciated.


texts: What are differences between Static Scope and Dynamic Scope?

texts:
My teacher has provided the following pseudo-code, and says that the output using static scope is 1 2 3, but the output using dynamic scope is 2 3 4.

void fun1(void);
void fun2(void);

int a = 1, b = 2, c = 3;

int main() {
    c = 4;
    fun1();
    return 0;
}

void fun1() {
    int a = 2, b = 3;
    fun2();
}

void fun2(){
    printf("%d %d %d", a, b, c);
}

Which variable we use in Static Scope? $c=3$ or $c=4$? (by Static Scope Rule and without considering C Rules).


texts: What is the significance of Bellman-Ford and linear programming for scheduling and makespans?

texts:
CLRS exercise 24.4-9 says the following:

Show that the Bellman-Ford algorithm, when run on the constraint graph for a system $Ax \leq b$ of difference constraints, minimizes the quantity $\max_i\{x_i\} - \min_i\{x_i\}$ subject to $Ax \leq b$. Explain how this fact might come in handy if the algorithm is used to schedule construction jobs.

I understand how to prove the result, but I'm having trouble imagining how to map these $x_i$ to quantities in scheduling, like "job begin time", "job end time", "job duration", "cost", etc. I've seen several places claim that this can be used to minimize "makespan", i.e. total duration of a schedule of jobs, but I don't see the connection.
In Chapter 24 of the book, constraints $x_k - x_j \leq b$, with $j,k\geq 1$ are converted into vertices $(v_j, v_k)$ with weight $b$. A source vertex $v_0$ is added, with zero-weight edges going to all $v_1, v_2 \ldots v_n$, so Bellman-Ford gives the solution $x_i = \delta(v_0, v_i)$, that is, the most negative path from $v_0$ to $v_i$.
Superficially, it sounds right to just say "$x_i$ are the completion times, so if you minimize the difference between the earliest and the latest, that minimizes the total or cost you spend working".
However, if $x_i$ is "the completion time for job $i$ or something like that, what would be the significance of a constraint like $x_i - x_j \leq b$? "Job $i$ must be finished at at most $b$ hours after job $j$"? That sounds somewhat contrived and unrealistic. What's a more natural mapping of these $x_i$ to scheduling concepts?


texts: Finding hash of a substring $[i, j]$ in $O(1)$ using $O(|S|)$ pre computation

texts:
Given a string $S$ of length $n$ characters, is it possible to calculate the hash of its substring $[i, j]$ (from index $i$ to $j$, both inclusive) in $O(1)$ using some form of precomputation? Can we use a modification of the rolling hash?

The following is a similar problem to my question. In it the string was given in a compressed form. Example: if the string is "aaabccdeeee" then the compressed form is:

3 a
1 b
2 c
1 d
4 e

The data was stored in an str[] array as :

str[] = [{'a','3'}, {'b','1'}, {'c','2'}....]

Note that hashing was used in the solutions, which checked if the given substring is a palindrome or not. Given a substring of string $S$ as $(i, j)$, they computed the hash of substring $[i, (i + j) / 2]$ and the reverse hash of substring $[(i+j+2)/2, j]$ and checked if they were equal or not. So if they wanted to check if in string S = "daabac" whether substring $[1, 5]$ is a a palindrome or not, they computed the following :

h1 = forward_hash("aa")
h2 = reverse_hash("ba")
h1 == h2

Code for the hashing concept

The hash precomputation was done as follows:

/* Computing the Prefix Hash Table */
pre_hash[0] = 0;
for(int i = 1;i <= len(str); i++)
{
    pre_hash[i] = pre_hash[i - 1] * very_large_prime + str[i].first;
    pre_hash[i] = pre_hash[i] * very_large_prime + str[i].second;
}

/* Computing the Suffix Hash Table */
suff_hash[0] = 0;
for(int i = 1;i <= len(str); i++)
{
    suff_hash[i] = suff_hash[i - 1] * very_large_prime + str[K - i + 1].first;
    suff_hash[i] = suff_hash[i] * very_large_prime + str[K - i + 1].second;
}

And then the hash was computed using the following functions :

/* Calculates the Forward hash of substring [i,j] */
unsigned long long CalculateHash(int i, int j)
{
    if(i > j)
        return -1;
    unsigned long long ret = pre_hash[j] - POW(very_large_prime, [2 * (j - i + 1)])*pre_hash[i - 1];
    return ret;
}

/* Calculates the reverse hash of substring [i,j] */
unsigned long long CalculateHash_Reverse(int i, int j)
{
    unsigned long long ret = suff_hash[j] - POW(very_large_prime, [2 * (j - i + 1)]) * suff_hash[i - 1];
    return ret;
}

What I am trying to do

I am looking for a general approach to the above concept. Given a Pattern $P$, I want to check if the pattern $P$ is present in a string $S$. I know the index $i$ to check where it may be present. And I also know the length of pattern $P$ represented as $|P|$. In short I want to check if hash of $S[i, i + |P|]$  and hash of $P$ match or not in $O(1)$ using some form of precomputation on $S$. (Ignoring the time taken to compute hash of $P$ else it would be $O(1+|P|)$.)


texts: Proof that {w ∈ {a, b} ∗ | |w|a = |w|b} is not a regular language

texts:
I know that the language {w ∈ {a, b}∗| |w|a = |w|b} is not regular since somehow, you can't store all the information needed in a DFA. I've seen that normally it's done with reduction to absurdity or pumping lemma and also having into consideration that the language a^nb^n is not regular
But I would like to see a formal approach of it to fully understand why and not only because of "intuition"

Could someone please help me? Most of examples just always show the same and I don't see how to apply them to my case.


texts: Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

texts:
I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access...

My question though is, when we have an implicit array representation of a min-heap, e.g.:

min_heap = [1, 2, 4, 3, 6, 5, 54, 12, 12, 34]

In this case, is it possible to infer the Kth-smallest value's index from the value of K, so you can use the array index to get the value in O(1) time?


texts: Partitioning a set so both parts have sum at least $c$ times the total sum

texts:
Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$?

If $c=1/2$, this is the famous partition problem which is NP-complete. What is known about the complexity for other values of $c$?

I posted the question to CS Theory several weeks ago. The only response was a comment that claimed that the problem is NP-hard, but the commenter never responded to my request for a  proof or reference.


texts: Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

texts:
I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this?

I know that a full node has 2 children.


texts:
Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is inefficient (i.e $|\mathcal P(L)| = 2^{|L|}$ tests -- not polynomial). I can always find out whether a perfect matching exists by computing a maximum cardinality matching and testing its perfectness, but this involves computing that perfect matching.

Is there an efficient way of deciding whether a perfect bipartite matching exists without computing the matching it self? Ideally I would want an algorithm which is faster than algorithms like Hopcroft Karp or matrix based matching algorithms, which explicitly find out the matching (i.e so not computing the matching makes sense).

Edit: The italic part.


texts: Yesterday I've done some research how to optimize genetic algorithm and I've encountered a very interesting theory that we can use Lamarckian theory (adaptive theory) to optimize the neural network. But I still didn't understand how can it be done? What I've read from some source to optimize the genetic algorithm we must do some adaptation to the parents before we do the mating (crossover & mutation) but how is exactly the adaptation done? For example, if I have a genetic algorithm population to train a neural network, how can I alter the chromosome of the population to be adapted to the environment? Is it based on the error of the output or how?


texts: It's possible to parse a document using a single pass from a state machine. What is the benefit of having two passes, ie. having a lexer to convert text to tokens, and having a parser to test production rules on those tokens? Why not have a single pass that applies production rules directly to the text?


texts: Recognizing strongly connected digraphs in NL

texts:
This homework solution gives a proof that
$L = \{G \mid \text{G is strongly connected directed graph}\} \in N\mathcal{L}$. One suggested way to proof that $L \in N\mathcal{L}$ by proving that $\bar{L} = \{G \mid \text{G is not strongly connected} \} \in NL$ and then using the fact $NL = coNL$.

The tutorial uses the following algorithm for $\bar{L}$:

  Nondeterministically select two nodes $(a,b)$
  Run $PATH(a,b)$. If it rejects, then the graph is not strongly connected, so accept. Otherwise reject.

Since $PATH$ itself is a nondeterministic algorithm (or rather, we have to use a nondeterministic algorithm to still be $N\mathcal{L}$, it is not clear to me why this is correct. Why is it okay to invert the answer of $PATH$ in this case?

For example, assume our nondeterministic choices wrongly lead us to believe there is no path between $a$ and $b$, then this nondeterministic branch would accept (which means our whole TM $M$ would accept, because there is one accepting branch). But if there is also a branch of $PATH$, then our graph $G$ might actually be strongly connected and $M$ will return a wrong answer by accepting.


texts: Can a unnormalized floating point number be recognized also when exponent is not zero?

texts:
From Tanebaum's Structed Computer Organization.

  Exercise 4 of Appendix B

  The following binary floating-point number consist of a sign bit, an excess $64$, radix $2$ exponent, and a $16$-bit fraction. Normalize $0$ $1000000$
  $0001010100000001$ ($\star$).

As far as I've studied, the number ($\star$) is already normalized and it is a representation of the number $1.0001010100000001 \times 2^0$.
Moreover, according to the IEEE754, if one is meant to represent an unnormalized number, she would have to set the exponent-related bits at $0$ --which is not the case.

My question is: what is the exercise asking to me? Can that be an unormalized number?

Maybe Tanebaum's simply asking the reader to multiply ($\star$) by $2^3$ then to subtract $3$ from the exponent. Yet to me, that has no sense at all --instead, you're really changing the value ...