texts: Necessary or useful models/techniques for simulating natural evolution?

texts:
I'm a Psychology student with a decent (yet not extensive) knowledge of mathematics and computer science. My knowledge on this two fields are those of a person beginning the third year of computer science (since I studied computer science for two years).
My field of academic interest is evolutionary psychology and behavorial biology. I want to program a fairly simple evolutionary model in Python, which would simulate evolution in a population, or group of populations, with an emphasis on the selection of behavioral traits. (I will progressively increase the complexity of the program throughout this year, but for the moment my aim is to keep it very simple.)
To name a simple example, create a population of organisms with a certain degree of altruism ranging from 0, totally selfish, and 1, totally altruistic. Organisms would compete for food: their sucess at getting enough food determines their reproductive potential, and their level of altruism would determine the chance of them sharing part of their food (thus lowering somewhat their reproductive potential) with organisms that didn't succeed at finding any on their own.
Of course there are many details to be precised in the previous model, such as how the altruism level of an organism determines the amount of food it shares and the amount it keeps for itself, should the sharing mechanism activate. But then again it's just an example. Many layers of complications (even game theory!) can be added on top of that fairly elemental model.
My question is, what are some general computer science models I should want to be familiar with to develop a program that simulates evolution? Should I, for example, learn neural networks, or wouldn't I find a use for one in my project?
In other words, what programming or computer science models/techniques are a must for my purpose?


texts:
Here is the problem. Given $k, n, T_1, \ldots, T_m$, where each $T_i \subseteq \{1, \ldots, n\}$. Is there a subset $S \subseteq \{1, \ldots, n\}$ with size at most $k$ such that $S \cap T_i \neq \emptyset$ for all $i$? I am trying to reduce this problem to SAT. My idea of a solution would be to have a variable $x_i$ for each of 1 to $n$. For each $T_i$, create a clause $(x_{i_1} \vee \cdots \vee x_{i_k})$ if $T_i = \{i_1, \ldots, i_k\}$. Then and all these clauses together. But this clearly isn't a complete solution as it does not represent the constraint that $S$ must have at most $k$ elements. I know that I must create more variables, but I'm simply not sure how. So I have two questions:

Is my idea of solution on the right track?
How should the new variables be created so that they can be used to represent the cardinality $k$ constraint?


texts: Prim's Algorithm - Building the Priority Queue

texts:
Suppose we were using a priority queue (PQ) to implement Prim's algorithm. My understanding is that initially the weight of all vertices is set to $\infty$. The weight of the starting vertex is then set to $0$. All of the vertices are then inserted into the PQ.

Does that mean that we can insert the vertices in any order into the PQ?
Given that we can insert the vertices in any order, suppose we have a graph with the following vertices $a$, $b$ and $c$ and the following weights $w(a,b)=1$, $w(a,c)=2$. Once we set a.key = 0 and then extract a from PQ, we have b.key = 1 and c.key = 2. Given the answer to (1) was yes, my understanding would be that in a binary tree representation of the heap, $b$ would now be the root and $c$ would be a child of $b$. However, depending on the order in which the $a$, $b$ and $c$ were added to the heap, $c$ could be either the left or right child of $b$, right?
Suppose now that the graph has vertices $a$, $b$, $c$, $d$ and edges $(a, b)$, $(a, c)$, $(a, d)$. Suppose they were inserted into the heap in the order $a$, $b$, $c$, $d$. The binary tree representation of the heap should then be:
$a$ is the root, $\operatorname{left}(a) = b$, $\operatorname{right}(a) = c$, $\operatorname{left}(b) = d$

So, that would mean that the parent-child relationships do not correspond to the parent-child relationships in the original graph and they don't have to, right?


texts: FFT implementation using Danielson-Lanczos Lemma

texts:
I am trying to understand FFT algorithm explained here

FFT(x) {   n=length(x);
if (n==1) return x;
m = n/2;
X = (x_{2j})_{j=0}^{m-1};
Y = (x_{2j+1})_{j=0}^{m-1};
X = FFT(X);
Y = FFT(Y);
U = (X_{k mod m})_{k=0}^{n-1};
V = (g^{-k}Y_{k mod m})_{k=0}^{n-1};
return U+V;
}

The author says that the above comes from Danielson-Lanczos Lemma.

I am unable to understand what is the meaning of the lines:

X = (x_{2j})_{j=0}^{m-1};

Y = (x_{2j+1})_{j=0}^{m-1};


texts:
Zero and one are defined by the successor function.

$$
\begin{align*}
&0 ≡ λsz.z \\
&1 ≡ λsz.s(z)
\end{align*}
$$

But why? $λsz.z$ is irreducible to a value. If I call this function on some value, I get back $z$, which is merely a variable in itself. If I call the function on two values, I get back the second value, which is not necessarily zero.

And yet we're just assigning the function the value $0$? Why? Why not assign zero to say $λs.(λz.xyt)$. This seems arbitrary.

This is from the arithmetic section of:
http://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf


texts: Can FPSPACE give exponentially long outputs?

texts:
I can't comment on this question, so I ask it here as a new question:

Ricky Demer states there in a comment to the first answer

"[...] since FPSPACE can give exponentially long outputs [...]"

How can this be? How can an algorithm in FSPACE give an exponentially long output? Does this mean, that we do not count the output space in the definition of FSPACE (contrary to what I have believed so far)?


texts: Algorithm to pick elements in one array that sum to a setpoint, and corresponding elements in other array to average to a setpoint?

texts:
Note: The input file is an excel file. However, I am only looking for help with the algorithm as I can then code it in VBA.

I need to scan both columns (shown below) to find any number of column 1 values that when summed match the setpoint (E2) and column 2 values that when averaged match the setpoint (E3). One constraint is that the chosen values in column 1 and column 2 must be from the same row (or same 'index', shown in the image highlighted in blue and green).

Explanation of the solution below:
What it should do is say 'A2 and A6 sum to 7 (match cell E2), and the corresponding B2 and B6 average to 3' (match cell E3). Therefore, these rows should be selected/highlighted in any appropriate way. (note that technically the first solution would be rows 2 and 3 as they fit the sum/average setpoints also).

Example that does not work as a solution:
It can't be A4 and A5 because although they add to 7, B4 and B5 average to 1.5, not the setpoint of 3.

Image of the problem (with a solution highlighted):

A solution for one of the cases (below) works only for the case where there are two rows that will sum/average to the setpoints. It will not work for cases where more than two rows are required. The solution should work for any number of rows required.

Example where three rows would be required (Solution is the first three rows):

Reason for this solution: B6:B8 sums to the setpoint of 8 and C6:C8 average to the setpoint of 3

I am looking for help with an algorithm. If the solution is a large number of rows required (>100), how can I iterate through the combinations efficienctly to find a set of rows that both sums/averages to the setpoints?

It may not be possible to find a solution to both setpoints, in this case finding a solution within an error is also ok

Note: If there is a more suitable stack exchange please advise.

Finding an algorithm is NP-Hard, therefore I am also looking for appropriate simplifications to avoid this. An error term may be an example of one simplification.


texts: What is a 'dynamic entity' in computer science?

texts:
I am doing some reading into computer science and how the computing system works in order to be ready for my 1st year at university doing a Computer Science degree. I came across a term within the definition for a computer system that I tried looking up for on the internet called 'dynamic entity'. The problem is, I couldn't specifically find the definition I was looking for that could explain simply what it meant. If there is someone who could explain this term for me in a simple, but easy to understand, explanation, I would be very grateful. Thank you.

The link I got the term from: https://books.google.co.uk/books?id=3ls6K2cJW_0C&printsec=frontcover&dq=computer+science+easy+reading&hl=en&sa=X&ved=0ahUKEwjz2r_cuIfkAhUxonEKHWBZAu8Q6AEIKzAA#v=onepage&q&f=true

The term can be found on page 4 of the book, where they explain what a computing system is.


texts: How to reformulate my problem as a mixed-integer quadratic problem

texts:
I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $s$-dimensional vector $a$ is to be computed to find $x$.

The only assumption that we have is $x=0$ when we project $x$ onto the space spanned by $s$ different rows (that we don’t know their indices) of the matrix $B$ which has $n$ rows. To do this projection we can use $P_s\in \mathbb{R}^{n\times n}$  which is $1$ on the diagonal entries that correspond to the $s$ selected rows of $B$ and $0$ elsewhere. Hence, $P_s x= P_s z + P_s Ba=0 \implies a=-(P_sB)^{-1}P_sz$.

The main issue is that we don’t know the positions of these $s$ rows, so the problem is combinatorial and we need to go through all possible $n\choose s$ projections to find the exact $x$ which corresponds to the least cost $f(x)=\|y-Ax\|_2$ where $\|v\|_2=\big(\sum_iv_i^2\big)^{1/2}$, $y\in \mathbb{R}^{m\times 1}$ and the matrix $A\in \mathbb{R}^{m\times n}$ are given.

So my question is how I can reformulate my problem as a mixed-integer quadratic programming to go through all possible $n\choose s$ submatrices of $B$ formed by the $s$ selected rows and finally find the set of rows which corresponds to the least $f(x)$.


texts: Algorithm for finding cut vertex and bridge in directed graph

texts: In un-directed graph it is easy to find cut vertex and bridge but in directed graph removing cut vertex/bridge must increase number of strongly connected componenets.


texts: Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$?

texts:
I'm currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples.

The question equation: $f(n) = 6n^3 + n^2\log n$

The exact line written for the answer is: $f(n) \leq 6n^3 + n^2 \centerdot n \text{, for all }n \geq 1, \text{since} \log n \leq n$

First of all, I don't really see why the logarithm was removed or why it actually matters when the dominant piece is the $6n^3$. I also don't get why it's $n \geq 1$ instead of $n \geq 6$ (unless it's a continuation of the first one.

Been staring at it for about 15 minutes and still not getting how it comes down to $n \geq 1$. Would anybody be kind enough to give me a hint as to what's wrong?


texts:
Lets say we consider the Erdős-Renyi undirected random graph $G(n,p)$ with $V(G) = \{1,2,\cdots,n\}$ and $\displaystyle{P((u,v)\in E(G)) = p} \quad \forall u,v \in V $.

Is there anything we can say about the probability of the $G$ containing a $HAM$ Cycle?

This seems like a helpful quantity to figure out for certain computations

Generating random graphs and seeing what fraction contains a $HAM$ cycle can of-course be done.

What is the rate of increase of $P(G\text{ contains }HAMCYC)$ as $p$ increases?


texts: How are LRU and Clock algorithm different?

texts:
I am modeling the Gclock-pro buffer replacement algorithm in Linux kernel.

Because there are many existing modeling works on LRU, I am considering adopting LRU model to roughly describe Gclock-pro, if they are similar.

I read some papers and documents looking for their relationship.

LRU page replacement scheme is hard to implement.
Second chance algorithm is a good approximation of LRU.
Clock algorithm is one way to implement Second chance algorithm.
GClock-pro algorithm is improved version of clock algorithm with additional hands. It approximates Low Inter-reference Recency Set (LIRS) algorithm.
LIRS outperforms LRU.

I think there is a circular relationship between LRU and GClock-pro. Unfortunately I have no idea where to start.

Can anyone give any intuition on their differences?


texts:
Wikipedia states on the page of the halting problem, "For any program f that might determine if programs halt, a "pathological" program g called with an input can pass its own source and its input to f and then specifically do the opposite of what f predicts g will do."

Suppose we have 2 neural networks, approximating f and g (allowing infinite size and depth limits). Is it wrong to assume that these two NNs can participate in a zero-sum game against each other, and that the Nash equilibrium (if it exists) of these 2 NNs contains the solution to the halting problem?


texts: Dominator tree with edges annotated by min-cut size

texts:
Consider the dominator tree of, say, the graph of objects in memory, computed by a memory profiler - one of the most powerful memory leak debugging features, I believe.

The dominator tree tells you "if you manage to make this object unreachable, you'll reduce overall memory consumption by its whole subtree".

Obviously, the next question is "How do I make this object unreachable?", and the dominator tree gives only a partial answer to that: "by disconnecting it from this parent node which dominates over it".

Min-cuts would answer this remaining question ("how do I make this node unreachable from that node"). I already asked a general question about this and unfortunately it stayed unanswered, but I think it would be useful to, at least, produce a dominator tree where every parent-child edge would be annotated with the size of the minimum cut between them.

I'm wondering: is there an algorithm for efficiently computing a dominator tree annotated in this fashion?


texts: Detect if a sentence is in passive voice

texts:
Given an English sentence, I am looking for a programmatic way to tell whether the sentence is written in passive voice.

Currently, I just check if there is a was or were inside the sentence. If yes, then the function will say that the sentence is in passive voice (I do no not know even if this is true).  Is there a better approach?

I just want to make a simple detector for passive voice, I do not care much for accuracy and efficiency. Here what I ended up with:

// http://english.stackexchange.com/questions/472/how-can-i-reliably-and-accurately-identify-the-passive-voice-in-writing-or-speec

// forms of be, have and get
int auxilary_verb(char* str) {
    if(strstr(str, "be ") || strstr(str, "been ") || strstr(str, "being ") ||
            strstr(str, "have ") || strstr(str, "had ") || strstr(str, "was ") || strstr(str, "were ")
            || strstr(str, "wasn") || strstr(str, "weren") || strstr(str, "got ") || strstr(str, "get ")
            || strstr(str, "getting ")) {
        return 1;
    } else {
        return 0;
    }
}

// past participles of the verbs here http://web2.uvcs.uvic.ca/elc/sample/beginner/gs/gs_10.htm
int past_participle_transitive_verb(char* str) {
    if(strstr(str, "brought ") || strstr(str, "cost ") || strstr(str, "given ") || strstr(str, "lent ")
            || strstr(str, "offered ") || strstr(str, "passed ") || strstr(str, "played ") || strstr(str, "read ")
            || strstr(str, "sent ") || strstr(str, "sung ") || strstr(str, "sent ") || strstr(str, "taught ") || strstr(str, "written ")
            || strstr(str, "bought ") || strstr(str, "get done ") || strstr(str, "left ") || strstr(str, "made ")
            || strstr(str, "owed ") || strstr(str, "paid ") || strstr(str, "promised ") || strstr(str, "refused ") || strstr(str, "shown ")
            || strstr(str, "taken ") || strstr(str, "told ") ) {
        return 1;
    } else {
        return 0;
    }
}

// Once a week, the house is cleaned by Tom. <- passive
// By the end of the week, I'll be gone. <- not passive, but ok.
int contains_by(char* str) {
    return (strstr(str, "by ") != NULL);
}

// how to find No direct object -> I don't know.
// The subject of the verb phrase is the entity undergoing an action or having its state changed -> I don't know.

int passive_voice(char* str) {
    // relax conditions, by applying || isntead of &&
    if(auxilary_verb(str) || past_participle_transitive_verb(str) || contains_by(str)) {
        return 1;
    } else {
        return 0;
    }
}


texts:
While I was doing
CLRS (3rd
edition), I came across this question on page 629:

Professor Sabatier conjectures the following converse of Theorem
23.1:

  Let $G = (V,E)$ be a connected, undirected graph with a real-valued
   weight function $w$ defined on $E$. Let $A \subseteq E$ that is
   included in some minimum spanning tree for $G$, let $(S,V -S)$ be any cut of $G$ that respects $A$, and let $(u,v)$ be a safe
   edge for $A$ crossing $(S, V - S)$. Then, $(u,v)$ is a light
   edge for the cut.

Show that the professor’s conjecture is incorrect by giving a
counterexample.

Theorem 23.1:

  Let $G = (V,E)$ be a connected, undirected graph with a real-valued
   weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that
   is included in some minimum spanning tree for $G$, let $(S, V
 - S)$ be any cut of $G$ that respects $A$, and let $(u,v)$
   be a light edge crossing $(S, V - S)$.  Then, edge $(u,v)$
   is safe for $A$.

Can anybody please give a proof or a counterexample to the conjecture
also because I used to think that all safe edges added to the graph
are light edges.

  DEFINITIONS :
  1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.
  2. Light edge:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.
  3. A cut Respects a set A of edges if no edge in A crosses the cut.
  4. Safe edge is the edge which we can add to MST without any violation of MST's property.These are those edges which are the part of final MST.

I have written most of the definition but for more queries you can also refer to CLRS chapter 23.


texts: Reduction from TSP to ATSP does not imply constant factor approximation algorithm

texts:
As I understand there is a constant factor approximation algorithm (e.g Christofides algorithm) for the symmetric TSP problem. This is however not the case for the asymmetric TSP problem (I am assuming we are talking about the metric case for both).
According to Wikipedia there is a reduction from ATSP to TSP, which then can be solved to obtain a solution for the ATSP instance - so why does a solution on this reduction not imply that there is a constant factor approximation for ATSP?


texts:
Does there exist a language which is PSPACE-complete and regular?  (reduction is polynomial with regard to time).

Correct answer here is "unknown".  I can't prove it. Can you help me?


texts: Big-O complexity when c is a tiny fraction

texts:
Finding Big-O is pretty straightforward for an algorithm where $f(n)$ is

$$f(n) = 3n^4 + 6n^3 + 10n^2 + 5n + 4$$

The lower powers of $n$ simply fall off because in the long run $3n^4$ outpaces all of them. And with $g(n) = 3n^4$ we say $f(n)$ is $O(n^4)$.

But what would Big-O be if instead of 3 we were given a really small constant, for example
$$f(n) = 0.0000000001n^4 + 6n^3 + 10n^2 + 5n + 4$$

Would we still say $f(n)$ is $O(n^4)$?


texts: Average case complexity of bubble sort vs insertion sort

texts:
This site already has some questions on this topic but I am confused after reading some of the answers.

Evaluating the average time complexity of a given bubblesort algorithm.

In the above link, answer by "Joe" says that number of swaps in bubble sort on average is same as number of inversions on average which is (n)(n-1) / 4.

However, https://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms says that in bubble sort average number of swaps  is $n^2 / 2$ and in insertion sort it is $n^2 /4$ and that's the reason for insertion sort being better than bubble sort.

Which one is correct? Can someone please help me?


texts: Is Smoothed Analysis used outside academia?

texts: Did the smoothed analysis find its way into main stream analysis of algorithms? Is it common for algorithm designers to apply smoothed analysis to their algorithms?


texts: If I have the integer ""1234" stored in a file, the size of the file when I use the command "ls -l" or "wc -c" is 5. If I have "12345" the size of the file is 6. Basically the number of bytes in a file = (number of individual digits) + 1. Now, I am assuming the "+1" comes from the space it takes to create the name of the file. But why is the rest of the byte count equal to the number of individual characters? Does the file system read the file character by character even we "write an integer" to the file? Elaboration on this would be very helpful.


texts: Sum of unique integers to cnf constraint

texts:
As a study project I try to solve the kakuro puzzle problem using SAT SOLVER.
I can't really find an efficient way to convert the sum of k unique integers (1...9) to a CNF constraint.
What I had in mind:

for a group of k cells (1,...k) and a sum of j:

    find all subsets with size of k from P({1,2,...9})
    correctSubSets <- filter out all subsets that SUM(subset)!= sum
    AllVars <- EMPTY_SET
    for i in 1...k:
       add to current cnf a union of correctSubSets s.t each prefixed with i
       add to AllVars a union of correctSubSets s.t each prefixed with i
       for each pair in AllVars:
              if pair represents two different cells ix,jy:
                  if there is no sum s.t x,y part of it:
                     add to cnf (-ix, -jy) (not ix or not jy)

example for sum = 5 and k=2:
AllVars={11, 24, 13, 22, 12, 23, 14, 21}
cnf = (11, 13, 12, 14), (21, 22, 23, 24), (-11, -22), (-11, -21), (-11, -23), (-12, -21), (-12,-22), (-12,-24) ....... and more and more

I fill like this is very though to implement and not efficient at all.
how to solve it correctly?


texts: Does solving mathematical equations with Cellular Automata structures means it is universal?

texts:
I'm working on a research about Elementary Cellular Automata (ECA), and i found a method to build a system that can solve mathematical equations by using a specific cellular automaton structure.

The system is about encoding the equation into numbers and by applying some rules, these numbers are transferred to a Cellular Automaton structure.

For example => x^3-81=0 , after encoding it to numbers, it showed a structure contains 3 triangle, which is the answer of the equation encoded     ===>  (x^3-81=0)  ==> (x^3=81) =>  (x=3).

So, i have read the article about turing-complete:

  a system of data-manipulation rules (such as a cellular automaton) is said to be Turing complete or computationally universal

What i want to say is, the equation was transferred to numbers {data-manipulation rules} and it computed the input (the equation), then showed the answer (output).
Does that makes the system a turing complete ?

I have also tested other equations:

x^2-25=0
x^3-27=0
x^4-16=0

And the system always shows the right answer as triangles.


texts: Build a scheduler, to simulate parallel game flow

texts:
I am building a strategy game where units can interact with each other.

As input I am getting a list of actions. I need to output a scheduler, that will tell when to start each action. The goal is to find the shortest time combination of all the actions.

Action is defined as interaction between two users or user with him self, it build from 4 parts:

performing unit - the unit that performs the action
receiving unit(optional) - the unit on witch the action is applied
supported actions - A list of actions that the receiving unit can perform while applying this action on him.
action time - how long does it takes to execute the action

Rules:

Units can only perform one action in a time
Units may have to perform more than one action

The best solution will be: Is to run all those actions in parallel. There are two things that stops me from doing it.

If more than one action have the same performing unit, they cannot start simultaneously as units can perform only one action in a time.(Rull 1)

The other problem is actions with receiving unit. I need to make sure that the receiving unit is currently performing one of the supported actions(defined in action part 4), if it's not, this actions cannot be started.

In case of actions without receiving unit, they can all be started simultaneously. How ever I need to make sure that I am not left with action that have a receiving unit, that cannot be started as the receiving unit already performed all his actions.(So supported action will never be started)


texts: Computing probability of sentence using N-grams

texts:
I have implemented N-grams by constructing a tree (or a trie, technically) that stores frequencies of each N-gram. Each path in the tree represents an N-gram and its frequency: the path consists of N nodes (each node containing a word), followed by a leaf node containing the frequency. So, each path in the tree is of length N + 1.

I'm now trying to compute the probability of observing a given sentence, and am having some trouble, particularly when N > 2.

For the sentence <s> Hello world </s> using N = 1, the probability is P(<s>) * P(Hello) * P(world) * P(</s>).

Using N = 2, the probability is P(Hello | <s>) * P(world | Hello) * P(</s> | world).

But for N = 3, I'm not sure what to do. If I compute P(Hello | <s>) * P(world | <s> Hello), then my tree will give an error since <s> Hello is a bigram and the tree is only defined for trigrams.

I considered maybe wrapping each sentence an additional time, e.g. <s> <s> Hello world </s> </s> then computing P(Hello | <s> <s>) * P(world | <s> Hello) * P(</s> | Hello world) * P(</s> | world </s>), but this seems non-intuitive and involves mutating the corpus in an ugly way.

What is the proper way to compute this probability?


texts: Why isn't there a big HTM machine already?

texts:
I've been reading a bit about Hierarchical Temporal Memory and Memory Prediction. I found a great paper: How the brain might work: A hierarchical and temporal model for learning and recognition, Dileep George's dissertation for his PhD at Stanford.

I was searching google, to see if such a big network has been deployed somewhere, but I found no results. I know that Numenta has such systems, but there is no information about the size, and what the machine can do. Does that mean that this method isn't good enough?


texts: Solving simultaneous multiple chinese remainder theorem on the quantum computer - possible?

texts:
Is it possible to solving simultaneous multiple chinese remainder theorem on the quantum computer?

We have $k$ variables. Each variable can take two values.

The question is: can we calculate all possible circuits equations chinese remainder theorem (which may be $2^k$) and reduce to the smallest result on a quantum computer?

I know the question can be very difficult but I wanted to ask.

I hope I have described the problem quite clearly (but maybe there are ambiguities).

For example we have table:

2 3 7 31

A B C D => [RESULT]

0 1 3 4 => 934
0 1 3 27 => 430
0 1 4 4 => 4
0 1 4 27 => 802
0 2 3 4 => 500
0 2 3 27 => 1298
0 2 4 4 => 872
0 2 4 27 => 368

Third line:

0 1 3 4 => 934

means the system of equations:

$x \equiv 0 \pmod 2$

$x \equiv 1 \pmod 3$

$x \equiv 3 \pmod 7$

$x \equiv 4 \pmod {31}$

and solution for this line in CRT (chinese remainder theorem) is 934.

The final result that the algorithm should return (minimum) is 4. This result is in line:

0 1 4 4 => 4

This is just an example - I wanted to show to know what I mean.

Someone may have some idea?

Sorry for the (maybe) difficult question.


texts: Controlled NOT gate a type of measurement?

texts:
I'm trying to understand the theory of quantum computing, and I'm a bit confused on a particular circuit:

Would the controlled NOT gate be a type of measurement, causing Q1 to be either |0> or |1>, or would the circuit be in a superposition of the |00> and |11> states until an actual measurement of Q1 or Q2 took place?


texts: How to solve recurrence. T(n). = T(n-1) + T(n/2) + n?

texts:
I am aware that to get a running time by recursion tree method, we need to draw a tree and find:

a) number of levels in tree.

Since left side of tree decreases by 1 in size, so it's longest path from root. Subproblem size at level i is n-i . setting n - i = 1 when it hits a size of 1, we get number of levels, i  = n - 1.

b) cost per node in tree : cn

c) Number of nodes at level i:   This is where i am stuck. Not able to find nodes at level i since left side decreases by 1, right side by half. Naturally,  tree is more dense towards left side.  Not every node will have two children.

if i can get answer to c, i can calculate T(n) = cost of level 0 + cost of level 1 + cost of level 2 +  ... cost of level n-1.
if y1 is number of nodes at level 1, y2 at level 2, etc... then
=> T(n) = cn + y1 * cn + y2 * cn + y3 * cn + .... yn-1 * cn  to get total cost.

Can anyone guide me to the approach i am taking ? is it correct ?
can i take an assumption that for sufficiently large n,  we can ignore T(n/2) and then proceed  ? .

Online searching confused me. Problem is 4.4-5 from CLRS.

Please see here

This solution says T(n) = O(2^n) and T(n) = omega(n^2) and does not explain how.

Also see here

This solution says T(n) = O(n^2).  but contradicts with above solution


texts: Constructing a data structure supporting prioritized key lookup

texts:
so this is more or less a shot in the dark as I am feeling stuck. Maybe some of you have an idea which helps.

Here is the problem description (pseudo formal):

I want to have a structure $T = \{ \hat{x_1}, \hat{x_2}, ... \}$ with $\hat{x_i} = (p_i, k_i, v_{k_i})$.

$p_i \in \mathbb{N}$ can be interpreted as an associated priority. They can be considered unqiue.

$k_i \in \mathcal{K}$ a key index, $d := |\mathcal{K}|$ is not required to be negligibly small, though generally $d \lt\lt |T|$

$v_{k_i} \in \mathcal{V}^{(k_i)}$ a partial key over some universe associated with the given key index. As a little pace killer, this key may not be hashable. The only requirement is totally ordered.

Considering an array $y = [v_i], i \in \mathcal{K}$,
the structure should be capable of supporting the following operations efficiently:

$lookup(T, y) \rightarrow \underset{x_i \in T : y[k_i] = v_{k_i}}{arg max}( p_i )$, i.e. the node $\hat{x_j}$ with a partial key matching and the highest associated priority.

$succ(T, y) \rightarrow lookup(T \backslash \{\hat{x_j}\}, y)$, i.e. the successor (in terms of priority) of a node $\hat{x_j}$ matching $y$

Ultimately I would also like efficient insertion and deletion (by priority).

(For insertion: The selection of $k_i$ for each node is another point of research and can by chosen at the time of insertion. It is essentially possible that this key index is subject to change if it helps the overall structure. But it is also not required that all key indices in $\mathcal{K}$ are supported for each node, i.e. one might need to insert a node which is only queryable by a single $k_i$.)

The key indices are somewhat causing a headache for me. My research so far includes standard priority search trees and dynamic variations thereof.
I also found this very interesting, though very theoretical, paper which takes care of the increased dimensionality (kind of) caused by the d-dimensional keys.

I know that I can construct d-dimensional binary search trees with a query complexity of $O(d + n log(n))$. These should definitely yield a gain though I am not capable of mapping the priority problem to it (Ref).

But I guess the complexity can be reduced even further if we consider that fact, that each node is only storing partial keys anyway.

My approach so far is somewhat naive as it simply creates a hash map for each key index in $\mathcal{K}$ and queries each hash map upon lookup. It then aggregates all the results and sorts them by priority.
This works fine for hashable keys but a fallback structure has to be used whenever they are not (I am using binary search trees).

Edit:

To clarify:
I would like to find a solution which is sub $O(d log(n))$ for queries.

The successor problem can be solved in at least $O(d)$, even if using some kind of tree. See this resource for an overview.


texts: My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since all weights = 1) while maximizing the number of vertices in the resulting subgraph. How do I approach this problem with flow?


texts: Count in relational algebra using Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }

texts:
schema(author)={name, newspaper}

The table contains a list of authors. Each author works for a newspaper. So a single newspaper may employ multiple authors. How can I get the names of the newspapers that have at least two authors working for them? My algebra consists of:

Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }

There is no count in the algebra. So I am limited to the above Ω. Any ideas how I can implement counting?


texts: Does a regular expression model the empty language if it contains symbols not in the alphabet?

texts:
Suppose $\Sigma = \{ a,b \}$ and the regular expression $(a^*b+dc)^*(b^*d + ad)^*$. Is it equal to $\varnothing$?

So I have a regular expression like this: $(a^*b+dc)^*$. As only $(a,b) \in \Sigma$, I see that:

$dc=\varnothing$

So $(a^*b+dc)^*=(a^*b)^*$.

Then:

$(b^*d + ad)^* = (\varnothing + \varnothing)^*=(\varnothing)^*$ and as $(\varnothing)^*=\epsilon$, $(b^*d + ad)^*$ becomes $\epsilon$.

So my regular expression is simply $ (a^*b)^*$? Am I correct, or does the fact that the regular expression contain at least one symbol not in alphabet make it wrong immediately?


texts: Are two non-Turing-recognizable languages closed under union?

texts: If I have two languages that aren't Turing-recognizable, is the union between them always not T-recognizable? Why?


texts: Determine shortest path in a 4x5 grid graph

texts:
Suppose we had a graph $G = (V,E)$.

This graph can also be seen as a $4x5$ grid graph as shown in the image.

There is a directed edge from $v_{i,j} \rightarrow v_{i,j+1}$ for $1 \leq i \leq n$ and $1 \leq j \leq m-1$.

Similarly, there is a directed edge from $v_{i,j} \rightarrow v_{i+1,j}$ for $1 \leq i \leq n-1$ and $1 \leq j \leq m$.

What is the most efficient algorithm to determine the shortest path from $v_{1,1} \rightarrow v_{n,m}$? My main idea is to use the Bellman-Ford algorithm, but I am clearly not taking advantage of how this graph is laid out. Any guidance would be much appreciated.

EDIT: The edges are weighted and may possibly be negative.


texts:
I have a basic question, if I can model a problem $(P)$ by a linear program, can we say that $(P)$ is polynomial?

Linear programs can be solved using simplex, and it was proved that simplex run in exponential time for some instances, so why some references assume that linear programming is polynomial?


texts: List count of occurrences pairs, triplets, etc. from sets

texts:
A receipt is an array of products. I have an array of receipts.

I need to generate a report in where I can find the products often bought together.

For instance, for a single receipt where the products bought are [A, A, B, B, B, C], a report would look like

Pair - count
A&B - 2
A&A - 1
B&B - 1
A&C - 1
B&C - 1

Notice that pair B&A is no longer counted because this is the same as A&B, and similar occurrences. It also has to be sorted by count, decreasing. Also notice that this is just from one receipt rather than multiple, which is what is required.

I also need the algorithm to scale to triples and quadruples, not just pairs.

How would I create an algorithm like this?

There are no set time efficiency constraints. In fact, a more readable solution is preferred over more efficient solutions although efficiency is also appreciated. A python solution is also appreciated, but any language or pseudocode will do.


texts: Merge a set of strings based on overlaps

texts:
I have a set of strings that are slices of a single, longer string. It is not guaranteed, however, that any two strings from this set must overlap: only that all of them together overlap. I want to reconstruct the original longer string.

For example, suppose the longer string is LGHFDJGHSJGHDFKSJBSFSHJKADGHS. The slices might be FKSJBSFS, JKADGHS, LGHFDJGHS, SFSHJKA and GHSJGHDFK. I need an algorithm to reconstruct the original LGHFDJGHSJGHDFKSJBSFSHJKADGHS.

I understand that this algorithm may be somewhat probabilistic: given any two strings, the probability that they overlap by pure chance is $\frac{2}{n}$ where $n$ is the size of the alphabet used. I want to find the "best" overlapping longer string.

So far I've asked around and I've been told to look into suffix trees and de Bruijn graphs. I have done so but I can't see how I can apply them to solve this problem. Any help would be appreciated.


texts: Regarding Backus' Commentary on von Neumann-style Programming

texts:
in John Backus' 1978 FP paper "Can Programming Be Liberated from the von Neumann Style" he says

To help assemble the overall result from single words [von Neumann ie.
conventional mutation-based] languages provide some primitive
combining forms in the statement world--the for, while,and
if-then-else statements--but the split between the two worlds [ie. between the expression-only and statement-only, as I understand him]  prevents
the combining forms in either world from attaining the full power they
can achieve in an undivided world.

He shows the expressiveness of functional programming, that's what the paper is about, but he implies there's a similar expressiveness that can be got from the statements-only part, per the above quote. However I don't know what he means by this; he gives no examples.
The only language that appears ruthlessly statement-y that I can think of is (pure) prolog (eg. see https://en.wikipedia.org/wiki/Prolog#Quicksort, there's no expressions as such only statements giving relationships) and it's not statements so much as the backtracking that gives it the power.
So what did Backus mean by this? What example languages are there that are statement only (but without backtracking)?
Edit: belated link to orginal paper https://dl.acm.org/doi/10.1145/359576.359579 for interest.
(The question has nothing to do with BNF form. Also, if someone can edit the title to better summarise the long quote, please do Edit: that's much better, thanks!)


texts: Complexity of Rearranging a Prefix Tree/Alternative Data Structures

texts:
Let $S$ be a subset of $[0,1]^l$. Is there some data structure that can represent $S$ and can perform the following operations/queries efficiently*?

$ADD(s \in [0,1]^l)$ - operation which updates $S$ to become $S\cup \{s\}$
$REMOVE(s \in [0,1]^l)$ - operation which updates $S$ to become $S \setminus \{s\}$
$PERMUTE(\sigma)$ - operation which updates $S$ to become $\{\sigma(s) : s \in S\}$, where sigma is a permutation of $s$, which rearranged its indices/letters according to a bijection
$START(t \in [0,1]^k)$ - query which returns whether or not there is a string $s \in S$ whose first $k$ letters are the same as $t$

*By efficiently, I mean that it can perform each of the above with worst case complexity $c^{o(l)}$. In other words, I am fine with complexity that is exponential, but I want the exponent to be sublinear in $l$.

A simple prefix tree can do 1, 2, and 4 all linear in $l$, but I can't fathom that it can efficiently do 3. However, if you needed to only support 4 for substrings up to length $k$, we could keep track of how are indices have been permuted since the beginning, and just have $k!\binom{l}{k}$ prefix-trees for each way that could start, which would make 3 and 4 linear, and 1 and 2 $O(l^k)$.


texts: Find all critical edges for minimum spanning tree

texts:
This is a problem from the textbook "Algorithms, 4th edition" by Robert Sedgewick and Kevin Wayne.

  4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to $E \log E$. Note: This question assumes that edge weights are not necessarily distinct (otherwise all edges in the MST are critical).

There is an algorithm (see below), as well as an accepted answer, at stackoverflow.
However, in my opinion, the correctness proof is not complete because it does not justify that all critical edges can be found. Moreover, I cannot figure out how the time complexity of $O(m \log m)$ is achieved in this algorithm (given the hint in the answer).

The algorithm is (in my understanding):

Run Kruskal algorithm on this graph. Whenever we encounter an edge $e$ whose insertion in the MST creates a cycle, the edges in this cycle with smaller weights than $w(e)$ will be reported as critical edges.

My questions are:

How to prove the correctness of this algorithm: (1) all edges reported are critical edges; (2) all critical edges are reported?
How to achieve $O(m \log m)$ with appropriate data structures?
If this algorithm is wrong, how to solve the problem?


texts: how to use type application rule (T-TAPP)?

texts:
In the following rule,

$$\dfrac{ \Gamma \vdash t_1  : \forall X.T_{12} }
        { \Gamma \vdash t_1 \ [T_2]  : [X \mapsto T_2]T_{12} }
        \textsf{ (T-TApp)}$$

whend doing type checking, how do know what is $X$?

Also, type checking will not give you a term which has a form $[X \mapsto T_2]T_{12}$, so how to deal with that substitution?

We will have $t_1 \ [T_2]$ during type checking and $T_2$ could be any type such as $T, T \to T,\forall X.T$. How do we know $[X \mapsto T_2]$, again?

I just could not understand how to apply this rule during type checking?

Please help!


texts: closure of Context free grammer to homomorphism using PDA

texts:
I was looking online, on sipser book, and on lecture notes and I can't find a proof to closure of context free languages to homomorphism that using PDA instead of CFG.
I'm not looking for a full and formal proof, I just want to understand the general idea.


texts: Why is the name half-adder used to represent the half-adder?

texts: I have recently came across half-adders and full adders in my Logic Network lectures. I have somewhat understood the theory, but I am still unable to understand the reason why they called them in that name? I mean, is there any reason why half-adders have the name ‘half-adders’?


texts:
So I recently came across Benford's law and immediately tried to code it out but the answer I got was rather confusing. I've been thinking about it for about an hour now and still can't get it,  I think my code is correct I'm pretty sure it is but the result is just not the one others get. Here's the code:
float[] a=new float[10000],flag=new float[10];

for(int i=0;i<10000;i++)
  {
    a[i]=floor(random(0,99999));
      if(a[i]>10000)
         a[i]=floor(a[i]/10000);
      if(a[i]>1000)
         a[i]=floor(a[i]/1000);
      if(a[i]>100)
         a[i]=floor(a[i]/100);
      if(a[i]>10)
         a[i]=floor(a[i]/10);

      for(int k=1;k<10;k++)
       {
          if(a[i]==k)
            flag[k]++;
       }

  }

Though I get roughly the same flag[k] (around 1100) but according to Benford's law that should not be the case. Can someone help me tell how my code is wrong?


texts: Why do we need Gibbs sampling (and MCMC)?

texts:
I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$.

Maybe my alternative suggestion would sound somewhat naive (even stupid) but why can't we just draw a number in random from $[0,M]$ for some sufficiently large enough $M$. Then, we divide the range to buckets with appropriate sizes according to the distribution.

This will be a true sampling of $\pi$.

One could argue that my suggestion demands a PRNG, but Gibbs Sampling uses randomness too when deciding the next state from the neighbors of the current state.

So for a reasonable distribution, wouldn't my suggestion work way better? It's essentially $O(1)$ and accurate.


texts: Christofides algorithm: why must an MST have even number of odd-degree vertices?

texts:
This question is not necessarily related to Christofides algorithm per se, I just ran into it when reading about it.

I assume that a minimum spanning tree must have an even number of odd-degree vertices, since Christofides algorithm uses this fact to find a perfect matching between "the set of vertices with odd degree in $T$" - an impossible mission for a graph with odd number of vertices...

I couldn't convince myself why this is true, can someone please convince me? Either by a formal proof or with an informal explanation.


texts: Selection algorithm variant for an array

texts:
Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with.

Let $A = A[1], ..., A[n]$ be an array of $n \ge 4$ distinct keys.
Describe an efficient algorithm to find the three smallest keys in $A$. Use words.
What is the worst case number of comparisons performed by your algorithm? Try to find an exact number. Ignore floors and ceilings. Explain your answer.

I would assume you use the randomized $k$-selection algorithm where $k=3$, but if you're recursively partitioning a group of integers around a pivot I'm not sure how you'd find $k=2$ and $k=1$ short of running the algorithm 3 times.
Ideas?


texts: The Ising Model and Computational Complexity

texts:
I've been told recently that one can use the Ising model can find solutions to certain NP-hard problems, such as Clique, although it doesn't do so in polynomial time.

Googling gets a few Arxiv results but where might I find an introduction to this interesting relationship?


texts:
After coming across the assertion that given

$$
    x^2 = y^2 \pmod n \\
    x \neq \pm y \pmod n
$$

we can then conclude that n factors into

$$
    n = \mathrm{gcd}(n, x-y) \mathrm{gcd}(n, x+y).
$$

in this article, I attempted my own example but it doesn't seem to work.  I think there's a missing hypothesis, but more importantly, I'm interested in understanding why this would work under the correct conditions.

First, the example given was

$$
\begin{align*}
    &6^2 = 1^2 \pmod {35} \\
    &x+y = 7 \\
    &x-y = 5
\end{align*}
$$

So applying the gcd with $35$ simply retains the values, yielding the correct factorization

$$35 = 7 \times 5.$$

However, my test example was

$$
\begin{align*}
    &8^2 = 4^2 \pmod {24} \\
    &x+y = 12 \\
    &x-y = 4
\end{align*}
$$
If we just blindly applied the stated result, we would get

$$24 = 12 \times 4.$$

I would guess the problem is that my selected factors are not coprime.  Does anyone have any intuition for why this method works (when it works) or any hints towards a proof?

After some brief pondering, I've noticed it certainly works if the values $x+y$ and $x-y$ are coprime.  Their product divides $n$ yet they contain no overlapping factors, so by collecting the factors of $x+y$ and $x-y$ which are also factors of $n$, we will end up with precisely all the factors of $n$ and nothing extra.


texts: How to be sure of a good solution in hyperparameter optimization

texts:
I have a very expensive black-box function and at least 15 parameters that I want to explore (usually 5-6 at a time). So far I have tried Genetic Algorithms and Gaussian Process Surrogate Optimization (bayesian optimization). Both methods work fine and efficiently up to 5-6 parameters. However, I am having an issue on how can one be sure that a solution found by GA/GPSO is a good solution, without basically knowing nothing about the output space. I don't really want to go for an exhaustive grid search since even with 5 parameters, it requires incredible amounts of evaluations, yet I cannot come up with anything better.

I would also very much appreciate suggestions/keywords for literature reading, or event different methods for hyperparameter optimizations.

Thanks in advance


texts: Need confirmation for and answer related to algorithm notations(ϴ,O and Ω)

texts:
In my class we have to answer a question:

Having this pseudocode:

XPTO(n)
sum = 0
if even(n)
    for i=1 to n
        sum = sum + i
else sum = 0

and knowing that even(n) have complexity ϴ(1), we can say the complexity of XPTO is ϴ(n)? Justify.

How do I justify this?


texts: What is Geometric complexity theory (GCT)?

texts:
I was reading about complexity theory and I got a term Geometric complexity theory. I google the term on internet and find out that

  Geometric complexity theory (GCT), is a research program in computational complexity theory proposed by Ketan Mulmuley and Milind Sohoni. The goal of the program is to answer the most famous open problem in computer science – whether P = NP – by showing that the complexity class P is not equal to the complexity class NP---- from wikipedia

Question :  How researcher in this area prove or disprove that P = NP ? ( A high level explanation is sufficient)


texts: Is this problem about picking optimal entries of a matrix NP-complete?

texts:
I am trying to solve a real-world problem that I was able to reduce to the problem described below. I would like to know the following things:

Is there literature about this problem?
Is the corresponding decision problem NP-complete?
Do you know an efficient algorithm to solve the problem?
If not, what would be a good technique to solve it approximately?

The problem is as follows. Given a $n \times m$ matrix $M$ with entries in $[0, 1]$, and a function $a \colon \{1, \ldots m\} \to \mathbb{N}$. For each column $j$, we want to pick $a(j)$ entries in that column, such that in each row, at most one element was picked. We want to do this in such a way that the sum of the picked values is maximized.

More formally, find a function $T\colon \{1, \ldots n\} \to \{1, \ldots m\} \cup \{\bot\}$ which maps each row to a column (or $\bot$), with the following two properties:

$\forall j \in \{1, \ldots m\} \colon \lvert T^{-1}(j)\rvert = a(j)$
The following expression is maximized: $$
 \sum_{\substack{i=1 \\ T(i) \neq \bot}}^n M_{i, T(i)}
$$

Of course, you could also define it the other way around, with each column mapping to a set of rows. Finally, the corresponding decision problem is in NP, as the function $T$ acts as a certificate.
I tried a reduction to knapsack, as the two seem quite similar, but I was unsuccessful.


texts:
I am using a digital computer to write this message. Such a machine has a property which, if you think about it, is actually quite remarkable: It is one machine which, if programmed appropriately, can perform any possible computation.

Of course, calculating machines of one kind or another go back to antiquity. People have built machines which for performing addition and subtraction (e.g., an abacus), multiplication and division (e.g., the slide rule), and more domain-specific machines such as calculators for the positions of the planets.

The striking thing about a computer is that it can perform any computation. Any computation at all. And all without having to rewire the machine. Today everybody takes this idea for granted, but if you stop and think about it, it's kind of amazing that such a device is possible.

I have two actual questions:

When did mankind figure out that such a machine was possible? Has there ever been any serious doubt about whether it can be done? When was this settled? (In particular, was it settled before or after the first actual implementation?)
How did mathematicians prove that a Turing-complete machine really can compute everything?

That second one is fiddly. Every formalism seems to have some things that cannot be computed. Currently "computable function" is defined as "anything a Turing-machine can compute". But how do we know there isn't some slightly more powerful machine that can compute more stuff? How do we know that Turing-machines are the correct abstraction?


texts: Algorithms that are using John's ellipsoid

texts: The Lowner–John ellipsoid is a minimum volume enclosing ellipsoid of some convex body $K$. This ellipsoid is unique (as is the maximum volume ellipsoid contained in $K$). I'm looking for algorithms based on those ellipsoids, or any significant practical use that requires finding them explicitly.


texts:
I am confused interpreting the statement of this question:

"If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?"

Should the symbol "|" (such as) be understood as an logical and?

The language L1, so,  would be $ L \cap L^R $ - a subset of L?

Or should the symbol "|" be understood as an logical or?

The language L1, so,  would be $ L \cup L^R $?

In both cases it is regular (I believe), since the languages $L$ and $L^R$ are regular, and the union or intersection will be also regular.

Am I understanding this right?


texts: Pittsburgh approach, how does encoding and fitness function work?

texts:
I am writing a genetic algorithm for Machine learning and came across Pittsburgh approach in some research papers. The papers didn't explain the algorithms proper or I am too stupid to understand. I know that each Individual contains set of rules and I have also implemented in binary but am having trouble with 6 float type values.
My question is:

How am I generating uncertainty value in the genes?
How will I be using encoding with real/floating type values?
How is the fitness function going to work?

I would love to it also if you could send me references to which I might be able to better understand the algorithm. I will be using float number so no binary methods or explanation.


texts: Best asymptotic randomized multidimensional index?

texts:
What data structure has the best asymptotic running time for nearest-neighbor search on multidimensional data?  I am interested in both preprocessing time and query time, but let's restrict attention to data structures with logarithmic average query time; how low can we make the average preprocessing time?  By average, I mean the with respect to approximately uniformly distributed data.

Kd-trees give $O(n \log n)$ average preprocessing time with $O(\log n)$ query time.  $O(\log n)$ query time is asymptotically optimal for deterministic algorithms, because $1$-nearest neighbor search can be used to solve the element distinctness problem.  Likewise, $O(n \log n)$ preprocessing is asymptotically optimal since the kd-tree can then be used for sorting.

However, this does not prevent the existence of better randomized algorithms, which give the $k$ nearest neighbors with high probability.  Indeed, for approximately uniformly distributed data, there may exist deterministic algorithms that are better.

Are there any randomized algorithms for multidimensional indexing that have a better (asymptotic) preprocessing time than kd-trees while still performing log-time queries?


texts: Finding Median in Log(n) time, Impact on Sorting

texts: I realize that we must do a minimum of $n - 1$ comparisons to find the median in a list of numbers, therefore the time complexity would be $\Omega(n)$. However, given a hypothetical scenario in a world where the median can be found in $\mathcal O(log(n))$ time, what would be the implications on the fastest sorting time? Would this allow us to beat $\mathcal O(n\log(n))$ and sort in $\Theta(n)$ time?


texts: Difference between auxiliary space v/s space complexity

texts:
I'm confused between these two terms as for example - the Auxiliary space of merge sort, heapsort and insertion sort is $O(1)$ whereas Space complexity of merge sort, insertion sort, heapsort is $O(n)$.

So, if someone asks me what's the Space complexity of merge sort, heapsort or insertion sort then what should I tell them $O(1)$ or $O(n)$?

Also, note in case of selection sort, I've read it's Space Complexity is $O(1)$ which is auxiliary space.


texts: I'm working on a paper that uses ε-greedy algorithms for choosing episodes of a sarsa q-learning algorithms. I searched for algorithm but couldn't get so much. Can you please give me the algorithms and a little explanations about it?


texts:
I have a problem and I've been struggling with my solution time and space complexity:

Given an array of integers (possible duplicates) A and min, low, high are integers.
Find the total number of combinations of items in A that:

low <= A[i] <= high
Each combination has at least min numbers.
Numbers in one combination can be duplicates as they're considered unique in A but combinations can not be duplicates. E.g.: [1,1,2] -> combinations: [1,1],[1,2],[1,1,2] are ok but [1,1],[1,1], [1,2], [2,1] ... are not.

Example:
A=[4, 6, 3, 13, 5, 10], min = 2, low = 3, high = 5
There are 4 ways to combine valid integers in A:
[4,3],[4,5],[4,3,5],[3,5]
Here's my solution and it works:
class Solution:
    def __init__(self):
        pass
    def get_result(self, arr, min_size, low, high):
        return self._count_ways(arr, min_size, low, high, 0, 0)
    def _count_ways(self, arr, min_size, low, high, idx, comb_size):
        if idx == len(arr):
            return 0
        count = 0
        for i in range(idx, len(arr)):
            if arr[i] >= low and arr[i] <= high:
                comb_size += 1
                if comb_size >= min_size:
                    count += 1
                count += self._count_ways(arr, min_size, low, high, i + 1, comb_size)
                comb_size -= 1
        return count

I use backtracking so:
Time: O(n!) because for every single integer, I check with each and every single remaining one in worst case - when all integers can form combinations.
Space: O(n) for at most I need n calls on the call stack and I only use 2 variables to keep track of my combinations.
Is my analysis correct or not?
Also, a bit out of the scope but: Should I do some kind of memoization to improve it?


texts: What is the common terminology to refer to the nth ancestor of a tree root?

texts:
Reading the Wikipedia article for common terminology for tree (data structure) there are several near references, but I don't read a formal declaration for how to refer to a specific generation of a tree's subtrees.
For example,

Definition
As a data type, a tree has a value and children, and the children are
themselves trees;  [...] Due to the use of references to
trees in the linked tree data structure, trees are often discussed
implicitly assuming that they are being represented by references to
the root node, as this is often how they are actually implemented.

And also,

Terminology.
"The height of a node is the length of the longest downward path to a
leaf from that node. The height of the root is the height of the
tree. [...] The root node has depth zero..."

The former implies subtree n could be refered to as the nth decendant of root or the nth tree. Can I be sure subtree only refers to decendants and not other branches at the same distance from root?
The latter refers to the height counting from the root (0). Again, height sounds uncommon to me. As in, "Please refer to the nodes at height 4 to see..." Since a tree is commonly displayed from the root branching downward, I'm predisposed to bias against the term height versus my preferred notion of depth.


texts: What are the applications of Rose trees?

texts:
I recently found out about the Rose tree data structure, but just going off of a Haskell data definition and the tiny Wikipedia description of it, I've got some trouble understanding what applications a Rose tree might have.

For reference, the Haskell data definition:

data RoseTree a = RoseTree a [RoseTree a]

For those unfamiliar with Haskell -- it's a recursive data type definition with an arbitrary type a, where the type constructor is provided with a literal of type a followed by an optionally empty list of type RoseTree on the same type a.

The way I see it:

This data structure is unordered by default (although I assume most practical applications do implement some form of ordering for searching)
The data structure doesn't enforce a fixed number of nodes per layer at any point, except the global root, which must have a single node

Given that minimal amount of information, I'm having trouble figuring out when one might use this type of tree.

In addition to the question in the title, if search is indeed implemented in most applications of a Rose tree, how is this done?


texts: A question on the linear speedup theorem

texts:
I am trying to understand the linear speedup theorem:

Let $L$ be a decidable language. Let $X^L$ be the set of all deterministic Turing machines which decide $L$. For a word $x \in \Sigma^*$ define:
$t^L(x) := \min_{M \in X^L} t_M(x)$ where $t_M(x)$ is the time of $M$ on input $x$. Now let's choose some machine $M$ which satisfies $t^L(x) = t_M(x)$. Then for all $A \in X^L$ we have:

$$t_M(x) \le t_A(x)\,.\qquad(**)$$

Now let's apply the linear speedup theorem for the machine $M$: We get a new machine $N$ such that:

$$t_N(x) \le t_M(x)/2 + |x| + 2\,.$$

But by (**) we have: $t_M(x) \le t_N(x)$ hence it follows, that
$t_M(x) \le t_N(x) \le t_M(x)/2 + |x| + 2$. From this it follows that
$t_M(x) \le 2 |x| + 4$.

But how can this be? It means that, for every word $x \in \Sigma^*$ there exists a deterministic Turing machine $M$ which decides $L$ such that the time of $M$ on input $x$ is at most $2|x| + 4$.

This seems very absurd. What am I doing wrong?


texts: If the Clique-k Problem is in P, why not Clique as well?

texts:
I have looked at the other answers to this but I still don't get it. (for instance: Why is the clique problem NP-complete?)

The general clique problem is defined as

$\text{CLIQUE} = \left\{ (G, k) | G = (V, E) \in \mathcal{G} \land \exists V_c \subseteq V . |V_c| \geqslant k \land V_c \text{ is clique in } G \right\}$

A clique of a given size can be found in polynomial time, for instance by this code:

# Iterates over all nodes. If node has at least size -1 neighbours,
# compares neighbour's neighbours with neighbours.
def CLIQUE(graph, size):

    for node in graph.nodes:
        if degree(graph, node) >= size - 1:
            neighbours = graph.edges[node]
            intersection = neighbours.union(set(node))
            for neighbour in neighbours:
                print neighbour
                print graph.edges[neighbour].union(neighbour)
        intersection = intersection.intersection(graph.edges[neighbour].union(neighbour))
            print intersection
            if len(intersection) >= size:
                return True
    return False

(rest of the program)

class Graph:
    def __init__(self):
        self.nodes = set()
        self.edges = dict()

    def from_file(self, deffile):
        with open(deffile, 'r') as f:
            for line in f:
                n1, n2 = line.split()
                self.nodes.add(n1)
                self.nodes.add(n2)
                if n1 in self.edges:
                    self.edges[n1].add(n2)
                else:
                    self.edges[n1] = set(n2)
                if n2 not in self.edges:
                    self.edges[n2] = set()

def degree(graph, node):

    return len(graph.edges[node])

So, given that the clique problem is 'Is there q clique of at least size k in G' and the above code returns true once it finds a clique of (at least) k nodes and runs in $\mathcal{O}(n^2)$, as it compares every node with every other node in the worst case, I don't understand how that code does not do what the general clique problem does... because apparenrtly it does not, as it runs in polynomial time and the general clique problem does not.


texts: Throughput increase/decrease by how much percent

texts:
I am learning computer architecture and organization. I am stuck in the following question. Can someone please help me?

The stage delays in a 5-stage pipeline are 300, 200, 100, 400 and 350 picoseconds. The second and third stages are merged into a single stage with delay 350 picoseconds. The throughput increase/decrease by ………… (percent).

This is what I tried:
Throughput of 1st case T1: 1/max delay =1/200
Throughput of 2nd case T2: 1/max delay= 1/350
%age increase/decrease in throughput: (T2-T1)/T1 * 100
= (1/350 - 1/200)/(1/200)*100
= -42.8
So the throughput decreases by 42.8%.
But the correct answer is given to be 0. I don't understand why?


texts: How to create disjoint sets out of an adjacency list

texts:
I'm not a computer scientist, so please bear with me if I'm misusing some terminology.

What I'm trying to do is to find the different components of an undirected graph.

I have an array of pairs that represent the edges of my graph, like so:
[[1,3],[4,2],[2,1],[5,6],[100,20],[22,5]] and what I want to create out of this are arrays (or objects) containing the connected vertexes (the disjoint sets or components, like this (for the above example): [[1,2,3,4],[5,6,22],[20,100]]

My first approach was to convert the array of pairs into an adjacency list, using hashmaps/tables/sets or something in this line it can be done in O(n) time and additional space (n being the number of pairs). Then using BFS, I scan every vertex in the graph. Whenever the queue is empty, I have completed a component/disjoint set. If unvisited nodes are still in the graph, this is a new component/disjoint set. Until all the nodes are visited.

Now, I learned about the disjoint-set data structure.

My question: Using disjoint-set data structure how can I convert my array of pairs into the disjoint components of the graph I'm looking for? Any resources are also very much appreciated. I'm still learning and don't really know what I'm talking about.

What are the pros and cons of the first approach compared to the second approach.

Oh, BTW, if this is the wrong place to ask this question, please, advise!

Thanks in advance!


texts:
Given a Diophantine equation $p(x_1,x_2,...,x_n)$,

Can I find a reduction from $\text{dioph}(\mathbb{N}) \leq \text{dioph}(\mathbb{N}_e)$?

$\mathbb{N}_e$ is the set of even numbers.

So I have to find a manipulation of $p$ such that I only have even numbers as solution.

How can I do this? Unfortunately I have no Idea.


texts: Is $P$ defined for TM which decide or accept a language?

texts:
Sipser defines $TIME(t(n))$ as the set of all languages that are decidable by an $O(t(n))$ time TM and then $P = \bigcup_k TIME(n^k).$

However I see also many definitions like
$$
P = \{ L \mid \text{There is a polynomial } p(n) \text{ and a TM which accepts each string } w\in L \text{ in max. } O(p(n)) \text{ steps.} \}
$$

The first definition by Sipser requires a TM which decides the language and the second definition requires only a TM which accepts the language.

Which definition is more common? Is there a theorem which relates both?


texts: Recurrence: space complexity to Tournament Method

texts:
Tournament method have this structure to found min and max (function getMinMax):

  mid = (low + high)/2;
  mml = getMinMax(arr, low, mid);
  mmr = getMinMax(arr, mid+1, high);

  /* compare minimums of two parts*/
  if (mml.min < mmr.min)
    minmax.min = mml.min;
  else
    minmax.min = mmr.min;

  /* compare maximums of two parts*/
  if (mml.max > mmr.max)
    minmax.max = mml.max;
  else
    minmax.max = mmr.max;

Time complexity is , but how can I found the space complexity? You stack  values, plus  values, plus  values... until  values. So  (log n times). . That's right?


texts: Are there any theorems/formulas that apply to the height of comparison trees?

texts:
I have been drawing some binary comparison trees, which correspond to compares made to sort an array, and I was wondering if there is any formula to determine the height of a comparison tree for an array of N values, in Sedgewick's algorithms 4th ed. book for N = 3, the height of a comparison tree is 3.

He draws his comparison trees in such a way that all the internal nodes and the root represent the comparisons, for example (i:j) means compare a[i] to a[j], if a[i] < a[j] then the left subtree represents all the rest of the comparisons that we need to make, to finish the sort, and the leaves represent the permutations that we get after the sort. For example the left path for N = 4 is : (0:1), (1:2), (2:3), (0,1,2,3).

After I drew a tree for N = 4, the height was not 4, more specifically, an example would be the following path : (0:1),(1:2),(2:3), here a[2] > a[3] (3:1),(3:0),(3,0,1,2). So is there a formula?

In the example above we first find out that a[0] < a[1] < a[2] and then we find out that a[2] > a[3], so we need to compare a[3] to a[1] and a[0], so far the path length is 4, but then we add the leaf (3,0,1,2) and now the path length is 5.


texts: Which textbook can I use after a high school CS course?

texts:
I just finished the AP Computer Science course in high school and since my school does not have any further classes, I was thinking about getting a textbook and continuing my study. APCS goes through Big O, Arrays + ArrayLists, Recursion, Linked Lists, a rough overview of some other data structures and some sorting and searching algorithms (all in Java).

I will start Calculus in school next year (if that helps to determine math level).

Since I was thinking about participating in CS tournaments, I thought it would be useful to learn more about algorithms and data structures.

I was looking at two textbooks, The Algorithm Design Manual by Steven S Skiena and Introduction to Algorithms by Cormen et. al. I was wondering which one, if any of these, would best fit my situation.


texts: Detecting spoken words in audio stream or file?

texts:
I am a hobbyist interested in single word recognition. What is the state of research? Where I can get papers or/and software tools regarding that?

Thanks in advance for any advice!


texts: Covering Variation of Longest Common Substring

texts:
Given three binary strings, find the maximum possible length of a contiguous block of 1's formed by shifting and overlapping the strings.

This may be interpreted as finding the maximum window size $k$ such that for each column $(a, b, c)$ across the three strings, it holds that $a \lor b \lor c$ is true. If we instead require $a = b = c$, then we recover the original longest common substring (LCS) problem, for which there is a linear time algorithm using suffix arrays. Can a similar linear time result be achieved here?


texts: An almost surely finite time game of coin toss where you win with probability $p$

texts:
Given a fair coin and a number $p\in(0,1)$. How do you design a game that finishes in a finite number of tosses with probability $1$, and further, with probability $p$ you win the game?
I thought about random walks where head, you add 1, tail you subtract 1. And you want to get to $n$. But that gives an approximation to $p$ and not $p$.


texts: Definition of “infix” in formal languages

texts:
I've got a simple question:

Let's say we have the following definition of a language over some alphabet: $L = \{w \mid w \text{ contains the infix } aab\}$

Does that mean $aab \in L$? or does "$aab$" have to be "wrapped" on both sides by other letters?


texts: Algorithm for Minimum Weight Maximal Independent Set

texts: Is there any algorithm for finding the minimum weight maximal independent set? Instead of finding all maximal independent sets and keeping the one with less weight, is there any easier method to do it?


texts: The number of balanced trees with N node and L leaves

texts:
An algorithm is requested to calculate all balanced binary trees which can be built with $N$ nodes, having exactly $L$ leaves. A balanced tree is a binary tree in which the difference between the heights of the left and right subtrees is at most 1, and the subtrees are themselves balanced.

I tried to use dynamic programming to calculate the number for the subtrees created from any subsequence of $1..N$. However, without building each possible subtree and calculating its height and differentiating the height of the subtrees from each other, it can't distinguish the balanced subtrees. Moreover, the sum of their leaves must be exactly $L$. There are many constraints, and I couldn't come up an algorithm, either a working nor an optimum one.

Could you please guide me?

Source: Assignment of Advanced Algorithms, Fall 2018, Tehran University


texts: Looking for sources: Graph search in social media

texts: I am looking for more information/references on how graph search is utilized in social media. Papers, books , anything really.


texts: detecting a cycle in an undirected graph problem is in $RL$ complexity class

texts:
I need come up with an algorithm for detecting a cycle in an undirected graph where the algorithm is in $RL$. That is, the algorithm detects a cycle with a probability greater-equal to $\frac{1}{2}$ but it doesn't return true for a graph with no cycle (no false-positive).

In class, we've learned that $USTCONN$ (the problem of telling if there's a path from $s$ to $t$ in an unidrected graph) is in $RL$.

I thought about utilizing it for the current problem:

We choose $s,t$ in random s.t $t$ has at least $2$ edges and check if there's a path between them.
Then, in the same fashion, we check if there's a path between $s$ and $t$'s neighbors (If there are too many we may limit it to some constant, randomly, since we must use only logarithmic space)
If we found two different paths from $s$ to $u_1,u_2$ where the latter are $t$'s neighbors then there must be two different paths from $s$ to $t$ - Which is a cycle.
We repeat the above sufficiently many times (TBD)

I would like to know if that is the algorithm expected from me to come up with before I put efforts in proving that this algorithm is indeed in $RL$.

Thanks!


texts: How many operations to produce this superposition of 3 qubits?

texts:
Suppose I have three qubits that of course represent $2^3=8$ states. I want to put these qubits so that they are in the particular superposition say...

$$a|000\rangle + b|001\rangle + c|010\rangle + d|011\rangle + e|100\rangle + f|101\rangle + g|110\rangle + h|111\rangle\,.$$

Here's the question: do I perform a 2d rotation on each qubit (each having its own $2\times2$ rotation matrix) for a total of three operations, or do I perform a single 8d rotation using an $8\times8$ rotation matrix?

Follow up question: if the answer is 'make an $8\times8$ matrix', doesn't this at some point boil down to just applying a rotation to each qubit?


texts: What is the appropriate means of bias field in image processing?

texts: I want to do image segmentation. In (Li, C. et al, 2011) article about A Level Set Method for Image Segmentation I saw that the authors use bias field estimation. I searched a lot but I couldn't understand the meaning of bias field...What is the appropriate mean of bias field?


texts: I want to understand type theory but I have to know first how I can apply it. Could there be more non-obvious applications of type theory aside from in type systems in programming? Could there be other applications, let's say in personality profiling and the likes?


texts: How can we construct a TM with a Halt1 Oracle that decides if a TM halts on all inputs?

texts:
Can we construct an explicit Turing Machine with a Halt1 oracle that decides if a standard Turing Machine halts on all inputs?

By a Halt1 oracle I mean that we have the ability to decide if Turing Machines with a Halting oracle halts or not.


texts: Solving inhomogeneous recursion using quadratic particular solution

texts:
I am interested in solving recursions and while I was trying to solve this one:
$a_n=a_{n-1}+4n-3$

I ran onto a problem, I don't see how to find an explicit solution using standard inhomogeneous method(finding homogeneous and particular solution). Specifically I have a problem with finding particular solution. Problem for me is how to find expression to represent $f(n)=4n-3$. I do know how to solve for $f(n)=n$ with representing $f(n)$ as polynomial $an+b$ and substituting in the recursion. Is there a way to solve this type of recursions when $f(n)$ isn't depending just on $n$. Can we solve for even more complicated expressions such as $f(n)=5n^2+2n+4$ or any polynomial of degree $n$


texts: DFA that accepts two more $1$'s than $0$'s

texts:
What is the state diagram of a DFA that follows

$L = \{w \in \{0,1\}^*\mid w\text{ has at least two or more 1's than of 0's}\}$.

Examples: $110$ doesn't work, $1110$ works.


texts:
I cannot really find a source that does not use the same examples provided by CLRS. I need a simpler example than MULTI-POP example. Could someone provide an example and explain me:

a) What is the difference between worst-case analysis and amortised analysis?

b) What is the difference between average-case analysis and amortised analysis?

c) In plain English(with using minimal notations), how can we provide a complexity(especially I am interested in potential method)


texts: Combinations and Permutations of M sets of distinct items?

texts:
I'm wokring on this problem for a while. I want to know:

The correct name of this problem, so I can look it up in textbooks\online.

Here is the problem descirption:

The (un-ordered) combinations to be generated are:

of 1 item size:   {a1}, {a2} .... {c4}
of 2 items size:  {a1, b1}, {a1, b2} ... {b2, c4}
of 3 items size:  {a1, b1, c1}, ... {a3, b2, c4}

The question is: Given any number of sets M where each set has distinc number of items, How many (un-ordered) combinations are there of size 1, 2, ..., up to M? And how to generate those combinations?


texts: Performance of microkernel vs monolithic kernel

texts:
A microkernel implements all drivers as user-space programs, and implements core features like IPC in the kernel itself. A monolithic kernel, however, implements the drivers as a part of the kernel (e.g. runs in kernel mode).

I have read some claims that microkernels are slower than monolithic kernels, since they need to handle message passing between the drivers in user space.  Is this true?

For a long time, most kernels were monolithic because the hardware was too slow to run micro-kernels quickly. However, there are now many microkernels and hybrid kernels, like GNU/Hurd, Mac OS X, Windows NT line, etc.

So, has anything changed about the performance of microkernels?  Is this criticism of microkernels still valid today?


texts: Finding infeasible sets of constraints (CSP)

texts:
Given a set of constraints, I want to check whether the constraints are feasible. What I am trying now, is to feed the constraints to a solver and check if the solver returns infeasible. I am using both CSP solvers and optimzation (such as MILP) solvers (in the latter case, I set a dummy objective function, e.g., maximize a constant).

This works, so I can check if a given set of constraints is feasible. However, now I am looking for a more general problem: How many set of constraints are infeasible. One way to do this is to generate all sets of constraints separately, and then feed each of them individually to the solver. Alternately, I can ask the solver to enumerate all solutions, then check which ones do not appear in. Both becomes impractical in my case, as the search space is too big to exhaustively enumerate.

  The question is, is there any practical way to find the sets of constraints which are infeasible by using standard CSP/optimization solvers?

Since the question is too broad, let me give a more specific example. Assume, we have 4 binary variables, $x_0$, $x_{1}$ and $y_0$, $y_{3}$. There are certain constraints (say, $x_0+x_1 = 1$, $x_0+y_0=1$, $y_1=1$) which are satisfied only for $(x_0, x_1, y_0, y_1) = (0, 1, 1, 1), (1,0,0,1)$; hence the rest 14 quadruples are infeasible (which I am interested in). In the first method, I am generating all 16 constraints and checking which ones are infeasible. In the second, I am asking the solver for all solutions and taking those 14's which are not present in the solution. In my case, the number of variables are too large (say, $x_0, \ldots, x_{127}$ and $y_0, \ldots, y_{127}$), so no method will work in practice.

Modern CSP solvers can check for feasibility for thousands of variables. What I am looking for is kind of the opposite direction: Can it look for non-feasibility?


texts: Proving that a simple algorithm is $\Omega(n^2)$ for all inputs

texts:
I am given the following algorithm, which checks whether a given matrix is symmetric:

isSym(A):
1.   b = True
2.   for i = 0 to n-1 do
3.     for j = i+1 to n-1 do
4.       if A[i,j] != A[j,i] then b = False
5.   return b

My aim is to prove that it is $\Omega(n^2)$ for any $n\times n$ input matrix. I have something, but I want to see if it is correct and if it is correct, whether there is a more obvious way to prove it.

Firstly, the outer loop in line $2$ runs $n$ times. As for the inner loop in line $3$, this runs from $i+1$ to $n-1$. Therefore this loop runs $n-i-1$ times regardless of input and is $\Omega(n-i-1)$, where $i$ goes from $0$ to $n-1$ in the outer loop. So I have

$\sum\limits_{i=0}^{n-1}\Omega(n-i-1) = \Omega(\sum\limits_{i=0}^{n-1}(n-i-1))$, where if I split the summation up I get

$\Omega(\sum\limits_{i=0}^{n-1}n-i-1) = \Omega(n^2 - \frac{n(n-1)}{2} - n)$

This can be simplified as $\Omega(\frac{n^2 - 3n}{2}) = \Omega(n^2)$

Is this the correct approach?


texts:
In S/Kademlia two crypto puzzles is used, one static and dynamic. The static is used to generate a key pair that makes an eclipse attack difficult to achieve, the dynamic to make Sybil attacks harder.

In the dynamic, I am very confused about the x which is found, since I can’t find any evidence for this ever being used again in the system, is it send along in a signature or what is it used to?

I do not think the paper mentions any use of it, I at least have not been able to find it, why I ask here for the use of x.


texts: books on algorithms for beginners in Ruby or Python or C. Not too math heavy

texts:
I am currently at student at Turing and I would like to learn more about algorithmic design while studying programming. Our school mainly deals more with web software, Ruby, and Rails, but I would like to gain an education in algorithms and data structure while here.

Do you have any books for beginners on algorithms or data structure? I only know Ruby and a little Python. Is there anything that you recommend that isn't the CLRS book... it's a tad over my head right now.

How much mathematics do I need to know? My guess is that I also need a book on discrete mathematics?


texts: Variant of greedy algorithm for vertex cover

texts:
Does the following approximation algorithm for vertex cover also have an approximation ratio of 2? Why? Why not?

Input: $G = (V,E)$

Set $C \gets \emptyset$ and $E' \gets E$.
while $E' \neq \emptyset$ do:

Pick any edge $(u,v) \in E'$.
$C \gets C \cup \{u\}$.
Remove from $E'$ all edges incident to $u$.

return $C$.


texts: How to add important events as input in neural network?

texts:
I'm quite new to neural networks so I apologize if this question is too basic/doesn't really make sense.
I have a financial time series dataset and I have a binary variable which is 0 if no important announcement regarding the company was announced that day and 1 if there was an important announcement. These events should intuitively be significant predictors of price and I was wondering if there was a way to add this to a neural network or if adding it as an input makes sense? Any examples would be appreciated too, thank you!


texts: What is the Big theta of $(\log n)^2+2n+4n+\log n + 50$?

texts:
$f(n)=(\log n)^2+2n+4n+\log n + 50$

I am trying to mathematically prove that $f(n)$ falls under some time complexity big theta. My guess is that it is $(\log n)^2$ because it is the dominant term.

I need to come to the conclusion of $f(n)\leq C(\log n)^2$, for some positive constant $C$ and $x\geq k$.

What I have tried is:

$(\log n)^2+\log n \leq 2(\log n)^2$

I want to add $6n + 50$ to both sides, but cannot find the constant $c$ by algebra in $c(\log n)^2$.

I have just tried putting random values of $c$ to make $c(\log n)^2 \geq 6n$ true and $c=100$ works for $n$ greater than some value, but is there a mathematical way of finding this value of $c$ and therefore finding the big theta of this function?

-----------------------------------------------

Additional try:

I have changed my thought and I think $n$ is the dominant term because polylogarithms grow slower than polynomial functions, $n^b$ where $b > 0$.

And so

$(\log n)^2 + \log n \leq 2n$

$(\log n)^2 + \log n + 6n + 50 \leq 9n$ for $n \geq 50$.

And, for the big Omega, it is obvious that $(\log n)^2 + \log n + 6n + 50 \geq 6n$

Thus, we can see that $f(n) \in \theta(n)$.

But I'm not sure as to if I have to prove that the polylogarithm $(\log n)^2$ grows slower than the linear function $n$ to complete the reasoning. Will that include the use of L'Hopital's rule?


texts: Difference between $\beta$-contracts and $\beta$-reduces in Hindley

texts:
I brought the book Lambda-Calculus and Combinators: An Introduction by J. Roger Hindley and the author explains what is $\beta$-reduction.

Now there is a difference between $\beta$-contracts and $\beta$-reduces:
$$
\begin{align*}
P &\rhd_{1\beta} P^\prime\\
P &\rhd_{\beta} P^\prime
\end{align*}
$$

Could someone please explain me what is the difference?


texts: Can we improve the precision of IEEE floats by dropping leading zeros in the mantissa?

texts:
It seems like it would be possible to add more precision to the IEEE 32-bit mantissa system if the leading zeroes were also dropped, just like the leading 1 is dropped due to it being implicitly known.

For example, the number 17 would be represented as 0|10000100|00010000000000000000000. The leading 1 of the mantissa is always dropped, since every number in scientific notation starts with a 1. My question is why can't the leading zeroes also be dropped? If we know based on the exponent that the decimal place gets moved 4 spots, shouldn't we also be able to deduce, just like the implied 1, that all other missing bits afterwards would be 0? Granted, in this example it wouldn't make a difference, but for larger numbers, or numbers with a lot of digits past the decimal point, it seems like you would be able to get more precision the more implied bits you drop.

(As I'm typing this, I'm also realizing that you might even be able to drop the next 1 in the mantissa. If the computer knows the number of places to move the exponent, you could have as many zeroes as you want sandwiched between two implied 1's)

Does anyone know if this was ever addressed (or if I completely messed up in my calculations, and it isn't really possible to drop that many bits)?


texts: Relation between CPU cycle and Addressing modes

texts:
Professor has given this question in exam. I am not able to find relevant reference for this question

Which Addressing Modes (for x86 architecture) consumes more CPU cycle?(Consider all are special purpose registers)
A. Indexed
B. PC-Relative
C. Indexed Register with displacement
D. None of the above

What I have understood is that Instruction fetch(1 cycle) and updating PC value is common for all the modes.
Indexed Mode takes 1 cycle( Effective address calculation, since base address is already decided) and 1 cycle for write to Memory.

PC- Relative will 1 cycle for Instruction decide, 1 cycle for Operand fetch from Memory and 1 cycle for Memory writeback.

Indexed register with displacement will take 1 cycle each for decode of n Instruction, 1 cycle for effective address calculation and 1 cycle for Operand fetch and 1 cycle for Memory writeback.
I am getting Indexed register with displacement mode as having more CPU cycle.

Correct me if I am wrong. Also provide reference for understanding link between CPU cycle and Addressing modes


texts: Solving " Tricolor Arrangement " Efficiently

texts:
A rectangular board with three rows and $n$ columns is filled with $3n$ counters, of which $n$ are red, $n$ are white, and $n$ are blue. The object is to rearrange the counters to have counters of each of the three different colors in every column. The only operation allowed is to swap counters in the same row. Design an algorithm to accomplish such a task or prove that such an algorithm does not exist.

Let $\mathcal{O}(1)$ be the cost of swapping the counters in the same row.

Iterate over each column. Let us consider that up to column $i-1$, we are done. Now we are at column $i$, there will be three counters, if they are of different colors then we are done, else fix one counter ( say white ) and scan other two rows to get two different color counters ( red and blue ). Running the previous step for a constant number of times ( six ) will solve the problem. More precisely there will be six possibilities in each column (123,132,.....,321), so I will try each of those.

The runtime of the above algorithm will be $\mathcal{O}(n^3)$ as there are $n$ columns and time spent on each column is $\mathcal{O}(n^2)$.

Question: Is it possible to solve the above-described problem linear time $\mathcal{O}(n)$ time as input here has size $\mathcal{O}(n)$? I am not even able to come up with an algorithm faster than $\mathcal{O}(n^3)$ time.

I have taken this question from the book titled Algorithmic Puzzles ( problem 46 )


texts: Since we need space for recursive calls, is the space complexity of the recursive factorial is n?

texts:
As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met:

In-place partitioning is used. This unstable partition requires O(1)
space.
After partitioning, the partition with the fewest elements is
(recursively) sorted first, requiring at most O(log n) space. Then
the other partition is sorted using tail recursion or iteration,
which doesn't add to the call stack. This idea, as discussed above,
was described by R. Sedgewick, and keeps the stack depth bounded by
O(log n).

Now please consider the following method computing the factorial of n recursively:

private static int fact(int n) {
    if (n == 1) {
        return n;
    }
    return n * fact(n - 1);
}

There is no tail recursion. Does it mean that we need O(n) extra space for the call stack?


texts: Continuous Mutual Correction from Multiple Sensors

texts:
I'm stumped on what exactly to search for; so here is a non-scientists description of the topic.

I've got multiple sensors of different types that are measuring the same physical value in different ways. The sensors are all subject to significant error or temporary unavailability, but in greatly different ways. I want to develop code that can use all available sensor data by maintaining slowly changing corrections for each sensor based on the other.

I would love guidance on what exactly to look for to begin a literature search on the topic. Thanks.

Notes based on comments:

A silly example would be collection sampled data on an instrumented automobile's scalar velocity from:

wheel rotation frequency sensor
pitot type anemometer
tri-cup anemometer
MEMS accelerometer
GPS

The physical value being measured, the signal, is not periodic or in any way predictable. It ranges from 0.0 to Max, where max is greater than zero and noninfinite. It is relatively easy to define reasonable limits for max_value, max_delta_value and so on be observation and calculation from simplified Newtonian models.
At least one sensor is subject to calibration/bias drift continuously. This should be at least 4 orders of magnitude below reported value, but in nonnegligible.
At least one sensor is unbiased, calibrated and provides confidence range data along with sample data. Per sample error can be as much as 2 orders of magnitude greater than sample value.
All sensors use wireless communications of data, so all samples are not reported. No error in measurement is introduced in transmission.


texts: Find minimum distance match in sub-linear time in a data base

texts:
The title seems a little vague. So let me explain the question in detail.

Suppose you have a data base. Each record in the data base is $<\mathbf{x},data>$, where $\mathbf{x}$ is an $n$-dimensional index vector.

A query is also an $n$-dimensional vector $\mathbf{y}$. So given the query $\mathbf{y}$, the data base will return the record $i$ such that $\mathbf{x}_i$ and $\mathbf{y}$ have minimum distance. (It can be any distance. But let's focus on Euclidean distance here).

The trivial solution is to scan every record in the data base and compute the distance. This will introduce linear complexity with regard to the number of total records in the data base.

So is there any sub-linear algorithms to solve this problem (approximately)?
For example, if the dimension $n=1$, we can organize the index in data structure such as binary search tree. But for dimension $n>1$, can we also organize the index into some special data structure?

Thanks for you time.


texts:
Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$.

It's well known fact in Space Complexity, but how to show it explicitly?


texts: Are two CCS processes equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas?

texts:
I was skimming this recent paper and I was struck by the following statement:

  two processes are equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas

I have trouble believing it.

I reason that:

weak bisimilarity does not account for tau-transitions and therefore is oblivious to the possibility of livelocks.
I believe the possibility of a livelock can be represented in HML,

and, therefore, a counterexample can be constructed.

Consider these processes:

One = lol.One;
A = lol.omg.A + zomg.A;
B = 'omg.B + 'zomg.B;
Two = (A | B) \ {omg, zomg};

Consider, furthermore, the HML formula

Livelock = max(X. <tau>X);

I believe that this formula is satisfied only by Two, which nevertheless is weakly bisimiliar to One.

I have tried to use the Edinburgh Concurrency Workbench to confirm my reasoning:

agent One = lol.One;
agent A = lol.omg.A + zomg.A;
agent B = 'omg.B + 'zomg.B;
agent Two = (A | B) \ {omg, zomg};
prop Livelock = max(X. <tau>X);
******
echo "Is One strongly bisimilar to Two?";
strongeq(One, Two); ********************* outputs "false"
echo "Is One weakly bisimilar to Two?";
eq(One, Two);       ********************* outputs "true"
echo "Is it the case that One |= Livelock?";
checkprop(One,Livelock);  *************** outputs "false"
echo "Is it the case Two |= Livelock?";
checkprop(Two,Livelock);  *************** outputs "true"

So, is it the case that two processes are equivalent with respect to weak bisimilarity if and only if they satisfy exactly the same set of HML formulas?

If so, why is this true, and what's the flaw in the counterexample, above?
If not, what did the authors mean or what sort of context am I missing? (Or was it a typo?)


texts: can a machine generate truly random numbers?

texts: I know that for most programs pseudo-random numbers are sufficient, but there are ways that machines can generate truly random numbers! There are devices that generate unpredictable processes. However, they tend to be biased somehow. So, is it possible to make devices that can generate unpredictable processes and also unbiased (truly random)? (Please note that I am not asking whether true randomness can be achieved by composing PRNG)


texts: Is this an LL(1) grammar? How to solve First - Follow conflict?

texts:
im trying to check if this grammar is LL(1).

S -> L = R
L -> * L | id
R -> L | R + R | num

As you can see there is a Left recursion on R production. So i remove that and what i get is:

S -> L = R
L -> * L | id
R -> L R' | num R'
R' -> + R R' | ε

Now the problem that i have is that First and Follow set of R' rule have a common non-terminal ("+") and also FIRST(R) and FOLLOW(R') has a common non-terminal.
So i wonder how to create the parsing table if there's this conflict. My question is: is there a way to solve this problem or simply this isn't an LL(1) grammar?

Thanks.


texts: Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$

texts:
The language was $L =\{a^n b^{n+1} : n\geq0 \}$.

This is my attempt:
I believed $L$ can also be expressed as:
$L =\{a^n b^{n}b : n\geq0 \}$
This implies that the number of $b$'s is always greater than the number of $a$'s. Thus, the complement is
$L' =\{w: w\in\{a,b\}^*: n_a(w)>n_b(w)\}$ or $L' =\{w: w\in\{a,b\}^*: n_a(w)\geq n_b(w)\}$.


texts: Smallest length such that all substrings of that length contain at least 1 common character

texts:
Given a string, I have to return the smallest possible value of $k$ such that all of its sub-strings of length $k$ have at least one common character. Each sub-string must have the same common character.

Examples:

y d c b f

Answer = $3$ (common character is 'c')

n n n n n n n n n

Answer = $1$ (common character is 'n')

y e y d y e y

Answer = $2$ (common character is 'y')

The only solution I have thought of till now goes like this:

Find all sub-strings of length $x$ from $1$ through $n-1$ (where $n$ is the length of the given string).
Compare the sub-string for common characters (and store which characters are common). As soon as I come across a pair of the sub-string of length $x$ which doesn't have any common characters I move to the next value of $x$. If no such $x$ is found, return $n$.

Is a more efficient solution possible?


texts: Constructing a deterministic one way infinite single tape Turing machine

texts:
If I have an input string that is only composed of $a$'s and $b$'s, how can I construct a Turing machine that only accepts strings where the number of $b$'s divides the number of $a$'s?

For example:

$aaaabb$ is accepted

$baaab$ is rejected