texts: How to evaluate the clock cycle for MIPS single cycle CPU

texts:
The Situation

I'm trying to read the book 'Digital Design Computer Architecture'.
In the part of Performance Analysis(7.3.4 in the book), Author refers to clock cycle for MIPS single cycle processor. But I think there's something wrong with author's evaluating clock cycle.

Author says,

T(Clock cycle) = T(pcq_pc) + T(mem) + Max[tRfread, t(sext)] + t(Mux)
                 + T(ALU) + T(mem) + t(mux) + T(RFsetup)

But I think clock cycle 'T' would be ( if T(RFread) > T(mux) + T(sext) )

T(Clock cycle) = T(pcq_pc) + T(mem) + T(RFread) + T(ALU) + T(mem) + T(mux) + T(Rfsetup)

Since I think the MUX followed by ALU already selects known sign-extend immediate before register value(the pin RD1 in below diagram) is known.

and if T(RFread) is less than T(mux) plus T(sext).

T(Clock cycle) = T(pcq_pc) + T(mem) + T(sext) + T(Mux)
                 + T(ALU) + T(mem) + T(mux) + T(RFsetup)

Some referenced information by the book.

T(pcq_pc) is propagation delay for PC.
T(mem) is read-propagation delay for instruction memory and data memory.
T(sext) is propagation delay for Sign Extend logic.
T(RFread) is read-progagation delay for register file.
T(mux) is propagation delay for MUX.
T(ALU) is propagation delay for ALU.
T(RFsetup) is setup time for Register file.(Register value is written on positive clock edge)

Here is Diagram for MIPS single cycle CPU.

Is my thought correct? If you think author is right, Could you tell my why?
Any help would be awesome!


texts: Constraint violation and efficiency in search

texts:
It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems:

Start with a feasible solution and expand search until constraints are tight and solution is maximal (or minimal).
Begin with violated constraints and search for maximal (or minimal) feasible approach.

For the Max-Flow problem Ford-Fulkerson satisfies condition (1), while Push-Relabel satisfies condition (2). An interesting point is that Push-Relabel is a more efficient algorithm than Ford-Fulkerson. My question is this:

  What other examples are there where (2)-based approaches outperform their (1)-based counterparts?

A follow up is:

  Do there exist meta-theorems regarding approaches based on condition (2)?


texts: Does Optimal Substructure implies Convexity and vice versa?

texts:
In undergraduate CS, Dynamic Programming problems are often related to Overlapping Optimal Substructure (https://en.wikipedia.org/wiki/Optimal_substructure).

Dynamic Programming is also often used in Convex Optimization. Under the context of Dynamic Programming or in general, does Optimal Substructure implies convexity?


texts:
I am familiar with 0/1 knapsack problem.
But if the following constraint is imposed... how do I solve the question?

If you choose some item 'U' you won't be able to choose another item 'V'.

For example
Items are given as [Name, Weight, Value]
Items are :
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50
If you choose B then you cannot choose A.
If you choose E then you cannot choose C.
If you choose D then you cannot choose A.
In the similar way the constraints are given.
Please provide me some way to solve the above problem. Any help is highly appreciated.


texts: Difference between order of convergence and order of consistency?

texts:
I understand that, as the time step is reduced:

Consistency: The local error must approach zero.
Convergence: The global error must approach zero.

But why are both the order of convergence and consistency of explicit Euler = 1, if the global error is $O(h)$ while the local error is $O(h^{2})$?

More details: The Euler method is used to approximate an initial value ODE by time stepping using the derivative.

For example, for ODE form:
$y'(t) = f(t,y(t)), \qquad \qquad y(t_0)=y_0 $

The solution at point $n$ is:
$y_{n+1} = y_n + hf(t_n,y_n)$

This formula can be obtained from the Taylor expansion, where $h$ is your time step:

$y(t + h) = y(t) + hy'(t) + \frac{h^{2} y''(t)}{2!} + ... $

So the local error is of order $O(h^{2})$. Now the global error is one order less which is why Euler is called a first-order method. So my question is: Why is the order of consistency also 1, even though the local error is of order 2?


texts: Balancing Steiner trees with Shortest Path trees

texts:
I'm working on a problem that combines Steiner Trees and Shortest Path trees. We have a (sparse, connected) graph $G=(V,E)$ with non-negative edge weights and edge lengths, a set of terminals $T \subset V$ and a root node $s \in T$.
The goal is to connect all terminals to the root node while minimizing the total edge weight + the total lengths of the paths from each terminal to the root.

Minimizing just the edge weights gives the Steiner tree problem. Minimizing just the sum of path lenghts gives a shortest path problem.

Khuller, Samir, Balaji Raghavachari, and Neal Young. "Balancing minimum spanning trees and shortest-path trees." gives an algorithm for balancing this between MSTs and shortest path trees, but only considers the path from that node instead of the sum of incoming paths.

I'm having trouble interpreting this article. Does the algorithm give
a minimal cost solution for its own problem or is it a heuristic approximation?
Can similar greedy strategies (expand from root to find shortcuts) also produce minimal cost solutions when balancing with Steiner trees (if you already have computed the Steiner tree)?

If (2) holds, then a custom solution for this cost function isn't required; you can compute the Steiner tree first, then minimize the path cost.


texts: Maximum likelihood estimate for softmax function

texts:
Given an undirected graphical model with no edges and only N nodes, I am trying to find a closed form solution to the ML estimate of each node given that
$p(x|\theta)=\frac{\exp(\sum_{s\in V}\theta_sx_s)}{\sum_x\exp(\sum_{s\in V}\theta_sx_s)}$, where $x=(x_1,\ldots,x_N)$ and the denominator is the partition function. I derived $\log p(x_1,\ldots,x_L|\theta)=\sum\limits_l\log p(x_l|\theta)=\sum\limits_s\theta_s\sum\limits_l x_{sl}-L\log\left(\sum\limits_x\exp\sum\limits_s\theta_s x_s\right)$, which is the log-likelihood function. To find the ML estimate of $\theta_s$, I tried to take the partial derivative wrt $\theta_s$ and set it to 0, but the partial derivative I get is $\sum\limits_lx_{sl}-\frac{L\sum\limits_xx_s\exp\sum\limits_s\theta_s x_s}{\sum\limits_x\exp\sum\limits_s\theta_s x_s}$ and at this point I don't know how to solve for $\theta_s$ and thus I can't get a closed form solution for the ML estimate. Can anyone help? Is my derivation correct? Am I even approaching this in the right way, or is there another approach I can take? Thanks!


texts: Chandy/Misra dining philosophers solution

texts:
So based on the Chandy/Misra section in this Wikipedia article we've got 5 philosophers numbered P1-P5.
Based on this quote:

For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirty or clean. Initially, all forks are dirty
When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so.

So with the knowledge that all forks are initially dirty, regard the following quote and the image underneath it.

For every pair of Swansons, give the fork to the guy with the smaller id.

My question is if P3 now requests a second fork from his neighbor P4, will P4 give up his single fork beacause it was dirty, even though he just picked it up?


texts:
Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?

I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (Just as the smallest upper bound is $n^7$)

The reason I say that the function is in the Omega class of functions larger than $n^5$ is because of the limit definitions of complexity [Source]:
$\require{enclose}$

$$\begin{array}{c|c|c}
\text{Big-}\mathcal O\ \text{notation} & \text{Comparison notation} & \text{Limit definition}\\ \hline
f \in \mathcal o(g) & f \; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px] \lt \kern .07em}}\ g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = 0\\
f \in \mathcal O(g) & f\; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\le \kern .07em}}\  g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} < \infty \\
f \in \Theta(g) & f\; {\scriptstyle \enclose{circle}{\bbox[7px]=}}\  g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} \in \mathbb{R}_{>0} \\
f \in \Omega(g) & f \;{\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\ge \kern .07em}}\ g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} > 0 \\
f \in \omega(g) & f\; {\scriptstyle \enclose{circle}{\kern .07em \bbox[6px]\ge \kern .07em}}\; g & \lim_{x\rightarrow\infty} \frac{f(x)}{g(x)} = \infty \\
\end{array}$$

Using the limit definition of $\mathcal O$, we correctly identify that $n^5+n^7 \in \mathcal O(n^7)$ and $n^5+n^7 \notin \mathcal O(n^6)$

However, using the limit definition of $\Omega$ tells us that the function is in $\Omega(n^7)$! But isn't the largest lower bound for this function $n^5$?


texts: optimal placement of fixed length items on a given length

texts:
I have got some equipment of standard lengths, say:

  equipment_lengths = {60, 48, 36, 29}

that I have to place on a given length of, say 100. I have to place this equipment so as to minimize material waste while covering the given length. I am allowed to exceed the given length of 100 but keep the excess minimized.  I am not allowed to drop short of the given length. Also I have an unlimited number of each equipment.

So, one solution to the above example would be:

  {60, 48} (excess = 60 + 48 - 100 = 8)

Another could be

  {60, 60} (excess = 60 + 60 - 100 = 20)

The first solution is preferable to the second one as it minimizes the excess.

My first approach has been to implement a greedy algorithm that takes the longest equipment and keeps placing those till I exceed the given length. Once that happens I remove the last equipment I placed and place the next smaller ones till I exceed again. In the end I select the combination with the least amount of excess. For example the algorithm will successively do the following:

60, 60 (excess = 20)
60, 48 (excess = 8)
60, 36, 36 (excess = 32)
60, 36, 29 (excess = 25)

So, now it will select {60, 48} as the optimal solution when you remove last one equipment on excess. The algorithm then repeats the exercise by removing the last two equipments and finds another optimal solution. Finally it chooses the best one among the two optimal solutions it found.

Now, I have been studying bin packing and knapsack problem variations and while these problems look similar, I haven't been able to apply them to my problem. Does my problem have a well known solution? If not, how should I go about it to efficiently find the globally optimum solution?

Additional information: I think giving preference to longer equipments should be a good idea as the equipments need to be joined with screws or bolts so joining two longer equipments would be less work than three shorter ones, but I don't think it's more important than material wastage.


texts: Solving recurrence relations using substitution followed by tree method/masters theorem

texts:
$T(n) = 4T(\sqrt n) + n$

First I substitute n = $2^k$:

$T(2^k) = 4T(2^{k/2}) + 2^k$

Now I rename the above as follows:

$S(k)=4S(k/2) + 2^k$

Now if I try to use tree method on this in the following way:

Work done at Level 1 = $2^k$

Work done at Level 2 = $2^{k/2} * 4$

Work done at Level 3 = $2^{k/4} * 16$
and so on.
We have a total of $log\ k$ levels. The final term is dominant. So we should get $2^{k/{2^{log\ k}}} * (log\ k)^2$

That gives me the answer as $T(n)=(log\ k)^2$ = $(log\ log\ n)^2$

Second method:

$T(2^k) = 4T(2^{k/2}) + 2^k$

Divide each term by $2^k$:

$T(2^k)/2^k = 2T(2^{k/2})/2^{k/2} + 1$

Now rename it as follows:

$S(k)=2S(k/2) + 1$

Now using masters theorem on the above gets us $T(n) = k = log\ n$

The actual answer seems to be $n$.
So, where am I making the mistake? Please let me know the the mistake in both the methods.

(Note: I actually mean asymptotic notation as the final answer).


texts:
A cache has following specifications:
Block size = 16 Bytes
Set size = 2 way set associative
Number of sets = 128
Physical address = 23 bits, byte addressable

My Questions are:
1) How many blocks main memory contains?
2) What is the extra memory required for cache?

According to me:
Total size of physical address = $2^{23}$ bits
Size of each block = 16 Bytes = $2^4 \times 2^3$ bits = $2^7$ bits
So total number of blocks = $$\frac{2^{23}}{2^7} = 2^{16}$$
But the answer in the book says it is $2^{19}$
As far as second question is concerned I don't know what does extra memory refers to.

Please help. Thanks in advance.


texts:
Does Kruskal's and Prim's algorithm work on directed graphs? I want the two algorithms to find a minimum spanning tree. For further enlightenment, I would like to know what other problems Kruskal's and Prim's can solve. So far, I only know they can solve minimum spanning trees. If it turns out there are an infinite number of problems Kruskal's and Prim's can solve, then no need to list all of them. I am learning this by myself and so far I only know one problem the two algorithms can solve.

I think that Prim's will not work because it is possible to have a node that points outwards to other nodes. If this central node is not chosen, then Prim's will be unable to give the MST including all the children.

I wonder if Kruskal's works. . . My counter example is a central node where all the children of the central node point to this central node. Running Kruskal's algorithm, we would get an MST that is not a shortest path, since we do not have path.


texts: Prove that the greedy algorithm to remove k digits from a n-digit positive integer is optimal

texts:
Given a positive n-digit integer, such as 1214532 (n=7), remove k digits (for example k=4) such that the resulting integer is the smallest one.

A greedy algorithm for this would keep removing digits such that the resulting integer is the smallest. For the above example:

Step 1: Remove 2 => 114532
Step 2: Remove 5 => 11432
Step 3: Remove 4 => 1132
Step 4: Remove 3 => 112

Can you prove that this algorithm is optimal (i.e. the final integer is the smallest possible)? Or if it is not, show a counterexample?

Thanks!


texts: Decidability of the TM's computing a non-empty subset of total functions

texts:
I have this HW problem:
Let $F$  be the set of computable total functions, and let $\emptyset\subsetneq S\subseteq F$. Denote
$$L_S=\{ \langle M \rangle | M \text{ is a TM that computes a function and } f_M\in S \}$$

where $f_M$ is the function $M$ computes.

Prove that for every such none-trivial $S$, $L_S \notin \mathcal{R}$.

I tried to  construct

$L_{f}=\left\{ x\#y\in{\Sigma^*}|y=f\left(x\right)\right\} $
$\tilde{S}=\left\{ L_{f}|f\in S\right\} $
$L_{\tilde{S}}=\left\{ \left\langle M\right\rangle |L\left\langle M\right\rangle \in\tilde{S}\right\} $

and then show with Rice that $L_{\tilde{S}} \notin \mathcal{R}$, when the idea behind it was to eventually show that $L_{\tilde{S}} \leq_m L_S $.
But the problem here is that I couldn't show a mapping reduction from $L_{\tilde{S}}$ to $L_S$ without assuming $L_{\tilde{S}} \in \mathcal{RE}$ (which I'm quite sure is not true).
So any other directions will be warmly welcomed!


texts:
The scenario is the creation of street maps. For example, two people at Open Street map edit the same part of the map at the same time. Now the one that submits the data later should see a diff. Assume they both started with no vertex, but they had the same aerial image as a basis to create the digital map.

Let's define a street map $M$ as a set of vertices and edges $M := (V, E)$ with

\begin{align}
V &\subseteq \mathbb{R}^2\\
E &\subseteq V \times V
\end{align}

I want to compare two maps $M_1$ and $M_2$, where $M_1$ was there first. Think of two teams creatings a map from satellite images on Open Street Maps (OSM).

What I want to understand is:

How many roads (edges) are new?
How many roads (edges) were removed?
How many roads (edges) were changed?

I only could think of Dynamic Time Warping to get a score how much things have changed. But very likely no single vertex will be exactly the same, but most will be close.

What is a change?

A "change" is fuzzy in this context. If it is only about a single vertex, I would say if the geo-positions of that vertex only changed by < 10cm, it is for sure only a change. Likely also if it is less than 1m due to the lack of precision in GPS (and likely also the aerial image).

It is more complicated for streets which consist of multiple line segments and not necessarily the same number of line segments. If one knows which line segments should belong together, I would use the Douglas-Peucker algorithm to reduce the street with more line segments to have an equal amount of line segments as the second street. Then one can check if a single vertex is over the threshold to determine if a segment is different. In this case different would mean there is a "removed" and "new" segment.

But when we cannot have such a mapping I only see the possibility to check everything for change. And this does not cover the case of a change in between.

For example, obviously street (a) and street (b) have quite a bit in common, besides only point (a). They have the whole line segment AY in common.

a: A---------------------------------X

b: A---------------------Y
                          \
                           \---------Z


texts: Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

texts:
We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes.

I want to show that this problem is NP-hard. Is there any idea to which problem is the best for reduction to this problem?


texts: What is the time complexity of this binomial coefficient algorithm?

texts:
Here's a naïve algorithm that computes $ \binom{n}k $ (or "n choose k"), with either $k=0$ or $1\le k \le n$:

def coefficient(n, k):
    if k == 0 or k == n:
        return 1
    return coefficient(n-1, k-1) + coefficient(n-1, k)

Now the time complexity has to be bounded by $2^n$, however we have to take $k$ into account. The best cases are when k = 0 or k = n. So, with k and n decrementing, we get the most branching when $k = \frac{n}2$.

I'm looking for the worst case time complexity. I can write the recurrence relation, but I don't know how to go from here:

$T(n,k) = T(n-1, k-1) + T(n-1, k) + constant$


texts: I don't get why the time complexity of insertion on a linked list is O(1)

texts:
I was watching the algoritmhs course by mycodeschool and he said that when we add a new item on a given position the worst case would be $O(n)$. Everywhere I look says insertion is $O(1)$...
Now I understand that insertion itself might be $O(1)$, but if I have the following interface (this is something I made up, not a real thing I'm working):
insertAtIndex(any item, int index)

Would this be $O(n)$? Since I will search $O(n)$ and then insert $O(1)$?
Thanks!


texts:
What are the  $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to?

I suspect that their, NEXP, ESPACE and 2EXPtime respecitvely.
And what bout $NP^{EXP}$


texts: Are there algorithms with non-convex and non-concave computational complexity?

texts:
If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational complexity of each algorithm can be described using a function that is neither convex nor concave.

However, this seems like a made-up case. Are there some algorithms, whose complexity in $\Theta$ notation can be described only using a non-convex non-concave function, or can each complexity be conveniently transformed to a convex or concave function?


texts:
How to use algebra in operations that involve asymptotic notation?
Like for example:

$C_1(n)= O(n)$
$C_2(n) = O(n^2)$
Is $C_2(n)/C_1(n) = O(n)$?


texts: Characterizing a CFG equivalent to a special type of PDA

texts:
Consider a nondeterministic PDA $P$ which pushes/pops at most one stack symbol on a transition. Suppose that for every string $\sigma \in L(P)$, there is an accept computation of $\sigma$ in $P$ which starts with an empty stack and ends with an empty stack and which has the additional property that during this computation, the stack size can increase, but once the stack size decreases it cannot subsequently increase. I want to show that there is a CFG equivalent to $P$ with the property that for each production in this grammar, there is at most one variable on its right-hand side.

My initial idea to approach this problem was to convert $P$ into an equivalent PDA $P'$ which either pops or pushes on every transition, but never both, which empties the stack before accepting, and which has a single final state. Then I would convert $P'$ into a CFG $G'$ using the standard method, as seen here. Finally, I could show that for every $\sigma \in L(P') = L(P)$, there exists  a derivation of $\sigma$ in $G$ such that every production applied in this derivation is of the form $A_{pq} \rightarrow aA_{rs}b$, where $p,q,r,s$ are states in $P'$ with the property that a transition exists from $p$ to $r$ which reads input symbol $a$ and pushes a symbol $u$ onto the stack and a transition exists from $s$ to $q$ which reads input symbol $b$ and pops $u$. However, I don't know how to show this to be the case.


texts: Building a tree with the heap property from an array and preserving its order

texts:
How efficiently can I build a binary tree satisfying the heap property from an array and such that the inorder traversal of the tree is the original array?

For example, if I have:

  2 1 5 6 2 3

I want to build:

  1
 / \
2   2
   / \
  5   3
   \
    6

Because it has the heap property and its inorder is the original array 2 1 5 6 2 3.


texts: Seeding the Mersenne Twister Random Number Generator

texts:
I am trying to understand how the Mersenne Twister random number generator works (in particular, the 32-bit TinyMT). I am still relatively new to the concept of RNG. As I read the source code, I noticed there were two ways to seed the MT: with a single integer seed or an array of integer seeds. What is the point in seeding with an array? Does it produce a better distribution or a longer period?

Also, I would appreciate it if somebody could explain to me what is meant by the "state" of the RNG, as I am seeing that word all over the source code. Is it like a finite state machine in a way?

Thanks for your time!


texts: FInding number of ancestors at given depth

texts:
I have a rooted tree with $n$ vertices.

I want to be able to answer the given queries in logarithmic time after setting up some sort of data structure (preferably in time $n\log n$.

The query is given by $v$ and $k$.

I want to find the number of ancestors of $v$ of degree less than or equal to $k$.( I call ancestors of degree $1$ sons).

I don't know how to do it.

At first I thought that I should only store the number of ancestors of $v$ of degree less than $2^j$. But this doesn't seem to work.


texts: Any CPUs using value prediction, dynamic instruction reuse?

texts:
There is a lot of research about techniques that try to reuse the previous result of an instruction, either memory loads or arithmetic, such as dynamic instruction reuse, value prediction, based on the concept of value locality.

What I wonder if there is any commercial CPU from Intel/AMD/ARM that actually uses any of these techniques, or are they still far away from being implemented in CPUs?

I mostly see these techniques as the runtime, CPU version of compiler optimizations such as common-subexpression elimination, loop invariant code motion, redundant load removal, catching cases that cannot be handled due to pointer aliasing, side-effects, etc.

Two of the papers that seem to have introduced these ideas:
Dynamic instruction reuse
Value Locality and Load Value Prediction


texts: Classification algorithm for high dimensional data which is uniquely definable in a very small sub-space

texts:
I am new to machine learning, so forgive me if I am doing something absolutely absurd.

I have a classification task (~100 classes) and have about 2 million training data points in a 2000-dimensional space. Coordinates of data points are integers (discrete). All points have non-zero coordinates only for < 10 dimensions. That is, each point can be uniquely defined in < 10 dimensional sub-space.

If I use a Gaussian Mixture Model (GMM) for each class, I will end up with ~100 GMMs in a 2000-dimensional space. I feel that given the fact that each point is uniquely definable in less than 10 dimensional space, there can possibly be a better way of doing it.

What am I missing here?


texts:
we know RAM contains instruction for we ask computer to do operations
we know ROM contains instructions which for computer to work

does this mean RAM contains address of instruction sitting in ROM?
ROM tell how to add and RAM points to that address of ROM which tells cpu to add


texts: Is there a generic algorithm for translating equational rules into corresponding data structures?

texts:
When implementing a term rewriting system, one “optimization” one can do is to represent operators known to have certain equational properties with a more directly representative data structure.  For example, one can use lists to represent uses of a binary operator known to be associative, rather than using the naïve syntax tree representation one is forced to use in the absence of any information about an operator.

I thought I recalled a result that stated that there was an algorithm that could take any (finite) set of equational rules about an operator and transform them into a data structure definition specialized for that set of equational rules.  However, when I tried to look for this result, I couldn't find anything like it anywhere.  Am I not looking hard enough or not in the right places, or did I just imagine this result entirely?  If I did imagine it out of thin air, is there any less-powerful result of the same form that is known, or any counter-result that dashes my hopes of such a generic algorithm existing?


texts: We have a normal knapsack problem but we can choose up to $t_i$ of the $i$-th object. How would you solve this problem with complexity less than $O(V(n + \sigma(t_i)))$ where $n$ is number of objects and $V$ is the total volume?


texts: Help understanding a theorem Kleinberg proves related to sequence alignment

texts:
This is from Kleinberg's Algorithm Design text (Theorem 6.14)
Let $M$ be an alignment of $X$ and $Y$. If $(m, n) \notin M$, then either the $m^{\text{th}}$ position of $X$ or the $n^{\text{th}}$ position of $Y$ is not matched in $Y$.
The theorem does not state that $m, n$ must be the last elements of $X$ and $Y$ respectively, but earlier, when introducing the topic, he uses $m, n$ to denote the last entries of the two strings. Which of these is correct?


texts:
Let consider well-known problem in distributed computing Broadcast Problem in network with stopping crashes.

The most appropriate solution to the broadcast problem is flooding algorithm, when the source of the message just send it to all available nodes of the network on the first round, if there are crashes on the edges some number of message will fail. Then on the second round, the nodes that received messages from the previous round send it to all available nodes and so on.

Let consider slightly different model, when on  every round the source node with message is capable to send a message to only one single node of course stopping failure might occur. It's very useful model, which can represent a sort of controllable or limited spreading.

Unfortunately I don't know the formal name of the model. Do you familiar with result in the model of "limited spreading", I am sure there are must some work in this direction.


texts: Understanding Randomized Select algorithm

texts:
Here is the algorithm in pseudo code:

Where $A$ is the array to search, $p$ is the starting index in the array, $r$ is the ending index and $i$ represent the number of smaller values we want from our goal value, the $i$ smallest number in the array.

I dont understand the $k$.

It gets a value that dont realy represent the index of the value in the original array, but the index value in the sub array we are at, at the recursion process.

Similarly, it doesnt represent the amount of values that are smaller than the pivot we are at, but the number of smaller values in the current sub array in the recursive process.

So how can we check between $i$ and $k$? They dont talk on the same arrays...

Thank you.


texts: Introduction into first order logic verification

texts:
I am trying to teach myself different approaches to software verification. I have read some articles. As far as I learned, propositional logic with temporal generally uses model checking with SAT solvers (in ongoing - reactive systems), but what about first order Logic with temporal? Does it use theorem provers? Or can it also use SAT?

Any pointers to books or articles for beginners in this matter is much appreciated.


texts: Why is the laplace transform not popular for image processing convolution? Most textbooks only conver the Fourier transforms.


texts: Why Djikstra's algorithm is said to have $\mathcal{O}(|V|^2)$ complexity?

texts:
Djikstra's algorithm assigns some number to non-removed vertex each time it finds a path from removed vertex to it. Number of assignments is $\mathcal{O}(|V|^2)$. However, complexity of assignment is not $\mathcal{O}(1)$, it is $\mathcal{O}(\log s)$, where $s$ is weight of the path from initial vertex to current.

And this means that complexity is $\mathcal{O}(|V|^2\log s)$.

Am I missing something?


texts: Are $BPP^{BPP^{\oplus P}}$ and $BPP^{NP}$ contained in $BPP^{\oplus P}$?

texts:
Does $BPP^{NP}\subseteq\Sigma_k^P\cap P/poly^{NP}\subseteq BPP^{\oplus P}$ hold at some $3\leq k<\infty$?
Also is $BPP^{BPP^{\oplus P}}\subseteq BPP^{\oplus P}$ known?

Note Sipser gives $BPP\subseteq \Sigma_2P$ and Adleman gives $BPP\subseteq P/poly$ and so I am tempted to say $k=3$ in $1.$ works. I am not sure relativization plays here.


texts: Examples for derandomization via small sample spaces

texts:
People in theoretical computer science stack exchange advises me to ask this question here. I ask the same problem in https://cstheory.stackexchange.com/questions/46668/examples-for-derandomization-via-small-sample-spaces and if you are interested in answers there, you can go to see it.

I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises.

I'm trying the technique of "Derandomization" for some algorithms, and I find some samples using the derandomization via small sample spaces and feel very interested.

To deepen the impression on derandomization via small sample space, I want to see more papers using that.


texts: UCT1 Algorithm: What does "total number of simulations" mean?

texts:
When reading up on the UCT1 algorithm (I'm writing a Monte Carlo tree search), I'm having trouble with the formula.
$$\frac{w_i}{n_i} + \sqrt{\frac{\ln t}{n_i}}$$
Wikipedia, this guy, and this guy all say that $t$, or whatever else they use for that variable, equals the "total number of simulations". What does this mean, exactly? The total number of simulations in the entire tree? The child nodes of that particular node? The "sibling" nodes? So, what is the $t$ is this equation? Thanks!


texts: Machine learning for labelling a directed graph

texts:
Just a pre-warning - I'm new to machine learning and the concepts that come with it, so please be nice with the terminology!

I have a directed Graph which represents a home and some devices in it. Users are able to create rules to control how devices interact with each other (e.g. when motion sensor triggered, turn on the light)

Users are able to build the graph themselves, and label the nodes however they see fit.

Here's an example of a basic graph:

Key:

Red nodes: Inputs - these are usually connected to sensors on devices
Orange nodes: Logic - allows you to connect other nodes together to change behaviour
Blue nodes: General - just used to help the user understand behaviour
Green nodes: Outputs - these control devices

The aim is to try and identify which rooms particular devices are in.

There are some nodes that we can already label without machine learning. I was thinking it could scan the nodes and look for any that contain a single room name. Those nodes would then get labelled with that room name:

From that we learn:

Device A = lounge
Device D = lounge
Device E = kitchen

Then the clever part.. it needs to be able to traverse the graph to make predictions on what nodes are in which rooms:

From that we should learn:

Device B = lounge
Device C = dining room
Device G = lounge
Device H = dining room

There's not enough info to determine where device F is located.

Any thoughts on how I could accomplish this?

I feel like this might need to go down a semi-supervised route, as I'm not going to have much training data to play with. I feel like https://research.googleblog.com/2016/10/graph-powered-machine-learning-at-google.html gives some good ideas, but I don't know where to start.

If it helps I'm planning to use TensorFlow.js to complete the task, but I'm open to other suggestions etc.

Thanks!


texts: Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete

texts:
I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete.

Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in V$) and a finite set of equalities of the form $x=a$ (where $x \in V$ and $a \in \{0,1\}$), is there an assignment of values from $\{0, 1\}$ to the variables satisfying all the inequalities and all the equalities?

How can I start to resolve the proof?


texts: Arranging tasks with specific constraints (scheduling)

texts:
I have the following problem:

Given a set of tasks and their duration, i need to arrange them taking in consideration some constraints; Here's an example:

Suppose we are scheduling talks in a conferece. Each talk has a duration, and we can use as many rooms as we need. For each room, we have two sessions: one in the morning, and one in the afternoon. Morning one starts at, say, 9 AM and must end exactly by noon. The afternoon one starts at 1 PM and must end between 4PM and 5PM.

How do i arrange these talks in sessions in such a way that uses the least amount of rooms possible?

I've researched some scheduling problems, but none of them seem to take into account the constraints i need. I have read about:

http://en.wikipedia.org/wiki/Interval_scheduling

http://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling

http://en.wikipedia.org/wiki/Flow_shop_scheduling


texts: Why is the A* search heuristic optimal even if it underestimates costs?

texts:
A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus on being admissible at the moment).

But why does it always find the optimal solution if the heuristic underestimates? For example, if it underestimates a non optimal path by more than what it underestimates the optimal one, isn't that equivalent to over estimating?


texts: Does there exist a travelling salesmen generating algorithm?

texts:
I'm curious if somebody has already figured this out.  Is there an efficient algorithm that will generate (in $\mathbb{R}^2$) a sequence of points in such a way that the solution to the travelling salesmen problem is known a priori, and such that we have a uniform distribution on the set of points? For example, I can think of an algorithm that will generate such a sequence by plotting a polygon, and the minimum distance would be the points going around the outside of the polygon, but the distribution on point-sets from this algorithm is highly biased.

So I would hope for an efficient algorithm that generates a set of points in $[0,1]^2$ (and its corresponding TSP solution), with equal probability to any set of points, i.e., each point has iid uniform distribution on $[0,1]^2$.  You could interpret "efficient" as "polynomial time".

PS: I strongly suspect that no algorithm could exist because if so, I imagine the problem would be solvable, so in this case, is there a database somewhere with a large number of solutions for randomly generated sets of points?


texts: General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?

texts:
I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2, which I also copied below.

What confuses me most is that

I find the non-recursive implementations using stacks are not easy to understand.
It also seems to me that the three non-recursive implementations are ad hoc on each own, and I can't find if there is a way to unify their creations.

Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?

Since a compiler can implement recursions using stacks, I believe it is possible to do that.

One reply I saw

  Usually, I replace a recursive algorithm by an iterative algorithm by
  pushing the parameters that would normally be passed to the recursive
  function onto a stack. In fact, you are replacing the program stack by
  one of your own.

Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}

  Note: if you have more than one recursive call inside and you want to
  preserve the order of the calls, you have to add them in the reverse
  order to the stack:

foo(first);
foo(second);

  has to be replaced by

stack.push(second);
stack.push(first);

In the idea of the reply, the non-recursive implementation of preorder is easier to understand than the non-recursive implemenations of the other two. The non-recursive implemenations of the other two don't seem to follow the idea at least closely, and can they be written to follow the idea closely?

Thanks.

Note the implementations from Wikipedia are

  Pre-order

preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node.left)
  preorder(node.right)

iterativePreorder(node)
  if (node = null)
    return
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    if (node.right ≠ null)
      s.push(node.right)
    if (node.left ≠ null)
      s.push(node.left)

  In-order

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

  Post-order

postorder(node)
  if (node = null)
    return
  postorder(node.left)
  postorder(node.right)
  visit(node)

iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      peekNode ← s.peek()
      // if right child exists and traversing node
      // from left child, then move right
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right
      else
        visit(peekNode)
        lastNodeVisited ← s.pop()


texts: Analysis of algorithms, 'big O' question

texts:
The main question is, how exactly is the big O analysis calculated on routines? Is there a specific formula that relates what each function in a program does to a big O calculation?

Also, what about more complex iterations, such as colour conversions etc?

I would like to point out that this is not a homework question, rather, it is a question from my own research/programming learning curve. I have code that I am working on, but would like to know how this analysis is carried out.


texts: How do I show that $a^n w b^n$ is not regular?

texts:
Given $ \Sigma= \{a,b\} $, show that $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\Sigma^m\} $ is not regular.

I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the middle part $w$.

I would pick the symbols $\ a^na^mb^mb^n $ as a starting point and show that this does breach at least one of the three properties of the pumping lemma. At this point I don't know if this is the right word to pick & how I do continue from here.


texts: Obtaining a recurrence from a rational generating function

texts:
Looking at some Generating functions of a series, I have conjectured -

If $G(x) \ =\ \frac{1}{1-x^{t_1}-x^{t_2}-...-x^{t_n}}$, then the recurrence equation of the the series is -

$a_n = a_{n-t_1}+a_{n-t_2}+...+a_{n-t_n}$

How can I prove or disprove this?


texts: Computer Organization and Assembly Language Programming

texts:
Why do we need to learn MIPS Assembly language before learning computer organization? What are the implications of learning it first?

As a computer scientist, why do we need to learn this one and where will these topics will become handy?

with references:

-Computer Organization and Design by Patterson and Hennessy

-Introduction to Digital Logic Design by John Hayes


texts: As a wannabe computer "scientist" I have problems differentiating theory and practice

texts:
Specifically I'm studying towards a research degree in HCI (human computer interaction). I have problems however differentiating theory and practice, or science and engineering. I know science is about advancing human knowledge. Providing evidence about something specific in a field. But it's also about theory right? I guess there's different ways to do science; you can prove something with numbers and results, but you can also do science simply by creating a new method or theory about how something should work right? Engineering on the other hand is more about putting into practice the theory, right?

I'd like to have some guidance, perhaps with examples, to what differentiates theory and practice, science and engineering. Also books/articles to read on the subject would be greatly appreciated.

PS: In HCI it's hard to do research with experiments - it's very subject and not quantifiable as other fields of computer science. Perhaps this is why my confusion is greater than one would expect.


texts: Minimum variable size if the information are coded in non-binary system

texts:
A typical HDD would represent information as either 1 (e.g. spin up) or 0 (e.g. spin down). Let's assume you want to represent the information physically in a hex system with 16 states, and assume this is possible with using some physical form (maybe the same spin).

What is the minimum physical size of a memory element in this new system in units of binary bits? It seems to me that the minimum is 8 bits = 1 byte. Therefore, going from a binary representation to a higher representation will, everything else equal, make the minimum variable size equal 1 byte instead of 1 bit. Is this logic correct?


texts: Determining if $G$ contains $K_4$ as a minor in polynomial time

texts:
I am trying to devise an algorithm for determining if an undirected graph $G$ contains $K_4$ as a minor. I was able to show in a previous problem how to test for $K_{2,3}$ by looking at all pairs of vertices and applying Menger's problem as a black-box on that pair of vertices (i.e checking for at least 3 vertex-disjoint paths). This gave an, although naive, $O(n^3)$ algorithm. However, the same trick doesn't seem to work for $K_4$, since the same type of structure cannot be exploited. How can one test for $K_4$?

I am also wondering what the best possible algorithm for $K_{2,3}$ and $K_4$ testing might be.... I seriously doubt that the brute-force approach highlighted above is optimal. Is there a known lower-bound?


texts: Why is there no FPTAS for the maximum independent set problem?

texts:
I want to prove that the NP-hardness of Maximum Independent Set implies that there is no FPTAS for the Maximum Independent Set problem unless $P=NP$.

I found the following approach after some research online:

Assuming that such an FPTAS exists which computes a $(1 - \epsilon)$-approximation for Maximum Independent Set on a graph G. I want to use this assumed algorithm as a subroutine in a new algorithm to solve the maximum independent set problem exactly. Now proving that this new algorithm runs in polynomial time would be a contradiction (assuming $P \neq NP)$ since this would mean that I solved the maximum independent set problem in polynomial time. Therefore there exists no FPTAS.

I can't figure out a polynomial time algorithm which uses the above assumed subroutine. How does this algorithm look like, how to use the assumed subroutine (for example what $\epsilon$ to choose?).


texts:
Are there any graph implementation data structures beyond the standard adjacency list/matrix ones? If so, what are they?

I welcome experimental ones as well as highly specialized ones.

A little background: I'm developing an algorithm that relies heavily on graph operations, so I'm doing research in graph implementation. I'm not looking for out-of-the-box solution, but rather for additional material in hope to combine my findings into something that will optimize my algorithm.

An adjacency matrix is not suitable for me in its core form, because it is costly to resize. In my environment, vertices are expected to be frequently added/removed.

An adjacency list is a bit better approach. Yet, it lacks the ability to efficiently cross-reference information from different nodes. Further, the graph is weighted, so I need immediate neighbors sorted for a fast search. However, the weights are also dynamic: they change frequently (are explicitly updated) and decay with time (change implicitly based on the type/time of the last operation).

The graph is expected to have somewhere between 50 and 100 vertices. Once a new vertex is added, it will form edges with some or all of the other vertices, depending on its life time.

I've tried using sorted lists, but still haven't found any efficient way to accommodate all the criteria listed above.
I also considered hash-tables, similar to the answer below, but they don't solve the problem with sorting.


texts: Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?

texts:
I've read a proof explaining why $A_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input.

Here's the copy-paste of that proof (link: https://courses.cs.washington.edu/courses/cse322/04au/Lect10.pdf):

$A_{\mathrm{TM}} = \{\langle M,w\rangle\mid M\text{ is a TM that accepts }w\}$ is
undecidable! Proof (by contradiction):

Assume $A_{\mathrm{TM}}$ is decidable  there’s a decider $H$, $L(H)$ = $A_{\mathrm{TM}}$.
$H$ on $\langle M,w\rangle = \mathrm{ACC}$ if $M$ accepts $w$
$\mathrm{REJ}$ if $M$ rejects $w$ (halts in $q_{\mathrm{REJ}}$
or loops on $w$).
Construct new TM $D$: On input $\langle M\rangle$:
Simulate $H$ on $\langle M,\langle M\rangle\rangle$ (here, $w = \langle M\rangle$).
If $H$ accepts, then reject input $\langle M\rangle$;
If $H$ rejects, then accept input $\langle M\rangle$.
What happens when $D$ gets $\langle D\rangle$ as input?
$D$ rejects $\langle D\rangle$ if $H$ accepts $\langle D,\langle D\rangle\rangle$ if $D$ accepts $\langle D\rangle$;
$D$ accepts $\langle D\rangle$ if $H$ rejects $\langle D,\langle D\rangle\rangle$ if $D$ rejects $\langle D\rangle$.
Either way: Contradiction! $D$ cannot exist, so $H$ cannot exist.
Therefore, $A_{\mathrm{TM}}$ is not a decidable language.

So, I don't understand why we need to give $H$ the input of $\langle D,\langle D\rangle\rangle$, why not give it the input of $\langle D,w\rangle$? And give $D$ the same input, isn't that the same thing? Or what's the logic behind the second $\langle D\rangle$? For some reason it's very confusing for me. Thanks.


texts:
Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the length of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle in order to find the length of $\text{LCS(A,B)}$?

Alternatively, given an oracle for finding both the subsequence and length of the Longest Common Subsequence between two sequences, it's easy to find $\text{LIS}(A)$: Given a sequence $A$, sort $A$ into $A'$, and calculate $\text{LCS}(A,A')$.

This question is prompted by the fact that there are $O(n\log n)$ algorithms for LIS but not LCS. On a separate note, are there any results comparing the hardness of the two problems or giving a superlinear/quadratic lower bound to LCS?


texts: Examples of difficult Hamiltonian Cycle Problems

texts:
I am working on implementing algorithms to solve Hamiltonian Cycle Problem. I need difficult problem graphs to test my implementations but my google-fu is weak and am unable to find any.
Please advise where I might find a set of difficult graphs for the Hamiltonian Cycle, or how to generate such graphs for testing.


texts: Can product DFA for intersection of two disjoint languages be minimal?

texts: I know that it isn't necessary that cross product automaton for two minimal DFAs be minimal, but according to my analysis, if two DFAs do not have any common string then their cross product of minimal DFAs would be minimal. What should I do to prove this?


texts: Are algorithms (and efficiency in general) getting less important?

texts: Since buying computation power is much affordable than in the past, are the knowledge of algorithms and being efficient getting less important? It's clear that you would want to avoid an infinite loop, so, not everything goes. But if you have better hardware, could you have somehow worse software?


texts: How to predict the time complexity of matrix multiplication and inverse on a GPU?

texts:
Nvidia GPU can speed up the matrix manipulation greatly. I want to have a basic idea to predict the consumed time for matrix manipulation.

How can I analyze the time complexity of matrix multiplication and inverse operation on a GPU?


texts: If $f(n) = O(g(n))$ then $\log\lfloor f(n) \rfloor = O(\log \lfloor g(n) \rfloor)$?

texts:
I need to prove that $\log\lfloor f(n)\rfloor = O(\log\lfloor g(n) \rfloor)$ if $f(n) =O(g(n))$.
I know that if $f(n) = O(g(n))$ then $\log f(n) =O(\log g(n))$, but I can't prove the current statement because it involves the floor function.


texts: Job assignment where each worker handles two non-consecutive jobs

texts:
There are $N$ workers and $2N$ jobs, named from $J_1$ to $J_{2N}$. There's a matrix $M$ denoting the subset of jobs can be handled by each worker: If $M_{i, j}$ is true, then worker $i$ can do job $j$.

Our task is to assign exact 2 jobs for each worker, s.t., each job is handled by exact one worker with respect to $M$. (So far the problem can be solved with max flow.) Moreover, If a worker $i$ handles job $j$, it can't handle job $j+1$.

The problem asks:

If there exists such an assignment
If there is, find out a solution to $\max_{Assignment}{\min_{i} {\left|  J1_i - J2_i \right|}}$, where $J1_i$ is the first job assigned to worker $i$, and $J2_i$ is the second job assigned to worker $i$. In other words, to maximize the minimum interval between two jobs for all workers.


texts:
We know that $NTIME(t(n)) \subseteq DSPACE(t(n))$ and we know - by Savitch's theorem - that $NSPACE(s(n)) \subseteq DSPACE(s^2(n))$.

By the space/time relation $(s(n) \leq t(n))$ I know that $NTIME(t(n)) \subseteq NSPACE(t(n))$, then by Savitch's theorem $NSPACE(t(n)) \subseteq DSPACE(t^2(n))$ and not $DSPACE(t(n))$, as stated above.

Where am I wrong?


texts:
Let $S(i,x_1,\ldots, x_n)$ be a primitive recursive predicate.
 \begin{equation}
 f(i_1,i_2,x_1,\ldots, x_n) =
 \begin{cases}
  1 &\text{ when for all i, }\; i_1 \le i \le i_2,\; S(i,x_1, \ldots, x_n)=1\\
  0 &\text{ otherwise}
 \end{cases}
\end{equation}

Show that $f(i_1,i_2,x_1,\ldots, x_n)$ is also primitive recursive

I use Davis Computability and Complexity book.
I get I need to write as described in this page.
Show $x^y$ is a primitive recursive function

But how to do for predicates? Even a similar example which has predicates would be very helpful.


texts: How to find whether a point is in a line or not

texts:
Suppose in a given plain there are  fixed number of lines. A point P lies on one of the line. How to find which line intersects the point P ? I am giving an example

In the above graph point P is on the line CE. We can determine it visually.But my problem is how to make the computer understand it. Is there any algorithm available to make it so ?


texts: Can the standard knapsack problem be solved using LLL?

texts:
It is well-known that the Merkle–Hellman knapsack cryptosystem can be solved using the LLL algorithm. In the Merkle-Hellman knapsack cryptosystem, we're trying to find a solution $x_i \in \{0,1\}$ such that

\begin{align}
\sum w_i x_i &= K,
\end{align}

where the $w_i$ are integer weights. Is it possible to find an approximate solution to the standard 0-1 knapsack problem

\begin{gather}
\text{maximize } \sum v_i x_i \\
\text{subject to} \sum w_i x_i \le K,\quad x_i \in \{0,1\}
\end{gather}

Using LLL?


texts: Is it decidable that a context free language contains a given regular language?

texts:
I've been asked to solve this problem, but I'm completely stuck now.

  Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable?

I know I've to find a reduction, and as a hint they told me that it is related to Acceptance Problem or Post Correspondence Problem, or probably with Non-empty Intersection problem ( $\{\langle G1, G2\rangle \in \text{CFG} \times \text{CFG} \mid L(G1) \cap L(G2) \not= \emptyset\}$), which are undecidable.

I've been reading about these problems for hours, and reading about reductions from these problems to others trying to find any idea, but I'm stuck.

I'd really appreciate any help, whether some hints or the answer.


texts: The transition function in a Markov decision process

texts:
A Markov decision process is typically described as a tuple $\langle A,U,T,R \rangle $ where

$A$ is the state space
$U$ is the action space
$T: A \times U \times A \mapsto [0,\infty) $ is the state transition probability function
$R:A \times U \times A \mapsto \mathbb{R}$ is the reward function

What does this $A \times U \times A$ actually mean in terms of the MDP? It  is written in all the papers, but never explained. Does it mean that all the states $a \in A$ are multiplied with all the action $u \in U$? Or something completely different?


texts: Is it possible to simulate oracle machines on 1-dimensional cellular automata?

texts:
My instinctual response is that it is possible, but I can't see how to simulate the oracle tape on a 1-d CA.

If not, are they able to be simulated on n-dimensional CA? My thought is that the oracle tape could be simulated on another row in, say, a 2+1-dimensional cellular automaton.


texts: In O(1) get the coordinate i,j of a diagonally ordered matrix

texts:
Say you have a matrix like this:

[][]int{
    {0, 2, 5, 9, 14},
    {1, 4, 8, 13, 18},
    {3, 7, 12, 17, 21},
    {6, 11, 16, 20, 23},
    {10, 15, 19, 22, 24},
}

As you can see, it is diagonally ordered

Question:
In Order O(1) if I give you a number N, give me the position i,j.

For example, on a regular ordered matrix

[][]int{
  {0,1,2,3},
  {4,5,6,7},
  {8,9,10,11},
  {13,14,15,16}
}

The solution is

j := n % len(m)
i := n / len(m[0])

With that you get i,j.
Ex: N=9 -> 2,1

But how to get them for diagonals?


texts: Prove or disprove {wtw^R | |w| = |t|} is context free

texts:
The language $S_c$ defined as: $S_c = \{wtw^R \mid w,t \in \{0,1\}^\star \text{ and } \lvert w \rvert = \lvert t \rvert \}$

It looks like the language can be "pumped" by context free pumping lemma, but the pumping lemma doesn't prove the language is context free. So I'm thinking of building a PDA that recognizes it. But I'm stuck on constructing the PDA, my initial thought is using nondeterminism to guess the string $w$ and $t$, then compare the values after $t$ which is string $w^R$. But still hard for me to come up a whole construction at this moment, any suggestions?


texts: Find maximum non contiguous subarray that respect a specific rule

texts:
Given these two arrays:

[5, 3, 4, 1, 2]

[1, 3, 2, 4, 5]

Find the maximum subsequence in both arrays that the index of the elements are in a crescent order:

Example: [3, 4] it's an answer because the indexes are in a crescent way in both arrays. (same as [1, 2]). Therefore, the subsequence the answer [3, 4, 1] is wrong, because the indexes are the crescent in the first array, but not on the second one.

The output of the program should be the length of the max non-contiguous subarray.

This is the code I wrote for solving this, but it only takes the first subarray, and I'm having difficulty to generate the other possibilities

vector<pair<int, double>> esq;
vector<pair<int, double>> dir;
// N is the size of esq and dir
// pair<int, double> where int is the key (show in the example array) and double is the value, used for sort previously.
int cont = 1;
for (int i = 0; i < N - 1; i++)
{
    int cont_aux = 1;
    pair<int, double> pivot = esq[i];
    auto it_dir = find_if(dir.begin(), dir.end(), [&pivot](const pair<int, double> &p) { return p.first == pivot.first; });
    int last_index = it_dir - dir.begin();

    for (int j = 0; j < N; j++)
    {
        pair<int, double> actual = esq[j];
        auto it = find_if(dir.begin(), dir.end(), [&actual](const pair<int, double> &p) { return p.first == actual.first; });
        int pos = it - dir.begin();

        if (pos >= last_index) {
            last_index = pos;
            cont_aux++;
        }
    }

    cont = max(cont, cont_aux);
}

cout << cont << endl;


texts:
Given an array of length $n$ we need at least $O(\log n)$ memory to store its length. And we need the same $O(\log n)$ memory to store index. With large $n$, index may not fit in one extra cell.

So it is impossible to construct a sorting algorithm for arrays which uses $O(1)$ additional memory.

On the other hand, one can construct sorting algorithm for some other sequence, e.g. list. This can be modification of bubble sort (or cocktail sort). Something like this:

1. goto head, set flag to false
2. if current element is bigger than next, swap and set flag to true
3. if there is no next element and flag is true, goto 1
4. if there is no next element and flag is false, end

So this algorithm uses only two extra cells: one for flag and one for swap.

Am I missing something or am I right and it is impossible to construct a sorting algorithm for arrays with constant memory?


texts:
Let's say we have the following grammar

expr1 ::= ... // Actual definition doesn't matter
expr2 ::= ... //
expr3 ;:= ... //
foo ::=  expr1 | expr2 | expr3

When it comes to parsing foo we note that foo could be parsed in parallel.

p1 = task parse( expr1 )
p2 = task parse( expr2 )
p3 = task parse( expr3 )

Question

Would continuing on the first to complete be better.

result = task.WaitAny( p1, p2, p3 ) // wait for any (parsing) task to complete

or would it be better to wait for all the (parsing) tasks to complete?

task.WaitAll( p1, p2, p3 ) // wait for all (parsing) task to complete

What are the potential issues with simultaneous parsing?
 or
Does the ordering of clauses matter?


texts:
A Boolean function is a function $f:\{0,1\}^n\rightarrow\{0,1\}$.

The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\{0,1\}$ to be flipped or to be left unchanged. The same can be said of $\mathrm{XOR}$ gates.

In this sense we can start with an initial machine configuration $\textbf{b}=(b_1,\ldots,b_n)$ such that $b_i\in\{0,1\}$ and $\mathrm{XOR}$ it with successive values $\textbf{v}_i$:

$
\textbf{b}\oplus\textbf{v}_1\oplus\textbf{v}_2\oplus\textbf{v}_3\ldots
$

Each state $\textbf{v}_i$ would represent a permutation of some element in $\textbf{b}$. This process effectively mimics a Turing machine and assumes that there is some generator for the values $\textbf{v}_i$.

So can we say that Boolean functions Turing complete?


texts:
I'm new to stackoverflow so please bear with me. A tutorial question I got given was as follows:

You are given that $C \subseteq D \subseteq F^n_q$ where $|C| < |D|$ and $C$ is a perfect code. Show that $d(C) > 2d(D)$.

I have been using the fact that $C$ is a perfect code so it attains the Hamming bound then saying that it is less than the Hamming bound for $D$, but you get an inequality involving a binomial sum on both sides, which is really messy. I'm not really sure what other properties I can use to work this out. Any help would be really appreciated, thanks


texts: A general algorithm for greedy algorithms

texts:
I have been refreshing on greedy algorithms as an algorithm design technique. I have read many sources for an explanation of what a greedy algorithm is, because I would like to put together a general greedy algorithm.

When reading these sources, I have gathered all of the important concepts to try to come up with this general algorithm for the greedy selection technique. By "general" I mean that it summarizes the behavior
 of the technique for all possible problem for who this technique would yield a correct solution.

I would like some input on it. Here is take 1:

Let $f$ be a function from $S$ to any set. The following algorithm tries to perform greedy choices per each search iteration of element of $S$, in order to try come up with the best possible point for $f$ over $S$ given a set of constraints $C$:

Select p0 from S;
i := 1;
Let P be a set of already chosen points from S to be initialized to {}
Let F be the set of values of f for each element of P to be initialize to {};
while S != {}:
    Make a greedy choice for p_i based on p_{i - 1};
    if f(p_i) is feasible based on constraints from C and has improved:
        p_{i - 1} := p_i;
    Add f_i := f(p_i) to F;
    Remove p_{i - 1} from S and save it in P;
 return P, F;

My specific question is: How far is this first take from being a correct generalization of the greedy selection technique for algorithmic design?

This should be fun :)


texts:
I think I understand the RP complexity class (along with coRP, BPP, and ZPP). However, I can't seem to think of how an RP algorithm might be formulated.

How can the random coin flip possibilities allow for a guaranteed response of NO when the correct answer is NO, yet return with a probabilistic chance YES or NO when the answer is YES?

Are these actually algorithms we have examples of or is it just a theoretical class without any known examples? If there are examples, could someone please lay one out?


texts: Is it possible to make N-way Controlled-NOTs out of Toffoli gates, without extra work bits?

texts:
I'm working on exercise 4.29 of Nielsen and Chuang:

  Find a circuit containing O(n^2) Toffoli, CNOT, and single qubit gates which implements a $C^n(X)$ gate (for n >3), using no work qubits.

As part of solving this exercise, I'm trying to figure out if the task of making a NOT-controlled-by-N-bits is possible classically (i.e. without using single qubit gates, except the NOT gate).

This is trivial to do if you have work bits initialized to 0 available, but I haven't been able to figure out how to do it without work bits. I'm also not sure how to approach an impossibility proof.

The main thing I've figured out is that, if I could make $Increment$ and $Decrement$ gates, then I could do it like this:

   ____    ____
--|    |--|    |---    --•--
--|    |--|    |---    --•--
--| +1 |--| -1 |--- == --•--
--|    |--|    |---    --•--
--|    |--|____|---    --•--
--|____|-----------    --X--

But I also can't figure out how to make those gates, at least not without the many-controlled-not gate I'm trying to make.

Is this even possible (the limited-to-classical case, not the exercise)?


texts: Express polynomial as sum of two lower-degree polynomials, modulo another

texts:
Suppose I have a polynomial $p(x)$, and a "modulus" polynomial $q(x)$ of degree $d$.  I want to find two polynomials $r_1(x),r_2(x)$ of degree $\le d_1,d_2$ such that
$$p(x) \equiv r_1(x) x^t + r_2(x) \pmod{q(x)}$$
Assume $d_1+d_2= d$, and that we are working over some finite field.
Given $p(x),q(x),d,d_1,d_2,t$, is there an algorithm to find $r_1(x),r_2(x)$ that meets the conditions above (if any exist)?
In the special case where $t=d_2$, this is handled by reducing $p(x)$ mod $q(x)$, but I'm wondering if there is an efficient algorithm for the more general case.  One algorithm is to express the coefficients of $r_1(x),r_2(x)$ as unknowns, write down $n$ linear equations in terms of these $d_1+d_2$ unknowns, and then solve the resulting linear system; this will take $O(d^3)$ time.  Is there a more direct solution exploiting that these are polynomials, perhaps one achieving faster performance, such as $O(d)$ time?


texts:
I am looking for algorithms to optimize a strictly monotonic function $f$ such that $f(x) < y$

$f : [a,b] \longrightarrow [c,d]
\qquad \text{where } [a,b] \subset {\mathbb N},  [c,d] \subset {\mathbb N}$
such that $\arg\max{_x} f(x) < y$

My first idea was to use a variant of binary search, pick a point $x$ in $[a,b]$ at random; if $f(x) > y$ then we eliminate $[x, b]$, and if $f(x) < y$ we eliminate $[a, x]$. We repeat this procedure until the solution is found.

Do you have any other ideas to maximize the function $f$ ?


texts:
I have the following claim:

Prove or disprove: If a key in a red-black tree has exactly one child (which isn't null) then it is always red.

My attempt:
Disproof.
We will exhibit a counterexample:

This tree satisfies the conditions of being a red-black tree,
since:

The root is black.
All leaves are black.
There isn't any red key.
In each path there is the same amount of black keys, in particular, we have three black keys in such paths.

However, we have two keys in level 1, which have one child and it is black.
$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad  \blacksquare$

Is this counterexample correct?


texts: Given regular language $L$, is $L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length} \in L \}$ regular?

texts:
I was given a question and don't really know to solve it.

  Given a regular language $L$, is the following language also regular?
   $$L_1 = \{ w \mid \text{each prefix of } w \text{ of odd length is in $L$} \}.$$

I think that $L_1$ should be regular, but I don't have a clue how to prove it.

Thank you for any input.


texts: A* to find the longest path in a directed cyclic graph

texts:
I have written an A* algorithm to find the shortest path through a directed cyclic graph.  I am trying to modify it to find the longest path through the same graph.

My attempt was to write it so that all I change is [1] the weights per edge (making them negative instead of positive) and [2] the heuristic function.

I seem to be having trouble getting it to do this. It is pretty good at finding the longest path sometimes, but it is not guaranteed.

It seems that the problem lies with [2] the heuristic -- for shortest path an L2 norm is a good optimistic way to get it to head towards the goal, but for longest path I want the heuristic to point it at paths that are further from the goal to continue to increase total length.

If I set the heuristic to return 0 so that it's a Dijkstra's search, it's less predictable as there's no incentive to search from nodes further away (using [1] negative weights per edge).

I think if I keep the weights positive and try to maximize the score instead of minimize it may work, but I was attempting to do this without changing the algorithm, only the edge weights and the heurstic.

I have found similar posts on stackExchange but they don't answer my specific questions:

Q1) Can this be done with A*

Q2) Is setting the weights negative the right thing to do

Q3) Is the only way to do this is to set the heuristic to zero and keep the weights positive and try to maximize the score instead of minimize it?


texts: How many valid and unique Turing machines are there with restricted states and characters

texts:
This is based off of my question here, where I was helped to find the number of Turing machines with restricted states and characters which is $(3(c+1)(n+2))^{(c+1)n}$. Now I'm wondering how many of those are unique, when I asked on IRC it was suggested that most of them are duplicates. Unique and valid in this case means that it is the only Turing machine included that when given the specific input terminates with the same tape, same position, and in the same accepting/rejecting state. Valid means they will accept/reject at some point regardless of input.

Some ideas I had to limit it are that some states might be unreachable and hence simplify down to one with less states. This reduces it by
$$(3(c+1)(n+1))^{(c+1)(n-1)}$$
different machines. This is true because for each machine one state smaller you can effectively leave it as is, just modify it by adding $c+1$ new transitions from a new state. Since you didn't modify any of the other states this is unreachable and won't affect execution, therefore they are functionally equivalent. The reason this won't apply to all below it is that they are included in the count for $n-1$. If they were padded to $n$ states and they started with $i < n-1$ states they would have to have $n-1$ states somewhere along the line as they were building up and therefore already be included.

Are there any other ways to remove equivalent programs?


texts: Matching two lists of different sizes with exceptions?

texts:
Suppose that I have two lists of numbers (which represent IDs for rows in a database):

list1 = [1, 4, 7, 8]
list2 = [2, 3, 5, 6, 7]

I would like to write an algorithm to pair each number in the larger of the two lists with a number in the smaller list such that:

Every item must appear in at least one pairing
No item from the larger list appears in more than one pairing
No item from the smaller list appears more than is necessary to satisfy the first constraint (in other words, if the larger list has 5 members and the smaller list has 3, no item from the smaller list appears more than twice)

The algorithm I came up with is fairly simple (in pseudo-code):

offset_into_smaller_list = 0
foreach item in larger_list
    pairing = [ item, smaller_list[offset_into_smaller_list] ]
    offset_into_smaller_list++
    if offset_into_smaller_list == sizeof(smaller_list)
        offset_into_smaller_list = 0

However, there's a small twist.

I also have a list of exceptions (a pairing that is forbidden).

I would like to modify the algorithm to take these exceptions into account. If one or more valid solutions exists, I'd like the algorithm to find one in the least amount of time possible.

My initial approach began with:

Calculating all combinations (there are sizeof(list1) * sizeof(list2))
Removing the exceptions from the list of combinations
Grouping the combinations using the item in each pair that belongs to the larger list
Iterating over the groups and selecting one pair from each group

I get stuck at the last step. After each iteration, the number of valid combinations that remain in each group shrinks.

Is there a better approach to this problem? How can I ensure that this algorithm will always find a valid solution if one exists? How can I make it as efficient as possible?


texts: Why is an accurate time so important for servers and computers?

texts:
I just saw this short documentary about atomic clocks. The person working for the Atom clock company gets asked what would happen is all the atom clocks would be turned off and he replayed that cell phone services and the internet would stop working. I have read that an accurate time is important but do not now why.

Why is an accurate time so important for servers and computers and why would these services stop working?


texts: is duality principle in boolean algebra is true for every expression

texts:
Let say A = 1 and B = 1
and then A+B = 1
now by using duality(replacing or gate by and gate and 1 by 0) we can say that, A.B = 0
but this is not 0, because 1.1 = 1, so please anyone clear my misunderstanding here, Thank in advance


texts: Maximum number of disks in RAID with parity?

texts:
From what I understand, to implement RAID 5, one would need a minimum of 3 disks, where 2 would be for data storage, and the third would be for the parity. But what is the maximum number of disks one can have?

For example, let's say each disk is 1GB, but I have 5GB of data, would I be able to make a RAID 5 with 6 disks? Is there a mathematical maximum?


texts:
Suppose I am given $n$ fixed width integers (i.e. they fit in a register of width $w$), $a_1, a_2, \dots a_n$ such that their sum $a_1 + a_2 + \dots + a_n = S$ also fits in a register of width $w$.

It seems to me that we can always permute the numbers to $b_1, b_2, \dots b_n$ such that each prefix sum $S_i = b_1 + b_2 + \dots + b_i$ also fits in a register of width $w$.

Basically, the motivation is to compute the sum $S = S_n$ on fixed width register machines without having to worry about integer overflows at any intermediate stage.

Is there a fast (preferably linear time) algorithm to find such a permutation (assuming the $a_i$ are given as an input array)? (or say if such a permutation does not exist).


texts: Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G?

texts:
The following problem is from my algorithms class:

  Given a graph $G(V, E)$, a set $C \subseteq V$ is called a biclique iff  $G[C]$ is a complete bipartite graph, where $G(C)$ is the subgraph induced by $C$. A biclique is called maximal if it is not a subset of a larger biclique. Then our problem asks whether there exists a subset of $V$ of size at most $k$ hitting all maximal bicliques of $G$, i.e., can we find $k$ vertices in $V$ such that every maximal bicliques of $G$ cantains at least one vertex of these $k$ vertices. Prove the problem is NP hard.

I'm trying to prove
$$\text{Vertex-Cover} \le_p  \text{This-Problem}$$
but haven't came up with a solution until now. Could anyone help me out here?


texts: Name for a class of problems solvable in $n^{O(\log \log n)}$

texts:
Isomorphism testing of projective planes can be done in $n^{O(\log \log n)}$. This class is contained in quasi-polynomial time. I would like to know more about this class and natural problems in it.

  Is there a standard name for this class of problems?

Also, I am looking for a reference (or survey) that gives other natural problems (without known polynomial-time algorithms) in this class.


texts: Is oracle computer capable of doing infinite loops?

texts:
Solve this problem: "build an infinite binary oscilator"

With a Turing Machine we can solve it

a=False
While True:
   a=not a
   print a,

then output will be

True False True False True False ...

(for ever)

I think an oracle can't do it, because its definition, it could solve in "one operation", but here there's not halting as a request of the problem statement. Is it true?

EDIT:  Oracle definition from wikipedia

".. an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used."

So what if that TM ask its black box oracle to create an infinite binary oscilation?

   1- oracle black box can't do infinite loops
   2-TM can't ask that problem to oracle
   3- Does it return a string with a source code as answer? weird
   4-or other options...


texts: Algorithm to find whether there is a path (any path) above length X between two vertices

texts:
We all know how to find the shortest path between two vertices, but what if I just want to know the answer to this question - is there a path, (any path), between vertex A and B of length larger than some X?

Should start from the shortest path, and then merge adjacent nodes if its length is less than X? (or extend the search "circle" gradually)

I don't want to first find all possible paths and then filter out those shorter than X, I want to stop the moment I find any path above a certain length between the two vertices, (and stop if I haven't found one after some MAX iterations)

(I assume I first do a shortest paths to find if there is at all any path between the nodes to avoid searching if there isn't)

It somehow feels it should be simpler that what I'm making it, but I can't seem to find a text-book algorithm for it (e.g. BFS / DFS / Dijsktra / Bellman Ford are not really helping here, right?)

I'm sure it's simple, but I need some push in the right direction.

(cross posted from https://softwareengineering.stackexchange.com/questions/283038/algorithm-to-find-whether-there-is-a-path-any-path-above-length-x-between-two based on suggestions in the comments)


texts:
I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG.

That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still reach after removal of edges.

If this is a standard problem, please point me to some model solution.


texts: VC dimension of monotone disjunctions of length k over n variables?

texts:
There are of course $n \choose k$ monotone disjunctions which bounds the VC dimension at $\log_2 {n \choose k}$. I'm wondering if this is bound at $k \log_2 n$? (Possibly follows from combinatorial identities).

More generally I'm looking at the claim in An algorithmic theory of learning: Robust concepts and random projection: "Further, it is NP-hard to learn a disjunction of $k$ variables as a disjunction of few than $k \log n$ variable." The author states this without proof; I'm assuming it's well-known or obvious but am trying to figure out why or where it is proved.


texts:
What is the difference between int 21h and int 80h?
I get that both perform interrupt functions, but what is their difference?


texts: What is the complexity of comparing point sequences?

texts:
Given two sorted arrays of floating point numbers $X$ and $Y$, we can define the  S-distance as follows. The S-distance is defined as the minimum cost associated with the transformation of one point pattern $X$ into a pattern $Y$ by deleting, adding, and moving points (that is adding a constant to all points).  The cost of a transformation is:

$$p_d|X_{delete}| + p_a|X_{add}| + p_m d$$

where $p_a$, $p_d$ and $p_m$ are parameters and $X_{delete}$ and $X_{add}$ are subsets of $X$ that are deleted and added.  $|X_{delete}|$, for example,  is the number of elements in $|X_{delete}|$ and not the sum of the values. $d$ is the value that we are adding to all the points in the sequence $X$.

For example, say $X = (1,2,3)$ and $Y = (2,4)$ then one possible transformation of $X$ into $Y$ has cost $p_d + p_m$ as we can delete $2$ from $X$ and then increase both the points in $X$ by $1$ to make $(2,4)$ (so $d = 1$).

By adding a point I mean inserting a new point into the array.

I am trying to work out what the complexity of computing this distance
is. It is not obvious to me how to do this by dynamic programming for
example.

@Gassa gives a solution using $O(n^2)$ hash function calls. Is there a simple dynamic programming (or other) solution that doesn't require any hash function calls at all?


texts:
Assume we are given $k$ bins of capacity $b$ and $n$ items with integral sizes $x_1,\dots,x_n$. The bin packing problem is to decide whether there exists an assignment of items to bins such that no bin exceeds its capacity. In this standard from, the bin packing problem is well known to be NP-hard. However, consider a version of the problem where every items has a twin of equal size. More formally, if $i$ and $j$ are twins, it holds that $x_i = x_j$.

For two bins, the problem is easy since there exists a feasible solution if and only if a packing where no twins share the same bin is feasible. However, what happens if we have more than two bins? I suspect that the problem becomes NP-hard. Unfortunately, I have not been able to prove this so far.

Does anyone have an idea for a reduction or know if the problem has been studied before? Also, if the problem is hard for twins, does the hardness carry over to triplets, quadruplets etc.?


texts:
I want to approximate a Gaussian function as shown below
$$
e^{\frac{-\|x-c\|^2}{2\sigma^2}} \approx \sum_{i=1}^{N}\alpha(c,c_i)e^{\frac{-\|x-c_i\|^2}{2\sigma^2}} \forall x
$$
Here c, $\sigma$ and $c_i$ are known. Are there functions $\alpha(c,c_i)$ which gives a good approximation? The limitation I am facing is that I can not optimize as I have to calculate the functions $\alpha$ for various c(around 1024*1024) thus leading to too many optimizations. I used linear solver as this optimisation problem can be framed as $A\alpha=b$. Here $x$ in the above equation is sampled according to each $c$. Hence for every $c$, both $A$ and $b$ in $A\alpha = b$ changes.

I am also fine if functions in RHS are not Gaussians i.e existence of pair of $\alpha$ and $f_\sigma$ such as

$$
e^{\frac{-\|x-c\|^2}{2\sigma^2}} \approx \sum_{i=1}^{N}\alpha(c,c_i)
 {f_\sigma}(x,c_i) \forall x
$$

Can someone help me to point out how to go about it?
Here N can be treated as a variable. So as N increases number of gaussians used to interpolate increases and hence get a better approximation.

Now to explain what I meant by a good approximation : The function in LHS is used as a filtering kernel to filter my data. Replacing it with RHS (one part of my algorithm) will help in speeding up my filtering algorithm by a huge margin. Now I check my performance by comparing actual filtering algorithm and this approximation by using parameters such as Mean Square Error.


texts:
Tomorrow I'm going to be teaching a class on Aho-Corasick string matching. I'm pretty sure I know how to pronounce Margaret Corasick's name, but I don't actually know the proper pronunciation of Alfred Aho's surname.

Can anyone comment on the proper pronunciation so that I can properly give credit where credit is due?

Thanks!


texts: Why are these BVH split heuristic formulas different?

texts:
I've been doing some research into changing the split heuristic I use for a work project comprised of a BVH binary tree.
The heuristic I currently use is centroid median as described here, but I seek to use the surface area heuristic (SAH) now. Several papers denote the cost function for determining the split as:
$$c(A, B) = t_{trav} + p_{A}\sum_{i=1}^{N_{A}}t_{isect}(a_{i}) + p_{B}\sum_{i=1}^{N_{B}}t_{isect}(b_{i})$$
Notionally it is described in detail here, but to summarize, it is the cost of a ray intersect of primitives at this split.
However, I've seen an optimization technique, described as "binning", where $K$ pre-determined bins are computed and therefore the cost function for determining the split is:
$$c(A, B) = A_{a}N_{a} + A_{b}N_{b}$$
This is outlined here in Section 3.1, as well is several other documents (1, 2, 3).
What's the rational/reasoning behind these two different cost models?


texts:
My basic position is that everything is in P. Then comes the time hierachy theorem and EXP. That's easy: simulate and then diagonalize. After that comes EXP-completeness; that's difficult to swallow. Papadimitriou basically says that the proof is very similar to that of Cook-Levin theorem and do it yourself. Also, I wish to see the paper why Checkers is EXP-complete, but couldn't find a free version on the net.

Can you show me why a problem can be EXP-complete and not in P provably? How is the diagonalization encoded in the problem instances?


texts: Under what circumstances are one-way functions reducible to their hard-core bits?

texts:
I've seen competing claims about hard-core predicates. On the one hand, there's the basic definition

  Let $f : \{0,1\}^n \rightarrow \{0,1\}^k$ and $b : \{0,1\}^n \rightarrow \{0,1\}$ be computable in polynomial time. We say that $f$ is a one-way function with hard-core bit $b$ if, for all randomized algorithms $B$ and all constants $c$,
  $$
\mathbb{P}(B(f(x)) = b(x)) = \frac{1}{2}+o(n^{-c})\,.
$$

But I've also read the statement

  We want the problem of finding $x$ to be reducible, in polynomial time, to the problem of finding $b(x)$, so that finding $b(x)$ is just as hard as finding all of $x$. In that case $b$ is called a hard-core bit for $f$.

How are these requirements related? Is one stronger than the other? Or do they imply each other?


texts: Sorting in computing longest increasing subsequence

texts:
I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman.
I'm struggling to understand parts of the proof of Theorem 3.5,
especially this bit:

Now consider the following enhancement $A^*$ of $A$. Whenever $A$ concludes that $L < k$, $A^*$ continues to completely sort $S$ [...]

This is used to show a bound for $L \ge k$, but why are they sorting the sequence?


texts: Complexity analysis of an unsolvable algorithmic problem?

texts:
In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned that any unsolvable problem would have a complexity of infinite.

However, this strikes me as strange. It feels intuitive to me to say that an unsolvable problem would have no complexity, as any attempt to solve it would be impossible. The quantity of infinity says to me that "if you had unlimited time, you could solve it", but what if it's a question that the answer simply cannot be computed for?

Is this O(infinity) concept common in algorithmic complexity analyses?


texts: SQL, optimizing a select statement in relational algebra

texts:
is it possible to rewrite the following sql statement
$\pi_{R.a,S.d} (\sigma_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}((R\times S)\times T))$
?

My problem is, i dont know if it is possible to split $\sigma_{R.b = "d" \land S.d \geq 100 \lor T.d \geq 200}$ to $\sigma_{R.b = "d"} \land \sigma_{S.d \geq 100 \lor T.d \geq 200}$,because the rules say i can split $\sigma_{x \land y}$ to $\sigma_{x} \land \sigma_{y}$ but i am not allowed to split $\sigma_{x \lor y}$.

Relations R(a,b,c), S(b,d) with a,d are integers, b,c,d are strings.

Edit: It is important to use brackets to specify which bool statements are compared, also if you have a statement that uses $ \land and \lor $ you are not allowed to not write the brackets, that was my major mistake. correct formular
$\pi_{R.a,S.d} (\sigma_{(R.b = "d" \land S.d \geq 100) \lor T.d \geq 200}((R\times S)\times T))$

In this case we are not allowed to split the $\sigma$ statement because we are bound to the $\lor$.

We could split the $\sigma$ if the statement would be:

$\pi_{R.a,S.d} (\sigma_{R.b = "d" \land (S.d \geq 100 \lor T.d \geq 200)}((R\times S)\times T))$
to
$\pi_{R.a,S.d} (\sigma_{S.d \geq 100 \lor T.d \geq 200}((\sigma_{R.b = "d"}(R)\times S)\times T))$
Which would lead to a smaller kartesian product.
At the end:
What we are seeking is to bring the $\sigma$ as close to the leafs as possible to reduce our kartesian produkt


texts:
It is well known that regular languages are characterized by the Myhill-Nerode equivalence. For language $L$ over $\Sigma^*$ define the equivalence $x\sim_L y$ over $\Sigma^*$ iff for all $z\in\Sigma^*$ we have $xz\in L \iff yz\in L$. Then $L$ is regular iff $\sim_L$ is of finite index, i.e., has a finite number of equivalence classes.

I know that the relation can be used to show that some languages are not regular, by indicating infinitely many strings that are not equivalent.

My question: can we easily use Myhill-Nerode to show closure properties of regular languages? Or should we use the "syntactic congruence" of languages?

As an example for prefix it is easy, as $x\sim_L y$ implies $x\sim_{\mbox{pref}(L)} y$.  But how do we handle suffix, concatenation, star, mirror?


texts: Number of multiplications and additions in the given code

texts:
$N:=2^p$

Input: $f \in \mathbb C^N$

1: $n=N/2$

2: initialize vectors $f^{(1)}, f^{(2)} \in \mathbb C^n$

3: $w_N^0=1$

4: for $j=0,\ldots,n-1$ do

5: $\ \ \ \ \ f_j^{(1)}=f_j+f_{j+n}$

6: $\ \ \ \ \ f_j^{(2)}=(f_j-f_{j+n})w_N^j$

7: $\ \ \ \ \ w_N^{j+1}=\exp(-2\pi i/N)w_N^j$

8: end for

9: if $N=2$ then

10: $\ \ \ \ \, $set $c:=(f^{(1)},f^{(2)})\in \mathbb C^2$

11: else

12: $\ \ \ \ \, $   evaluate (recursively) $c^{(1)}=FFT(f^{(1)})$

13: $\ \ \ \ \, $ evaluate (recursively) $c^{(2)}=FFT(f^{(2)})$

14: $\ \ \ \ \, $ set $c=\Big(c_0^{(1)},c_0^{(2)},c_1^{(1)},c_1^{(2)},\ldots,c_{n-1}^{(1)},c_{n-1}^{(2)}\Big) \in \mathbb C^n$

15: end if

  Let $m_p$ be the number of multiplications and $a_p$ the number of additions for $N=2^p$. I want to show that

$$m_p\le p2^p, \ \ \ \ \ a_p\le p2^p, \ \ \ \ \ p\in \mathbb N$$

  Therefore we have a total complexity of about $N \log (N)$ complex additions/ multiplications

We didn't hear about $\mathcal O$ yet, I first of all just want to understand why $a_p\le p 2^p$. I came across the following $f^{(1)},f^{(2)} \in \mathcal C^{2^{p-1}}$ so we have a 'recursion depth' of $p-1$, and $N$ additions and $N$ multiplications every time we run it. Therefore $a_p=2^p+2\times 2^{p-1}+4\times 2^{p-2}+\ldots + 2^{p-1}\times 2=p\times 2^p$. I don't know if this is correct and I don't get where $2^p+2\times 2^{p-1}+4\times 2^{p-2}+\ldots + 2^{p-1}\times 2$ comes from


texts: How is the Longest Path Problem NP complete?

texts:
From the following link:

https://www.csie.ntu.edu.tw/~lyuu/complexity/2016/20161129s.pdf

So basically, in our iff proof, we have to show two directions:

Forward: If Hamiltonian Path has a yes-instance, so does longest path. This makes sense because we can just let "k" = |V| - 1 if hamiltonian path is yes. Then clearly there is a longest simple path with |V| - 1 edges.

I'm having trouble with the backward part

Backward: If Longest Path has a yes instance, so does longest path. Let's assume that there is a longest path from s to t of length k (this can be a different k than the one we defined above?). How does that guarantee that there is a hamiltonian path from s-t? If it is the same k, where k = |V| - 1, then I agree there is a hamiltonian path, but what if this k is something different?


texts: Fast, stable, almost in-place radix and merge sorts

texts:
I've developed LSD radix sort algorithm that is

stable,
about as fast as the classic LSD radix sort,
require only $O(\sqrt{RN})$ extra space when we sort into R buckets.

The same technique also allows to perform stable, efficient, almost in-place merge & quick sorts; as well as stable almost inplace merge/partition operations; and also applicable to some other list processing algorithms.

I describe it in my answer to this question. I believe that the proposed modifications to classic algorithms has important practical value. Other known techniques for (almost) in-place stable sort:

WikiSort and GrailSort that have even smaller memory requirements but seems to perform more data moves than the simple mergesort
highly theoretical in-place stable sorts that doesn't even pretend to have practical usefulness

EDIT: I've found this technique described 4 years ago in section 3.2.3 of paper A comprehensive study of main-memory partitioning and its application to large-scale comparison- and radix-sort


texts: Is there a "natural" undecidable language?

texts:
Is there any "natural" language which is undecidable?

by "natural" I mean a language defined directly by properties of strings, and not via machines and their equivalent. In other words, if the language looks like
$$ L = \{ \langle M \rangle \mid \ldots \}$$
where $M$ is a TM, DFA (or regular-exp), PDA (or grammar), etc.., then $L$ is not natural. However $L = \{xy \ldots \mid x \text{ is a prefix of y} \ldots \}$ is natural.


texts:
I recently came across a function called the strawman algorithm which the pseudo code looks like this:
StrawmanSubarray(A):
  Initialize bestsum = A[0]
     For left=0 to n-1:
        For right = left to n-1:
           Compute sum A[left] + . . . + A[right]
           If sum > bestsum: bestsum = sum

The time complexity is Θ (n^3), and I don't quite get where is the 3rd n comes from to get Θ (n^3)?


texts:
On our lecture slides we have two different notations of the gaussian function.
First it gets introduced as follows:
$$p(x_n|\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{(x_n-\mu)^2}{2\sigma^2}\} \text{ with } \theta=(\mu,\sigma)$$
But later it is used like this:
$$\frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{||x_n-\mu||^2}{2\sigma^2}\}$$
What is the difference between $$(x_n-\mu)^2$$ and $$||x_n-\mu||^2$$ or are they equal?


texts:
I've been going through the control signal table and I noticed something
confusing on when I should set the value as 'don't care' or 0 for control signal.

For example when doing the R type add instruction, we don't go through the
data memory. When we are done with addition inside the ALU, the result will justbypass the data memory and will be written on the destination register.

So I thought, being 'don't care' for the MemWrite and MemRead would also be ok
rather than being 0. But on the signal table, it says 0.

I wonder where the differences are made when deciding rather to put 'don't care' and 0.

Thanks!


texts: Is the set of context free grammars that generate all words in co-RE?

texts: Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.


texts: A set that is not polynomial time enumerable

texts:
For a set $I\subseteq \Bbb N$, defined $s_{I}(n)=\min\{i\in I\mid i>n\}$. The set $I$ is called polynomial-time-enumerable if $s_I(n)$ is computable in $\mathsf{poly}(n)$ time.
Most of the sets I can imagine are polynomial time enumerable. I am really looking for an example of a set of integers that is NOT polynomial time enumerable.
Thanks in advance.


texts: Converting context-free grammar to chomsky normal form

texts:
I'm trying to prove that the following CFG can be converted to a CNF:

S -> aAB
A -> aAa
A -> bb
B -> a

Here below is how I've managed so far:

Step 1: add a new start state

S0 -> S
S -> aAB
A -> aAa
A -> bb
B -> a

Step 2: remove epsilon rules

There are no such rules in this CFG.

Step 3: remove non-terminal to non-terminal rules

S0 -> aAB
S -> aAB
A -> aAa
A -> bb
B -> a

Step 4: make right-hand-side not contain more than $2$ non-terminals or $1$ terminal:

S0 -> BC
S -> BC
A -> BF | EE (A -> aAa and A -> bb in one line)
B -> a
C -> AB
E -> b
F -> AB

So this is where I got confused. I have now both C and F that go to AB. If I've done this correctly that would mean that either C or F can simply be removed. Or, of course, I've done something wrong in this procedure.


texts: Proving there exists an infinite number of Turing machines is a decidable problem

texts:
I have a Turing machine M and I have to answer the question are there infinitely many Turing machines that recognize L(M)? I also need to describe a Turing machine that solves this problem. My idea is to say that we can simply increase the number of states by adding a new unreachable state. Each time I add a new state, it's still considered a new TM and because they're unreachable, I can say that they still accept the same language.

The only problem I'm having is describing a TM that can solve the problem. I was thinking that if I create a new TM (let's call it N) that represents M, I could say that N just needs to modify the transition function to create an unreachable state and once it does that it can add an infinite number of unreachable states which means there exists an infinite number of TM's. My problem is that I'm not sure if this is all I have to do to prove this and if it is then is my TM N enough to solve the problem or does it need to do more than just modify the transition function? N has to be decidable so it can't just keep adding states or else it will go on forever.


texts: How static Bayesian networks are stored? Like Hugin etc

texts: I wanted to know the standard format to store the Bayesian network structure? I came across Hugin format and others. But couldn't find out the documentation as how its been written, if I wanted to write a piece of package that writes the BN in a file which can be read by other popular Bayesian inferencing tools for Bayesian networks.


texts: Restricting possible permutations in Graph Isomorphism problem

texts:
Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG $(1,2)$, $(3,4)$, $\dots$, $(2n-1,2n)$. Call these vertices pairs as super vertices.

Call two such graphs $2n$ vertex labelled graphs $G$, $H$ whose adjacencies are $A$ and $B$ respectively $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ iff there is a permutation $P$ such that $A=PBP'$ on the condition that the permutation $P$ permutes only supervertices (only a subset $n!$ of permutations of $(2n)!$ allowed).  In particular, the permutation must map even-numbered vertices in $G$ to even-number vertices in $H$; and if vertex $2i$ in $G$ is mapped to vertex $2j$ in $H$ by the permutation, then vertex $2i-1$ in $G$ must be mapped to $2j-1$ in $H$.

Is $\mathsf{vertex}$-$\mathsf{pair}$-$\mathsf{isomorphic}$ $\mathsf{GI}$-$\mathsf{complete}$?