texts: I can not see why MSD radix sort is theoretically as efficient as LSD radix sort

texts:
Here is the pseudocode for LSD radix sort from http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

   public static void lsd(String[] a)
   {
        int N = a.length;
        int W = a[0].length;
        for (int d = W-1; d >=0; d--)
        {
             int[] count = new int[R];
             for(int i = 0; i < N; i++)
                   count[a[i].charAt(d) + 1]++;
             for(int k = 1; k < 256; k++)
                   count[k] += count[k-1];
             for(int i = 0; i < N; i++)
                   temp[count[a[i].charAt(d)]++] = a[i];
             for(int i = 0; i < N; i++)
                   a[i] = temp[i];
        }
   }

I guess that by 256 they mean $R$. We have a simple for loop, so the time is $\Theta(W(R+N))$ The reason why I use $\Theta$ is because the bound is tight, this is how many operations you will be doing no matter what, so it's worst case and best case performance at the same time. The space requirements are $\Theta(N+R)$

The following is the pseudocode of MSD:

    public static void msd(String[] a)
    {
        msd(a, 0, a.length, 0);
    }

    private static void msd(String[] a, int lo, int hi, int d)
    {
        if (hi <= lo+1) return;
        int[] count = new int[256+1];
        for (int i = 0; i < N; i++)
             count[a[i].charAt(d)+1]++;
        for (int k = 1; k < 256; k++)
             count[k] += count[k-1];
        for (int i = 0; i < N; i++)
             temp[count[a[i].charAt(d)]++] = a[i];
        for (int i = 0; i < N; i++)
             a[i] = temp[i];
        for (int i = 0; i < 255; i++)
             msd(a, l+count[i], l+count[i+1], d+1);
   }

Since the recursion we will stop recursing after $W$ levels in the worst case, the space complexity becomes $\Theta(N + WR)$

however what about time? Just from space itself, it seems like MSD is actually pretty bad. What can you say about the time? To me it looks like you will have to spend $R$ operations for every node in your recursion tree and also $N$ operations per every level. So the time is $\Theta(NW + R*amountOfNodes)$.

I do not see how and why MSD would ever be preferred in practice given these time bounds. They are pretty horrible, but I am still not sure whether I get the time bounds in a correct way, for instance I have no clue how big is amountOfNodes..

Keep in mind that I would like the analysis to be in terms of R and N. I know that in practice R is usually small so it's just a constant, but I am not interested in this scenario, since I would like to see how much does R affect the performance as well.

I asked a kind of similar question yesterday but I did receive any replies, I think the reason for that was because my question was not well structured, so I could remove this question if the admins wanted. Thank you in advance!


texts: What's the difference between transdichotomous model and RAM?

texts:
In Wikipedia, it says

  the transdichotomous model is a variation of the random access machine in which the machine word size is assumed to match the problem size.

However, a random access machine is by definition a register machine, whose registers can store any non-negative number.

In addition, the concept of "word" is even not mentioned in the Wikipedia page of random access machine.

So what's the difference between transdichotomous model and RAM?


texts:
this may be a shot in the dark, but I am trying to teach myself more machine learning concepts. I have found a textbook and am trying to work through the exercises in it. Could anyone help me with this example?

Example:

Use genetic algorithm to solve the following optimization problem, including the initialize population, fitness function and each iteration until you find the optimal solution.

max f(x1, x1) = 2x(1)^2 + x(2)^2 + 3x(3)^2

s.t.     x1 ∈{0,1,2,3,4,5,6}
         x2 ∈{0,1,2,3,4,5,6}
         x3 ∈{0,1,2,3,4,5,6}

Any information that anyone could give me or even resources that work through examples like this would be greatly appreciated.
Thanks.


texts: Algorithm for DFA accepting any string with ending with a particular substring

texts:
Is there any possible general algorithm for constructing a DFA such that it accepts any string, which has a given sub-string in the suffix(end) for any given language. The algorithm should directly construct the DFA transitions, and not create an NFA first and then convert it to a DFA. In other words, the algorithm accepts the suffix as input, constructs the transitions for each state and then process the input string.

Ex 1: Language: {a,b}, Suffix- abab, Accepted Strings - bbbabab, aaabbabab
Ex 2: Language: {a,b}, suffix- babab - Accepted Strings - bababab, aababab


texts: Exercise: Sliding window protocol: Bits for sequence number

texts:
This is a task in a lecture on computer networks:

"Suppose you are designing a sliding window protocol for a 1-Mbps point-to-point link to the moon, which has a one-way latency of 1.25 seconds. Assuming that each frame carries 1 KB of data, what is the minimum number of bits you need for the sequence number?"

R = 1-Mbps = 125KBps

d_prop = 1.25 sec  so I assume RTT = 2.5 sec

The solution I was given ignores the transmission delay but I calculated it to be

d_trans = 1KB/125KBps = 0.008s

Within one second you can put 125 frames into the link if you allow full utilization.
I assume the task ignores the size of the acknowledgements as well as the processing and transmission delay of the receiver for simplicity.
Nothing else is said about the links properties.

Since within 1 second you could send 125 frames, within 2.5 seconds you could send. 312.5 frames. If we include the senders d_trans then within 2.508 seconds we could send frames 313.5 frames until the acknowledgement for the first frame should be received. If you complete the LastFrameSent then I think you should need a send_window_size(SWS) of 314 to acknowledge each frame individually.
In this case you would need Ceil(log2(314)) = 9 bits for the sequence numbers.

The solution given by the tutor says that you need at least 10 bits and part of the explanation I noted down is that (ignoring d_trans) you can send 312 frames until the first frame is received. And then you can supposedly send another 312 frames until you receive the first ACK back, so you'd need a SWS of 624.

So did I misunderstand anything about the task or did the tutor make an error by doubling the one-way-latency (which I assume to be the same as d_prop) twice?
Can additionals assumptions be made regarding the properties of the link?

I saw a similar question where the link was considered the be a full-duplex link (which wasn't explained in the lecture iirc). But even if you'd consider a full-duplex link which means only the half of the bandwidth may be used then you could only send ~156 frames until you get the ACK and then you'd need 8 bits instead of 10, right?

Thank you for your help.


texts: Using closure properties to show that $L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)$ is regular or not

texts:
i'm trying to figure out whether this Union $\left [  L_1=\{a^lb^mc^m|l,m\ge 0\} \cup L(b^*c^*)\right]=K$ is regular or not, now since regular languages are closed under intersection, so i assume $K$ is regular then its intersection with $L(a^*b^*)$ should be regular which is $K\cap L(a^*b^*)=L(a^*)\cup L(b^*)$ right ?

1 - Does this implies that the Union is also regular ?

2 - i know that $L=\{a^lb^mc^m|l,m\ge1\}$ is CFL, but is $L_1$ also CFL ?, which is basically  $L_1=L\cup \{\epsilon ,a,bc\}$

3 - is $K$ regular or not and how to prove it ?

Any Hints would be appreciated.


texts: Why are there so many available loopback addresses?

texts:
I don't really know whether this is the correct site where to post this question, I'm sorry if I'm mistaken.

I am studying computer networks and during the explanation of the ip protocol the professor described the reserved addresses such as 255.255.255.255, 0.0.0.0 etc.
Of course, one of such addresses was 127.0.0.1, but what he told us is that any subnet such as 127.*.*.* behaves as a correct loopback address.

My question is: is it there a reason why there are so many available loopback addresses? Is it so for historical reasons? It looks like a waste of 3 possible bytes of addresses. Why is it so?


texts: Question on word probability for hierarchical softmax used in natural language processing

texts:
I am reading the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf

On page 4 of the paper they describe the hierarchical softmax which is intended to reduce the computational complexity (I believe only during training time) of training a neural network to learn word vectors. The hierarchical softmax output layer is a balanced binary tree.

Here is the description given in the paper for computing $p(w\vert w_I)$ (where $w_I$ is the input word or set of words, and $w$ is the missing word we are trying to predict):

More precisely, each word $w$ can be reached by an appropriate path from the root of the tree. Let $n(w,j)$ be the $j$-th node on the path from the root to $w$, and let $L(w)$ be the length of this path, so $n(w,1)=root$ and $n(w,L(w))=w$. In addition, for any inner node $n$, let $ch(n)$ be an arbitrary fixed child of $n$ and let $\lbrack x \rbrack$ (can't figure out how to generate brackets used in paper) be $1$ if $x$ is true and $-1$ otherwise. Then the hierarchical softmax defines $p(w_O \vert w_I)$ as follows:

$$p(w\vert w_I) =\prod_{j=1}^{L(w)-1}\sigma(\lbrack n(w,j+1)=ch(n(w,j))\rbrack \cdot v_{n(w,j)}'^T v_{w_I})$$

where $\sigma(x) = 1/(1+\exp(-x))$.

Now, I understand that we are using the sigmoid function to essentially "squish" the dot products of our two vector arguments in values between $0$ and $1$ (i.e. probabilities). But, I don't understand the user of the indicator function in this equation. Going down the tree I feel like we should be multiplying probabilities at each branch, and somehow I know the indicator function must be "steering" us down the tree, but I cannot tell how. Intuitively, I feel like it would be more appropriate to have an indicator function that outputted $\sigma(x)$ or $(1-\sigma(x))$ based on left or right turns.


texts: Given a language L what can we say about the decidability of whether this language is regular or not?

texts: Can we develop a turing machine which on given a language L as input gives as output whether this language is regular or not?


texts:
I have read about the N-queens problem and I don't understand the following objective function:

$O(board)=N^2/2-L$

$N$ ... number of queens
$L$ ... number of pairs of queens that attack each other

Why they use $N^2/2$? They wrote that it is the number of pairs of queens but I don't understand that can someone maybe explain it to me maybe with visualization


texts: Why databases make the distinction between basic logical operations and functions

texts: It just occurred to me that things like "greater than or equal to" and other "logical operators" are also just simple functions, such as gte(a, b) == a >= b. This makes me wonder why these are treated as "special" in databases and why they are not just functions like SQL functions. Wondering if there is some advantage to treating them differently like they do.


texts: What is the global function we are trying to Optimise with Clustering Algorithms?

texts:
I am doing some reading (and implementation) of some Clustering Algorithms.

First I started with the well known K-Mean algorithm and implemented it directly from a paper.
Got a kind of decent understanding of what I going on there.

What I am actually interested in is Particle Swarm Optimisation based clustering.

For Particle Swarm Optimisation, you need to have a global fitness function that will (in this case) tell you how well clusters this is.

The general notion of well clustered I have found is that each cluster is compact.
But how to express this mathematically?

I thought that we would go though each cluster and check its positional variance (away from its centroid).

For some cluster C
 :

$$\mu(C)=\dfrac{1}{|C|}\sum_{\forall\tilde{x}\in C}\tilde{x}$$

$$\sigma^{2}(C)=\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

No point converting to standard deviation, unless using a gradient based optimization approach, which PSO is not.

then the global fitness would be to minimize the average variance, which is proportional to minimizing the total variance since we have a fixed number of clusters.

if $S$ is the set of all clusters the we are to minimise some function $g$.

$g_{mine}(S)=\sum_{\forall C\in S}\sigma^{2}(C)$

ie  $$g_{mine}(S)=\sum_{\forall C\in S}\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

According to Chen, C.-Y. & Ye, F. Particle swarm optimization algorithm and its application to clustering analysis Networking, Sensing and Control, 2004 IEEE International Conference on, 2004, 2, 789-794

Equation 7 (Rewritten to use my notation)

$$g_{chen}(S)=\sum_{\forall C\in S}\sum_{\forall\tilde{x}\in X}(\tilde{x}-\mu(C))
 $$

The difference from what I had is the $\forall\tilde{x}\in X$, for $X$ the whole spaceof data rather than $\forall\tilde{x}\in C$.

This is what got me wondering if I was correct in the first place.
as it can be seen that $g_{mine}\ne g_{chen}$. It can't since the extra points are going to change it and will not cancel since all variances are positive.
However they are equivalent if $\forall S, S'$ $g_{mine}(S)\ge g_{mine}(S') \iff g_{chen}(S)\ge g_{chen}(S')$

In:
 Ahmadyfard, A. & Modares, H. Combining PSO and k-means to enhance data clustering Telecommunications, 2008. IST 2008. International Symposium on, 2008, 688-691

Equation 6 has: (again with notation switched)

$$g_{ahmadfard}(S)=\dfrac{1}{|X|} \sum_{\forall C\in S}\sum_{\forall\tilde{x}\in C}\left(\tilde{x}-\mu(C)\right)^{2}$$

This is equivalent to mine (at least in proportionality) as:  $|X| \times g_{ahmadfard}(S) = g_{mine}$, and since $|X|>0$ thus $\forall S, S'$ $g_{mine}(S)\ge g_{mine}(S') \iff g_{ahmadfard}(S)\ge g_{ahmadfard}(S')$

Ye and Chen also came up with another function in:
Ye, Fun, and Ching-Yi Chen. "Alternative KPSO-clustering algorithm." Tamkang Journal of science and Engineering 8.2 (2005): 165.
It is very complicated and beyond the scope of this question

What are the pros and cons of $g_{chen}$ vs $g_{mine}$ vs $g_{ahmadfard}$ ?


texts: Directed Acyclic Graph partition into minimum subgraphs with a constraint

texts:
I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number  of subgraphs with the following 2 constraints:-

A sub-graph should have nodes of similar color
A sub-graph cannot directly or indirectly depend on it's own output

Example:- In the attached picture, the sub-graph with yellow nodes is invalid since input from the red node breaks rule#2 : 4th node from top has an input which depends on output of 2nd node - via the red node (outside the sub-graph)
Hence the algorithm should partition it after #2 or #3 so that 2 and 4 are on different sub-graphs

Am sure this is a pretty common problem in Graph theory and must have a name and a standard algorithm for it. Thanks in advance for any pointers to it!


texts: What is instruction throughput and instruction latency?

texts:
I was reading an article on an alternative method of modulo reduction and i couldn't understand the following excerpt (Those in bold) :

"A single 32-bit division on a recent x64 processor has a throughput of one instruction every six cycles with a latency of 26 cycles. In contrast, a multiplication has a throughput of one instruction every cycle and a latency of 3 cycles."


texts: How does literals in compiled languages differ from literals in interpreted languages?

texts:
A literal is a piece of data which gets its value at compile time.

Means: Becomes set at compile time and afterward the value is fixed incorporated into the machine code as a code consisting out of 0s and 1s.

What are literals in interpreted languages like for example JavaScript?

As far as I know the code within JavaScript functions aren't touched by the interpreter until it becomes executed.

Can one say that literals exists in these languages? regarding my definition of a literal (first paragraph).


texts:
If the main memory address has 18 bits (7 for tag,7 for line and 4 for word)
and each word is 8 bits.
I found that the main memory capacity is 256-KBytes, total cache lines is 128 line,
total cache words is 128*16(16 word per block/line) = 2048 words.
Then what will be the size of cache words?
I am very confusing on it. I can't get the definition of cache words.
Can anyone tell me what is the cache words?
Thank you!


texts: Show that PTIME and PSPACE is closed under Klenee star

texts: How to show that PSPACE and PTIME are closed under Kleene star ?  I can only show that NP is closed, but it is easy because we can use non-determinism to guess partition of word. In these two cases I don't have idea how to attack it.


texts: Proving that language is regular or not regular

texts:
Let $L$ be a regular language. Prove that:

  $L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$
  $L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$
  $L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$

  are regular and:

  $L_{+-+}=\left\{ uv:\exists_w |u|=|w|=|v| \wedge uwv\in L \right\}$

  is not regular.

Seems very hard to me. I suppose 1-3 are similar (but I may be wrong), but I don't know how to approach. General idea is usually to modify finite state machine for $L$ to accept other language. But those constructions are often very sophisticated and I still can't come up with it alone.


texts: efficiently calculate nearest common ancestor in a family tree (each person has two parents)

texts:
I'm well aware of ways to efficiently calculate the lowest common ancestor in a tree of nodes which converge to a single root (ie, each node has only one parent).  Just iterate back to root for each person, then walk back from root tossing off anything common.

In a matriarchal society, for example, this could be used to quickly calculate how any two people are related as long as only the mothers are considered.

But if both parents are considered, eg mother AND father, then the algorithm just described breaks down.

So I wondered is there an algorithm to tell two people how they are related in a family tree where both parents are considered?  For example, see the Icelandic genealogy app (https://www.islendingabok.is/) which does precisely that.  How's it done, algorithmically speaking?


texts:
Input : $x \in \mathbb Z$ and $a_1,a_2,\dots,a_n \in \mathbb N$.
Output : $b_1,b_2,\dots,b_n \in \mathbb Z$ such that $\sum_{i} a_i b_i=x$ and $\sum_{i}|b_i|$ is minimized.
Main question is, can we solve this problem with greedy or parallel algorithms?


texts: I'm on second year IT studies. I can't do this on my own and my teacher is not eager to help. I went that way but I'm pretty sure it's wrong. Please, help :/


texts: A problem about master theorem and recursion

texts:
Prove or disprove the following statement:
If $f(n)\in \Omega(n^2)$ and $T(n) = 2T(n/2) + f(n)$ then $T(n) \in O(f(n))$.
I think that the statement is false.
Do you know any counterexamples?


texts: pseudo clique with at least connectivity x and maximum weight of the nodes

texts:
Let $G=(N,E)$ be a undirected graph of nodes $N$ and edges $E$. Each node $n \in N$ has a weight $w(n)$. The weight of a graph is defined as the sum of the weights of its nodes, i.e., by $w(G) = \sum_{n \in N}w(n)$.   The connectivity of the graph is defined to be $c(G) = \#E_G / (\#N_G \cdot (\#N_G - 1)/2)$ -- this measures the fraction of edges in comparison to the maximum possible number of edges.

Given $G$ and a number $x$, I want to find the maximal-weight subgraph $G'$ which has at least connectivity $x$, i.e., I want to find $G'$ that makes $w(G')$ as large as possible, subject to the requirement that $G'$ is a subgraph of $G$ and $c(G') \ge x$.  This looks like some kind of generalization of the clique problem; here I essentially want to find a "pseudo-clique".  Is there any efficient algorithm for this problem?


texts: Prove that every regular subset of $a^nb^n$ is finite

texts:
How to prove that every regular subset of $L=\{a^nb^n \mid n\ge0 \}$ is finite?
I know that every finite language is regular, and it's not true that every regular language is finite.
I also know that $a^n b^n$ is non-regular language.
I can find examples of finite regular subsets of $L$, for example $\{\epsilon, ab, aabb\}$, but how do I prove that all regular subsets of $T$ are finite?


texts:
Is existence of registers in CPU an obligation, Or we just do it for performance?

Can we theoretically and practically have computer architectures that don't use registers?
If yes, please name computer architecture and computer models that doesn't have register.

Update: Do stack machines use register? If yes, is it possible to have stack machines without registers?


texts:
I'm not sure the best way to name this problem, but basically I need to construct a complete $k$-ary tree for $k \geq 2$ which has this nice property as $k=1$ tree that we can create a ring out of it.

For example, to construct $k=1$ suppose $N$ is the number of nodes. If for each node $x$ ($\in 0..N-1$), we pick the child as (x+1) % N. Then picking any $r$ as the root, the tree remains the same structure except for there is no connection between $r-1$ and $r$ (modulo $N$). Each node has the same parent or no parent and has the same child or no child for all possible root.

For $k>2$ there is no such construct that I can find. Suppose just $k=2$ . If I arrange the binary in which $x$ has two children (x+1) % N and (x+2) % N. It doesn't give a correct tree with all the nodes anymore.

Another way is to do (((x-r)%N)*2+1 + r) % N and (((x-r)%N*2+2 + r) % N which gives a correct tree, but seems like there is $N$ possible choice of parent/child depending on root, the structure dramatically different all the times.

In other words, given an unknown root $r$, give $x$, it's still possible to know the possible connecting nodes (or bounded the number of connecting nodes < $O(N)$)

Another attempt to clarify this question -- an equivalent problem: I need to create a connected graph of out $N$ node, such that when given a node $r$, I can create a complete $k$-ary rooted by $r$ tree by removing some edges out of the graph. Obviously with a complete graph this is possible, can we create a graph in which each node connects to only $O(k)$ other nodes?

This works for $k$=1 with a line-graph.


texts: I am trying to understand what is the hardware structure of the row buffer in the main memory. If there can be any shift operations or any other opeartions that can be made on the row buffer? Also, any in-depth material/reference for this will be appreciated. Thanks!


texts: Algorithm for finding the set of minimum coordinate pairs

texts:
Consider these two sets of coordinate pairs with weights:

| set 1           |    | set 2           |
| (1,0) - (0,1) 1 |    | (1,1) - (1,1) 2 |
| (0,1) - (1,1) 4 |    | (0,0) - (0,0) 1 |
| (1,1) - (0,0) 3 |    | (1,0) - (1,0) 3 |
| (0,0) - (1,0) 8 |    | (0,1) - (0,1) 6 |

Each set has the properties:

A coordinate is a 2-tuple, which is a point in a Euclidean plane, more specifically it is the position of each element of a square matrix M (in this case 2x2):

[[(0, 0), (0, 1)],
 [(1, 0), (1, 1)]]

Coordinate pairs define a 1:1 unique mapping from one matrix m1 to another m2. Both matrices have the same dimensions.

The objective is to find a configuration from multiple sets of such coordinate pairs so that the properties above are not violated (e.g. (0,0) - (1,1) and (1,0) - (1,1) would be a violation), and that the best minimum possible is found for each coordinate pair, this can be thought of as the finding coordinate pairs such that the overall sum of the weights is minimized.

Solution (trivial):

| (1,1) - (1,1) 2 |
| (0,0) - (0,0) 1 |
| (1,0) - (1,0) 3 |
| (0,1) - (0,1) 6 |

What I would like to know if there is a specific name for this kind of problem (I suspect it is a combinatorial type problem), and if there is, is there a known algorithm for achieving this efficiently?


texts: i think that it's true that AM is contained in $\Pi_2$ but I'm not sure how to prove it.  How do I prove that $AM \subseteq \Pi_2$?


texts: Matching a set of paths to an incrementally generated graph

texts:
I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be potentially infinite).

The problem is to match the maximum number of edges in the paths to the smallest graph B. The matching should be such that the order in which the edges appear in the paths is preserved in the graph, and each path is matched to a distinct path in the graph. This distinctness requirement comes from the fact that each path in graph A must have a corresponding path in graph B but might not generated yet.

The graph nodes are immaterial and the edges have non-unique labels upon which matching is performed. Also, the paths to be matched can have arbitrary edges added/deleted while matching is to the graph B. If the solution does not meet a threshold (X% of edges matched), we can query an oracle, that generates a slightly bigger (i.e., more complete) graph but the goal is to minimize the queries as the graph can potentially be infinite.

Example:

Paths:
-A-> -B-> -C->
-A-> -D->

Graph:
-A-> -X-> -B-> -C->

Result:
Matched: A-A, B-B, C-C
Unmatched: D

Query Oracle (A-D?) gives resulting graph.
-A-> -X-> -B-> -C->
 |-D->

Result:
Matched: A-A, B-B, C-C, D-D

I tried to lookup standard solutions from assignment and graph isomorphism but didn’t find anything similar. So, here is a solution I came up with:

I am using a branch and bound algorithm to match every edge in the paths to every edge in the graph (M X N table). For each possible assignment, I am keeping track of which other assignments are possible containing with the particular assignment
The bounding condition (& feasibility) is defined by the same ordering of the edges in the graph as it is in the paths. Also, two paths cannot be mapped such that they violate each others ordering.
If we are not happy with this solution, we can query the oracle, get a bigger graph and repeat 1 & 2. Otherwise, the technique outputs the possible edge mappings.

My question is that I am not sure if my solution still falls under branch & bound algorithms, as it no longer follows the standard branch & bound tree structure. Also, it would be great if anyone can point out optimizations or a better way to do this.

Note: At every iteration, N changes and the table grows horizontally. The biggest inefficiency is in step #2, which needs to be recomputed at every stage for safety (e.g., a loop being added in the graph invalidates previous solutions).


texts: Optimal order placement of a good across different places when cost and quantity is unknown

texts:
I am looking for some help in devising/researching an algorithm. I have come up with some solutions on my own, but would like some guidance as to whether there exists a more formal/robust/mathematical solution.

The problem can be stated as follows:

I would like to purchase X amount of a good at as low of a price as possible.

There are Y amount of places that this good is available for sale

The price and quantity available at each particular place are initially unknown

There exists a probability that the price of a good at a place will change as a function of the amount of time since the order was placed. The distribution is skewed to the right, with a mean u

The simple solution is to query all places. Wait for all price and available quantity to be discovered. And then purchase goods from lowest price to highest price until I accumulate the desired amount.

However, this implementation leads to the problem where the price of a good can change while I am waiting for all of the quotes to come in. For example, if the price discovery from one location takes too long, it will lag the entire order process. During this time the price could have changed at a place where an order could have been completed (since the price and quantity were known and acceptable, although maybe not optimal). This will result in a worse price when compared to simply not waiting at all.

At the opposite end, I could simply fulfill an order if the price is deemed reasonable when it is discovered. This approach runs the risk that there is a better price available, and had I waited for its price to be discovered, I could have gotten my good for cheaper.

A hybrid of the two strategies would involve waiting a fixed amount of time for prices/quantities to come in, processing those, and then processing the rest as they continue to come in. I feel this is the optimal algorithm, but I am not sure how to more mathematically define the amount of time I should be waiting.

Is there a robust mathematical solution that will define the amount of time I should be waiting? Please let me know your thoughts. Thank you.


texts:
I want to construct a LOOP-computable program for the integer division (quotient):

x = a DIV b

The LOOP specification can be seen here: https://en.wikipedia.org/wiki/LOOP_(programming_language)

I don't know how to do this without a while.


texts: In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path), but what if the cost is negative, won't the search algorithm possibly trapped in infinite loops? If solution is using a closed set to track explored nodes, we will lose ability of reopening a node when less cost is seen, thus optimal might compromise.


texts: Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

texts:
This problem is based on an order picking problem with a forward area.

The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each day, there is a set $D$ of deliveries. Each delivery $d_i$ is a set of items such that $d_i \subset I$ and $|d_i| < k$. The items for each delivery have to be picked from $F$ and each delivery must be completed before the items for the next delivery can be picked. The items in $F$ are not consumed ($F$ contains pallets of each item, and we assume that a pallet does not run out). If a delivery requires an item that is not in $F$, the required item can be swapped with an existing item.

We now need to find an order $d_1,...,d_n$, such that we minimize the amount of swaps needed.

My question is: is there any available literature on this kind of problem? Specifically regarding genetic algorithms, since that is the goal of my research.

Thus far, the closest thing I have found is the Traveling Salesman Problem, using the minimum number of swaps between deliveries as distance measure. However, since the items in $F$ are not only influenced by the predecessor of a delivery, the distance between two consecutive deliveries also depends on (all) previous deliveries.


texts:
Give a randomized algorithm that takes input two $n \times n$ matrices $A$ and $B$ with integer
entries and does the following: If $A$ and $B$ are similar, then with high probability the algorithm outputs
an $n \times n$ invertible matrix $C$ with rational entries such that $CAC^{−1} = B$; otherwise it outputs $A$ not
similar to $B$. Ensure that your algorithm runs in polynomial time.


texts: Calculation of effective average instruction execution time in a 2-level paging system

texts:
System has a two level paging scheme
  Average CPU time for a instruction = 100ns
  Average number of memory accesses per instruction = 2
  Regular memory access = 150 ns
  Page fault service time = 8ms
  TLB hit ratio = 0.9
  Page fault rate = 0.0001

  What is the average instruction time if the time required for address translation is negligible?

I worked out the solution as follows

Average instruction execution time = CPU time + Memory access time

Memory access time = No. of memory accesses by the instruction * average memory access time

Average memory access time =
 [probability of a TLB hit * regular memory access time]
 + [probability of a TLB miss * (Time for accessing the 1st level of the paging tables
     + Time for accessing the 2nd level of the paging tables
     + Time for accessing memory which may not be paged in with the translated address)]

Time for accessing the 1st level of the paging tables
= Time for accessing the 2nd level of the paging tables
= Time for accessing memory which may not be paged in with the translated address
    = [probability of a page fault * (page fault service time + regular memory access time) ]
      + [probability of no page fault * regular memory access time]
    = [0.0001 * (8 ms + 150ns)]  + [0.9999 * 150 ns]
    = 950 ns

Thus, average time per memory access = [0.9 * 150ns] + [0.1 * 3 * 950ns] = 420ns

Average instruction execution time = 100ns + (2 * 420ns) = 940ns

However the choices for this question are 645ns, 1050ns, 1215ns and 1230 ns.

I can't seem to be able to see where I have reasoned wrong.

EDIT

Average number of memory accesses per instruction is 2


texts: Can a loop be expressed by only the sequence of statements and the choice of statements?

texts:
The theorem of structured programming says that any algorithm can be expressed by those three control structures:

Sequence
Selection
Iteration

Isn't it possible to rewrite any loop using a finite sequence of statements and choice between statements? Isn't this what compilers do? Can't we thus omit the third structure and stay equally expressive?


texts: Deciding whether a context-free grammar's language is empty

texts:
Consider the formal problem:

  Given a context-free grammar $G$, is the language $L(G)$ empty?

Can we determine if the problem is recursively enumerable, recursive, in NP, or in P? Can the entire procedure be explained?


texts: Quadratic probing maximum load factor with $c_1 = c_2 = 0.5$ to guarantee successful insertion

texts:
For quadratic hashing, i.e an open-addressed table with the hash function of the form -

$h(x, i)= (h'(x) + c_1i + c_2i^2) \mod m$

Setting $c_1 = c_2 = 1/2$, and $m$ to some power of 2, leads to a hash function

$h(x, i) = (h'(x) + 1 + 2 + ... +i) \mod m$

I have read that the load-factor of a quadratically probed table should not exceed $0.5$ to guarantee insertion to succeed if an empty cell exists in the table. Wikipedia's article here https://en.wikipedia.org/wiki/Quadratic_probing#Limitations says that

"With the exception of the triangular number case for a power-of-two-sized hash table, there is no guarantee of finding an empty cell once the table gets more than half full, or even before the table gets half full if the table size is not prime. "

So what is the maximum load factor that will guarantee successful insertion for this case?


texts: Fixed point, what does it mean in the world of computer science

texts:
I keep coming across references to fixed point in questions and answers at stackexchange and I look up the meaning on the web obviously finding reference at sites such as Wikipedia. However none of the references really answer my question of what is a fixed point and what does it mean in the world of computer science.

EDIT

After 8 years this finally popped into my head.

How would you explain fixed point to a kindergartner?

A fix point is when you do the same thing again and again and nothing changes. So if your room is messy and you clean it, it is now at a fixed point because if you clean it again it is still clean.

I know there is a joke or comic in there somewhere but I don't have my comedian hat on today.


texts: Find all intervals that are contained in a query interval

texts:
Given a set of intervals $S = I_1, ..., I_n$, what is the fastest way to find all intervals of $S$ that are completely contained in an interval $I_\text{query}$? It should also support incremental (dynamic) insertion of new intervals to $S$.

Interval trees are not suitable for this, since they are designed to query overlapping intervals. Similarly, segment trees are designed to query all intervals that contain a query point.

A solution would be to use an interval tree to find overlapping intervals, then use linear search and eliminate those from the results that are outside of the specified query interval.

Is there any better/faster solution for this?


texts: Linear-time algorithm to check monotonicity of polygonal chain

texts:
A polygonal chain $C$ is called monotone with respect to a straight line $L$, if every line orthogonal to $L$ intersects $C$ at most once.

I want to design a linear-time algorithm to check whether there exists a line $L$ such that a given chain $C$ with $n$ vertices is monotone relative to $L$, and find such a line.

My idea is to take an angel of monotone chain and transfer it to the unit circle and suppose there is a line L !  like this

But I don't know how to find a good solution that the L exist


texts: 1/2 Approximation to MAX-DICUT by rounding a linear program

texts:
Consider a graph $G=(V, A, w)$, where each arc $(u,v)\in A$ has a non negative weight $w_{u,v} \in \mathbb{R}^+$, partition $V$ into $U$ and $W$, $W=V-U$ such that $\sum_{(i,j)\in A} w_{i,j}z_{i,j}$ where $z_{i,j} = [[i\in U \land j \in W]]$.
By getting a randomized cut we have a 1/4 approximation:
\begin{align}
\mathbb{E}\left[\sum_{(i,j)\in A} w_{i,j} z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j}\mathbb{E}\left[z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j} \Pr(i\in U \text{ and } j\in W) \geq \frac{1}{4} OPT
\end{align}
We can instead solve an integer program to get an exact solution. Consider a randomized algorithm that solves the linear relaxation of the integer program below and puts each vertex $i$ in $U$ with probability $1/4+x_i/2$.
\begin{align}
\text{maximize } &\sum_{(i,j)\in A} w_{i,j} z_{i,j}\\
\text{subject to }& z_{i,j} \leq x_{i} &\ \forall (i,j) \in A\\
& z_{i,j} \leq 1- x_{j}                &\forall (i,j) \in A\\
& x_{i}\in\left\{0,1\right\}  &\forall i \in V\\
& 0\leq z_{i,j} \leq 1 &\forall (i,j) \in A\\
\end{align}
We can relax the integer program to a linear program by relaxing $ x_{i}\in\left\{0,1\right\}$ to $ x_{i}\in[0,1]$ for all $ i \in V$.
\begin{align}
\mathbb{E}\left[\sum_{(i,j)\in A} w_{i,j} z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j}\mathbb{E}\left[z_{i,j}\right] = \sum_{(i,j)\in A}w_{i,j} \Pr(i\in U \text{ and } j\in W) = \sum_{(i,j)\in A}w_{i,j}(\frac{1}{4}+\frac{x_i}{2})\left[1-(\frac{1}{4}+\frac{x_j}{2})\right]
\end{align}
I have trouble however going further and showing that this is a 1/2 approximation though.


texts: information theory, find entropy given Markov chain

texts:
There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below:

a) The random variable representing the $i$-th output from this information source is represented by $X_i$. It is known that the user is now in state $S_1$. In this state, let $H (X_i|s_1)$ denote the entropy when observing the next symbol $X_i$, find the value of $H (X_i|s_1)$, entropy of this information source, Calculate $H (X_i|X_{i-1}) $ and $H (X_i)$ respectively. Assume $i$ is quite large

How can I find $H(X_i|s_1)?$ I know that  $$H(X_i|s_1) = -\sum_{i,s_1} p\left(x_i, s_1\right)\cdot\log_b\!\left(p\left(x_i|s_1\right)\right) = -\sum_{i,j} p\left(x_i, s_1\right)\cdot\log_b\!\left(\frac{p\left(x_i, s_1\right)}{p\left(s_1\right)}\right)$$
but I don't know $p(s_1)$.

$$A=\begin{pmatrix}0.25 & 0.75 & 0\\0.5 & 0 & 0.5 \\0 & 0.7 & 0.3 \end{pmatrix}.$$

From matrix I can know that $p(s_1|s_1)=0.25$, etc.

But what is the probability of $s_1$?
And how can I calculate $H (X_i|X_{i-1})$?


texts: Computational power of quantum finite automata

texts:
I am preparing some lecture notes on the computational power of quantum finite automata (QFA). I am a bit confused about which models of QFA are stronger and which models are weaker than standard finite automata (FA). There is one-way QFA (1QFA) and two-way QFA (2QFA). For each model, we can either have "measure-once" (MO) or "measure-many" (MM) version. I thought MO-1QFA was stronger than FA but apparently it is not. I also thought MM-1QFA is same as one-way probabilistic finite automata. Apparently, MO-1QFA is weaker than MM-1QFA. This is a little puzzling because measure-many quantum Turing machines are same as probabilistic Turing machines. However, measure-once Turing machines are stronger than the measure-many version.

Could you please state which models are actually computationally stronger than the other? Where do we place 1-way and 2-way probabilistic finite automata (1PFA, 2PFA) in this picture?

Thank you in advance.


texts: Question about spanning trees and creating them through BFS and/or DFS algorithms

texts:
The question is as follows:
True or False: For every non-directed connected non-weighted graph and for every spanning tree T of the graph there exists a vertex v such that T is a DFS tree with the root v.

What about if instead of DFS I used BFS?

I have no clue where to begin with this one. I feel like I'm overlooking some basic characteristic of the algorithm or the tree that it produces. Any help would be appreciated!


texts: Sorting array of strings (with repetitions) according to a given ordering

texts:
We get two arrays:

ordering = ["one", "two", "three"]

and

input = ["zero", "one", "two", "two", "three", "three", "three", "four"];

We want to find the array output so that

output = ["one", "two", "two", "three", "three", "three", "zero", "four"]
// or
output = ["one", "two", "two", "three", "three", "three", "four", "zero"]

The strings (with possible repetitions) should be sorted as in the ordering array. Not found/contained strings should be put at the end of the new array and their order doesn't matter.

The $n^{2}$ solution is obvious, can we do better? The memory doesn't matter and it doesn't have to be an in-place algorithm.


texts: Computational power difference between all interconnected qubit vs few interconnected qubit

texts:
Recently I came across some news that Google and IBM are planning to  unveil a 50 qubit quantum computer. I read that in this design, each qubit is not connected to all other qubits rather only to the two nearby  qubits(neighours). In layman terms, what difference will this create in terms of the system's computational power?

I can't find the article but the architecture  image is below. Hopes that will help.


texts: Calculate the area of the shape created by multiple paths

texts:
I'm trying to write an algorithm to calculate the area created by multiple paths that can be overlapping or not. Here is an example:

Basics

4 separate paths (A,B,C,D) which are a collection of vertices (A1,A2,...)
Area desired is represented by green

Edge Cases

As shown with B, a path might have segments that don't contribute to a filled shape
As shown with C, a path might be completely enclosed by other paths and therefore should basically be ignored.
As shown with D, paths may create independent shapes
As shown with A and B, it should be a union of all the shapes

My first question is if an algorithm for this already exists. If it does, it would save me a lot of effort :). I tried searching around but I don't even know how to describe this problem concisely.
Assuming one doesn't exist for this exact purpose I have to move on to figuring it out myself. I'm assuming the right data structure for the job is a graph. I'm thinking I will add points for each intersection (highlighted in red) as I insert paths into the graph.
Then "all I need" is an algorithm for tracing around the outside of each shape because calculating the area of those irregular polygons will be simple. Does something like that already exist? My primary hangups when I think about how to do this are:

What vertex do I "start" at?
How do I account for multiple shapes (D as well as A,B,C)?
How do I account for the parts of shapes like formed by A1,A5,A5 where I'll be visiting that intersection point multiple times?

I'm not necessarily looking for a complete solution, I'd love thoughts on if you think I'm approaching this the best way so far and if you have any ideas/suggestions on how to achieve this.
Thanks in advance!


texts:
I'm reading a book from Michel Reynal called Fault-Tolerant Message-Passing Distributed Systems.
In chapter five of the book, The Read/Write Register Abstraction, I have a few questions.
On page 85, it writes about composability and that atomicity is composable, therefore atomic registers compose for free.
Now my questions are:

Are there any more descriptions about composability?
What does it mean that Atomicity is composable?
What did Reynal mean by saying that Atomic registers compose for free? What kind of costs did he mean by saying their composition is at no additional cost?
Can the proof be much simpler? I can't understand it.


texts: Is it decidable "Given a TM M, whether M ever writes a non blank symbol when started on the empty tape."

texts:
I came across below problem in this pdf:

  Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.

Solution given is as follows:

  Let the machine only writes blank symbol. Then its number of configurations in the com computation on w is q × 2, where q is the number of states of M; the factor 2 is for the choices re. the direction of heads movement; there is no factor for the written symbol because that is always blank. So the problem is decidable, decided by the following machine: input (M,w), run M on w for q × 2 steps; if it M ever writes a non blank symbol, stop with yes answer; if M never writes a non blank symbol, stop with no answer

Doubts:

Q1. How be sure all q x 2 configurations will happen while running q x 2 steps on w? Some configuration may get repeated in q x 2 steps.

Q2. Question says "when started on the empty tape", but the answer tried to simulate  TM on non empty string w. How does it makes sense?


texts: Converse proof for random coding capacity of AVC

texts:
I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof itself is quite dense (using Lemma 2 in the paper).
I am wondering if there is any work that proves the converse of AVC random coding capacity (shared randomness). If anyone can write the proof here then that works as well. I am ok with a proof for deterministic coding capacity of AVC as well if it is different from the above-mentioned paper.


texts: How can I identify that a restricted variant of Boolean SAT remains hard or not?

texts:
While I was studying SAT problem and its different instances, in Algorithms for the Satisfiability (SAT) Problem: A Survey by J. Gu et. al PDF, I came up with this variant (not mentioned there, but I though of it) and searched, but could not find anything useful.

Consider this variant:

  Suppose $f$ is a boolean function in $n$ boolean variables, but with this extra property, that $f$ is increasing. I have thought of $n$ boolean variables, $X_1, \ldots, x_n$ as representation of subsets of a set with $n$ elements, and if some  subset like $X$ satisfies $f$, then all $Y$ s.t. $X \subseteq Y$ satisfy $f$, too. What I want is finding the collection of all minimal $X$ where $f$ satisfies each of them, but not any $Z$ where $Z \subsetneq X$?

Is this problem still hard?

If I consider the $x_1, \ldots, x_n$ as a number, then increasing property of $f$ helps solving it in polynomial time, just a binary search suffices! So, I made it a little bit harder.

Any help, even offers of search terms is appreciated.


texts: DCEL operations on quad-edges, Twin, Next, and Prev

texts:
Suppose I have a quad-edge data-structure, and I want to be able to perform the operations of DCEL (twin, next, prev) on the quad-edge data structure. Let the current edge I am operating on be e. I know that e.twin would simply be e.rot.rot. I am just unsure about next and prev.

(Quad-Edge visualization given below.)

next should be equivalent to Lnext in the picture. Thus I tried to derive it and got e.rot.rot.rot.Onext.rot. prev should be equivalent to Lprev, which is the twin of Onext, i.e. e.Onext.rot.rot.

Is this correct? I am using quad-edges to prove properties on half-edges, so I want to make sure I got the basics correct before I proceed.


texts:
Given two binary heaps, each represented by a binary tree with 2k-1 elements, design an algorithm to merge the two heaps into one heap in linear time.

I've been having some difficulty in solving this problem. One thing I have thought of is traversing one of the trees using a tree traversal algorithm and adding each element to the other tree. The complexity for the traversal should be O(n) while adding to a binary tree is O(log n). One thing I'm not sure of is, would this method be O(n log n) or O(n) + O(log n)?

Another thought I had was to take the elements from the trees and put them into a sorted list. I would then create a binary tree from that list. Creating either a min or max-heap from a sorted list seems like it would be O(n) since insertions are O(1). Is that true or am I making an error in my thinking?


texts: What kind of math problems can be solved by automated theorem provers?

texts:
Can I prove following statements with using available automated theorem provers?

$(a+b)^2=a^2+b^2+2ab$.
If $ 11 \mid 2a-3b$, then $ 11 \mid 7a-5b   $.
If $ ax^2+bx+c=0$, then $x=\frac{-b\pm\sqrt{b^2-4ac}
}{2a}$.
If $a$ is even then $4a$ is even.

and so on!

I am asking this question because I just found the application of Automated theorem provers in proving theorems in logic.


texts:
For this question, I have tried everything that I can think of, but cannot solve it.  What I want to do is iterate over all possible values of $z_1$, but every method I use, it requires me to know what $p(m|z_1)$ will be for various $z_1$ values.  Thus I am stumped and looking for help.

  A robot applies the so-called simple counting approach to build a grid
  map of a 1D environment consisting of the cells $_0,\ldots,c_3$.
  While standing in cell $_0$, the robot integrates four measurements
  $_{_0}, \ldots, z_{t_3}$.
  After integrating these measurements, the resulting belief of
  the robot with regards to the occupancy of the four cells is $_0 = 0.25$,
  $_1 = 1.3$, $_2 = 0.5$, $_3 = 1$. Given the three measurements $_{_0} = 0$, $_{_2} = 3$, $_{_3} = 1$, compute the value of the measurement $_{_1}$.


texts: Need help understanding this optimization problem on graphs

texts:
Has anyone seen this problem before? It's suppose to be NP-complete.

  We are given vertices $V_1,\dots ,V_n$ and possible parent sets for each vertex. Each parent set has an associated cost. Let $O$ be an ordering (a permutation) of the vertices. We say that a parent set of a vertex $V_i$ is consistent with an ordering $O$ if all of the parents come before the vertex in the ordering. Let $mcc(V_i, O)$ be the minimum cost of the parent sets of vertex $V_i$ that are consistent with ordering $O$. I need to find an ordering $O$ that minimizes the total cost: $mcc(V_1, O), \dots ,mcc(V_n, O)$.

I don't quite understand the part "...if all of the parents come before the vertex in the ordering." What does it mean?


texts: 1D Peak-finding problem, how to derive the formula?

texts:
I couldn't find a good answer to how this formula was derived for the divide and conquer algorithm in a 1D Peak-Finding problem.

About the problem

Basically, there's an array of numbers and we want to find a peak in this array (a peak is a number higher than the two numbers to the left and right of it).

The formula

  $T(n) = T(n/2) + \Theta(1)$

I watched the MIT video on "1. Algorithmic Thinking, Peak Finding" but the formula was just written as though it was something really obvious. I guess it might be, anyone kind enough to explain it?

I can sort of guess that $n/2$ comes from the fact that we are always choosing only one side of the array, but this is really just a guess and I get totally lost when suddenly the formula is expanded and we get

  $\Theta(\log_2 n)$

instead...


texts: Expressing pseudo-polynomial runtime solely in terms of the input size

texts:
In case we have an algorithm which is pseudo-polynomial and runs in  $O(n^2C)$ for some $C$ that is encoded in binary. Is it correct to say that if $C=2^n$  then $O(n^2C)=O(n^22^n)$
and because $n=\log C$ we can write that $O((\log C)^22^n)=O(2^n)$ because $2^n$ grows more rapidly than $\log C$?


texts: Using Rice's theorem to prove undecidability of $E_{TM}$

texts:
I saw this proof and I wondered if I could prove $E_{TM}$ with Rice's theorem similar to the one described in the answer. Can you do the same thing by letting $M$ to only accept empty strings? (the $M$ that is described in the answer of the proof)
So

If $x$ is empty, accept

If $x$ is any non-empty string, reject.


texts: Find the smallest group of numbers with sum bigger then $X$

texts:
Given a list of numbers $S$ where $0 < s_i < 100$, find the minimum sum group of numbers with a sum bigger than $X$.
Each number can be used multiple times.
Ex: for $S = [3,4.1], X = 10$ the solution is $[3, 3, 4.1]$
Is it a known problem? What will be the best way of solving it?
For now, my best solution is to randomly pick numbers and repeat the process multiple times.


texts: Time complexity of $\sim c \cdot n^3$ with a computer which is 10 times faster

texts:
I am trying to solve the following question

  There's an algorithm with time complexity $\sim c \cdot n^3$. Suppose
  there's another computer which is 10 times faster. How much bigger can
  our $n$ be to be solved in the same time?

My answer so far is $\sqrt[3]{10}$.

$n^3$ can be 10 times bigger, so I have to multiply N with $\sqrt[3]{10}$. Is my conclusion correct or is there a fault in my reasoning?


texts: Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

texts:
The following is an excerpt from a material on NP-Theory:

"Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a
path from s to t using edges of G, on which each vertex of G appears once and only once. By
HAM-PATH we denote the problem of determining, given G, s and t, whether G contains a
Hamiltonian path from s to t. I now explain a reduction
HAM-PATH < HAM-CYCLE.
Let G, s, t constitute an input for HAM-PATH. We want to convert it to an input G′ (an
undirected graph) for HAM-CYCLE. We add a new vertex u to the vertex set of G in order
to obtain the vertex set for G′. The edges of G′ are all the edges of G plus two extra edges
(u, s) and (t, u). I leave it to the reader to visualize that G′ contains a Hamiltonian cycle if
and only if G contains a Hamiltonian path from s to t."
I am confused as to why do we need to add a vertex u to create G′. Why can't we simply connect s and t and then check for a Hamiltonian Cycle. If it exists, then a path would also exist(as path is a sub-graph of cycle in an undirected graph) and we would be done. What am I missing? I am specially asking this for undirected graphs. I am clear about directed graphs that existence of cycle having s and t does not guarantee Hamiltonian path.

Illustrations or counter examples are welcome!


texts: Find every edge for which every s,t-path in a DAG goes through that edge

texts:
Given a connected sourced/sinked directed acylic graph $G = (V, E \subseteq V^2, s \in V, t \in V)$, we want to enumerate the edges $e \in \mathsf{Bottleneck}(G) \subseteq E$ for which every $s$,$t$-path contains $e$. I don't actually know the real name for this notion; so I'm calling it the "bottleneck set", but when I google that I get unrelated concepts.
An obvious solution is for each edge $e \in E$, run DFS on $G$ to get all $s$,$t$-paths, and check each one for whether it contains $e$. If all of them do, then $e$ is part of $\mathsf{Bottleneck}(G)$. However, this has runtime $O(E(V + E))$. Is there a faster way?


texts: What are appropriate isomorphisms between formal languages?

texts:
A formal language $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$, that is, a set of words over that alphabet. Two formal languages $L$ and $L'$ are equal, if the corresponding sets are extensionally equal as subsets of $L\cup L'$. One can use languages in complexity theory to formalize the concept of a "problem." One could complain that "in general" extensional equality is undecidable, but I believe this would be misguided.

I'm pondering the following problem since some time: Two languages $L$ and $L'$ over alphabets $\Sigma=\{a,b\}$ and $\Sigma'=\{c,d\}$ (where $a$, $b$, $c$ and $d$ are distinct letters) can never be equal, even if they describe "exactly" the same "problem." But they should be isomorphic, if they really describe "exactly" the same "problem." What I would like to know are possible notions of isomorphism appropriate for complexity theory. I initially thought a computationally weak "translator" like a finite-state machine could be used to define the allowed isomorphisms, but this already seems to break down for trivial syntactic translations between equivalent logical formulas. (See for example this table with the syntactic definition of the dual $A^\bot$ in linear logic.)

Today I had the following idea: A definition of the language corresponding to a certain "decision problem" often has two parts: (1) An encoding of the allowed problem instances as finite strings of symbols, and (2) a definition of the "accepted" problem instances which belong to the language. If the checking whether a given finite string of symbols is an encoding of an allowed problem instance already requires a machine computationally stronger than a finite-state machine, then this stronger machine should also be used for the definition of the allowed isomorphisms.

  Questions: Has this line of reasoning any chance of "resolving" my problem? Has my problem already been solved, so that I just need to read the right references? Does my problem itself makes any sense, or is this just as misguided as complaining about undecidability of extensional equality?

Edit (not an answer yet) I noticed that "(1) An encoding of the allowed problem instances as finite strings of symbols" already contains the (hidden) assumption of a normalized input. Without this assumption, two different finite strings might correspond to the same problem instance. Instead of checking whether a given finite string is valid, the checking might produce a normalized input (and map invalid strings to a special string).

This setting has the advantage that the machine doing the checking/normalization is already equipped with means to transform finite strings to other finite strings. The allowed machine (complexity class) for this task could be part of the problem definition, and the (iso)morphisms would use the same machine (complexity class). (The suggestion of "poly-time many-one reductions" from Raphael's comment would then indeed be one possibility for problems in $\mathsf{P}$.)

A drawback is that this way of specification might only be appropriate for deterministic machines. Non-deterministic machines might require more flexible ways to specify/decide whether two input strings correspond to the same problem instance.


texts: Single big BST vs multiple smaller BSTs? Which is faster for search?

texts:
Lets say that I am storing 10^9 keys in a single BST.
Compared to having lets say having multiple BSTs of sizes 10^6 containing chunk of the bigger tree? Search through all of them executing in parallel.

I am talking about only search performance here, Given that processing power is not a bottle neck.


texts: Confusion in the solution to first readers-writers synchronization

texts:
I am studying the solution to “First Readers-Writers Problem” from the book Operating System Concepts (9th edition) and it describes:

  First readers–writers problem, requires that no reader be kept waiting unless a writer has already obtained permission to use the shared object. In other words, no reader should wait for other readers to finish simply because a writer is waiting.

And what I have understood from this is that if there is any reader running and a writer comes, then that writer would be blocked until reader has completed. But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer.

First of all please correct me if I am wrong here. But if am right, then what I have understood is that, the code for  the reader below does not guarantee this.

Code for reader-writer is given below:

//data structures
semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

//Code for writer
do {
   wait(rw_mutex);
   . . .
   /* writing is performed */
   . . .
   signal(rw_mutex);
} while (true);

//Code for reader
do {
   wait(mutex);            //Line 01
   read_count++;

   if (read_count == 1)
      wait(rw_mutex);      //Line 02

   signal(mutex);
   . . .
   /* reading is performed */
   . . .

   wait(mutex);            //Line 03
   read_count--;

   if (read_count == 0)
      signal(rw_mutex);    //Line 04

   signal(mutex);
} while (true);

Now suppose following sequence of events occurs:

Suppose a first reader comes and it blocks the writer on the line mentioned as Line 02 in comments.
Then a writer comes which is waiting for rw_mutex.
Then the first reader is executing the code line mentioned as Line 03 in comments and it has locked the mutex semaphore.
At the same time a second reader comes and it starts waiting on the line mentioned as Line 01 in comments.
Now when the first reader executes Line 04, it releases the lock on rw_mutex and the writer which was waiting in its while loop is unlocked now and starts executing.
The second reader will be unlocked when the first reader executes the line after Line 04 that signals the mutex semaphore.

Now if we see the overall flow, then the writer runs before the second reader. So does the code logic work the same as described above?

Please correct me if I am wrong.


texts:
If two CFG's differ only in what names they use for their non-terminals, are they different?

For example, are these CFG's different:
$$\begin{align*}
S &\to A  \\
A &\to a \end{align*}$$
and
$$\begin{align*}
S &\to B  \\
B &\to a
\end{align*}$$


texts:
I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance.

My problem

I have a set of elements (that I would describe as a graph) that may be of three categories:

Provider nodes
Consumer nodes
Interconnections between nodes

Each node can have one or more interconnections tied to it.

My goal is to correlate each consumer to a set of providers to whom is connected, both directly through an interconnection or indirectly through multiple hops from one consumer to the other. Indirect interconnections can't go through a provider, only a consumer.

Our current approach is to analyze this graph starting with providers, hopping through interconnections recursively until a all unvisited consumers are hit. We then take this "island" of consumers bordered by a set of producers and assign these producers to each consumer we visited.

The approach gave us the right results but at a very high cost, in terms of time spent analyzing the graph.

Do you have any suggestion for an algorithm that can come in handy to solve this problem? I would also consider alternative data structures to hold our input (right now they are a set of tuples in a relational database describing the correlation between nodes and interconnections).


texts: Showing Optimal Substructure for Stacking Boxes DP Problem?

texts:
I am having trouble wrapping my head around the Stacking Boxes dynamic programming problem, and understanding how it has optimal substructure and overlapping subproblems.  If it has the optimal substructure and overlapping subproblems, then I can use dynamic programming to solve the problem. How do I know that the stacking boxes exhibits the optimal substructure?

I have read that it is similar to the longest-increasing-subsequence problem which exhibits optimal substructure and overlapping subproblems, but I am unable to see how it relates to the stacking boxes problem.


texts: Determining the classification of languages

texts:
$L_0 = \{ \langle M, w, 0 \rangle \mid \text{$M$ halts on $w$}\}$
  $L_1 = \{ \langle M, w, 1 \rangle \mid \text{$M$ does not halt on  $w$}\}$

  $L = L_0 \cup L_1$

I need to determine where in the hierarchy of languages (recursive, recursively enumerable, not recursively enumerable) $L$ and its complement $\overline L$ belong. I reasoned as follows

$L = \{ \langle M, w, x\rangle  \mid \text{$M$ halts on $w$ when $x=0$, $M$ doesn't halt on $w$ when $x = 1$, $x \in \{0, 1\}$}\}$

$L$ is clearly not recursively enumerable as a Turing machine wouldn't be able accept in all cases.  It can accept only in case the input refers to $L_0$, but can't in case the input refers to $L_1$.

$\overline L = \overline L_0 \cap \overline L_1 = \emptyset$
Thus $\overline L$ is recursive.

Is my reasoning ok? This is a question from a previous exam paper.


texts: How does the Spark M7 “Concurrent Fine-grain Memory Migration” benefit a garbage collector?

texts:
Sun has been making a lot of noise about the Spark M7 and its inbuilt support for the java garbage collector.   However there seem to be very little easy to find information about it.   Please can someone explain what is so great about “Concurrent Fine-grain Memory Migration”?

Does the M7 cpu have any other novel ways of helping a garbage collector?


texts: How are replacement policies implemented?

texts: Suppose there is a set-associative cache using LRU or ARC replacement policy. What implements these policies? Is it a hardware module or is there a soft doing this?


texts: If a language is context free, then its complement is decidable

texts:
I am having a bit of trouble figuring this out. If L is context-free then we know it is decidable. The class of decidable languages is closed under complement thus, $L$ $\cap$ $L^{c}$, therefore $L^{c}$ is decidable.

Does this make any sense?


texts: Language grammar correction with supervised learning

texts:
I want to work on automatic grammar correction using machine learning (possibly using recurrent or deep neural networks). The algorithm will be supplied with both corrected and initial documents for supervised learning.

I am now looking for some survey or research papers to start with. I have searched and downloaded tens of articles but none of them seems related.

I would appreciate if someone could provide a few good starting points (papers, books).
also I suspect that I am not using the correct keywords for my search. I'll appreciate if you could also suggest suitable search keywords.


texts:
Below I will list a concrete example and the confusion it causes.

Let's first say we have a decision problem, which is:

"Is X <= 400?"

We define the alphabet as the set of natural numbers.

The language formed by this problem is $L = \{ w | w <= 400 \}$

We define a Turing machine, M, over the alphabet, that halts in an accepting state on any word that is in L. Ie the Turing machine recognises L.

$L(M) = \{ w |$ M halts in an accepting state on input w$\}$

Am I correct in saying that, we do not know whether this Turing machine will halt for any given input?
Since this is a decision problem, the language realised from it, will always b finite?
Am I correct in saying that we have defined this Turing machine to accept one word at a time, where the words are numbers. We could have made it accept two words, if the algorithm was modified to accept two inputs.
How would the Language be for the problem: "Is X <= Y?"
For a decision problem, the elements in the Language realised are the solutions?

I left out the notion of an algorithm, in my explanation, Is it not needed as it is implicit in the Turing machine halting on any input of L? Which means it implements some algorithm that can solve the problem?


texts: Find the number of values between i & j(given as input) in an unsorted array in O(1) time

texts:
Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j$, can we find the number of values $i<k<j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement is that the preprocessing should be $O(n)$ in both time and space.

I tried calculating an auxiliary array $B$ of size $M$ (where M is the maximum value in $A$) where $B[i]$ stores the number of elements smaller than $i$ in the given array. But for this the time and space complexities would be of order $O(M)$. Can one do better than that?


texts: Preservation of context-free languages under prefix and suffix elimination

texts:
Let $\Sigma=\{0,1\}$ be our alphabet. Let $L$ be some context-free language, which is known to start and end with 0's, meaning that every word $x$ in $L$ has a form $x=0y0$. Let $M$ be a language obtained from $L$ by deleting one starting and one ending $0$, $L=0 \cdot M \cdot 0$.

My question:

Is $M$ still context-free? It seems yes, however I can't prove it. I have tried to construct a push down automaton for $M$ from that of $L$. However, starting $0$ seems to give possibly infinite amount of configurations. So I don't know what to do.

If this question appeared somewhere, I would be grateful if you could provide a reference or a link.
Thanks.


texts: Why does 9 qubit Shor code have distance 3?

texts:
Distance of a Stabilizer code($S$) is defined by minimum weight of an element in $N(S)-S$ .

Why 9 qubit Shor code has distance 3?

Is there a way to directly see $N(S)-S$ from $S$?


texts: How exactly the "load word" instruction loads from RAM?

texts:
PS: MIPS architecture

This is a model of a memory RAM of 4GB: it has 4,294,967,295 addresses, and each address has 32 bits. Can somebody tell me why the load word instruction needs an offset to the address? My book says that the offset must be multiplied by 4, but for me, I could simply give the address of the array, and then specify which word I wanted to load by saying that the first word is the number 1, the second is the number 2...
So why I need to multiply the offset?
Update:
My book says MIPS architecture adresses bytes, not words like I thought. So... wtf? So each address of a memory RAM stores only 8 bits? Does it means that when I access a 32bit address of the RAM via the bus, the RAM outputs just 8 bits data through the same 32 bit BUS? Then,the load word instruction would have to access the RAM 4 times just to transfer the entire word to the register. I don't understand it.


texts: Why is programmed I/O not suitable for high-speed data transfer?

texts:
I am learning about computer architecture and organization.
I have read that programmed I/O is not suitable for high-speed data transfer because it does not support synchronous mode of data transmission that is a requirement for many high-speed peripherals like disk.
But programmed I/O supports synchronous mode of data transfer. I am confused. Can someone please help me?
References:
Assignment 10 question number 2


texts: What is the intuition behind a Free-Choice Petri Net?

texts:
So I've found this definition in a paper called Time and Petri Nets, Popova-Zeugmann, L., but I am unable to understand the intuition behind it.

  N is a free-choice net (FC net) if each shared place is the only pre-
  place of its post-transitions, i.e., $\text{if}\ t, t' ∈ p^•\ \text{then}\ ^•t\ =\ \{p\}\ =\ ^•t'$.

Could someone give me an example of what this allows to, or disallows to do?


texts: Conceptual question about entropy and information

texts:
Shannon's entropy measures the information content by means of probability.  Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that we are more uncertain about what will happen next.

What I would like to know is if entropy increases, does this mean that information increases?
If there are 2 signals, one is the desired and the other is the measurement signal. Let error be the difference between the two. Or error can be the estimation error in the context of weight learning.

What can we infer if the entropy of this error term decreases? Can we conclude that the error is reducing and the system is behaving close to the desired signal's behavior?

Shall be grateful for these clarifications


texts: Existence of Efficient Set Difference Algorithm

texts:
As a foreword, I'm not asking what the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great).

Basically, given two sets $S$ and $T$, I want to compute the two set differences $I = T \setminus S$ and $R = S \setminus T$. The goal is that if $S$ represents a "before" set, and $T$ an "after" set, I want to know what elements were inserted into (represented by $I$) and removed from (represented by $R$) the original set $S$ to get to $T$.

A naïve approach would be to compare every element of $S$ with every element of $T$, a worst-case runtime of $O(n * m)$, where $n = |S|$ and $m = |T|$.

An improvement would be to treat $S$ as a list and sort it, then do a binary search in the sorted list for every element in $T$. This would be worst-case (I believe) $O(n \log n + m \log n)$.

However, I think I can get it down to $O(n + m)$, and here's my thought process:

If $S$ is a list of $s_i$ and $T$ a list of $t_i$, we can define a "modification" bit for each element in each list.

If we define
$$c_i = \begin{cases} 1, & s_i \in R \\ 0, & \text{else} \end{cases}$$
and
$$d_i = \begin{cases} 1, & t_i \in I \\ 0, & \text{else} \end{cases}$$

and we define a "concatenation" sequence of the two:
$$x_i = \begin{cases} c_i, & 0 \leq i < n \\ d_{i-n}, & n \leq i < n+m \end{cases}$$

we can define a "modification" number:
$$X = \sum_{i=0}^{n+m-1} 2^i x_i$$

We can then compute $R$ and $I$ by breaking down the "modification" number $X$ into $c_i$ and $d_i$, giving
$$I = \{ t_i | d_i = 1 \}$$
and
$$R = \{ s_i | c_i = 1 \}$$.

Now, since $c_i$ and $d_i$ rely on $R$ and $I$, we can redefine them based on how $R$ and $I$ are defined:
$$(s_i \in R) \iff (s_i \in S \land s_i \notin T)$$
$$(t_i \in I) \iff (t_i \in T \land t_i \notin S)$$
So $c_i$ and $d_i$ are now:
$$c_i = \begin{cases} 1, & s_i \in S \land s_i \notin T \\ 0, & \text{else} \end{cases}$$
$$d_i = \begin{cases} 1, & t_i \in T \land t_i \notin S \\ 0, & \text{else} \end{cases}$$

Therefore, the modification number $X$ only depends on the original sets/lists $S$ and $T$. Furthermore, since $X$ is composed of $n + m$ bits, any set difference algorithm should be able to compute these bits in $\Omega(n + m)$ time. It could then compute $S$ and $T$ as described above, which would take $O(n)$ and $O(m)$ time, respectively.

My primary concern is the assumption that computing $n + m$ bits should only take $\Omega(n + m)$ time - my reasoning for that is based on the proof of the lower bound of the general sorting algorithm, and how sorting a list is similar to computing $\log_2 n!$ bits, which (from Sterling's Approximation) is $O(n \log n)$.

Again, I'm mostly interested in the validity of my reasoning, and whether or not this means a linear-time algorithm exists for computing set-differences.

An example application that I'm currently interested in (and what originally inspired this) is when a SCSI host rescans its bus for changes in device topology. Typically, it has a list of custom device objects that represent the corresponding device's current state. Upon rescan, the host gets a list of devices currently on the bus, but only by a small identifier (such as it's bus location or LUN).

The problem, then, is how to efficiently map this new device list to the existing device object list, so that unchanged devices are mapped to their corresponding objects, and any device objects whose corresponding devices have been removed can be cleaned up, and any new devices can have objects allocated for them.

If I let $S$ be the list of current devices (by their ID, with some other simple mapping from the ID to the object data), and $T$ be the results of the rescan, then I can efficiently compute $I$ and $R$, and allocate new objects for devices in $I$ and clean up objects for devices in $R$ in linear ($O(n + m)$) time.


texts: Is SAT is in NL?( under certain conditions)

texts:
Consider a certicate for 3SAT that lists an assignment for each occurrence of a variable in the order
of appearence,e.g. 100000 for ($x\bigvee$$y\bigvee$z)$\bigwedge$($\neg(w)$$\bigvee$$y\bigvee$z). This certicate is of polynomial length and can
be read once to check the satisability of the given formula. Does this prove that SAT is in NL?


texts: Looking for a use case of a $k$-$d$ tree with a norm other than $L^2$

texts:
In Python's implementation of $k$-$d$ tree
it is possible to manually change the norm used for computing distances from
$L^2$ to $L^p$.

When would one use a norm other than $L^2$ in a $k$-$d$ tree?


texts: Whats the difference between Processor bus and System bus

texts:
Is there something called Processor Bus? Whist solving one of the MCQ I ended up seeing the term "Processor Bus". Does this thing actually exists?

I did some research, but couldn't find one article that talks about Processor bus.

It would be great, if someone can guide me along.


texts:
Why is it that the test for an infinite language on the DFA $M$ has an upper bound of $2n$?

That is to say, when testing for a string of length $k$, why does the theorem say:

$$n \leq k < 2n$$

I understand the lower bound of $n$ IAW the Pumping Lemma of $|w| \geq n$. I'm just not sure why $2n$ was chosen and I think I'm over complicating it.


texts: Can breakpoints of the beachline move up in Fortune's algorithm?

texts:
In these slides describing Fortune's algorithm for constructing a Voronoi diagram, it is noted on page 7 that break points of the beach line can move upward. How is this so?

In most of the cases I can think of, break points always move downward. I couldn't easily think of a case where a break point would move upward.

Is there an example in which an upward break point is produced as sweep-line moves down?


texts: What is the level of generality of the bias-variance tradeoff?

texts:
I have just learned about the "bias-variance tradeoff" in machine learning, in the context of it being applied to simple regression models.

Now I am wondering: is this tradeoff a general universal principle that is applicable to every (conceivable) learning algorithm, or is it specific to particular algorithms, like regression?


texts: Expressing unsigned comparison through signed comparison of 2's complement

texts:
Let n > 0 be a natural number and for any two reminders a, b modulo 2^n we have that a < b iff a xor 0x800..00 <(signed) b xor 0x800...00.

It is also true that a <(signed) b iff (0x800...00 & b <= 0x800...00 & a) && (a & 0x7FF...FFF < b & 0x7FF...FFF).

Is there a way to prove the equivalence of these two propositions?


texts: How does the free program identifiers (fpi) extend over constraints and type schemes in $HM(X)$?

texts:
Chapter 10 of Advanced Topics in Types and Programming Languages; gives a very comprehensive description of type inference by constraints solving.

They introduce the free program indentifiers of an environment $\Gamma$ with the pair of equations $fpi(\emptyset) = \emptyset$ and $fpi(\Gamma;x:\sigma) = fpi(\Gamma) \cup fpi(\sigma)$.

I would like some clarification for the $fpi(\sigma)$ term.  Does it contains the set of free type variables ($ftv$)?

Specifically they say (page 408):

  The sets of free type variables of a type scheme $\sigma$ and of a constraint $C$, written $ftv(\sigma)$ and $ftv(C)$, respectively, are defined accordingly... The sets of free program identifiers of a type scheme $\sigma$ and of a constraint $C$, written $fpi(\sigma)$ and $fpi(C)$, respectively, are defined accordingly.  Note that $x$ if free in $x \preceq T$.

The last sentence seems to indicate that type variables are program identifiers.

Are there any other program identifiers? Do predicates and the name of ground types are program identifiers?

Is the result of $fpi(x \rightarrow integer)$ the set $\{x, integer, \rightarrow\}$?


texts: Is Partition Problem with non-integer input NP-complete?

texts:
The Partition Problem supposes that we have a set $S=\{s_{i} \in \mathbb{R^{+}}\}_{i=1}^{n}$, is there a subset $T$ such that $\sum_{s \in T} s = \sum_{s \notin T}s$?
I have read a lot of proofs using the Subset Sum problem: Given an integer set $S$ and an integer t, does there exist a subset $U$ of $S$ such that $\sum_{s \in U}s = t$? My problem is that most of them does not consider that the partition problem does not require the inputs to be integers, and a lot of them transform the input $S$ of the Subset Sum problem to $S\cup \{ \text{some elements} \}$ in the Partition Problem. If the input to the partition problem is non-integer, or, worse, irrational, I do not think this method works.
I have tried to reduce the partition problem to subset sum problem, by transforming the input $S$(which could be irrational numbers) to $S^{\prime} = \{ 2\lceil s_{i} \rceil \}$ and $t = \sum_{i} \lceil s_{i} \rceil$. Besides, I have also tried a few other similar ways including considering the floor function. However, whichever I tried, I could not prove that partition problem has a solution on $S$ if and only if the subset sum problem has a solution on $(S^{\prime},t)$. I do not find any contradiction if the subset sum problem has a solution on $(S^{\prime},t)$ and the partition problem does not have a solution on $S$, and vice versa. It sort of makes sense to me because having the result in integer subset sum problem could hardly have any implications on the non-integer partition problem.
Would anyone have any hints on how to prove the non-integer version of the Partition Problem is NP-complete by reducing it to the Subset Sum Problem?


texts: Is it possible to have high compression but low predictability?

texts:
Can you have a process that generates a binary sequence with high compression rate (low entropy) but impossible to predict next symbol?

'impossible to predict' - sequence cannot be predicted theoretically. But I was also asking about the real life example (no polynomial algorithm).


texts: Increasing Cache Line and Programs with bad Spatial Locality

texts:
I'm reading on caches and I'm feeling a bit lost with spatial locality.

From my understanding, increasing the cache line with a program that has high spatial locality reduces the miss rate.

But for a program that has low spatial locality, does an increase in cache line have any effect on the miss rate?


texts: If there is any sense of an optimal set of instructions in an ISA

texts:
So there are One Instruction Set Computers, having only one (complicated) instruction like addleq, "add and branch if less than or equal to zero". And then there are extremely complicated Instruction Set Architectures (ISAs) with 100's of instructions like x86.

Most computers today I think use the x86 architecture, though ARM architectures seem like they are gaining some attention. I think x86 is popular (for one reason or another) because they have created these many instructions to handle specific use-cases, and so can be performance-optimized for specific common instruction scenarios.

However, I am interested in the fact that all logic can be boiled down to AND + NOT or OR + NOT. I'm not sure if this means you can implement a computer with just these two instructions, or if it's not possible to model things like ALUs using them. But it's interesting.

What I'm wondering though is if there is any notion of "optimal" in the architecture of an ISA. For example, it's a lot easier to represent things you can do in a computer with the let's say 20 or 30 or so regular operators like + and >= and =, etc. LLVM also shows you can have a pretty small instruction set, not taking into account the instructions with multiple different variations based on the datatype (int32 vs. int64, etc.). But either way, from a practical perspective I suspect most people don't use the 100's of x86 instructions, and instead use a standard small subset. Compiler architects probably do because they have the time and resources to do all the micro optimizations perhaps.

But then there are the optimizations in terms of processor speed. Implementing custom instructions like x86 does probably allows you to take advantage of hardware accelerations. So there is a balance.

My question is if there are any resources/papers/topics on "optimal" and "minimal" ISAs. Maybe they have like 10 or 20 instructions or something like that. Some minimal but not too minimal as in OISCs.


texts:
I'm reading a book about computer network theory, and one topic is discusses is routing algorithms.  It only mentions (probably not intentionally) how routers participate in forming the understood network topology stored in each routers memory - the routing tables.

So this brings me to my question, do Host acts like dedicated routers in this case and participate in and become part of that understood topology of the network in nearby routers?

For example, it says that routers communicate with each other to form their routing tables to find the best path. Do hosts as end user machines find themselves in this routing table (as an entry in dedicated router, routing tables) or routing topology?  Do they participate in forming it?

Likewise do Computer Hosts, have entries for nearby dedicate routers in their routing tables? I'm trying to find the relation ship between a router and a host in the this process.

The issue I'm having, is if they don't participate in this process, how do the routers not where the end user machines are in the topology?

Thanks :-)


texts: How does the OS detect B&B violation from hardware?

texts:
After reading about Base & Bounds memory protection mechanism from Stanford CS140 lecture notes, I understood from the explanation below that there is an integrated circuit performing B&B checks somewhere in the CPU (correct me if I'm wrong):

On each memory reference, virtual address is compared to the bound
register, then added to the base register to produce a physical
address. A bound violation results in a trap to the operating system.

However I didn't find any information about how the OS detects such violation from the hardware in order to handle the exception.
Does anyone have any idea?


texts:
If $f:A^*\rightarrow A*$ and $g:A^* \rightarrow A^*$ are partial recursive we want to prove $h:A^* \rightarrow A^*$ with the following definition is partial recursive
$$ h(x) =
  \begin{cases}
    \lambda       & f(x) = \lambda\\
    g(x)  & \textrm{otherwise}
  \end{cases} $$
for $x \in Dom(f)$.

One of my friends tried using a $\textrm{step}$ function that we know is primitive recursive and also partial recursive
$$ \textrm{step}(x,y) =
  \begin{cases}
    C_{\lambda}       & x = \lambda\\
    y  & \textrm{otherwise}
  \end{cases} $$
and defined $h(x) = \textrm{step}(f(x),g(x))$. but I think there is a problem here because we are not using the fact that $f$ and $g$ are partial recursive. Is this solution correct or not?


texts: Complexity of Independent Set on Triangle-Free Planar Cubic Graphs

texts:
I know that IS (is there independent set of size at least $k$?) on planar cubic graphs is NP-Complete, and IS on triangle-free graphs is also NP-Complete. But how about IS on triangle-free planar cubic graphs? Is it still an NP-Complete problem, or there are some polynomial time solutions?

Any ideas or referrences are appreciated, thank you in advance!


texts: What is the difference between computational model, model of computation and a computer?

texts:
I was browsing the forum where i came by this question, it says that rule 110 from {ECA} is a computation model.
What is the difference between a computation model and model of computation and how can we relate them to computers ?

A model of computation is the definition of the set of allowable operations used in computation and their respective costs.

what does it mean to 'define the allowable operations used in computation'?
Can we say that rule 110 or cellular Automata in general are computers ?


texts: Delete a consecutive range of leaves from a binary tree

texts:
Suppose I have a binary tree containing $n$ leaves and whose depth is $d$, where the data is in the leaves (the internal nodes don't hold data values).

I want to delete a consecutive interval of leaves.  In other words, suppose we order the leaves from left to right and number them $1,2,\dots,n$.  I am given a pair of indices $i,j$, and I want to delete leaves $i,i+1,\dots,j-1,j$.  This operation should also delete an interior node if all of its descendant-leaves are deleted.

Can this be done efficiently?  Can it be done in $O(d)$ time, regardless of $i,j$?


texts: The fastest way to check if a move is a winning move in Tic Tac Toe

texts:
I'm creating a tic tac toe game, there will be two players: X and O. X will be a human, and O is an AI which will always choose the best move to play.   My board is an 11x11 board and the winning condition is 5 in a row.

How do I know if a board is at end state (where one player has won)? For the 3x3 board, you can do it easily with just a few steps. But for the larger board (11x11) and the winning condition is smaller than the dimension, it's way more complex. The best solution I have found is to check for each n x n (n is the winning condition) square for a winner.  But that seems slow.

So here is my question: if you know the last move of a player, can you use that position to check if that player wins without checking every n x n square in the board?


texts: In which O-class does my Θ-result belong?

texts:
In a multiple-choice test, I'm asked to solve the recurrence $T(n)=2T(n/2)+n/2$.
I've done this using the master theorem: $f(n)=n/2$, $a=2$, $b=2$, so we're in the second case and $T(n)=\Theta(n\log n)$.

But the possible answers are $O(\log n)$, $O(n)$, $O(n \log n)$, $O(n^2)$ and $O(n^2/\log n)$ and more than one may be correct. What do I do now?


texts: Deleting nodes from graph so that they can be separated by a straight line

texts:
I have 2 types of points in a 2D plane, type 'A' and type 'B'. How do I delete the minimum possible number of points so that remaining can be separated (on different sides) by a straight line.

I tried modeling this as a graph, where I have 2 types of nodes, and i delete nodes from it. But I can't formulate an algorithm.

How can I go about formulating an algorithm for this situation?


texts: Showing $1$-reducibility of $\overline{\text{HALT}'}$ to index set

texts:
Note: overline denotes complement

I am trying to show that $\overline{\text{HALT}'}\leq_1 \{i\colon\Phi_i=\Phi_e\}:= A$ for some fixed $e$ but I am misunderstanding the problem or method and can't figure out where I'm going wrong. I am using the construction of the proof of Rice's theorem to prove this and I thus do the following:

Let $e_0\colon \Phi_{e_0}\uparrow$. We thus have that, as long as $\Phi_e\downarrow$, $e_0\in\overline{A}$. Now choose $e_1\in A$ and define $s$ such that $$
 \Phi_{s(x)}(y) = \begin{cases}
 \Phi_{e_1}(y),& \text{if } x \in \text{HALT},\\
 \text{undefined},& \text{if } x\not\in \text{HALT}
 \end{cases}
 $$
we thus get that $x\in\text{HALT}\implies s(x)\in A$ while $x\not\in\text{HALT}\implies s(x)\in\overline{A}$ and it follows that $\text{HALT}\leq_1 A$ and $\overline{\text{HALT}}\leq_1\overline{A}$.

This is, however, the opposite of what I want but I can't seem to see where I'm going wrong? Any help would be greatly appreciated!


texts:
While reading about minimal instruction set computer I found out that one needs at least (for example) the ability to increment or decrement the value stored in register, a test for zero and a jump.
A machine with such instruction set would be Turing-complete, correct? Is this called "Counter machine"?
But then I found out about the so-called "Random-access machine" which adds "indirect addressing", meaning I can access a register not just by explicitly specifying memory address or label but I can also fetch an address out of an address, like [Rn]. This should be useful for enabling mechanisms akin to "pointers" in C-like languages, for example.
My question is, why there is the need for "indirect addressing"? Since I presume both machines (without and with indirect addressing) are Turing complete, is it "merely" for convenience? Or are some programs which cannot be expressed without indirection?
PS: I'm a complete noob in this area so please bear with me: if I was to implement memcpy, i.e. to transfer the values of bunch of registers to other bunch of registers, how would I do it without indirection? I mean, I can write copy 1 word from x to y, copy 2 words from x to y, ... but in general, how do I say copy n words from x to y without it?
Edit:
For example, imagine I receive zero-terminated string via network, say 1 2 3 0 which I would like to store to some of my infinitely-many registers. Receiving 0 halts the program. I have an instruction take r which copies one word from the input to register r. No indirection means (?) that r has to be a direct constant number. How do I then move to "n-th" register? In other words, I don't understand how do I move back and forth among the registers, when the only mechanism I have is to read/set register 1, 2, 3, ...?


texts: Why do DFAs with a single final state have less power?

texts:
I came across this question in a test and I had to answer whether it is true or false.

  DFA with single final state has the same powers as DFA with more than one final state.

I was confused by what definition of "power" have they used. Generally, we always use power as a term to represent the class of languages a machine accepts and to me, it seems that since it is a DFA, regardless of the number of accept states, the power should be the same.

However, the question says that this is false and a DFA with more than one final state is more powerful. Is that true? I've never come across this in any textbook.


texts: How to determine the dimensions of the bias vector in a Convolutional layer (tensor flow)?

texts:
In the Deep MNIST Tutorial for Tensor Flow, (and in general), we create a convolutional layer with a weight tensor, say W,  of shape (patch dims, #input channels, # output channels). However, when we define the bias tensor, b, its shape is only (#output channels).

When we convolve W and the input x, with correct padding, we will get a volume with depth = #output channels. How can we add a single bias vector to such a volume?

Are we supposed to expand the bias vector to take on the spatial dimensions of the input x?


texts: Language comprising of Turing machine encodings

texts:
Let $A$ be the language $\{\langle M\rangle\mid M\text{ is a Turing machine that accepts only one string}\}$

According to my understanding, if a Turing machine is able to decide if another Turing machine will accept only one string, then the halting problem could also be solved. Therefore, $A$ is non-recursively enumerable in my understanding.
Is it correct ?


texts: Explain this Neural Network used for Knowledge Graph Embedding

texts:
I am interested in better understanding the neural network used in the paper LogicENN A Neural Based Knowledge Graphs Embedding Model with Logical Rules. To my knowledge this is the most advanced and complex knowledge graph embedding.

The neural network is described as follows:

Entity pairs, $[h,t]$ , are input and relations are output.

The score of a given triple $(h, r, t)$ is $f^r_{h,t}$ and is given by:

The beta vector are the embedding of relations.

The phi vector is the feature mapping of the hidden layer of the network which is shared between all relations.

This neural network works with a single hidden layer.

The first problem is: when I look at the picture, I think this neural network should have multiple hidden layers but in the text it's written "we use a single hidden layer".

The second problem is: when I look at the picture, I think that there is no direct relation between the outputs and the hidden layers but in text it's written "the feature mapping of the hidden layer of the network which is shared between all relations".

Please, explain this neural network. Any help is appreciated.


texts: How does Lamport imply anomalous behavior is impossible given these constraints?

texts:
Lamport's paper: Time, Clocks, and the ordering of Events in a Distributed System
Anomalous behavior occurs because Lamport's logical clocks are not enough to guarantee that the total ordering of events derived from the unique partial ordering and a non-unique total ordering is not enough to guarantee that the ordering is correct with respect to physical time.
He gives two conditions PC1 and PC2:
PC1: There exists a constant $ \kappa $ << 1 such that for all i:
$ |\frac{dC_{i}}{dt} - 1| < \kappa $
PC2: For all i, j:
$ |C_{i}(t) - C_{j}(t)| < \epsilon $
PC1 says that individual clock drift in the system must be less than some constant $ \kappa $. PC2 says that clocks must be synchronized so that the difference in time between any 2 clocks does not exceed $ \epsilon $.
This is what I do not understand. He says that anomalous behavior is impossible if this proposition holds, deduced from PC2.
proposition:
PC2 implies $|C_{i}(t + \mu) - C_{j}(t)| > 0$ if $\frac{\epsilon}{1 - \kappa} \leq \mu$.
I have no idea where he comes up with this, maybe my math isn't too great.
Note: $\mu$ is a constant that must be less than the shortest transmission time for interprocess messages.
PC1 implies $|C_{i}(t + \mu) - C_{i}(t)| > (1 - \kappa)\mu$. This is apparent because (1 - $\kappa$) is less than 1. But apparently he combines this with PC2 to deduce the proposition.
How does he arrive at this??