texts: center star alignment induces optimal alignments on pairs with the center string?

texts:
I'm trying to follow the center star algorithm error analysis - section 6.5.3. They claim that for the center string $S_1$ the distance induced by the algorithm $d(1, j)$ is always equal the optimal alignment $D(S_1, S_j)$ since $\delta(-,-) = 0$.

I don't understand this argument. For each j, the algorithm aligns a totally different string $S'_1$ with many surplus gaps from the previous iterations.

How come we arrive to the same exact cost? Can't it be that for the new string $S'_1$ there's a very cheap alignment that would have costed lots of extra gaps if it was $S_1$?


texts:
From my understanding(correct me if I am wrong) when I read data from RAM memory it is copied into processor cache and than it is copied into register to be used by the processor. When I create data (like variable) is it first created in register and than copied to cache and from cache to RAM or is it directly created in RAM?

Additional question:Does stack and heap exist only in RAM or do they exist in processor cache as well?


texts: Efficiently deciding whether TM accepts all inputs in at most $k$ steps

texts:
I want to decide if a deterministic TM $A=(Q, \varGamma, \delta, q_s, q_h)$ halts on every input in at most $k$ steps. If the TM $A$ stops after $k$ steps, then  the positions $A$ can reach are limited by $2k$. Thus I can create a NFA with state set:

$$ Q' \subseteq \{1,\dots,k\} \times Q \times \varGamma^{2k} \times \varGamma \times \{-k,\dots,k\} $$

which keeps track of all necessary information to simulate $M$ with a suitable transition function. This construction is exponential in $k$ and I wonder if this can be avoided by using a PDA. Does the stack give ma enough information to avoid this exponentail blow up?


texts: What do these Big-O notations mean in context of comparison

texts:
What do the following mean, in the context of greater than, or smaller than?
$$
O(n \log n) > O(n)
$$
$$
O(nlogn) < O(n^2)
$$


texts:
I have been a computer nerd for many many years. I can program in quite a few languages, and I can even build them.  I sat down with a buddy the other day and asked how a computer actually takes electricity and does something with it, and we just couldnt figure it out, and Google wasn't much help either.

I mean, how does a computer take a constant flow of electricity and turn it into 1's and 0's and then actually do something with those 1's and 0's like turn a light on for 15 seconds?

I understand gates (AND, OR, NOR, NAND, NOT) and a little about diodes, resistors and transistors, but I figured this would be the perfect place to have it explained in true laymens terms!

Can anybody point me in the right direction or give me a brief explanation?


texts:
I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it.
Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{V},\mathcal{E})$ where $\mathcal{V}$ is set of vertices and $\mathcal{E}$ is the set of edges where each edge $(i,j) \in \mathcal{E}$ assigned a positive weight $w_{ij}$. Matching is the subset of edges such that no two edges share a vertex. The maximum cardinality weighted matching is the matching that maximizes the total weight of edges in the subset of matching that maximizes the total number of edges chosen in the matching
I searched but there is always maximum weighted matching which means the matching has maximum weight but may not has maximum cardinality all the time. I appreciate it if you can recommend a reference for the maximum cardinality weighted matching. I want the matching that maximizes the cardinality first then the weigt of the matching.
For example, 1 --- 2 --- 3 --- 4
The weight between 1 and 2 is 1.
The weight between 2 and 3 is 10.
The weight between 3 and 4 is 1.
The maximum cardinality weighted matching I want is 1--2 and 3--4.
The maximum weighted matching outputs 3--4


texts: Complexity of a naive algorithm for finding the longest Fibonacci substring

texts:
Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows:

$$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\
\text{a} &\mbox{if } k = 1 \\
F(k-1) \star F(k-2) &\mbox{else} \end{cases} $$

with $\star$ denoting string concatenation.

Thus we'll have:

$F(0) = \text{b}$
$F(1) = \text{a}$
$F(2) = F(1) \star F(0) = \text{ab}$
$F(3) = F(2) \star F(1) = \text{aba}$
$F(4) = F(3) \star F(2) = \text{abaab}$
...

Given a string $S$ formed by $n$ symbols, we define a Fibonacci substring as any substring of $S$ which is also a Fibonacci string for a suitable choice of $\text{a}$ and $\text{b}$.

The problem

Given $S$, we want to find its longest Fibonacci substring.

A trivial algorithm

For each position $i$ of the string $S$, suppose that $F(2)$ starts there (it's enough to check that the $i$-th and $(i+1)$-th symbols are distinct). If that's the case, check if it can be extended to $F(3)$, then $F(4)$, and so on. After that, start again from the position $i+1$. Repeat until you reach the position $n$.

We must look at each symbol at least once, so it's $\Omega(n)$. There are only two for loops involved, so we can furthermore say that it's $O(n^2)$.

However (somewhat unsurprisingly) this naive algorithm performs much better than usual quadratic algorithms (if it does a lot of work on the $i$-th position, it won't do a lot of work in the next positions).

How can I use Fibonacci properties to find tighter bounds for the execution time of this algorithm?


texts: What languages does a (1-way) quantum finite state automata recognize?

texts:
Sorry if this is well known, but most of the research is paywalled.

So far I know that it is a subset of the regular languages, but I cannot seem to find any (available) research which pins it down.

Thanks!


texts: Finding number of smaller elements for each element in an array efficiently

texts:
I am stuck on this problem:

  Given an array $A$ of the first $n$ natural numbers randomly permuted, an array $B$ is
  constructed, such that
  $B(k)$ is the number of elements from $A(1)$ to $A(k-1)$ which are smaller than $A(k)$.

  i) Given $A$ can you find $B$ in $O(n)$ time?
  ii) Given $B$ can you find $A$ in $O(n)$ time?

Here, $B(1) = 0$. For a concrete example:
$$\begin{vmatrix}
  A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\
  B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\
\end{vmatrix}$$

Can anyone help me? Thanks.


texts: Good way to describe co-RE (co-recursively enumerable)?

texts:
I get that R is a set of languages that are decidable by a Turing Machines

And that RE is a set of languages that a each language can be recognized by a TM, that is the machine will halt when given a word from that language and loop otherwise.

But I can't wrap my head around co-RE.  Is there a good way to describe it? A good example to convey what it really means?


texts:
Beginner in DFA related studies, was trying to figure out how to create a DFA with {a,b,c}, that can recognize a * b * c *.

Appreciate the help.


texts: Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$?

texts:
I have encountered the following question in my homework assignment in Data Structures course:
"Does a function $f$ exists such that: $f(n-k) \ne \Theta(f(n))$ for some constant $k\geq1$ ?"
I think no such function $f$ exists, but I do not know how to prove it (or give a counter-example if one exists).


texts: A key-value datastructure with fast (on average) member move and nearest neighbors search?

texts: I have a 3 dimensional float key search space (say a simulation world). I want to keep my values (ints, agent ids) in a data structure that can perform nearest neighbors search (with search for N neighbors in a range surrounding a given key) as fast as possible in terms of search algorithmic complexity (on average). Also I need a fast (on average) remove-insert or key update mechanism in that datastructure. I wonder what is such structure?


texts: Reasoning approaches for implementing a Knowledge-based System?

texts: What are the major approaches in implementing a Knowledge-based System (KBS)? Approaches used to take decisions in a KBS that I have come across so far are the case-based and rule-based reasoning approaches. I would like know about other approaches and implementations. I would appreciate any recommendation about helpful texts or websites or other resources.


texts: recognize strings of 1's and 0's which are multiples of 3

texts:
Construct a minimized Deterministic Finite Automaton that recognizes strings of 1's and 0's that are multiples of 3.

This was one of the questions asked in my cycle test.

What would be a correct interpretation to this question?

Strings having a number of 0's and 1's that are multiple of 3, e.g.000111, 011010
Strings of 0's and 1's which in binary notation is a multiple of 3, e.g. 11, 110
Or any other radix notation, taking 0's and 1's, and checking if they are multiples of 3


texts: For a school project, I'm planning to compare Spiking Neural Networks (SNNs) and Deep Learning recurrent neural networks, such as Long Short Term Memory (LSTMs) networks in learning a time-series. I would like to show some case where SNNs surpass LSTMs. Consequently, what are the limitations of LSTMs? Are they robust to noise? Do they require a lot of training data?


texts: Parallel Thread Processing Variable Question

texts:
if there is a better stack exchange suited for this question please inform me.

say you have a thread that is constantly checking the state of a variable in 2 ms intervals

volatile int var = 0;
while(true){
if(var == 1)
   break;
Sleep(2);
}

you have another thread thats overwriting this variable to 1 in an external process/thread but setting it back to 0 once its complete with its process and this process takes 1 ms.

if this second thread never gets interrupted in anyway (like with an APC) will the first thread ever catch the second thread modifying this variable?

if the cpu only has 1 thread this would be impossible, but on a processor with multiple parallel threads is this likely?


texts: I understand that ECC checks for errors and corrects them automatically without the knowledge of the operating system or user. I don't understand however why servers often use ECC memory?


texts: Perfect random number generation using normal numbers

texts:
This paper describes a computable normal number. One property of normal numbers is that, written in binary, the $i^{th}$ bit is equally likely to be 0 or 1 (in the sense that as $n$ gets large, the number of 1-bits and 0-bits before the $n^{th}$ bit are about the same). Doesn't this mean that the algorithm that computes bits of this normal number is a perfect random number generator? I thought deterministic random number generation is inherently pseudo-random, by information-theoretic limits or whatever. (Also: can anyone figure out the complexity of computing the $i^{th}$ bit using their method? The math in that paper is beyond me).

Finally: many easily-computable irrationals, like $\sqrt{2}$ and $\pi$, are very strongly conjectured to be normal. If that were proven, wouldn't that provide a poly-time perfect random number generator? Which is definitely impossible? What am I missing here?


texts: What is the complexity of this algorithm for sparse matrices?

texts:
I am reading a paper on sparse matrices and there is an algorithm for sparse lower triangular systems. In the below pseudo-code $l$ is a sparse matrix and $x,b$ are sparse vectors.

x=b
for j=0 to n-1 do
    if x[j] != 0
        for i=j+1 to n-1 do
            if l[i][j] != 0
                ~5 operations.

The paper claims that this algorithm is $\mathcal{O}(n+|b|+f)$, where $|b|$ is the number of non-zero entries in $b$ and $f$ is the number of floating point operations carried out.

I do not understand why this algorithm is not $\mathcal{O}(n|b|f)$.

Reference:
Chapter 3 - Section 2 of
https://epubs.siam.org/doi/book/10.1137/1.9780898718881

Some context on sparse matrices:
Sparse matrices usually appear when solving problems using numerical schemes such as the finite element method. These matrices usually have a very small number of non-zero entries per row. For instance, a $n$-by-$n$ matrix might only have $\mathcal{O}(1)$ entries per row. The situation might not be as good as this in the algorithm above (there is no mention of a definition of sparse matrices in the book, as far as I can see.)


texts:
I have found that naive Bayesian classifier performs much better than classification using mixture of multivariate Gaussians.

Here is the problem: I have a set of objects with attached features (10 of them), part of the set is the training set with pre-assigned labels, another part needs to be classified into 3 classes.

I have tested two methods:
(a) approximating distribution of each feature within class as a 1-dimensional Gaussian distribution, calculating probabilities from each feature separately to belong to each class, using Bayes theorem to calculate final (posterior) probability and making a classification on the basis of maximum probability;
(b) approximating distribution of feature vectors within class by 10-dimensional Gaussian distribution and making classification again on the basis of maximum probability.

I have found that method (a) performs much better. What may be the reason for this? I expected that they would perform at least equally.
Does it have anything to do with the topology of the distribution of the features in the training set?


texts: Space complexity for finding the minimum number outside the list of numbers

texts:
We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$.

We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$.

  What is the space complexity of this problem ? (The space to store the input, $L$, does not count.) What if the input $L$ is in a stream which you can only read from left to right for at most constant number of passes ?

The obvious way to solve this is just to copy $L$ into the working memory and then (in-place) sort $L$, and find $x$ in the obvious way. This algorithm uses space of size $n$.

Can we do better ?


texts: Client-Server Architecture /State Model and Process Mode

texts: how i can define what are Client-Server Architecture for a website that suggestion courses for students after  students insert the history of courses. The language will be PHP,mysql and HTML. In this case ,server side is the PHP and client side will be the HTML . Is that how i can define the Architecture? If no , what are the process to follow to defined it ? Also,what are the State Model and Process Mode?


texts: Partitioning a graph into subgraphs with overlapping nodes

texts:
I'd like to partition a graph into subgraphs with overlapping nodes.
To do a simple partition into two, I could use kernighan_lin_bisection algorithm available in networkx package.
import networkx as nx
from networkx.algorithms.community.kernighan_lin import kernighan_lin_bisection

if __name__ == '__main__':
     G = nx.gnm_random_graph(n=30, m=55, seed=1)
     A, B = kernighan_lin_bisection(G)

For creating more than two partitions, it is mentioned here, https://stackoverflow.com/questions/63357626/networkx-kernighan-lin-multipartition, that metis can be used. However, I came across an old post that mentions partitioning with overlapping nodes is not supported in metis. I would like to ask for suggestions on references to algorithms/packages that support
partitioning with overlaps.
EDIT:
I'd like to partition into subgraphs with >= 4 overlapping vertices.
e.g. in the subgraphs presented here . i.e.

for any cluster C1 there must be a cluster C2 such that |C1∩C2|≥4

The number of overlap nodes (overlap size) is 3 and 1. But I want the overlap size to be >=4 overlap nodes.
EDIT 2:

For example, why not simply pick another pure-yellow vertex randomly
and add that to the green set, so that yellow and green overlap by
exactly 4? And why not pick the remaining 3 pure-yellow vertices and
add them to the blue set, so that yellow and blue overlap by exactly
4?

Yes, I could do this. I'm trying the óverlapping communities algorithms available in CDLIB to do the same.
 import networkx as nx
 from cdlib import algorithms

if __name__ == '__main__':

    g = nx.karate_club_graph()

    coms = algorithms.angel(g, threshold=4, min_community_size=10)
    print(coms.method_name)
    print(coms.method_parameters)  # Clustering parameters)
    print(coms.communities)
    print(coms.overlap)
    print(coms.node_coverage)

Output:
ANGEL
{'threshold': 4, 'min_community_size': 10}
[[14, 15, 18, 20, 22, 23, 27, 29, 30, 31, 32, 8], [1, 12, 13, 17, 19, 2, 21, 3, 7, 8], [14, 15, 18, 2, 20, 22, 30, 31, 33, 8]]
True
0.6470588235294118

From the communities returned, I understand 1 and 3 have an overlap of 4 nodes but 2 and 3 or 1 and 3 don't have an overlap size of 4 nodes.
It is not clear to me how the overlap threshold (4 overlaps) has to be specified
here algorithms. angel(g, threshold=4, min_community_size=10). Since it is mentioned in the comment below that the "overlap is upper bounded" , I tried setting threshold=4 here. However, from the documentation available for angel

:param threshold: merging threshold in [0,1].

I am not sure how to translate the 4 overlaps to the value that has to be set between the bounds [0, 1].
Could someone please clarify? If there are suggestions on the other overlapping communities algorithms that I could try from CDLIB, I'd be happy to try. I also had a look at the percolation methods implemented in the kclique algorithm of CDLIB. Unfortunately, I am not sure how to specify the overlap threshold here.
I'm really sorry for not being clear, I'm new to this field and I am learning from here.


texts: Why is OPT at least the most valuable item for FPTAS Knapsack?

texts:
In all the presentations of an FPTAS for Knapsack I've seen, it is asserted that the optimal value is at always at least the value of the maximum-valued item (e.g. here, slide 12, where we have $V \leq V^*$, where $V$ is the value of the maximum valued item and $V^*$ is the optimal solution.).

Why is that? I mean, we could have a knaspack problem with two items, one with value $10000$ and size $10000$, and one with value $1$ and size $1$, and for a knapsack capacity of $1$ clearly the optimal solution is $1$, but $V = 10000$, and $V^* < V$.


texts: Why most purely functional red-black trees are left-leaning?

texts:
Is there any particular reason for picking a left-leaning red-black tree over a regular red-black tree when trying to do a purely functional implementation?

I've not researched very deeply into this subject matter but I see that Okasaki's implementation is left-leaning, and just as Yamamoto's.

Left-leaning red-black trees are considered to be harmful, so I'd like to know the reason behind this, if any.


texts: Computing the intersection of two NPDA where it is possible

texts:
Apropois to Raphael's suggestion on Intersection of two NPDAs:

Let $A_1$ and $A_2$ NPDA for context-free languages $L_1$ and $L_2$, respectively. Assuming that we know that $L = L_1 \cap L_2$ is context-free, can we (effectively) construct NPDA $A$ for $L$?

Any type of algorithm would be acceptable, but the more practical the better.


texts: Are there any programming languages which support user defined control structures?

texts:
For instance, the user would define a for each loop in their code as having a structure something like:

foreach([variable1] : [variable2]){
    [statements]
}

(when [ ] are placeholders) and then the pieces would be used like this:

for(i = 0; i < variable2.length; i++){
    variable1 = variable2[i];
    statements
}

and then in the rest of the program, the user could use a for each loop with that format:

total = 0;
foreach(num : numbers){
   total += num;
}

I hope that example makes sense. To be clear, I am saying that in this hypothetical language a for each loop does not exist, but the user can define one which will, for then on, work exactly the same as any other structure. Are there any languages which allow this?


texts:
How to show that the following language is undecidable using reduction on the halting problem?
$L: = \{w \in \{0,1\}^* |$ TM $M$ with $w = \langle M \rangle$ does not accept any input $\}$
When TM doesn't accept any input, does it mean that the Turing machine halts or it just rejects any words?
And how to show that this language is not semi-decidable? I think to do it with a complement but I don't know how to start. Should I use the Rice's theorem in this proof?


texts: In which environment we use NFA(Non Deterministic Finite Automata)?

texts: We have two types of Automata. One is NFA and second is DFA. These are little bit different but thing is that in which environment we prefer NFA over the DFA?


texts: Why the height complexity of a data structure, generally expressed in terms of $\log n$, do not contain a ceiling or floor ?


texts: $NP = PSPACE$ and what that would mean about $PH$

texts:
So, a paper showed up on arXiv: https://arxiv.org/abs/1609.09562

The above states in the abstract that it contains a proof that $NP = PSPACE$

Since $NP \subseteq PH \subseteq PSPACE$, that would mean that $PH$ collapses, right? Well, the paper makes no mention of this and this seems pretty significant because "if $\mathcal{P}$ were true then PH would collapse to the second level" comes up for quite many propositions $\mathcal{P}$. I am afraid that I am missing something here. Does this paper's result imply that that $PH$ collapses to the first level?


texts:
Hello Computer Science stackexchange, I am trying to make an object tracking system. I have a module for object detections which feeds into a object tracking module. However, due to objects sometimes not getting detected and a greedy tracking algorithm the output of these two modules end up with 68 objects where the ground truth is only 23 and  an illustration of this can be seen in figure 1.

First I tried to make a greedy algorithm which simply took the closest start frame to an ID's last frame. This gave some problems because sometimes two IDs would have the same last frame as their closest, which meant the first ID would get the association. I have also tried to introduce euclidean distance as a weight parameter, but the problem is still that I want to find the global best matches (I don't know the terminology) which can output 23 track ids instead of 68.
So my question is, what field of algorithms is this problem a part of and what do I search?
And how do I solve this problem?
Thanks in advance and sorry if the problem isn't defined well enough.
Update:
As previously mentioned the ID takes the closest first frame to the ID's last frame, an example of this can be seen in figure 2.  Here it can be seen that ID 0 has 21 possible IDs to associate with, where it will take either ID 48, 49, 50 or 51 depending on how small the euclidean distance is. So imagine that ID 0 has the position [100,100] and the other IDs has (with distances to ID 0):
ID 48: [135,153] (63.51 pixels)
ID 49: [75, 50] (55.90 pixels)
ID 50: [531, 56] (433.24 pixels)
ID 51:  [352, 731] (679.46 pixels)
Here it would take ID 49 as it is the closest in distance.


texts: Is showing two different derivations enough to prove that a CFG is ambiguous?

texts:
I'm wondering, is showing two different ways to derive the same word enough proof to show that a context-free grammar is ambiguous?

For example:

O = start symbol
Non-terminal = {O}
Terminal = {r, s}
Productions =
     O -> r
     O -> Or
     O -> sOO
     O -> OOs
     O -> OsO

There are two different derivations for the word rsrrs:

O -> OOs -> OsOOs -> rsOOs -> rsrOs -> rsrrs
O -> OsO -> rsO -> rsOOs -> rsrOs -> rsrrs


texts: Can map-reduce speed up the count-min-sketch algorithm?

texts:
Is there any possibility of improvement in the result of count-min-sketch algorithm if we will use Map Reduce approach?
Improvement in performance can be in terms of accuracy, time complexity or the work done needed.


texts:
I study graph theory on my own using Diestel's Graph Theory book (with Algorithmic graph theory in mind). I don't understand what local property, global property, locality mean given a graph $G$.

For example, on the page 5 it says

  The average degree quantifies globally what is measured locally by the
  vertex degrees: the number of edges of $G$ per vertex. Sometimes it will
  be convenient to express this ratio directly, as $\varepsilon(G) := |E|/|V|$.

In particular, I found the following phrases including the word local...

local information (pg. 46)
maximum local density (pg. 61)
the above local structures (pg. 101)
locally looks like a tree (pg. 110)
there is a local reason for it (pg. 110)
we are looking for local implications of global assumptions (pg. 181).

and many more...

Could someone explain (possibly with examples) what these local and global mean in the context of the graph theory?


texts: How is the size of a register related to the size of primary memory?

texts: I understand that registers are temporary storage compartments which (usually) hold 8 bits, or 1 byte, of information at a time. This information is sent from a register into the Central Processing Unit (CPU) where, with the help of a control unit and an ALU, the byte is decoded and sent back to occupy the space of another register. This data is finally transferred from the register to the storage and into primary memory, such as ROM or RAM, but I am unclear whether this is the case. Could someone please help elaborate if I have missed anything crucial in the process and whether the outcome should be as such? In my mind, that is how a processor would handle data as registers would be used to fill up the free space of primary memory; Input > Register > CPU > Register > Output / Store


texts: Where should I start to understand how computers work?

texts:
I am interested in how computers work but I have no idea how the concept of 0's and 1's converts to making possible for people to control a computer by programming. I would like to understand from very fundamental levels of computer and continue studying more in depth until I am satisfied. Where should I start? Is there a name for this topic? What books should I read?

**Edit: This was my first post and I think I got a lot of good suggestions on where to start. I will be looking up all the answers posted here. Thanks a lot for everyone who answered on this post.


texts: Runtime of a programm that takes the square of a root

texts:
Assume $u(n)$ calculates $n^2$ in $n$ steps, thus is in $O(n)$, and $v(n)$ calculates the square root of $n$ in $\sqrt n$ steps, thus is in $O(\sqrt n)$.

What is the runtime of the program u(v(n))?

The argumentation in my solution is:

"We calculate the square root first, then we take it's square. $\sqrt n + \sqrt n = 2\sqrt n \rightarrow O(\sqrt n).$"

I don't understand that. Wouldn't it be actually $n + \sqrt n$?


texts: Given a large set 2d points, choose 4 of them to make a polygon with the biggest area

texts:
I need an algorithm that will find four points.

These four points form the vertices of a polygon

Which four points make a polygon with the most area?

Sample data: http://jmp.sh/v/8lAytDc00UrOa17Z6Oo6


texts: Turing Machines and Algorithm for Language Acceptance

texts: Is there an algorithm to decide if any two Turing machines accept the same language?  I can't find a definite answer to this.  My guess is that there isn't, because then we would be able to decide if a Turing machine accepts a given language and halts, which is undecidable.  Is there a better explanation for why this is or is not the case?


texts: Theoretical minimum number of registers for a modern computer?

texts:
I took a course on compilers in my undergraduate studies in which we wrote a compiler that compiles source programs in a toy Java-like language to a toy assembly language (for which we had an interpreter). In the project we made some assumptions about the target machine closely related to "real" native executables, including:

a run-time stack, tracked by a dedicated stack pointer ("SP") register
a heap for dynamic object allocation, tracked by a dedicated heap pointer ("HP") register
a dedicated program counter register ("PC")
the target machine has 16 registers
operations on data (as opposed to, e.g., jumps) are register-to-register operations

When we got to the unit on using register allocation as an optimization, it made me wonder: What is the theoretical minimum number of registers for such a machine? You can see by our assumptions that we made use of five registers (SP, HP, PC, plus two for use as storage for binary operations) in our compiler. While optimizations like register allocation certainly can make use of more registers, is there a way to get by with fewer while still retaining structures like the stack and heap? I suppose with register addressing (register-to-register operations) we need at least two registers, but do we need more than two?


texts:
Based on: J. P. Carvalho, "On the Semantics and the Use of Fuzzy Cognitive Maps in Social Sciences" (WCCI, 2010 -- PDF) and Richard Dagan's web page Cognitive Mapping.

A cognitive map consists of nodes representing concepts and ties indicating relationship between the concepts.
In Carvalho section IV, the semantics is used in perspective of the presented model. Dagan's definition of semantic map is that it is a tree like structure branching from a main concept.

Also, the answer Are semantic networks ontologies? further adds to my confusion as to what is the significant different between cognitive map where nodes are concepts and semantic map where also the nodes are concepts.

I am unable to find significant difference between concept map and semantic map. Can somebody please explain in simple language? Thank you


texts: Compressing sparse tries using multidimensional matrices

texts:
Wikipedia's trie article says:

  [Compressing the trie representation by merging the common branches] is also typically used in the implementation of the various fast lookup tables needed to retrieve Unicode character properties (for example to represent case mapping tables, or lookup tables containing the combination of base and combining characters needed to support Unicode normalization). For such application, the representation is similar to transforming a very large unidimensional sparse table into a multidimensional matrix, and then using the coordinates in the hyper-matrix as the string key of an uncompressed trie. The compression will then consist of detecting and merging the common columns within the hyper-matrix to compress the last dimension in the key; each dimension of the hypermatrix stores the start position within a storage vector of the next dimension for each coordinate value, and the resulting vector is itself compressible when it is also sparse, so each dimension (associated to a layer level in the trie) is compressed separately.

This is all uncited! It says it is similar to "transforming a very large unidimensional sparse table into a multidimensional matrix". What is such a transformation, and how such a matrix is helpful to implementing a compressed trie? I've been unable to find anything. Obviously, not understanding this, I'm at a loss for how using the coordinates within that allow one to implement a trie!


texts:
Disclaimer: I am a biologist, so sorry for (perhaps) basic question phrased in such crude terms.
I am not sure if I should ask this question here or on DS/SC, but CS
is the largest of three, so here goes. (After I posted, it occurred to me that Cross-Validated might be the better place for it, but alas).

Imagine there is an agent, who makes binary decisions. And an environment, which, for each of the agent's decisions ("trials"), either rewards the agent or not. The criteria for rewarding the agent's decisions are not simple. In general criteria are random, but they have limitation, for example, environment never rewards more than 3 times for the same decision and never alternates rewarded decision more than 4 times in a row.
Sequence of criteria might look something like this then
0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 0 1 0 ...

but never
0 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 ...

because reward criterion cannot repeat more than 3 times.
In these conditions it is quite easy to formulate the strategy ideal observer should undertake to maximize the reward. Something along the lines of

decide randomly
if you detect that criteria repeated 3 times -- decide opposite than last criterion
if you detect that criteria alternated 4 times, decide according to the last criterion

Now, the difficult part. Now the criterion on each trial depends not only on the history of previous criteria, but also on the history of agent's decisions, e.g. if agent alternates on more than 8 out of the last 10 trials, reward same decision as agent made last time (as if to discourage the agent from alternating) and if agent repeated same decision on more than 8 of the the last 10 trials, i.e. he is biased, make criterion opposite of the bias. The priority of history of criteria over history of decisions is specified in advance, so there is never ambiguity.
The sequences of decisions (d) and criteria (c) might now look like this
d: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 0 1 0 1 0 ...
c: 1 0 1 0 0 0 1 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 1 0 ...
                       ↑ here criteria counteract bias in decisions

I do not see any simple way of inventing maximizing strategy for the agent. But I am sure there must be one, and some kind of clever machine learning algorithm should be able to identify it.
My question is not so much about how to solve this problem (although I would be happy if you suggest a solution), but more how these types of problems are called? Where can I read about it? Is there an abstract solution or only simulation can help? In general, how can I, as a biologist, approach this type of problem?


texts: Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?

texts: The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in polynomial time. But is there a proof of whether or not it can be verified in polynomial time assuming P ≠ NP?


texts: How to determine the average of two strings?

texts:
Given two strings $s$ and $t$, is there a way to find a string $a$ such that $d(a,s)=d(a,t)$, where $d$ is the Levenshtein distance?
I am sure that a genetic algorithm would work pretty well but I would prefer an explicit solution.


texts: When proving a problem is NP-C, how do I select another NP-C problem for the transformation?

texts:
I'm taking an algorithms course in which we are discussing proofs that problems are NP-Complete.

Our proofs usually take the form:

Given a problem $\Pi$,
 1. Prove that $\Pi$ is NP.
 2. Select an NP-C problem $\Pi'$.
 3. Find a transformation $\propto$ from $\Pi'$ to $\Pi$.
 4. Prove that $\propto$ is polynomial.
 5. Prove that iff a solution $S$ to $\Pi'$ is correct, then $\propto(S)$ is a solution to $\Pi$.

I have a question about step $2$. When I'm attempting to prove that a problem $\Pi$ is NP-C, how do I go about selecting $\Pi'$? Is there a systematic approach I can use? If not, what is the intuition behind selecting $\Pi'$, and how can I practice and develop that intuition?


texts: acyclic in chord graph and elimination ordering in chordal bipartite graph

texts:
From wiki, "a chord graph is one in which all cycles of four or more has a chord." My first question is if a graph is acyclic, i.e., there is no cycle in the graph, can it be called as a chord graph?

Another question is about elimination ordering in chordal bipartite graph. It is well known that in a chordal bipartite graph, given $x_1<x_2$, $y_1<y_2$ and $(x_1,y_1),(x_1,y_2),(x_2,y_1)\in E$, then $(x_2,y_2)\in E$. But given a chordal graph $G$, if we add in $G$ vertices $x_1,x_2,y_1,y_2$ where $x_1<x_2$, $y_1<y_2$ and edges $(x_1,y_1),(x_1,y_2),(x_2,y_1)$, is $G$ still a chordal bipartite graph?


texts: Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?

texts:
If have a cellular automaton, can I see the state of the board after something like $10^{{10}^{10}}$ time steps? For trivial cases, this is possible - for example, a cellular automaton where the state of the board is known to repeat after some finite period.

But are there any cellular automata (or perhaps even similar computational structures) that display chaotic behavior but can also be very quickly evaluated to extreme time steps into the future?


texts: Which algorithms are useful in this case?

texts:
Suppose you are given a 3-D sphere of known radius. Input of n points is provided, which have been selected randomly on the surface of the sphere. Each input field consists of a polar angle theta (Θ) and azimuthal angle phi, Φ (in spherical coordinate system).
Now I need to find a new point (n+1) such that this point has average maximum distance from every other point present of the surface. If I take the sum of all the distances from this new point (n+1) to the previous points. Then the average must be the maximum.
The output must be provided in the spherical coordinate system. Also the distance between two points is over the surface, not straight lines going through the sphere.
How can this problem be solved? Which algorithms are useful for this problem and what are their running time complexities?


texts: Pumping Lemma for Regular Languages with 3 variables (a^nb^mc^m)

texts:
I've been trying to understand the pumping lemma, and how to apply it to a language such as a^nb^mc^m where n >= 0 and m >= 0. The pumping lemma states that:

For any regular language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and

(1) |uv| ≤ n

(2) |v| ≥ 1

(3) for all i ≥ 0: uviw ∈ L

It states that there exists some n such that this holds true. In the language a^nb^mc^m if I were to replace m with the pumping length, and choose a pumping length, for example 3, such that a^nb^pc^p I could get the string:

aabbbccc

If I chose:

x = aa

y = b

z = bbccc

then xy or aab <= p and y > 0. Then if I pump up y by 2 for example, I would get the string aabbbbccc. But this is not in the language as there are more b's then c's. The problem i'm having is if I instead split my string as such:

x = a

y = a

z = bbbccc

then xy or aa <= p and y > 0. If I pump this string by 2 for example, I would get the string aaabbbccc, which is in the language. So in this case the pumping lemma is passed.

So my question is, for the pumping lemma does my second example passing mean that the language a^nb^mc^m passes the pumping lemma, or does the fact that I found a case where splitting x and y with this pumping length makes it false, mean that the language does not pass the pumping lemma. And if that is the case then if I had the language:

a^nb^m  where n >=0 and m >=0 and I choose m to be p, and made the pumping length 3 for example, I could end up with the string:

aabbb, where x = a, y = ab, z = bb, which when pumped would produce aababbb which is not in the language, but I know that a^nb^m is a regular language.

Hopefully you can see where my confusion lies. I been researching for a while and I just can't find a clear cut answer on this. Any help would be extremely appreciated.

Thank you.


texts: $O(n \log n)$ algorithm for disjoint segment visibility problem

texts:
Consider we have $n$ disjoint segments and a point $P$ which is not on any segment. I want to find an $O(n \log n)$ algorithm to check which segments are visible from $P$. A segment is visible from $P$ if it has a point which is visible from $P$.

My idea is to use a sweep half-line with one end-point on $P$, sort points clock-wise by degree and start from an end-point on the nearest visible segment (which I don't know how to find), rotate and detect one visible and some possible invisible segments at a time. All I can think of is $O(n^2)$ so far. Can anyone suggest an $O(n \log n)$ algorithm.


texts: Where we Use Dynamic Programming and Greedy Algorithm?

texts:
Can someone tell me where we use Dynamic/Greedy algorithm and how we trace from the question that it will solved by any one of the above?

Thanks


texts: Evaluating Statements Using a Parse Tree

texts:
I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, there can be 3 children e.g.

child 1: multiplicative_expression
child 2: '*'
child 3: cast_expression

I expect to implement a new class for interpreting the parse tree. However, I have no idea how to even traverse the parse tree in order to evaluate the statements. How do I traverse the tree properly in order to interpret all the types of statements? I want to interpret not only multiplicative statements but also if-else statements etc.


texts: Measures and probability in formal language theory

texts:
I am looking for references for the following problem:
I have a very special class of regular languages and my aim is to express (and to justify my conjecture) that this class itself is very small in some way (as a subset of the regular languages) and that the languages contained in this class are rather "bloated".

For the latter point, I could prove that all languages in the class have a large diameter with respect to many common metrics on strings. However, I want to consider the following: Given a language from the class, we know it has a large diameter, but does it also have a large "volume" (that is, measure), or put differently, if I choose randomly a finite word, is there anything meaningful to say about how "probable" it is that the word belongs to the language? Of course, we can lift the problem: Picking a random language, how probable is it to get a language in the class?

Are there any references or standard approaches for looking at classes of (regular) languages from this point of view (or is this considered as generally uninteresting)?


texts: DFA for binary language with constraints on triplets

texts:
I need to create a deterministic finite automata whose language consists of words over $\{0,1\}$ of any length, satisfying the following constraint:

  Among any subsequent 3 numbers, there needs to be exactly two 1s, and exactly one 0.

I've spent a couple hours studying DFAs, but I can only find solutions like the one I need to one of these issues. Meaning that among the 3, there can be at most 1 of something, or there needs to be at least 2 of something. I'm pretty much lost in how I'm supposed to combine these into a single DFA.


texts: Why does paging not have external fragmentation?

texts: I have read that paging does not suffer from external fragmentation as the frames and the pages are all of the equal sizes, but when we store a last level page table in a frame at that time it may not fully occupy the frame. Similarly, if n such page tables are stored, that does not occupy the frames entirely, then there can be a case where all the gaps exceed a page size. Then there should be external fragmentation, right? So why is it said that paging does not have external fragmentation?


texts: Is there a technique for statically checking that a function is only called at a particular rate?

texts: I was reading this article about types, and started wondering how static type checkers could enforce other properties in programs. For example, say I wanted to create a language which would allow checking at compile time that a particular function was only called at most once every 300ms. How would I go about specifying the language to allow that to be enforced? What existing languages try to enforce similar properties?


texts: Are there undecidable properties of non-turing-complete automata?

texts:
Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability).

I would like to get an example (if possible) of an undecidable problem that is defined without using Turing machines explicitly.

Is Turing completeness of a model necessary to support uncomputable problems?


texts: Calculating a polynomial's coefficients from its roots

texts:
Let $P$ be a monic polynomial polynomial given by its roots:
$$P(X) = (X-x_1)\times...\times(X-x_n)$$

What is the minimum asymptotic complexity to compute its expansion of the form:
$$a_nX^n+...+a_0$$

What I have found so far are Vieta's formulas which give an expression of each $a_k$ as a sum over $1\leq i_1 < ... < i_{n-k} \leq n$. This would suggest the complexity of computing the $k$th coefficient is something like ${n-1 \choose n-k-1}={n-1 \choose k}=O(n^k)$, thus making the total complexity bonkers (I guess something like $O(n^n)$).

Yet my teacher's presentation suggests it is a $O(n^2)$, which doesn't match my calculation at all.


texts: Easy proof for context-free languages being closed under cyclic shift

texts:
The cyclic shift  (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this operation, with references to papers from Oshiba and from Maslov. Is there an easy proof of this fact?

For regular languages the closure is discussed in this form as "Prove that regular languages are closed under the cycle operator".


texts: Merge Sort Confusion - Initial Phase Missing?

texts:
Below is the solution to a merge sort exercise - "Use a merge sort to sort the list". I'm confused because I thought that there needed to be an initial phase of breaking the list in to sub-lists, yet here only the "reconstruction" phase is shown.

Am I missing something, or is there a problem with the given solution please?


texts: Find a simple path visiting all marked vertices

texts:
Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is marked if $v\in M$.  The problem is to find a simple path in $G$ that visits the maximum possible number of marked vertices. The associated decision problem is: is there a simple path that visits every $v\in M$?

The problem is obviously more general than the problem of finding a Hamiltonian path in an arbitrary graph, so it is NP-hard.

I see no obvious strategy; one can't simply disregard the unmarked vertices, since they (and their incident edges) may be part of the optimal path.  Indeed, omitting them may disconnect the graph completely.

My questions:

Does this problem have a well-known name?
Are there any good approximation algorithms, heuristics, or simple reductions to problems I might know more about?
Where can I find this problem discussed in the literature?


texts: What is the relation between correlation and causation in machine learning?

texts:
It is a well-known fact that "Correlation doesn't equal causation", but machine learning seems to be almost entirely based on correlation. I'm working on a system to estimate the performance of students on questions based on their past performances. Unlike other tasks, like Google search, this doesn't seem like the kind of system that can be easily gamed - so causation isn't really relevant in that regard.

Clearly, if we want to do experiments to optimise the system, we will have to care about the correlation/causation distinction. But, from the point of view of just building a system to pick questions that are likely to be of the appropriate difficulty level, does this distinction have any importance?


texts: Create binary numbers with a described pattern

texts:
I am looking for an algorithm that can create binary numbers following certain patterns. Let $n$ be the size; and assume that is a power of 2. Let $E$ be the exponent; $n = 2^E; k = \log n$. The $0, 1$ on the "top level" are symbols, and let $0^n, 1^n$ represent $n$ consecutive zeroes and ones respectively.

For size 2, $E = 1$, and the one number is given by $0^1 1^1 = 01$.

For size 4, $E = 2$, and the two numbers are $0^2 1^2 = (0^2 1^2)^1 = 0011$ and $(0^1 1^1)^2 = 0101$.

For size 8, $E = 3$, and the three numbers are $(0^4 1^4)^1 = 00001111$, $(0^2 1^2)^2 = 00110011$, $(0^1 1^1)^4 = 01010101$.

For size $n = 2^E$, the $E$ numbers include $(0^1 1^1)^{n/2} = (0^{2^0} 1^{2^0})^{2^{E-1}}$ to $(0^{n/2} 1^{n/2})^1 = (0^{2^{E-1}} 1^{2^{E-1}})^{2^{0}}$. Thus, the $E$ numbers can be parameterized by a natural number $k$ from 0 to $E-1$ such that the member is expressible as $(0^{2^k} 1^{2^k})^{2^{(E-1)-k}}$.

Is there an algorithm using bit manipulation that can generate each of these numbers in the set with algorithm in the range of $O(1)$ to $O(n)$?
Important Note: I am looking for an algorithm that generates binary numbers not strings unless transformation from strings to binary numbers can be in the range of $O(1)$ to $O(n)$.


texts: Using Brzozowski's derivatives method to construct a minimal DFA

texts:
so I am currently learning about dfa and nfa and i came across the following question which requires me to use Brzozowski's derivatives method to construct a minimal DFA recognizing the language defined by the rational expression below. I am having quite a bit of trouble understanding how Brzozowski's derivatives works and how I would apply it to the expression below. Could someone please show me step by step how I would do it alongside and explanation.

What seems to be the main problem is that I am not sure how to derive the derivative such as dR/da.

X = (aa + b)* ab (bb)*


texts: What theorem are these? (from Scott Aaronson's blog)

texts:
Browsing Scott Anderson's blog, I found this list of theorem. Among them are:

If every second or so your computer’s memory were wiped completely
clean, except for the input data; the clock; a static, unchanging
program; and a counter that could only be set to 1, 2, 3, 4, or 5, it
would still be possible (given enough time) to carry out an
arbitrarily long computation — just as if the memory weren’t being
wiped clean each second. This is almost certainly not true if the
counter could only be set to 1, 2, 3, or 4. The reason 5 is special
here is pretty much the same reason it’s special in Galois’ proof of
the unsolvability of the quintic equation.
It would be great to prove
that RSA is unbreakable by classical computers. But every known
technique for proving that would, if it worked, simultaneously give an
algorithm for breaking RSA! For example, if you proved that RSA with
an n-bit key took n5 steps to break, you would’ve discovered an
algorithm for breaking it in 2n^1/5 steps. If you proved that RSA took
2n^1/3 steps to break, you would’ve discovered an algorithm for
breaking it in n(log n)^2 steps. As you show the problem to be harder,
you simultaneously show it to be easier.

I learnt a bit of computer science in college, but I had never heard of these 2. I am very interested in knowing these. Any know what theorems are these? Thanks.
(since I can't comment...can you be more detailed about how "natural proof" do anything here?)


texts: Fast k mismatch string matching algorithm

texts:
I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P matches a substring of T with at most k mismatches. This is different from the k-differences problem (edit distance). A mismatch implies the substring and the pattern have a different letter in at most k positions. I really only require k=1 (at most 1 mismatch), so a fast algorithm for the specific case of k=1 will also suffice. The alphabet size is 26 (case-insensitive english text), so space requirement should not grow too fast with the size of the alphabet (eg., the FAAST algorithm, I believe, takes space exponential in the size of the alphabet, and so is suitable only for protein and gene sequences).

A dynamic programming based approach will tend to be O(mn) in the worst case, which will be too slow. I believe there are modifications of the Boyer-Moore algorithm for this, but I am not able to get my hands on such papers. I do not have subscription to access academic journals or publications, so any references will have to be in the public domain.

I would greatly appreciate any pointers, or references to freely available documents, or the algorithm itself for this problem.


texts: Exponential-size numbers in NP completeness reduction

texts:
In the proof of Theorem 4 in [GS'12], the authors reduce an instance of PARTITION to their problem. Therefore, they create for each element $a_i$ in the instance of PARTITION a number $2^{c \cdot a_i}$ for a suitable constant $c$, which is later used in the reduction. They argue, that the instance remains of polynomial size since these exponential-size numbers can be encoded implicitly. Nevertheless, can we really work with those numbers in polynomial time? What if we add such two numbers $2^{c \cdot a_i}$ and $2^{c \cdot a_j}$ for $a_i \neq a_j$ in the course of the algorithm, then the resulting number cannot be encoded in this way any longer. Is this reduction valid?

[GS'12]: Martin Groß and Martin Skutella, "Generalized maximum flows over time", 2012.


texts: Raptor Algorithm: Differences between trip and route

texts:
I'm reading Microsoft's white paper "Round-Based Public Transit Routing" (the RAPTOR algorithm). In this algorithm, there are some definitions that I don't understand:

About trip:

  trip represents a sequence of stops a specific vehicle (train, bus,
  subway, . . . ) visits along a line

About route:

  Each route consists of the trips that share the same sequence of
  stops.

So, if I understand, trip means a "bus route" and a route is collection of trips to make a path? If my guess is true, why does it state:

  Typically there are more routes than trips

And if a route is just a collection of trips, how can I build all routes?


texts: Efficient algorithm for finding maximum subset of intersecting rectangles

texts:
What is an $O(n \log n)$ algorithm to find how big the largest subset of $n$ axis-aligned rectangles (in the plane) that contain a common point is? Perhaps by reducing this to a problem with such runtime?

An $O(n^{3})$ algorithm could be

for each of the n rectangles
    for each of the 4 sides of the rectangle
        find the points where it intersects other rectangles and keep the set of those points
        loop through the intersection points set and update the count


texts: Status on Naoki Katoh's "Rectangle Wiring Problem" (minimum length tree to cover a partitioned rectangle)?

texts: I have found this interesting problem in graph theory and geometry which is allegedly an open problem but latest status seems to be from 01/25/02. I can't seem to find any more information about it, not even other papers describing it.


texts: Detecting shapes using CNNs in respect to other shapes in the image

texts:
I'm solving a problem of detecting an optic disc in a retina image. As you can see from the image:

the optic disc is the epicentrum of the blood vessels, has an irregular circular shape and has a brighter color than the rest of the retina.

Now I want to use a convolutional neural network to detect it. I know that typical approaches to detecting something in an image using CNNs (consisting mostly of conv., pooling, dropout and fully connected layers) devide an image into smaller parts, each of them is send to a classifier asking whether there is the object or not.

But I'm thinking about another approach. It'd be a model, which gets a normal RGB image of Height x Width size as input, which goes through several convolution layers so as the size remains the same (Height x Width) but with more channels let's say N. There would be no pooling layers(??), so the final output of the convolution would be of the size Height x Width x N.

In this output there'd be Height x Width feature vectors of the size N, each somehow describing the pixel on this position in the original image and its neighbourhood (??). Now what I'm trying to do here is to take these individual vectors as inputs to a fully connected layer network. Output of this would be some number describing the relative position of the input pixel in respect to the position of the optic disc in the image (maybe its distance, or the position itself, I don't know yet...). The training data consists of an image and the x, y position ot the optic disc.

But I'm not sure about some things about this approach. Can I not to use pooling layers? I thought maybe it wouldn't be transform invariant then, or something like that. I'm also not sure if what I'm doing in the fully connected layers is correct. I don't understand neural networks so well to say that "it is obvious that this should work" or "or this is that case where it is not easy to say and it's worth implementing it to see how it will work" or "this obviously won't work because...". So my question is just: which one of this three cases is this?

And isn't there some "obvious" method for this stuff and I'm just trying to solve something that was already solved? (maybe RNNs or something...)


texts: Time complexity of algorithm inversely proportional to size of sub problem?

texts:
Let's say I have an algorithm with time complexity $T_n = T_\frac{n-1}2 + 1$, $T_0 = 0, T_1 = 1$.

Assume (Induction hypothesis) $T_n = C\log_2(n+1)$ for some $C$. $T_1$ imposes $C \geq 1$.

Therefore from I.H. (plugging in the formula at $\frac{n-1}2$):

$$T_n = C\log_2(\frac{n-1}{2}+1) + 1$$
$$T_n = C\log_2(\frac{n+1}{2}) + 1$$
$$T_n = C\log_2(n+1) - C + 1$$
Setting $C = 1$ gives

$$T_n = C\log_2(n+1)$$

And so by induction

$$T_n = \log_2(n+1)$$

This result makes very little sense to me. How come reducing the size of the subproblem from $n/2$ to $(n-1)/2$ increases the time it takes? (From Master's theorem, $T_n = T_{n/2} + 1 \Rightarrow T_n = \log_2(n)$. Similarly, increasing to $(n+1)/2$ gives $T_n = \log_2(n-1)$. What am I failing to see here?


texts: How to select a subset of columns in a given matrix to satisfy a condition?

texts:
Let $a_{kn}$ be positive real numbers for all $k\in\{1,\dots,K\}$ and $n\in\{1,\dots,N\}$ and let $t>0$. I need to find a subset $S$ of $\{1,\dots,N\}$ of minimum size
 such that:

if $|S|=1$ then $a_{ki}\geq t$ for all $k\in\{1,\dots,K\}$ and $i\in S$.
if $|S|>1$ then for all $k\in\{1,\dots,K\}$, there must exist some $i\in S$ such that  $a_{ki}/a_{kj}\geq t$ for all $j\in S\backslash\{i\}$.

I need to find a good heuristic for this problem (an optimal if possible).

Example:

let $t=2$; and
the matrix $A$ given as:

$$A=\begin{pmatrix} 50 & 1 & 1\\ 1 & 70 & 1\\ 1 & 1 & 40\end{pmatrix}.$$

The set $S$ should be $\{1,2,3\}$.

To solve the problem, I need to enumerate all possible subsets of $\{1,\ldots,N\}$. Do you see any particular characteristic of the problem that I can use to solve it?


texts: sub-optimal but fast partition generation

texts:
I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. But I am not really interested in THE optimal solution. I am interested in a FAST algorithm that generates some good partition wrt the criterion.

Let us say a set is [1,23,12,2456,234,16,188,22] and needs to be divided 3-ways. When partitioning we try to minimize the max difference between the size of all subsets.

One quick partition that can be generated is {[1,23,12],[2456,234,16],[188,22]}. This may not be optimal or maybe it is. It does not matter in this context.

We could have an algorithm: put 1st element in 1st set, 2nd element in 2nd set, all others in 3rd set. This would give us: {[1],[23],[2456,234,16,188,22]}. One can see this algo will be very fast but wrt to our criterion, it does not necessarily give a good-looking solution.

Can someone suggest existing work in this direction?


texts:
The naturals $\mathbb{N}$ can be encoded with a binary unary code such as

$$
\begin{align}
    1&=0_b\\
    2&=10_b\\
    3&=110_b\\
    &...
\end{align}
$$
The length this the encoding grows linearly with the natural number it represents. For example the length of $110_b$ is 3 and it also represents the number 3.

I am looking for an upper bound on the optimality of the prefix free encoding. For example, can we design a prefix coding of $\mathbb{N}$ such that the length of the encoding grows according to ~$\sqrt{n}$, instead of $n$. Is there an upper bound on the optimality that we can prove?


texts: Does a polynomial-time reduction from A to B imply that B is in NP if A is?

texts:
Let f be a polynomial-time reduction of a decision problem A to a decision
problem B. We know that, if B $\in$ P then A $\in$ P. Similarly, if B $\in$ NP then
A $\in$ NP. However, what about the other direction? Assume that A $\in$ NP and
consider the following non-deterministic algorithms to decide whether y $\in$ B:

"Guess" non-deterministically some x.
Verify that f(x) = y by computing f(x) in polynomial time and comparing
it with y. If f(x)$\neq$y, reject.
Check (using the polynomial-time nRAM for A) whether x $\in$ A and return
the answer.

Why does this not qualify as a proof that B $\in$ NP?


texts: Algorithm to identify rearrangements between two sequences of unique values

texts:
I have two sequences, seq1 and seq2, each consisting of unique values. Values can appear in seq1 or seq2 which do not appear in the other, and these values can appear in any order. How do I identify which values have been moved in seq2, such that values appear earlier or later in seq2 relative to the values in seq1? To visually describe the problem, any value whose arrow from seq1 to seq2 overlaps with another should be marked as moved, and is bracketed.

In the image above, C and D should be marked as moved.

In the image above, B and D (and probably C) should be marked as moved, though I’m mainly interested in the start and end values which have been moved.

In the above image, no values should be marked as moved.

However, if we add C to the end of the second sequence, D, E and C should be marked as moved.

New values should trivially be marked as moved, but the values around them should not.

Is there a way identify moved values with just a single traversal through both sequences? Either the canonical name of this problem or pseudocode would be greatly appreciated!


texts: Chazelle's discrepancy book: greedy method

texts:
In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem 1) is obtained by a simple probability argument.  Unfortunately, I fail to follow the intended argument.  Could someone enlighten me?

Here $\chi(S_i) = \sum_{v\in S_i} \chi(v)$ is the discrepancy of the set $S_i$ with respect to a function $\chi$ that assigns weights to each element.

  Given a set system $(V,S)$, with $|V| = n$ and $|S| = m$, pick a random coloring $\chi$, meaning that for each $v_j$, the "color" $\chi(v_j)$ is chosen randomly, uniformly, and independently, in $\{-1,1\}$.  We say that $S_i$ is bad if $|\chi(S_i)| > \sqrt{2|S_i|\ln (2m)}$.  By Chernoff's bound, we immediately derive
  $$Pr[S_i \text{ is bad}] < \frac{1}{m};$$

and now the bit I don't follow:

  therefore, with nonzero probability, no $S_i$ is bad.

Clearly this holds if the $m$ events "$S_i$ is not bad" are mutually independent.  It also holds by a form of the Lovász Local Lemma if these events form the edges of a hypergraph (with $V$ as vertices) that is "nice enough".  But I don't see why this is immediately apparent in every case, as the author seems to imply.  If the $n$ individual values $\chi(v_j)$ are iid, then I simply don't see that the $m$ events "$S_i$ is not bad" are necessarily of a nice enough form to use the probabilistic method, and they certainly don't seem to be iid.

What am I missing?

Any counterexample must be rather large (with the size of $m$ exponential in $|S_i|$), so I provisionally do believe the statement.  But I would like a convincing proof, or a pointer to another reference.


texts: How to find n-1 complete matches for bipartite graphs that are related (speed-date)?

texts:
How can one assign n people pairwise to n-1 tables, in a speed-date fashion, such that no two persons meet twice and each person is at each table exactly once? Does this problem have a name?

The problem in full

Given n people (n is even), assign them in pairs in n-1 rounds. Each round represent a list of n/2 pairs, each pair being two individuals that have not met earlier.

For each round, find a match between the n/2 pairs and n-1 tables, so that every pair are assigned a table. The tables are unique. Through all n-1 rounds, an individual should meet each other individual exactly once, and be at each table exactly once.

What have I tried?

Here is the naive bipartite matching algorithm I've created so far:

Create rounds using the round-robin tournament scheduling.
Represent each round as a bipartite graph, pairs vs tables.
For each round, find a match.

For each player, remove table matched in this round.

In pseudo:

n = 6
tables = [1, 2, 3, 4, 5]
players = [{'i': 1, 'tables': copy(tables)}, {'i': 2, 'tables': copy(tables), ...]
rounds = roundRobin(players)
# each round has a list of pairs
# each pair is two players
# [
#     [[1,6], [2,5], [3,4]],
#     [[1,2], [3,6], [4,5]],
#     ...
# ]
matches = []
# keep matches

for round in rounds:
    match = hopcroft_karp(round, tables)
    # pair 1 to table 1, ...
    # [ [1, 1], [2, 2], [3, 3] ]

    if len(match) !== len(round):
        # TODO: backtrack
    else:
        add match to matches
        for edge in match:
            pair = round[edge[0]]
            table = edge[1]
            removeTable(pair[0], table)
            removeTable(pair[1], table)

Example

For some n, there is no solution. For example n = 4. I'm unsure for which n the problem has solutions. Here is n = 4 as an example:

People: 1, 2, 3, 4
Tables: A, B, C

Round 1: A:1,2 - B:3,4
      In round 1, we can assign tables at random, because
      the problem is the same with renaming tables.
Round 2: C:1,3 - ?:4,2 <-- not possible
      4 has already been at table B.
      2 has already been at table A.
      Table C is taken by pair 1,3.
Round 3: ?:1,4 - ?:2,3 <-- same as round 2


texts: Why multiple rotations might be needed after deletion in an AVL tree if after insertion there can be at most one needed?

texts:
I understand that after deletion you have to retrace to update ancestors and after insertion you do the similar however at most one rotation will be performed.

The question is why is there the difference in number of potential rotations for these two operations.

To me it seems like these operations should be the reverse of each other but this difference in their properties suggests they're not. Why?


texts:
I'm working on a class library (C++) that can be thought of as a producer/consumer queue of producer/consumer queues. There are many queues of data, and the goal is to assign worker threads to process these queues, as needed, using coroutines. At any rate, the details aren't necessarily important to the question, but I'm struggling to wrap my head fully around the synchronization requirements.

I've started with a list of basic operations (like adding an element to the top level queue), along with some preconditions, postconditions, and what I'm calling "exclusions" which are things that are not supposed to happen during the operation. It seems to only scratch the surface though.

Finally, my question: Is there a way to model algorithms (either notation or diagram) that helps to tease out temporal ordering requirements? What needs to be locked when? What transactions need to be atomic? What order can reads/writes be carried out in?


texts: calculate the complexity of binary search algorithm

texts: How do i calculate the complexity of this algorithm at the best case and its complexity at the worst case and the average complexity by assuming that the probability that the element is in the list is 0≤p≤1 and that all sites are equal probability


texts: Are two terms where one is without a $\lambda\beta$ normal form unconvertible in $\lambda\beta$?

texts:
I know that if you try and make the theory

$$\lambda\beta+\{s = t\ |\text{ s, t are terms without }\lambda\beta\text{ normal forms}\}$$

then that theory becomes inconsistent. Are two terms where one is without a $\lambda\beta$ normal form also unconvertible in $\lambda\beta$, ie can it ever be true that $\lambda\beta \vdash s=t$ if $s$ dosen't have a normal form?


texts: Bucket sort has uniformly distributed data

texts: Implementation of bucket sort is mainly useful when input is uniformly distributed over a range. So the ques here is what is the significance of having input data uniformly distributed for applying bucket sort? What happens if this does not hold?


texts: Why does the firefly algorithm need an intensity function?

texts:
I am studying the firefly algorithm and I would like to ask about the Intensity function that is defined at the beginning of the algorithm.

What is it for? Some literature give different functions for $I$.  Wouldn't it be easier if the intensity be just the function itself (for example in a maximization problem)?


texts: Is the reversal of a minimal DFA also minimal?

texts: The question is pretty much in the title. Is there ever a time where some language $L$ can be accepted by a minimal DFA with $n$ states, but $L^R$, the reversal of $L$, can be accepted by a DFA with $m$ states, where $m<n$?


texts: How do I know if my algorithm is right (without coding)?

texts:
For some background :
I think I am quite good at advanced (graduate/research level) mathematics and physics but I have no CS background. Now I am taking a graduate level class on algorithms.

I don't think I have ever written a wrong proof in mathematics - as in either I can prove something or I can't. I have never faced a situation whereby I wrote a wrong proof - its just obvious if I am writing a wrong proof.

BUT with algorithms it seems that its just trivial to write a wrong algorithm. I am simply not getting as to how does one know if what one has written is right or wrong. There seems to be something "mysterious" going on here - like while I write a recursive/dynamic programming solution etc. - I am thinking that I wrote something right but then somebody comes along with an example where my answer doesn't work!

Its quite contrary to my years of experience of writing proofs in mathematics!

This is getting freaking scary! Its better to not be able to do something than to be writing a wrong answer and not knowing it! (...often enough I land up writing a greedy solution trying to optimize something locally but its not the globally correct answer!..how does one see it!?...coming up with a counter-example is also almost always very hard!..)

Can someone help?

I am currently doing a lot of practice with this but I wonder if there is something that I am missing totally!


texts: How to check wether a 2SAT implication graph has a bad loop or not?

texts:
m doing a practise quiz which my professor has posted online, one of the questions im very confused about was this one.

   Consider the clauses {x,y} , {~x,y} , {~y,z} , {~z,w} , {~w,~y}
is this true or false?

The implication graph contains the following bad loop:
x -> y -> z -> w -> ~y -> x

I said that this statement was false , however it came out that its true, can someone explain to me why this is the case?

Because i thought a bad loop would be a transition between a letter to the negation of its own then back to the original for example x -> ~x -> x


texts: Choosing heuristic for A* algorithm where cost is less than absolute distance

texts:
Looking for information on choosing a heuristic for instances where the cost of traversing an edge can be less than one.

For example, say movement is allowed in the cardinal directions. Should all edge costs be at least one, then I would consider diagonal distance. However, if costs can be less than one, this could lead to an instance where diagonal distance will be an overestimate and thus is not an admissible heuristic.

My thought on the matter is perhaps to find the smallest possible cost and figure out a constant to divide diagonal distance by to guarantee it will never overestimate?

Would appreciate some guidance or some resources to look further into this.


texts: Quickly locating nearest rectangle from a point

texts:
The problem is as follows:

  There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the nearest rectangle from $p$? The distance from a point $p$ to a rectangle $R$ is defined as the Euclidean distance between $p$ and its nearest counterpart $q \in R$. If $p$ is inside the rectangle, then the distance is $0$.

Actually what I want is the distance between $p$ and its nearest rectangle, so if we can directly get this distance, it's even better.

The naive solution is to compute the distance between $p$ and each rectangle, however this is time consuming in my case, so I want to know if there exists such a data structure.

Edit:

These rectangles may intersect, and the total number is very likely less than 20 (typically around 5). It is trivial if we only want to know this minimal distance for a few points, linear scan will do the work. However when the number of such points becomes very large, the overall computation overhead cannot be ignored, that's why I want to quickly find the nearest rectangle.


texts: Curiosity on system device nomenclature - Gaussian Mixture Models

texts:
Would not know if this is the best SE website to ask, but I could not find anything better, especially because the answer might involve a fair amount of computer science (although this is an hypothesis).

I hold a MSc. in Statistics, and thus have extensively explored Gaussian Mixture Models. That's why, upon buying my brand new Lenovo E580 laptop (Windows 10 Pro x64), I was surprised to find, under the System devices drop down menu in the Device Manager, a reference to GMMs (although I'm not sure what the actual item is pointing to). I have included a picture to clarify the point.

Questions

1) What is the highlighted item referring to?

2) How do GMMs have anything to do with this?


texts: Origins of the Segment tree data structure

texts:
I'm interested in the first appearance in the CS literature of the data structure described here which is used to answer Range Queries. Although I have come across the same data structure many times with the name segment tree (mostly in algorithmic competition sites), it seems that the same name is also used for this data structure which is quite different from the first one and has application in computational geometry.

I'd like to know who introduced the data structure described in the TopCoder tutorial and if another name was initially used as there seems to be a confusion between the two data structures that go by the same name.


texts: Generating a Covering Array Matrix with Simulated Annealing

texts:
I've been reading the following paper to understand how I can develop a non deterministic algorithm for test cases generation https://www.researchgate.net/publication/293043297_A_two-stage_algorithm_for_combinatorial_testing

I understand that he is using a two stage solution, having a greedy algorithm as a solution for the first stage. I'm struggling to understand the steps of the first stage and the algorithm itself, specifically in the section 3.1, for which I have the following doubts:

It mentions that it receives as an input a CA of size N*K-1, but isn't the value N determined by the algorithm? Maybe an example of the inputs would clarify it.In section 3.3 though, from the step 1 and 2, I understand that the inputs have fixed values for N and if we don't have those values, then a different solution should be applied.
I'm not very sure how to interpret "free cells". Its just new empty slots
that will have a generated random number?
It would be easier to have instructions and a more detailed algorithm specification. However, I'm also failing to understand the pseudo code:

From the pseudo code, I'm not sure whats the M value (I don't think its mentioned), also the meaning of the +∞ symbol and also I'm not sure how he can compute the missing tuples. Perhaps I don't have enough knowledge or I'm not inferring correctly the instructions in the description and the algorithm itself. I'm looking for someone that can help me understand these particular points. (I can't find any contact email from the author).


texts: Bounded Integer Edge Weights, Dijkstra's Algorithm

texts:
I'm trying to understand how we can get the time complexity of Dijkstra's Algorithm down from O(V²) (for a matrix-implemented Dijkstra's) to O(V) if the edge weights of our graph are bounded by a constant C. I've read up on this MIT lecture but can't really wrap my head around the explanation.

It says that all paths are less than (|V|-1) * C, but why can't they be equal to (|V|-1) * C? For example, if the graph has one edge between each node and the weight on every node is C. Shouldnt it be less than or equal to?


texts:
I have the following problem, I would like to know an efficient algorithm to solve it.

Suppose I have a weighted graph $G$ and a set of vertices $K$, I want to find a walk which starts at a vertex $s$ and visits at least once every vertex of $K$ such that the distance is minimized.

There is no constraint on repeated nodes or edges in the walk found and is not guaranteed that the graph does not contain cycles. Some people have suggested me that it maybe NP-Hard due to a reduction from TSP, but there is no restriction of visit vertices exactly once, and is well known that TSP have that.


texts: Why there's a single accepting state in G-NFA's?

texts:
It's clear that we can only have a single start state in G-NFA's but I would like to know why we can't have more than one accepting state in G-NFA's.I think it's better to have more accepting states so that we could avoid epsilon transitions.

Is this only a rule that  might make conversion of NFA to Regular expressions simpler or is there any specific reason.If this rule makes the conversion simpler could anyone tell the reason behind it.


texts:
Lets say I have a global dataset and I run queries over those data set.
For example my dataset would be

#id, #Name, #Employee, #Birthdate, #number_of_children
1, Nick, Nasa, 1982, 1
2, Jack, Exon, 1985, 5
3, Tom, ABCD, 1978, 0

And I can run queryies on those dataset.
sample queries would be
* #Query => #Result_ids
* (Name starts with A) => [1]
* (Birthdate before 1983 and have children ) => [1]

I want to store those queries on a data structure and I want to be able to do set operations on those queries like intersection and union. So an example union operation would be.

(Birthdate before 1983) intersection (have children) => (Birthdate before 1983 and have children)

I also want to be able to findout if one query is subset or superset of another one. For example.

(Birthdate before 1983) is superset of (Birthdate before 1980)
(Have 3 children) is subset of (Have more than 1 children)

(Name = Jack and born in 1980) is subset of (Born before 1990)

I will have a program that will have thousands of queries. And it will combine those queries to make more variety of queries. When I have a new query, I will compare it with existing queries to see if I have an exact query in store or have a superset.

Can anybody suggest me a data structure that is fast enough to store and operate on those data?


texts: Please check my answer to a pseudocode CASE statement question

texts:
This is a pseudocode question in my IGCSE CompSci textbook:

  Use a CASE statement to display the day of the week if the variable DAY has the value 1 to 7 and an error otherwise.

This is my answer to it:

CASE Day OF
    1 : OUTPUT "Monday"
    2 : OUTPUT "Tuesday"
    3 : OUTPUT "Wednesday"
    4 : OUTPUT "Thursday"
    5 : OUTPUT "Friday"
    6 : OUTPUT "Saturday"
    7 : OUTPUT "Sunday"
    OTHERWISE OUTPUT "Day invalid"
ENDCASE

Is this answer correct?

(I realise this is a very rudimentary question for a Year 10/11 CompSci class but I’m homeschooled with no teaching guidance whatsoever. So a big cheers to anyone who would take the time to check my answer for me.)


texts:
Consider we need to solve the Matrix chain multiplication using dynamic programming for this problem :

The table for min. cost is shown below :

Edit : Reference https://www.radford.edu/~nokie/classes/360/dp-matrix-parens.html

The table for Optimal locations for parentheses:

I know how to construct these tables but I don't know how to extract the min. number of multiplications that will be achieved for multiplying these matrices from the min cost table and also I can't construct the overall places of the parenthesis that should be used to achieve this min. number of multiplications from the optimal location of parenthesis table ?
So please someone mention the resultant min. number of multiplications for this solution of this problem with the final parenthesis locations that should be used to achieve this min. number. Many thanks.


texts: Metropolis algorithm Simulated annealing

texts:
Someone could explain me in a simple way why Bruce Hayek theorem guarantee an optimal schedule for Metropolis algorithm?
For me is enough an informal explanation.

Thanks.


texts:
(x >= 0 && y >= 0)
q = 0;
r = x;
while ( r >=y ) {
  r = r - y;
  q = q + 1;
}
(x = q*y +r) && (r >= 0) && (r < y)

For this what if y = 0 ?

If y = 0, then r stays at r inside the while loop, which makes r >= y true always. So it doesn't seem to terminate.

So I think, for pre-condition, doesn't it have to be (y > 0) to make sure this program terminates ?


texts: Reduction to equipartition problem from the partition problem?

texts:
Equipartition Problem:

Instance: $2n$ positive integers $x_1,\dots,x_{2n}$ such that their sum is even. Let $B$ denote half their sum, so that $\sum x_{i} = 2B$.

Query: Is there a subset $I \subseteq [2n]$ of size $|I| = n$ such that $\sum_{i \in I} x_{i} = B$?

Can the partition problem - same as the above but without the restriction on $|I|$ -  be reduced to the above problem ?


texts: What algorithms exist for solving natural number linear systems?

texts:
I'm looking at the following problem:

Given $n$-dimensional vectors of natural numbers $v_1, \ldots, v_m$ and some input vector $u$, is $u$ a linear combination of the $v_i$'s with natural number coefficients?

i.e. are there some $t_1, \ldots, t_m \in \mathbb{N}$ where $u = t_1 v_1 + \dots + t_m v_m$?

Obviously the real-number version of this problem can be solved using Gaussian elimination. I'm wondering, has the integer version of this problem been studied? What algorithms exist to solve it?

Note that this is using natural numbers, but not modular arithmetic, so this is somewhat separate from the Chinese Remainder Theorem and systems like that. Also, it seems related to Diophantine equations, but I'm wondering what has been done in the case where only non-negative integers are considered?  This is also reminiscent of a multi-dimensional subset-sum problem, generalized to allow us to take an arbitrary number of copies of each vector.  It also seems related to testing whether $u$ is an element of the lattice generated by $v_1,\dots,v_m$, except that here we only allow linear combinations with non-negative coefficients.

For anyone interested, this is motivated by looking at whether a Parikh vector is in a linear set, as in Parikh's Theorem.

In particular, I'm interested in an algorithm that could solve the problem using only natural number operations, avoiding going into the reals/floating point numbers.


texts: Is a push-down automaton with two stacks equivalent to a turing machine?

texts:
In this answer it is mentioned

  A regular language can be recognized by a finite automaton. A context-free language requires a stack, and a context sensitive language requires two stacks (which is equivalent to saying it requires a full Turing machine).

I wanted to know regarding the truth of the bold part above. Is it in fact true or not? What is a good way to reach at an answer to this?


texts: Inplace sorting of variable length records

texts:
Is there an in-place algorithm for sorting variable length records?

For example a vector of arbitrary length strings.

Most provided in-place algorithms assume that you can switch two elements without affecting the rest of the structure.  However this does not work if your records differs in size.

Googling leads me to this. However, they finish with:

  After writing all sorted output blocks, merge them into the final sorted file using any convenient merging algorithm. When allocating buffers or making other preparations, the merging steps can take advantage of the fact that every variable-length block written by step 7 has the same maximum size (just less than the size of buffer 1 or 2)." I do not feel that doing in-place merging of arbitrary length records is in any way trivial.


texts: Is this simplified consensus problem easier than the original?

texts:
There is a famous Consensus Problem in Distributed Computing.

Let's consider and try to find the best possible algorithm for a simplified version of the consensus problem.

Assumptions: a process may undergo only crash failure (process abruptly stops and does not resume), process represent a complete graph.

Simplification: a crash failure may occur only between round, so there no a case when a process succeeds in sending some message and fails to send other message during the same round.

The algorithm for the general case FloodSet when a process may crash during the round is described in Distributed algorithms - Nancy Ann Lynch. By the analysis it was shown that $f+1$ rounds is enough to reach a consensus.

Intuitively, it looks like that the simplification completely changes the approach to the solution. It is may be enough just one round, every processes send an input message to every other processes and agree on the minimal value.

What is the simplest possible algorithms for simplified problem ?

What can we do in the case of general graph?


texts: Proving a language comprised of 2 languages is regular

texts:
So glad to find this place. I have been struggling for quite a while with this given question and i am not sure how to fully address it.

The question:
$L_1$ and $L_2$ are regular languages over the same $\Sigma$. prove that the following language is regular as well:

$L^\frown \:=\left\{\:w\:\in L_1 | \:w=\sigma _1\mu _1\xi _1\sigma \:_2\mu \:_2\xi \:_2...\sigma \:_n\mu \:_n\xi \:_n\right\}$ Where $n \geq 0$, for every i:$\left(1\:\le i\:\le n:\:\sigma _i\mu _i\xi _i\:\in \Sigma \right)$, $\mu_1\mu_2...\mu_n \in L_2$.

Prove using:
1)Closure properties.
2)Building an multipication automaton

My try:

1)I do not understand how to define the homomorphism from which I can deduct using closure properties that the given language is indeed regular.

2)Since both $L_1$ and $L_2$ are regular, There exist two deterministic finite automatas that can accept them: $A^i\:=\:\left(\Sigma ,\:Q^i,q_0^i,F^i,\delta ^i\right)$ ($i\:\in \left\{\:1,2\right\})$. So, let L be the automaton that accepts those two languages: let L be $L\:=\:\left(\Sigma \:,\:Q^1\:X\:Q^2,\left(q_0^1,q_0^2\right),F^1X\:F^2,\delta \:\right)$. However, here I don't know what its transition function should be

Would really appreciate your help with it, if possible with explanations to understand so I'll be able to overcome similar questions in the future.

Thank you so much!


texts: What's the best algorithm to find the shortest path between 2 vertices in a graph?

texts: Considering an undirected and unweighted graph, what's the best algorithm to find the shortest path between two vertices?


texts: Average depth of a Binary Search Tree and AVL Tree

texts:
My professor recently mentioned that the average depth of the nodes in a binary search tree will be $O(log(n))$ where $n$ is the amount of nodes in the tree. I ended up drawing out a bunch of binary search trees and I don't think I am understanding the concept correctly. For example, if $n=4$ the tree is either going to have a node with a maximum depth of $3$ or node(s) with a maximum depth of $2$. In the case of where the maximum is $3$, then we would have nodes of $0$, $1$, $2$, and $3$ depths. This would give us an average depth of $1.5$ and $log(4)$ is $2$.

My professor also said that an AVL tree's nodes will ALWAYS have an average depth of $O(log(n))$, which makes even less sense to me, since with the example above of $n=4$ the closest we got to $log(4)$ was $1.5$ with a tree that had nodes of depth $0$, $1$, $2$, $3$ but in an AVL tree we couldn't have that tree.

The $O(log(n))$ stuff would kind of make sense if the root started with a depth of $1$, but I specifically asked the professor if that was the case and he said no.


texts: Is there an example of how SOS can be used to show infeasibility of a set of multivariable equations?

texts:
Lets say one is given a set of $m$ real polynomial equations in $n$ variables, $P_1 = P_2 = P_2 .. = P_m =0$. I understand that there is some theorem which says that if there is no solution to these simultaneous equations then one necessarily will be able to find polynomials $Q_1,Q_2,..,Q_m, R_1, R_2,..,R_k$ such that $deg(P_iQ_i)$ and $deg(R_i^2)$ are all  $\leq d$ for some $k$ and $d$ such that,  $\sum_{i=1}^m Q_iP_i + \sum_{j=1}^k R_j^2 = -1$

Can someone kindly reference this theorem and its proof?

Now lets say one is looking at a $d$ which is not sufficiently large. Then one will be looking at the set of all polynomials of the form $S = \sum_{i=1}^m Q_iP_i + \sum_{j=1}^k R_j^2$ such that $deg(P_iQ_i)$ and $deg(R_i^2)$ are all  $\leq d$ for various $k$. But this is a convex set in the set of polynomials? And $-1 \not \in S$. Then there will exist a separating hyperplane between S and $-1$ and the normal to that plane gives a degree-d pseudo-distribution on S.

Does someone have a concrete example of the above phenomenon?
Why is this pseudo-distribution indistinguishable from an actual distribution on $S$ if one is only looking at moments $\leq d$?


texts:
Good afternoon.

At work I'm currently developing a system which takes user input (well structured) and then stores it in memory to do some processing.

The input is basically a dataset formed by matrix of pxq dimension, with q columns of data and p rows; where each row has the following structure:

n indexes, m attributes, k classes, with $n, m, k \geq 1$

The system can handle inputs from several users at the same time, and the values of n, m, k can be different per dataset. However, no matter which values, there has to be a unique data structure capable of handling the size of the dataset, and store the data in memory efficiently, with a particular emphasis on data reads and inserts, which are the most frequent operations.

I'm currently struggling with two things:

How to describe such structure at a high level (without considering the how it will be stored in memory) using only math equations.
Finding an efficient data structure which can be created previous to the user input. This means, as soon as the text fields are shown to the user, the data structure has to be created and after the user fills every data in the dataset and press Enter the data needs to be inserted (and quickly) into the data structure. However, I don't know if this is entirely possible or if it's the best approach.

I'm open to suggestions. Currently what I have thought of is:

The system takes a dataset $d_{pq}^{nmk}$ as a matrix formed by $p$ rows and $q$ columns.

We define an index $id_{i}, i = 1\ldots n $ as following:
$id_{i} = [a-zA-Z\_][a-zA-Z0-9\_]*$

In an analogous way, it's possible to define an attribute $a_{j}, j = 1\ldots m$ and a class $c_{l}, l = 1\ldots k$:
$a_{j} = [a-zA-Z\_][a-zA-Z0-9\_]*$
$c_{l} = [a-zA-Z\_][a-zA-Z0-9\_]*$

Where each row of a dataset $d_{pq}^{nmk}$ is the union of exactly $n$ indexes, $m$ attributes and $k$ classes, as folowing:
$ID = \bigcup_{i = 1}^{n} id_{i} $
$AT = \bigcup_{j = 1}^{m} a_{j} $
$CL = \bigcup_{l = 1}^{k} c_{l} $

Therefore, a the $t-th$ row of a dataset $d_{pq}^{nmk}$ can be expressed as:
$r_{t} = ID_{t} \bigcup AT_{t} \bigcup CL_{t}$

And thus, a dataset $d_{pq}^{nmk}$ can be expressed in s implified way as:
$d_{pq}^{nmk} = \{r_{t}\}, t = 1\ldots q$

However, I'm not sure if this definition is just enough good as a formal expression of the dataset. Also, I feel it doesn't help to think of a good data structure to handle the dataset (except by a list of lists, of course).

I was thinking the simplest approach would be to define a record with two types (a label which indicates if the value represents a index, ar atribute or a class) and the value itself. After that, the data structure could be a list of lists, where each row is a list, and the dataset itself is formed as a list of rows (which are lists). However, if the dataset is big enough, I think this approach would be really really slow, but I have not been able to find a better data structure.

Any kind of help or resource for further research is welcomed.


texts: Greedy Heuristics with an Altered Subset Sum/Partition Problem

texts:
Say we have a constant-time function that accepts some integer set. The function outputs True if we can split the integers into two subsets of an equal sum. If we can't partition the integers given, the function outputs False.

Suppose we can use this function at any time, with any set of integers. Can we make a greedy algorithm using this function that will output one of the specific subsets that sum to half of a particular positive integer set?

The heart of the question:
If we know at any time the boolean result of canPartition() on any set of integers, can we greedily use that to output the specific values of a partition?


texts: Unique integer priority queue with both $O(1)$ insert and extract-min?

texts:
I'm aware of the two questions prioritizing inserts and extracts individually, each in $O(1)$ time, but does there exist a unique integer priority queue algorithm for the range $[0, n)$ that can do both insert and extract-min in $O(1)$? The closest one I've found so far is this one, with the following qualities:

Insert: $O(1)$
Extract-min: $O(\log \log n)$

None of the other operations need to be any quicker than what's sane for a few dozen unit tests with very small numbers. I'd prefer space to be no more than log-linear, though, given my use case (not absolute, but they're very frequently created and destroyed).

Note that the n will need to change every so often, but I plan on placing it in a resizable array with amortized linear growth and shrinking, so that shouldn't affect much.

Edit: I've found that for my purposes, a hash map + bitset is sufficient (it was for fast and low-memory unique ID generation), so this question more remains out of curiosity.


texts: Obtaining a computational history of a Turing Machine

texts:
I am currently reading the proof presented in Sipser's "Theory of Computation" for the undecidability of the problem of checking whether the language accepted by a linear bounded automata is empty. In this proof, a contradiction is derived via a reduction from the problem of checking whether a Turing machine, $M$ accepts a given input, $w$. The proof seems to use the fact that from an input in the form $\langle M,w \rangle$, it is always possible to get a computational history, $C$, of $w$ when run on $M$. Then, $C$ is fed into some LBA, $B$, which checks if its input is an accepting configuration of $M$.

It seems to me that in order to obtain $C$ in the first place, we must simulate $M$ on $w$. However, if $M$ does not halt (and since $M$ is not an LBA, it is not guaranteed that there are a finite number of configurations), then we will never obtain $C$ (and $C$ would not be finite). It seems that the problem of obtaining a computational history of a Turing machine is equivalent to checking whether a Turing machine accepts its input. So what is the method used to always obtain $C$ from $M$ and $w$? Don't we need to prove the existence of such a method if we are going to use it to derive a contradiction?


texts: In cache addressing, what value is placed in the offset field?

texts:
There is a 64 KB 1-word cache, and a word is 32 bits.  From that I can derive that the length of the tag field is 16 bits, the length of index field is 14 bits, and, as my professor taught me, there is always 2 bits left behind for a byte offset.

Why the offset field is 2 bits, other than it fills in the remaining 2 bits of the word, and what its contents is was never covered in the course.

But when I looked around on Google, I read, and correct me if I am wrong, that the length of the offset field can vary.  Although I have found answers on how to determine the length, I could not find anything about determining its contents when a read hit/miss is performed.  My professor merely said "the byte offset is not used to select the word in the cache".

Just looking for clarification.


texts:
I implemented dependently typed lambda calculus in the spirit of this article: http://www.andres-loeh.de/LambdaPi/LambdaPi.pdf

The calculus, works and I experimented with it and like it. However, I want to add inductive types to do more complex stuff. What are the options for doing this?

I am thinking about two ways of doing so

Introduce Fin-N, Product and W-types and represent inductive types with them.
Generate induction and recursion axioms.

What can you recommend? How inductive types are represented in systems like Coq, Idris and Agda? Which articles can you recommend me?


texts:
How to solve fractional knapsack in linear time? I found this on Google but don't really understand it.

Choose element $r$ at random from $R$ (set of profit/weight ratios)
Determine

$R_1 = \{ p_i / w_i | p_i / w_i > r, for 1 \leq i \leq n \}, W_1 = \sum_{i \in R_1} w_i$
$R_2 = \{ p_i / w_i | p_i / w_i = r, for 1 \leq i \leq n \}, W_2 = \sum_{i \in R_3} w_i$
$R_3 = \{ p_i / w_i | p_i / w_i < r, for 1 \leq i \leq n \}, W_3 = \sum_{i \in R_3} w_i$

if $W_1 > W$

recurse $R_1$ and return computed solution

else

while (there's space in knapsack and $R_2$ is not empty)

add items from $R_2$

if (knapsack gets full)

return items in $R_1$ and items just added from $R_2$

else

reduce knapsack capacity by $W_1 + W_2$
recurse on $R_3$ and return items in $R_1 \cup R_2$
add items returned from recursive call

I don't get how it works, what $R$ and $W$ are supposed to represent ... can someone explain? Or maybe if you have another algorithm to propose?