texts: CPU overused vs RAM normal usage, RAM overused vs CPU normal usage

texts:
I got asked this question in an interview, where they showed me graphs of CPU being overused and RAM being normally used, and graphs of vice versa. What deductions can we make from this, and how can we fix both scenarios?
I mentioned that this was a multiprocessing vs multithreading argument. Is this true?


texts: What are the guidelines/tips for calculating the complexity of a chained-recursive function?

texts:
Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions..
Are there any tips or general guidelines for calculating the complexity (time/space) for functions of the following form?
int f1(int n)
{
    if(n < k) // for an arbitrary k
        return 1;
    return f1(f1(n/2) + f1(n/3) - f1(n/5));
}

Or:
int f2(int n)
{
    if(n < k)
        return k;
    return f2(g(n/k));
}

int g(int n)
{
    // Some code of known complexity here to calculate an arbitrary c
    return f2(n/c);
}

Specifically, recursive functions that call themselves with their own return value as a parameter (e.g func(func(value)); )
Thank you in advance for any assistance provided.


texts: Tearing down the FSM description of congestion control

texts:
I was going through the text Computer Networking- A Top-Down Approach by Kurose and Ross, there I found subtleties with the TCP congestion control FSM which is shown below:

Mainly I am having difficulty in understanding the action transmit new segment(s), as allowed and transition to the Fast Recovery state.
I have read the equivalent portions from the textbook Data Communications and Networking by Forouzan but there though the explanation is easy but there is no FSM or a programmatic approach.
Now let us consider the slow start phase as shown in the Kurose & Ross text:

The time diagram which they explain about the $cwnd$ doubling after each transmission round is easy and is just like what the Forouzan text says. But I find it difficult to understand the implementation based on the arc labeled with :

in the slow start phase.

Suppose the sender starts with  $cwnd = 1$ $MSS$ then sends this (1st) segment to the network layer and awaits the acknowledgment.
The sender gets "new ACK" for the previous packet and increases $cwnd$ to $2$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $2$ segments (2nd and 3rd) to the network layer and awaits the acknowledgments.
Now the sender receives "new ACK" corresponding to 2nd segment and increases $cwnd$ to $3$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $3$ segments to the network layer and awaits the acknowledgments.
Now the sender receives "new ACK" corresponding to 3rd segment and increases $cwnd$ to $4$ $MSS$. Then in accordance to "transmit new segment(s), as allowed", the sender sends $4$ segments to the network layer and awaits the acknowledgments.

From points 3 and 4, I find that the situation does not match with the slow start phase as shown in Fig 3.51. (i.e. the no. of segments sent are 1,2, 3,4 instead of 1,2,4)

I cannot understand the Fast recovery state's action. Specifically the Forouzan text says :

Most TCP implementations have two reactions:

If a time-out occurs, there is a stronger possibility of congestion; a segment has probably been dropped in the network, and there is no news about the sent segments. In this case TCP reacts strongly:
a. It sets the value of the threshold to one-half of the current window size.
b. It sets cwnd to the size of one segment.
c. It starts the slow-start phase again.

If three ACKs are received, there is a weaker possibility of congestion; a segment may have been dropped, but some segments after that may have arrived safely since three ACKs are received. This is called fast transmission and fast recovery. In this case, TCP has a weaker reaction:
a. It sets the value of the threshold to one-half of the current window size.
b. It sets cwnd to the value of the threshold (some implementations add three segment sizes to the threshold).
c. It starts the congestion avoidance phase.

In the Forouzan text, there is no such transition to the Fast Recovery state. But here in Kurose there is such a state and there is an arc labeled :

whose working I do not quite understand in detail.

What extra work is the version in Kurose doing as compared to the one given in the Forouzan text? Can anyone explain me the subtleties with a comprehensive example covering all the cases of the FSM, so that I can understand the thing better.


texts:
I have a simple looking question. What is the most efficient conversion of  $\sum_{i=1}^n x_i = y$ to 3-sat?  Here $x_i$ is either $1$ or $0$ and $y$ is some positive integer.

Can you do better than making a SATISFIABILITY instance with $\binom{n}{y}$ clauses, each of which is the conjunction of $y$ positive literals and $n-y$ negative literals and then just feeding the whole thing into the Tseitin transform?


texts: Optimal ordering of items with contradictory constraints

texts:
I've got a set of items that I'd like to sort into a list. The items have two independent sets of constraints that the ordering should respect:

A set of hard constraints that must be satisfied, e.g.: Item A has to come before item B
A set of soft constraints whose satisfaction I'd like to maximise, e.g.: It'd be nice if item A came before item B
It can be guaranteed for either constraint set that orderings exist that fully satisfy them, but it's not guaranteed that an ordering exists that satisfies both
Each item is subject to at most one constrain in each set, i.e.: each has zero or one items that they must come after, and zero or one items that it'd be nice if they came after.

If I had just had the hard constraints then a topological sort is all that's required, but I can't see how to extends those approaches to maximise the satisfaction of the soft constraint set.

Context: this was posted over at stackoverflow and it was suggested it was a better fit here. Of the two approaches suggested in that question, one has obvious counterexamples while the other, once I'd implemented it, turned out to have slightly-less-obvious counterexamples.

So, is there an accepted approach for finding a list order that will fully satisfy one constraint set while maximising the satisfaction of another?


texts:
I can't get what is the operator-precedence grammar...  I need to convert this grammar to the grammar of weak precedence but I can't get it even.
What does this notation mean A -> aXYb? What's a, X, Y, b? Can someone show a real sample of OPG (grammar + some built expression)? How many start states can it have?
I tried to read but got a nothing almost.


texts: How to implement conditional probability distribution on set-valued Random Variables

texts:
I'm trying to implement conditional probability distribution when the events of two RVs are sets. If I try to extrapolate concepts from real or categorical variables to sets things become confusing for me. In the usual scenario, for some pair of discrete RVs, $X,Y$, we can compute the conditional probability of two "punctual" events by using the Bayes theorem:
$$P(Y=y|X=x)=\frac{P(X=x|Y=y)P(Y=y)}{\sum_{y'\in\mathcal{Y}}P(X=x|Y=y')P(Y=y')}=\frac{f(x,y)}{\sum_{y'\in\mathcal{Y}}f(x,y')},$$
where $f(x,y)=\sum_{(x',y')\in (\mathcal{X},\mathcal{Y})}\chi(x'=x,y'=y)$ is an accumulator function giving the total number of times the specific joint event $x,y$ is observed in the sample space (i.e. the indicator function $\chi(x'=x,y'=y)$ equals one when $x'=x,y'=y$ holds). I'd like to compute such probability when events drawn by $X,Y$ are sets $\boldsymbol{x},\boldsymbol{y}$, respectively. So, how to define the corresponding $f(\boldsymbol{x},\boldsymbol{y})$?
I've tried with two main options:
$$(1)\hspace{10mm}f(\boldsymbol{x},\boldsymbol{y})=\sum_{(\boldsymbol{x}',\boldsymbol{y}')\in(\mathcal{X},\mathcal{Y})}|(\boldsymbol{x}\cap\boldsymbol{y})\cap(\boldsymbol{x}'\cap\boldsymbol{y}')|,$$
and
$$(2)\hspace{10mm}f(\boldsymbol{x},\boldsymbol{y})=\sum_{(\boldsymbol{x}',\boldsymbol{y}')\in(\mathcal{X},\mathcal{Y})}|(\boldsymbol{x}\cap\boldsymbol{y})\cap \boldsymbol{x}'\cup(\boldsymbol{x}\cap\boldsymbol{y})\cap \boldsymbol{y}'|,$$
On the one hand, the motivation behind $(1)$ is that $\boldsymbol{x}\cap\boldsymbol{y}$ provides a measure of how the attributes of both sets should be observed jointly (such as any intersection event). In turn intersecting this intersection event against other intersection events $\boldsymbol{x}'\cap\boldsymbol{y}'$ should provide the measure of how much the joint attributes are observed through the sample space. On the other hand, the motivation behind $(2)$ is that in order to compute $f(\boldsymbol{x},\boldsymbol{y})$ we need to look for $\boldsymbol{x}\cap\boldsymbol{y}$'s attributes in each event of the sample space, without building new events.
However, I'm not sure which one of these analogies is correct (or none at all) with respect to the usual notion of observing the joint event in a sample space. Please, some one can help me to clarify/fix/prove this?
Thank you in advance


texts: $O(n\log n)$- algorithm for finding tree root

texts:
All numbers from $1$ to $n = 2^k-1$ are written in unknown way in a full binary tree of height $k$.  We say that a number $t$ lies between $i$ and $j$ if after removing $t$ from the tree we obtain that $i$ and $j$ are in different connectivity components. Propose an algorithm for determining a number in the root of tree asking $O(n\log n)$ questions of the type "Is $t$ lies between $i$ and $j$"? The answer may be "yes" or "no".

I will be gratefull for hints and ideas.


texts: How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$?

texts:
I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question.

My thoughts: I think the most straightforward way to formulate this question is as in my title: Given constants $t,s,k \in \mathbb{N}$, how many TMs are there that run in $t$ steps or fewer on all inputs of size $k$, and how many TMs are there that use $s$ tape squares or fewer on all inputs of size $k$? This seems like the most direct and simple way to ask the question, but we might want to restate it in a different way -- for example, given a function $p(k)$, how many TMs are there that run in time $p(k)$ on inputs of size $k$ for all $k$ (or how "dense" are these TMs)? This seems harder to me.

We should probably fix a tape alphabet (or a Godel numbering??). We could consider two TMs with different but isomorphic state diagrams to be the same or different, either way.

The immediate problem is that there are an infinite number: Take any TM that satisfies the criteria and add "dead states". I can think of two ways to deal with this. The first (which I don't like) is to add an additional parameter: how many TMs whose description has length $\leq L$ satisfy the criteria? The second (which I prefer) is to consider two TMs equivalent on inputs of size $\leq k$ if, for all such inputs, the TMs have exactly the same behavior (enter the same states and write/move on the tape identically). Then we would restrict to the minimal TM in each equivalence class, or just ask how many equivalence classes satisfy the criteria.

Edit: As pointed out by Vor in the comments, the problem with the second approach is that it's basically the same as a circuit at that point. So how about the first one? Or is there a nicer way to formalize this question?

Any references/literature, thoughts, or answers would be very interesting and appreciated!


texts: Suppose we have two entities $A$ and $B$ and some relationship between them. If there is an $M:N$ relationship between them (i.e. an $M$ on the line connecting $A$ to the relationship and an $N$ connecting the relationship to $B$), how do we read this? Would it be the following: A single instance of $A$ is related to $N$ of $B$ and a single instance of $B$ is related to $M$ of $A$?


texts: Minimum absolute value of subset sums of integer values

texts:
$f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$
How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$?
When $\mathbf{POLY}\overset{\Delta}{=}\{ f:\{0,1\}^*\rightarrow \{0,1, \}^* |$ exists polynomial TM which competes $f  \}$


texts:
We are given a $n \times n$ grid, where each node can maintain a single "active" edge with one of its 4 neighbors at each time step. The active edge of each node changes periodically clockwise or anticlockwise, in the sense that if, for example, at time $t$ node $v$ has an active edge with its upper neighbor, and it rotates clockwise, at times $t+1$, $t+2$ and $t+3$ it will maintain an active edge with its right, lower and left neighbors, respectively.

at time $t=0$ node $(i,j)$ holds a message, and at each time step a node that has already received the message can transfer it through an active edge to one of its neighbors, if that neighbor also maintains this edge as active at this time step.

I am looking for sufficient conditions (initial active edges configurations and rotation direction of all the nodes) such that the message can be transmitted to all nodes in the grid. It's clear this is predetermined by the initial conditions, and depends upon the connectivity of a graph G' that represents them (where neighboring nodes that both maintain an edge as active at some time step are connected in G'). Given that G' it's possible to find total broadcasting time by graph traversal (BFS). The main question is how to know if two edges share an active edge at some time step (given that their behavior is cyclic).

Thanks!


texts: Prove that we can change probability in definition of PP class

texts:
According to Wikipedia, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. If the answer is YES, the algorithm will answer YES with probability more than 1/2. If the answer is NO, the algorithm will answer YES with probability less than or equal to 1/2.

So, the problem is to prove that if in definition we change probability from 1/2 to any rational number (0,1) we obtain the same class of problems.


texts: Need help in understanding these relational algebra queries

texts:
I just finished reading about operators in relational algebra and tried to solve this problem. But I dont even understand what the first statement is doing. From what I know, $π$ (project) is a unary opeartor that takes a single relation and selects some attributes from all of the attributes (columns) of that relation. Then what does $\pi_{R-S,S}(r)$ mean? Also, why have they used $r$ as the argument to project operator? Shouldnt it be $R$ as that is the name of the relation given in the problem?
Let R and S be relational schemes such that $R={a,b,c}$ and $S={c}$. Now consider the following queries on the database:

$\pi_{R-S}(r) - \pi_{R-S} \left (\pi_{R-S} (r) \times s - \pi_{R-S,S}(r)\right )$
$\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall u \in s \left(\exists v \in r \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right )\right\}$
$\left\{t \mid t \in \pi_{R-S} (r) \wedge \forall v \in r \left(\exists u \in s \left(u = v[S] \wedge t = v\left[R-S\right]\right )\right ) \right\}$
Select R.a,R.b
From R,S
Where R.c = S.c

Which of the above queries are equivalent?

1 and 2
1 and 3
2 and 4
3 and 4


texts: Solving road trip problem in linear time

texts:
Consider the following problem:

  You are on a road trip, and there are $n$ cities along a road, labeled
  $1$ to $n$. Conveniently, these cities all lie on a single road, and
  the distance between two adjacent cities is one mile. We are currently
  at city $1$, and would like to drive to city $n$. Each day, we can
  drive at most $k$ miles, before we sleep for the night. We pay $a_i$
  for lodging at the city located at mile $i$. Each lodging cost is a
  positive number. Given that we can spend an arbitrary number of days
  on the road trip, determine a plan of driving to minimize lodging
  costs.

  Input: An integer $k$, and a length $n$ array of positive integers
  $a_1,...,a_n$.

  Output: The minimum lodging cost to complete the road trip starting
  from city 1 and ending at city n.

The most trivial way of solving this problem is to adapt the well-known dynamic programming algorithm for computing the longest increasing subsequence of an array. This requires $n$ iterations and at each iteration, we must compute the minimum of the previous $k$ values, due to the restriction on distance driven per day. This yields an algorithm of time complexity $O(nk)$.

I'm wondering...is there a way to solve this problem in only $O(n)$ time? My intuition is telling me that there is a way to not have to check $k$ prior values at each iteration. Does anyone have an idea?


texts: Why are the 1st 2nd and 3rd normal forms ignored in some database books/courses?

texts:
Why are the 1st 2nd and 3rd normal forms ignored in some Database books/courses?

specifically:

https://lagunita.stanford.edu/courses/Engineering/db/2014_1/about

and

https://www.amazon.com/Database-Systems-Complete-Book-2nd/dp/0131873253/ref=sr_1_4?ie=UTF8&qid=1488557782&sr=8-4&keywords=database+systems

only cover BCNF and 4thNF.

Why?


texts: Empirical Risk and True Risk - Generalization Error Proof

texts:
I showed that, over an uncountable domain,learner A and a distribution P, such that for every sample size m and all samples S from $P^m$
$$
: L_S(A(S)) − L_P (A(S))| = 1
$$
Now I wanna prove for countable domains. Lets assume X = N. I wanna prove that, for sample size m, and every $\epsilon> 0$, there exists a learner A and a distribution P over X, such that
for all samples S from $P^m$ we have
$$
|L_S(A(S)) − L_P (A(S))| ≥ 1 − \epsilon
$$
Not sure how to go about it. Any help is appreciated.


texts: Source code or detailed explanation of "WKS" virtual memory compression algorithm?

texts:
I've been trying to find information on various program data virtual memory compression algorithms that are in the "WK" family of algorithms. So far, I've been successful with the "WKdm" compression algorithm ( see here and here ). The other algorithm that I'm interested in is a variation on the "WKdm" algorithm called the "WKS" algorithm. The paper in which it was first introduced can be found here. The problem is that the paper does not describe the algorithm in any detail and just gives a very brief high-level overview of some major differences with the "WKdm" algorithm without any in-depth technical description. I have only found one other reference in the literature to the "WKS" algorithm. I've also contacted the author of the algorithm but I've yet to receive a response.

Does anyone know the details of the "WKS" algorithm?

Any information would be greatly appreciated.

Thank you,

jdb2


texts: Is my grammar correct for this context-free language?

texts:
$\{a^nb^2a^n \mid n \ge0\}$

I'm studying for my final and I came across this language. I haven't dealt with characters of the same length on opposite ends with something in between.

I came up with the following grammar, but I think it accepts strings that it should not such as:
$abb, bba$, etc.

$$\begin{align}
S&\rightarrow X\\
X&\rightarrow XbbX \mid \epsilon\\
A&\rightarrow aA \mid \epsilon
\end{align}$$


texts: Can a program exist that halts only if it can prove that it doesn't halt?

texts: Consider a program P that enumerates possible proofs in some proof system and halts only if it finds a valid proof that P does not halt. Clearly no such proof exists, or the program would eventually find it, causing a contradiction. But that argument itself appears to constitute exactly such a proof. It seems like that means that P cannot exist (for proof systems sufficiently powerful to express that argument), but I can't otherwise see why that should be the case.


texts: Is there a clear line between algorithmic problem and an algorithmic problem instance?

texts:
E.g. the algorithmic problem of sorting:
 input: sequence of some objects;
output: reordering of sequences such that some relation works for each next element of a sequence.

Right? So what's the instance of a problem?

So instance could be:
 input type: integers; relation in the output: $\geq$.

or instance is some specific input:
like $\{1, 2, 3\}$; plus some relation, e.g. $\geq$.

It looks like there is a problem, then like instance, and then kind of sub-instance.

Also, for example, sorting such that relation is $\ge$ vs $\le$ is it two different algorithmic problems? Or two different instances of the same algorithmic problem?

Also if input data is numbers vs input data is strings, is it two different algorithmic problems or two instance of the same algorithmic problem?


texts: Transforming undirected maximum spanning tree into directed augmented network

texts:
I am having trouble transforming a maximum weighted spanning tree into a directed tree such that each node is allowed at most one parent node. Taken from page 141 Friedman et. al (1997), the outline of the algorithm is as follows:

1) Compute $I_{\hat{P}_{D}}(X_{i};X_{j})$ between each pair of variables $i \neq j$ where $$I_{\hat{P}_{D}}(X_{i};X_{j}) = \sum_{x,y} P(x,y) log\left(\frac{P(x,y)}{P(x)P(y)}\right)$$
2) Build a complete undirected graph in which the vertices are the variables in $X$. Annotate the weight of an edge connecting $X_{i}$ to $X_{j}$ by  $$I_{\hat{P}_{D}}(X_{i};X_{j})$$
3) Build a maximum weighted spanning tree

4) Transform the resulting undirected tree to a directed one by choosing a root variable and setting the direction of all edges to be outward from it.

I have done steps 1-3, my trouble is on step 4. As of right now I have a set of names of continuous variables $X = \{x_{1}, x_{2}, \ldots, x_{n} \}$ and a $(from , to)$ matrix of the form
$$
\begin{bmatrix}
x_{1}&x_{10}\\x_{3}&x_{7}\\ \vdots& \vdots
\end{bmatrix}
$$
For example in the undirected maximum weighted tree, there's an edge going from $x_{1}$ to $x_{10}$ and so forth (note that this could have easily been read as an edge from $x_{10}$ to $x_{1}$ because as of right now the graph is undirected). I understand exactly what's going on I'm just unsure how to actually program it. If somebody could give me a pesduocode-type overview of how I should go about implementing step 4 it would be much appreciated. If someone could provide a link to a detailed implementation of this algorithm that would be fine as well. This is my first post on stackexchange, please forgive me if I have not provided enough information or posted this question in the incorrect location.


texts: Do "Type-2" Turing machines with infinite length inputs have more computational power?

texts:
Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of time to run.

A related variation is the "type-2 Turing machine" defined by Weihrauch, which (if I understand correctly) is basically a Turing machine with an infinite-length input, and a write-only output tape for which previous outputs cannot be changed. Such models are useful for describing real computation.

Does this model of computation have more computational power than a standard Turing machine, similar to the inductive one?

I would naively guess yes, since the theory of "type-2 computability" and "type-2 recursion" seems to be distinct from the ordinary theory of computability, and it seems intuitive that anything which is "type-1 computable" should also be "type-2 computable" (but not the other way around). However, I am unsure of all this.

Burgin (2004) seems to suggest this as a model of hypercomputation in his book on "super-recursive algorithms," but as he does not offer a proof of such, I may be misinterpreting.


texts: How close are common programming languages to not being Turing complete?

texts:
The term "Turing completeness" has been discussed in several of the Computer Science classes that I've taken. However, I've never gotten an intuitive feel for what Turing completeness actually requires. I found this question, but the answers are a bit more mathematical than what I am looking for.

Take a common programming language, such as C++, Python, Java or Lisp. How close are these languages to being not Turing complete? Do these languages have elementary features that if removed would make the language not Turing complete? Or could you change a property of the language (for example, making something random) and by doing that make the language not Turing complete?


texts: Graph theory: BFS (Breadth First Search) - why is current processed first?

texts:
I am referencing some code I found on GeeksForGeeks.com: Why is the current node printed (and processed) first before its children are processed? Wouldn't "breadth first" mean "Process children first, then process parent"? or, is that only for Trees? I can't be the only one to not understand this, so instead of flaming me, somebody please simply post the answer?

void Graph::DFSUtil(int v, bool visited[])
{
    visited[v] = true; <-- why is this printed FIRST?
    cout << v << " ";

    // Recur for all the vertices adjacent
    // to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}

// DFS traversal of the vertices reachable from v.
// It uses recursive DFSUtil()
void Graph::DFS(int v)
{
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Call the recursive helper function
    // to print DFS traversal
    DFSUtil(v, visited);
}


texts: Representing a network with two types of connections: A fishing application

texts:
I want to represent a fishing network using a graph representation. My question surrounds how I can write the adjacency matrix if there are two types of connections, which I want to capture together.

Here's the most basic setup. Say there are two people represented by nodes.

Person one owns a fishing right and also acts as an authority who can land fish.
Person two is a fisherman.

Person one sells the signle fishing right to person two. Person two catches the fish and sells the fish back to person one. Intuitively, I want to write a directed adjacency matrix, in which positive i,j values represent the fishing rights transaction and negative j,i values represent the physical fish transaction, which leads to the following adjacency matrix:

\begin{bmatrix}
     0 & 1 \\
     -1 & 0
   \end{bmatrix}

My question is: Can I use signs like this to represent related but distinct connections? The basic logis follows from the fact the total fish caught = the total fishing rights. By summing the elements, we get zero representing a closed system. Here is a more complicated example:

\begin{bmatrix}
      0 & 1  & 0  \\
      0 & 0  & 0  \\
      0 & -1 & 0 \\
   \end{bmatrix}

In this example person one sells the fishing right to person two as before. Now there is a person three, however, who lands the fish. Again the sum of all the elements is zero as total fishing rights = total fish caught. The network captures a different reality, however. In this second network, all the activities are separated as in an open market. In the original network, all the activities were through a relationship between person one and person two.


texts:
Turing Machine stay at first cell and dont move to the left/right. Its condition!!!(Machine can only rewrite content of cell or dont do anything)

Turing Machine looped when two iterations in which the content of the cell is same, the state of machine is the same, and therefore these are completely identical(*).

And I need to know when this Turing Machine looped. How many iteration will be between (*)?


texts: algorithm time analysis "input size" vs "input elements"

texts:
I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm

Seems that input length for the algorithm depends a lot of the kind of data and the algorithm you are talking about.

Some authors refer to input length to the size of characters that are required to represent the input, so "abcde" if use as input set in an algorithm will have an "input length" of 6 characters.

If instead of characters we have number (integers for instance) then sometimes the binary representation is use instead of characters so the "input length" is calculated as $N*log(L)$ (Being L the Max number in the input set).

There are other problems that even if the input set are numbers, they describe the "input length" as "decision variables", so for a input set of length N with numbers in the range $0-2^{32}$ the input length is just N (subset sum for instance), or even more complicate the number of binary place values that it takes to state the problem (what I believe is just the same as $N*log(L)$)

So:

it depends on the algorithm?
What means and when to use each input length "version"
Is there are some rule I can use to decide which one to use?


texts: Teaching computer science in developing countries - any literature?

texts:
I've been teaching computer science in a developing country and I've seen how the everyday challenges are very different from what I was used to. The students are different. The teachers are different. The system is different.

So now that I'm starting to get over the culture shock, I'd like to draw more attention to the challenges (and maybe present some ideas of my own) by writing about my experiences and observations. I've been studying the literature but, so far, I haven't found one single paper about computer science education in developing countries. It's hard to believe that I might be the first one to write one so I'm asking for any pointers to any relevant literature, please.


texts: What is the big O for $n^{\log n} + n!$?

texts: By intuition $n^{\log n}$ should be as the same as $n!$. By Stirling's approximation, $n!=n^ne^{-n}\sqrt{2\pi n}$, which makes me think both are also the same. So, is this $O(n!)$ or $O(n^{\log n})$?


texts: Are permutations of context-free languages context-free?

texts:
Given a context-free language $L$, define the language $p(L)$ as containing all permutations of strings in $L$ (i.e. all strings in $L$ such that the order of symbols is not important). Is $p(L)$ context-free?

I found two papers dealing with similar, but not identical, questions:

Generating all permutations by context-free grammars in Chomsky normal form by Asveld (2003) deals with finite languages.
Permutations are not context-free: An application of the interchange lemma by Main (1982) deals with "permutation languages", i.e. sets of strings of the form $w x p(x) z$, where $p(x)$ is a any permutation of $x$. Also, the result is limited to alphabets with 16 symbols.


texts: Time complexity described by recurrence relation

texts:
I need to find the time complexity described by the following recurrence relation.

$T(n) = T(n/2) + T(n/3) + T(n/6) + n$

$T(1) = \Theta(1)$

The solution must be something like $T(n) = \Theta(f(n))$.

Obviously the standard form of the master theorem can't help me and any other special cases that I have found weren't useful.


texts: What is the time complexity of checking if a number is prime?

texts:
Could some one please explain how to get the time complexity of checking if a number is prime? I'm really confused as to if it is $O(\sqrt{n})$ or $O(n^2)$.

I iterate from $i=2$ to $\sqrt{n}$ and continuously checking if n%i != 0.

However, do we consider the complexity of the square root function also?

If we do, the Newtons method for finding square roots has a complexity of $n^2$.


texts: Organisation and Architecture of Quantum Computers

texts: What are devices and their interconnections used alongwith Quantum Processors? Are they compatible with hardware devices like Cache, RAM, Disks of current computers?


texts: Machine learning - PCA and KNN on rgb images are too slow

texts:
I work with python and images of tables (taken from above). My aim is to take a photo of a random table and then find the most similar tables to it in my database. By most similar I mean tables of similar shape(square, rectangular, round, oval), texture, colour etc.

For now, I am just running a PCA and then a KNN on all the pixels of rgb images of tables to let my computer find the most similar ones among them. Obviously the k-nearest neighbours of a table image must be images with tables which are very similar to it. The images are common images of tables and are of 529x940 dimensions.

My final goal is to run this program with 2000 or even 4000 table images so I need a more efficient machine learning algorithm for my task than the PCA and the KNN.

Can you recommend me another more efficient machine learning algorithm for this task?
Is Support Vector Machine significantly or Histogram of Gradient better for this task?


texts: Is there any efficient algorithm for primality testing for numbers that are of the form $4k+3$ using the square root function?

texts:
I was reading CLRS and it asked to show that if $p$ is a prime of the form $4k+3$ and $a$ was a quadratic residue, then $a^{k+1}$ is a square root (one can also easily show that $a^{-k}$ is a square root).

I was wondering if using the previous fact and also that we knew we had a number of the form $N = 4k+3$ (not necessarily prime), then maybe there is a different primality testing for (any?) $N$ using the square root function (i.e. $SQRT_N(a) = a^{k+1} $).

So the algorithm that I thought was the following:

Choose a Quadratic Residue (QR) $a \in \mathbb{Z}^*_N$ (one can easily do this by checking if $a^{\frac{p-1}{2}} \equiv 1 \pmod p$ holds). Once we have a QR, compute $a^{k+1} = x_a$ and check if $x_a^2 $ is equal to $a$. If its true, then we conclude that $a$ is prime. Otherwise, we choose a different QR $a' \in \mathbb{Z}^*_N$ and repeat the algorithm. One can repeat this algorithm $k$ times. If after $k$ times there is no success then conclude the number is composite.

I have mainly intuitions on why its correct but not a formal proof. From the first fact that $x_a = a^{k+1}$ is a square root when $p$ is prime, it must mean that $x_a^2 \equiv a \pmod p$. Therefore, if $a$ is a QR then that check will pass (half the time we will choose a QR so the probably that we choose a non QR is only 1/2).

However, if $N$ is composite, it seems we have no guarantee that $x_a^2 \equiv a \pmod N$. So if it doesn't hold we are sure its not prime. But if it does hold then if its prime we are right but if its composite we might be wrong? Basically, is it possible to use the SQRT function when $N = 4k+3$ to decide if $N$ is prime or not?

I also thought of an another algorithm that deserved its own question: Is computing a square root of a number and having more than 2 roots a reliable way to decide primality?


texts: Infinite Union operation of Formal Languages

texts:
Is every formal language  not closed under infinite union operation ?
I know that Regual Languages are not closed under infinite union operation and I have counter-example for it but I don't have any counter-example for other languages. Intuitively , I think it should not be closed but intuition could be wrong also. So please clarify whether every language (like DCFLs,CFLs , Recursive , Recursively Enumerable)  is closed or not under infinite union operation.


texts:
We have been reading about algorithms for MST, strong-connectivity, routing, etc. in directed graphs.

Also recently people have been doing research for dynamic and fault tolerant algorithms for directed graphs.

But I was wondering if there are any practical applications where the underlining graph network is "Directed". Other than social-networks all problems that I could think of like rail/road network, Internet network, etc. deal with undirected graphs only.

Edit 1: I understand that these can be used to model some scenarios where links are directed but I was wondering how often these scenarios occur in real-world, and how important is study of fault tolerance for directed graphs.


texts: Concatenating polyhedra at their region of contact

texts:
Given two polyhedra(with triangulated faces), P1 and P2. I want to create a polyhedron P, which is the result of joining the two at their region of contact. With join I do not mean union but physically, it is more like welding P1 and P2, so if there is say a cylinder(P1) and a cube(P2) aligned on same axis with P1 partially out of P2, union operation will result in disappearance of the part of cylinder inside the cuboid but I want to preserve that region in P. In other words, P1 and P2 should be concatenated at their region of contact.

I would like to know if there is any practical algorithm for this? I think that it is more like computing overlay of P1 and P2 but I do not find any approach for the same in 3D.


texts: Why is this language is not context-free?

texts:
Anyone could apply some theorem to prove this is not context free? I read lot's of material. it's not homework, it's not exam, it's not anythings. I want to learn, if some people try to answer this question one year later, it's not important, but anyone try to learn me.

$$L_{a}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$$


texts: Why is the CPU Involved During Keyboard Echo?

texts:
I'm currently studying for a computer science exam, and I've come across a concept that has me somewhat stumped.

  When one types a key on the keyboard, an ASCII character is transmitted to the CPU. Upon reception of this character, the CPU outputs the same character to the screen. This process is called echoing. Instead of having the CPU involved, why don’t we simply have this echoing process done within the keyboard/screen unit so that the CPU is free to do other useful work?

Now, intuitively, I feel like this is because there is no defined keyboard/screen unit, and the CPU is the device which is responsible for communicating between the screen and the keyboard, through the interconnection network. However, I feel like the fact that a keyboard/screen unit is mentioned may mean I'm missing an important concept. Is this the case? Why do we involve the CPU in the echo process?


texts:
I am trying to solve the following problem:

  A set $S$ is self-reducible if the following holds: $x \in S$ iff $x = 1$(Base case) or (recursively) $l(x) \in S$ and $r(x) \in S$ where $\left|l(x)\right| < \left|x\right|$, $\left|r(x)\right| < |x|$, and $l$ and $r$ are both deterministic polynomial time computable functions.  What is the maximum possible complexity of a self-reducible set (you can choose $l$ and $r$)? For your complexity estimate, prove upper and lower bounds.

Now, I think $S \in P$, because to decide if $x \in S$, we can simply iterate $l$ and $r$ until they both get to $1$ or not, and since the length must decrease each time, the time taken will be polynomial in the length of $x$.  Is this correct?

Also, what could the problem mean by a lower bound? By defining $l$ and $r$ to be $1$, we get $\Sigma^*$, the set of all strings, which is regular...


texts: Detailed step of Dijkstra's algorithm performance analysis

texts:
Reading the book of Dasgupta-Papadimitriou-Vazirani.pdf  about the performance of Dijkstra's algorithm on Page 118, we are given:

4.4.3 Running time
At the level of abstraction of Figure 4.8, Dijkstra's algorithm is structurally identical to breadth-first search. However, it is slower because the priority queue primitives are computationally more demanding than the constant-time eject's and inject's of BFS. Since makequeuetakes at most as long as $|V|$ insert operations, we get a total of $|V|$ deletemin and $|V| + |E|$ insert/decreasekey operations. The time needed for these varies by implementation; for instance, a binary heap gives an overall running time of $O((|V|+|E|)\log |V|)$.

I understand that it has $|V|$ insert and deletemin operations but can someone please explain why we have $|V|+|E|$ insert/decreasekey operations? First of of all, why does one algorithm have TWO kinds of insert operations? If they are the same kind, then where can we learn more about what decreasekey actually does?  The Wikipedia page doesn't seem to cover it much either (unless I missed or misunderstood it).


texts: Do "inductively" and "recursively" have very similar meanings?

texts:
Do "inductively" and "recursively" mean very similar?

For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having been determined, and is initialized with the first component, would you call it works recursively or inductively? I have been using "recursively", but today someone said it "inductively".


texts: What is the expansion of the regular expression $(a^*b^*)^*$

texts:
Consider the regular expression $(a^*b^*)^*$

Does this mean that there are zero or more occurences of the term $(a^*b^*)$ before the term is expanded or that there are zero of more occurences of the term $(a^*b^*)$ after the term itself has been expanded?

Here is an example of what I'm try to say

zero or more occurences of $(a^*b^*)$ BEFORE expanding $(a^*b^*)$
$(a^*b^*)^* = a^*b^*a^*b^*a^*b^* = aababbab$

or

Zero or more occurences of $(a^*b^*)$ AFTER expanding $(a^*b^*)$
$(a^*b^*)^* = (aab)^* = aabaabaab$


texts: Is the language $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$ decidable?

texts:
I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now I am beginning to wonder whether it is actually decidable.

I have designed the following algorithm. Let $G_{M,x}$ be the configuration graph of $M$ on input $x$ (each node represents a snapshot  of $M$, starting from $M(x)$). To decide whether on $x$ we use $m$ space, we visit, DFS-style, each node of $G_{M,x}$ starting from the first node. Each node can be computed from the prior node and we can memorize every node we have encountered so far into a data-structure. Now:

If we encounter a node which takes up at least $m$ space, we halt and
say yes.
If $M$ halts before reaching size $m$ or if we encounter a
cycle (i.e. find a node we already visited), we stop and say no.

We apply this algorithm for each $x \in \{0, 1\}^n$, looking for at least an $x$ on which we say yes.

Does this algorithm work? Why or why not? To me it sounds like it works, but I don't know how to prove it. I guess we need to prove that this algorithm actually decides the problem and that it always halts.

Informally, I believe a way to prove this would be to say that we only have finitely many snapshots which represent less-than-$m$-space configurations: in a finite time, either we encounter some of them more than once (so we enter in a cycle) or we exceed the $m$-space limit. Either way, we halt and answer the question.


texts: Simple example: 2-approximation for vertex cover

texts:
I am having trouble finding an example for the following algorithm to prove that it calculates a 2-approximation:

  Repeatedly select a vertex $v$ of highest degree, add one of its edges $(v,w)$ to the cover, and remove all edges incident to $v$ or $w$.

Please give me insights on how to pick an example.


texts: Given DAG G(V,E), and weight on the vertices, find the heaviest path that starts from s

texts:
Given: G(V,E) DAG, vertex s, and function w: V -> R. (the weight on the vertices)

Define: We define a weighted path in G as sum of all the vertices weight.

Question: Find the heaviest path in G that starts from s. in linear time.

Well, first of all we notice it's DAG, so we can use topological sort here. and also.

My thoughts so far: for each vertex v in G, w(u,v) = w(v). Then my friend told me to multiply by minus one and check for w(p1) < w(p2) before the multiplication iff w(p1) > w(p2). But I'm not sure why it needs to be added.

Then we came up with proceeding with topological sort, relaxing all the edges that are outgoing from the nodes (according to the sort - meaning we start from the heaviest, and we continue with the heaviest edges..)

Time complexity linear.. O(E+V).

My question: If my algorithm is correct, how can I prove it? Is there another algorithm you can think of to solve this question in linear time?


texts: Is it possible to determine an instance of an NP-hard problem is easy or hard by the optimization?

texts:
I have an NP-hard problem and an optimization to deal with the problem.
I want to know that is it possible to distinguish between easy and difficult instances of the problem by the parameters of the optimization, like the number of iteration to solve them?
I am not sure that there exists any relation or not. But, I thought that difficult instances need brute force search that may lead to more iterations to find the solution. Therefore, difficult cases need iterations in greater order than easy ones. Note that, I know there exist different algorithms. But we are talking about a given one. It does not matter the algorithm X is faster than Y. We want to compare the number of iterations between easy instance A and hard instance B in a given algorithm X. The comparison will be correct for instances A and B in algorithm Y on a different scale. Consider that the number of iterations is just an assumption and, I don't know what parameter of optimization can make this comparison for instances.
At first, I want to know that is there any relation between optimization's parameters and easy or hard instances.  Then, if yes, what is the valid way to make a comparison?


texts: Finding the kth element of a permutation

texts: Is there a way to generate a random permutation of the numbers 1 to N such that I can find the k-th element of the permuted list without needing to either 1) store the entire permuted list, or 2) compute the elements 1..k-1?


texts: Semantic natural language processing - from texts to logical expressions? Universal knowledge base?

texts:
My question is - is there a semantic natural language processing that tries to understand the meaning of the texts and that tries to derive the consequences of the understood meaning? Is there a universal knowledge base that can be used for the "grounding" of the texts?

I have heard a lot about statistical NLP and NLP with neural networks but those approaches are not scalable, are not exact and are not satisfying. Is there (and if not - then why) a semantic NLP and semantic natural language understanding that tries to translate the texts into logical formulas? Today we have a vast array of logical formals - both rigorous and both nonmontonic, adaptable, fuzzy, probabilistic and so on? So - if we have those logics why don't we translate texts into them?

And if texts are translated into logical formulas then the universal knowledge base (KB) can be built. This KB should be used as reference KB. I.e. if some text contains the phrase "logical continuum" then this KB should contain all the possible definitions (expressed as logical formulas) of this phrase (according to the different texts, authors) and one should be able to reason over those definitions, to use definitions for applying this phrase into the new text (possibly - computer generated texts), to use definitions for deriving more general or more special notions with relevant definitions, to form completely new concepts. There can be two types of terms in this KB: abstract ideas and concrete real world facts, like country Belgium and so on.

I am aware of existence of some KBs like ConceptNet and WordNet (not really useful) and Cyc/OpenCyc (formal KB with reasoning capabilities) and there is also very promising framework OpenCog which (fortunately) has interesting reasoning engine, but (unfortunately) lacks the public knowledge base for experiments. OpenCog is really interesting, because it unifies probabilitist and rigorous reasoning: each concept (Atom in their terms) have strength/probability value and if those values converge to 1, then proababilistic reasoning tends to rigorous classical logic style reasoning. But that's all.

So - are there such notion as semantic NLP and are there endeavours to create universal knowledge base for semantic interpretation of any text? Are there ongoing projects in this field?


texts:
This is a question on a practice final.

Which of the following statements are true? If it is false, what is the underlying reason behind that?

I. If 3-CNF-SAT is in P, then Clique is also in P.

II. For decision problems $L_{1}, L_{2}$ in NP, if P is not NP, $L_{1}$ is at least as hard as $L_{2}$, and $L_{2}$ is at least as hard as $L_{1}$, then $L_{1}$ and $L_{2}$ are NP-complete.

III. For decision problems $L_{1}, L_{2}$ in NP-complete, if $L_{1}$ is not in P, then $L_{2}$ is also not in P

We are told that only the third statement is True, but there's no explanation why on the key. I have tried to figure this out, and the only conclusion I've come to is:
(I) cannot be true because if A is polynomially reducible to B, this implies B is at least as hard as A, not vice-versa (Not sure if this is a correct conclusion, so feedback on this would be appreciated.)

This is the first time I'm learning about the notion of hardness, so I don't understand most of the technical explanations I've found. Any clarifications on why I, II is incorrect, and why III is correct would be appreciated.
Self study I've done includes reading multiple StackExchange posts, multiple Wiki pages, and the corresponding section in the Cormen book. I just personally understand concepts better if I see different explanations.


texts: Is this path finding problem in a 01-matrix NP-complete?

texts:
The problem:
Input: An $n \times n$ matrix of 0's and 1's, and a position pos of this matrix (i.e. a pair of integers $i,j$ with $1 \leq i,j \leq n$)
Output:
YES if there exists a path through adjacent matrix entries $\dagger$, starting at pos, covering each matrix entry with a 1 exactly once, and not covering the matrix entries with a 0.
NO otherwise.

$\dagger$ a matrix entry is adjacent to the one immediately to its left, to the one immediately to its right, to the one immediately upwards and the one immediately below.

Informally, the matrix can be seen as a labyrinth where the 0's are walls, you start somewhere, and you have to walk through the whole maze without repeating any position.
Example input:
1100
1100
0000
0001
Pos: (1,1)

Corresponding output:
No (because you can't reach the position (4,4))

Is this problem NP-complete? If it is, what other NP-complete problem has been reduced to it? If it isn't, what approach can I use to design an efficient algorithm?
I think this is a particular case of the hamiltonian path problem (except that you have a fixed starting point). The graph can be constructed by taking the matrix entries with 1's as vertices. 2 vertices are adjacent iff their corresponding matrix entries are adjacent. So I think that reducing this problem to the hamiltonian path problem should be easy. Of course, to prove it is NP-complete, we would have to do the reduction backwards.


texts: Draw a function by only using two input NOR gates

texts:
T = (BD + A'BC'+A'CD)

How can i draw this by only using NOR-Gates? This is what i have done so far:
https://imgur.com/a/JG2eU

Have I understood this right?


texts: Reduction of Circuit Satisfiability to CNFSAT

texts:
CNFSAT is Karp reducible to Circuit-SAT by replacing all the conjunctions with AND gate, disjunctions with OR gate and negations with NOT gate. However, if we apply the same approach to Karp reduce Circuit-SAT to CNFSAT, it may result in an exponential algorithm but the instance map should be done in polynomial time.

How should we approach it then?


texts: proving the error bound for a hypothesis

texts:
Given a hypothesis $h:X\rightarrow Y$ ($h$ is returned by an Empirical Risk Minimization (ERM) strategy with realizable case i.e. $h$ is consistent with the sample examples) over $X=[0,1]\subseteq R$ where $Y=\{0,1\}$ and $D$ is the uniform distribution over $X$. How can I prove that for the accuracy parameter $0\leq\epsilon\leq 1$ we might get $err_D(h)>\epsilon$? where $err_D(h)$ is the true error of $h$ in the distribution $D$.

This is a homework and all I can do is using probabilities (as its shown in the course slides and other sources) to give some bounds on the error (i.e. $P(err_D(h)> \epsilon)\leq k(1-\epsilon)^m$) where $k$ is the number of bad hypotheses $|H_B|$ s.t. ($\bar{h}\in H_B | err_D(\bar{h})>\epsilon)$ and $m$ is the sample size.

MY question is: is there any other way (beside using probabilities) to prove this? It just seems odd to me when the question asks for a prove and the answer is about probability bound. I am new to the field of learning theory and this might seems like a silly question but I am really trying to understand the intuition behind using probabilities.


texts: Find minimum number of points which intersect overlapping arcs

texts:
Say I have a circle of a fixed radius, with overlapping arc intervals along its edge. I want to return a minimum set of Points which intersects all arcs in $n^2$ time.
I'm having some trouble proving that my algorithm works. I'm getting caught up with arc intervals that span $0,2\pi$.
For example I have the intervals (in degrees): [45,90],[315,50],[300,25],[310,350] - when I do a sweep I find that the first degree with the least intersects (2) - is 25 - committing to this yields needing 3 points {25,45,310}, whereas the optimal solution is 2 points {~45,~350}. I'm thinking I can maybe just exclude that angle of the least intersects - but I'm not sure how to prove I won't run into a similar problem with a different set of arcs?
So far I have:
# place Intervals in a minHeap based on "starting" radian/degree O(n)
# i = sweep intervals to find first radian/degree with least intersects O(n)
p = float(+inf)
P = {}
while minHeap is not None:
  I = minHeap.deleteMin()
  if I.start>I.end:
    I.end += 360   # trying to normalize
  end if

  if I.start < i:
    minHeap.insert(new interval with I.start + 360 and I.end +360) #too early to evaluate
  else:
    if I.last <= p:
      p = I.last #looking for the counterclockwise radian/degree which covers most arcs
    end if

    if I.first > p:
      #found an interval out of reach - updating trackers
      p = p % 360 #normalizing
      P[p] = true #will eventually return P
      p = I.last  #updating to the new most counterclockwise rad/degree
    end if
  end if
end while
return P


texts: how to find total paths in a graph which have only one vertex common with a given path

texts:
Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$.

How can I find the total number of paths in the graph that do not share any edge with the (unique) path from $a$ to $b$ and have only one vertex in common with it?

For example, suppose I have following graph :

and am given $a=4$, $b=5$.  Then there are six paths satisfying the above condition:  $(1,1)$, $(1,3)$, $(2,2)$, $(2,6)$, $(4,4)$, $(5,5)$ where $(x,y)$ is the path from $x$ to $y$.


texts:
trying to figure out how to approach this problem.

  Suppose a sender in a network wanted to communicate the length n of the block it will be using in a subsequent transmission. If there were not limits on the value of n, there would be a problem to simply send the number in binary, since the receiver would find it difficult to know where the end of the number is. Hence we need to encode the integer n using some variable length prefix code, and send the code for n before the code of the length-n block. Design a prefix code for integers and show that an integer n can be encoded with a codeword of length at most log n + O(log log n) - bits.

So I know Huffman's greedy algorithm for generating prefix codes, but I don't have any frequencies to build the 2-tree. I was thinking to solve the problem, I would build a tree for 0-9, but I have a feeling I'm way off with that approach. I'm also not quite sure how to show that an integer can be encoded using log n + O(log log n) bits.

Any help to get me started would really be appreciated. Thank you for your time!


texts: Difficult Question to Understand (Computer Artitechture)

texts:
You are designing an elevator controller for a building with 25 floors. The controller has two inputs: UP and DOWN. It produces an output indicating the floor that the elevator is on. There is no floor 13. What is the minimum number of bits of state in the controller?

Answer: The system has at least five bits of state to represent the 24 floors that the elevator might be on.

Can someone explain how this comes to be?


texts: If the universe were predetermined, would non-deterministic automata still make sense?

texts: If the universe were governed by predeterminism (i.e. some deity decided in advance how everything, ever, would play out), would the notion of non-deterministic automata make sense?  Or would it not, but we wouldn't know it?


texts: Maximimal Independent Set on Ring and Path

texts:
Let's consider distributed version of algorithm for finding MIS of any graph $A$.

For details, MIS - Maximimal Independent Set.

Slow version of distributed algorithm for MIS, page 2 -  Distributed algorithms. Maximal Independent Set

In worst case, time complexity of the algorithm is $\text{O}(n)$ and a message complexity is $\text{O}(m)$. If nodes of the network are not unique than it's not possible to find MIS.

I am interested in few special cases, when the graph is a path and ring.

Exercise: Consider a path graph $G$ with vertex UIDs to be a random permutation of $\{1,…,n\}$, time complexity of MTS_Slow is $T \leq c\log n$ for a constant $c$ with probability $1-\frac{1}{n}$.
What is a time complexity and it's probability on a ring $G$ with vertex UIDs to be a random permutation of $\{1,…,n\}$.

Ideas: Time complexity has $\log n$ factor, therefore on each phase number of candidates for MIS nodes from a path graph $G$ should be divided by constant factor. Lets consider the worst case, when only one node is choicen to join MIS on each phase, it occurs when the nodes' UID's are located in increasing or decreasing order, it happes with probability $P(B)=\frac{1}{2^n}$, $P(A)=\frac{1}{2}$, where B - nodes' UID is placed in increasing order, A - the next node's UID is bigger the the current one. But how to show that the number of candidates is getting lower by any arbitrary constant factor. The problem is I have a difficulties in defining probability for taking arbitrary constant factor of nodes on each phase.

Case with ring should be similar to a path graph case.

I will appreciate any help in solving this exercise.


texts: Traversals from the root in AVL trees and Red Black Trees

texts:
We all know that for insertion() operation in AVL tree following can happen:

We traverse down the tree from root to appropriate node and there insert the key and then for maintaining height balance we have to check heights of the ancestors of the newly inserted node and in doing so, we could end up traversing up to the root.

I completely agree with this.

But according to me the same can happen in Red Black tree because first we would traverse down the tree to appropriate node and then insert the key.Then there is a possibility that a series of rotation and flip color operations could make us traverse the path up to the root.

Now my question is : why following statement is right?

  In AVL tree insert() operation, we first traverse from root to newly inserted node and then from newly inserted node to root. While in Red Black tree insert(), we only traverse once from root to newly inserted node.

It came as a question, which of the following statements is right about AVL and Red Black trees and the option with given statement was marked correct in the answer key. I am trying to figure out mistake in my second observation?


texts: Multi-dimensional Knapsack with added one-per-group constraint

texts:
I have some sets (A, B, ...) each containing some vectors (e.g. [1, 0, -1]). How can I pick exactly one vector per set such that they sum to a specified target vector?

For example:

A: { [1, 0, -1], [3, 0, 0], ... }
B: { [0, -1, -1], [2, -1, 0], ... }

Target: [3, -1, -1]

Solutions:

1) A=[1, 0, -1], B=[2, -1, 0]
2) A=[3, 0, 0], B=[0, -1, -1]

I think this is a variation of the multi-dimensional knapsack problem with the added 'one-per set' constraint. Has this been written about anywhere?

For my domain, there are 30 sets each containing 50 vectors with 30 dimensions. These vectors are sparse with ~80% zeroes. There is at most one negative number per vector.

Any pointers to research papers or proposed algorithms would be hugely appreciated.

Thanks.


texts: If you had a polynomial time algorithm for determining boolean satisfiability how would you prove/disprove a conjecture like the Reimann-Zeta hypothesis (or the Pythagorean theorem for that matter) from axioms?


texts: What uses have been proposed for overlaid skewed associativity?

texts:
In "Concurrent Support of Multiple Page Sizes On a Skewed Associative TLB" (2004; PDF), André Seznec proposed using overlaid ways with different indexing functions with guaranteed avoidance of bank conflicts. This mechanism allows TLB look-ups for multiple page sizes to be done in parallel without the overheads of CAM-based TLBs or the capacity mis-match issues of a separate TLB for each size. (TANSTAAFL: This comes at the cost of reduced associativity for each page size and does not work well with a wide range of page sizes where less significant bits can not be used by all page sizes to determine the bank.)

I have termed multiple indexing functions sharing a single memory array "overlaying", though there might be a better name.

Mohsen Sharifi and Behrouz Zolfaghari proposed using multiple indexing functions with a single bank to reduce conflict misses ("YAARC: yet another approach to further reducing the rate of conflict misses", 2007, PDF)

"Skewed Compressed Caches" (Somayeh Sardashti et al., 2014; PDF) exploits unified storage to avoid conflict misses when a superblock of memory has variable compressibility.

(The merged-associative TLB proposed in Arkaprava Basu's PhD dissertation "Revisiting Virtual Memory" (2013; PDF 6.5MB) allows the OS to specify a page size by virtual address ranges that exclusively use that page size so that all banks of the TLB can be indexed in parallel. This does not overlay the banks, though it could be trivially extended to do so; similarly page-size prediction could be used (as probably presented in "Prediction-based superpage-friendly TLB designs", Misel-Myrto Papadopoulou et al., 2015, showing the similarity to hash-rehash).)

Despite the fact that Seznec proposed the idea over a decade ago, I have not found other explorations of its utility. Are there any other proposed uses for this mechanism of overlaying ways?


texts: Partition a set of factors so that the difference between products is minimized

texts:
I'm sure this problem must be well-known...
Given a collection $S$ of numbers, partition them into exactly two sub-collections, $A$ and $B$ (I mean, by definition $B$ is just $S-A$) such that the difference of products
$$
    \Delta = \left|\left(\prod_{x\in B}x\right) - \left(\prod_{x\in A}x\right)\right|
$$
is as small as possible.
If it helps, you can assume that all the members of $S$ are integers, and in fact you can assume that they are all prime! In my particular use-case, we're trying to split some big integer $n$ into its "squarest possible" pair of factors, and $S$ is simply a prime factorization of $n$ which we happen to have lying around.
What's the best way to do this? The brutish ways I have thought of are:

Trial division (assuming everything is prime). Awful performance.

    int PS = productOf(S);
    for (int PA = sqrt(PS); PA >= 1; --PA) {
        if (PS % PA == 0) {
            int PB = PS / PA;
            return { factorsOf(PA), factorsOf(PB) };
        }
    }

Search all the possible partitions. Would give better performance, I think, because $\lvert S\rvert! \ll \prod{S}$, but still "obviously" a dumb algorithm.

    int currentDiff = productOf(S);
    intset currentA = {};
    for (intset A in partitionsOf(S)) {
        int PA = productOf(A);
        int PB = productOf(S)/PA;
        if (PB >= PA && PB-PA < currentDiff) {
            currentA = A;
            currentDiff = PB-PA;
        }
    }
    return { currentA, S - currentA };

Is there any simple-ish algorithm to solve this problem without relying on brute exhaustive search?
I wonder if it would work to minimize the difference of sums $\sum_{x\in B}{\log{x}} - \sum_{x\in A}{\log{x}}$, and if that problem has a simpler known solution...


texts: The research area of data exchange format,i.e. the format that stores serialized objects

texts:
As we know, if we want to design and implement a programming language like JAVA, C++ and C language, we will reference the compilation theory. Similarly, if we would like to design and implement a data exchange format language, like JSON and Google protocol buffer to store the serialized objects, what theory shall we use to solve the problem? More precisely, does there exist a domain that study how to design a data exchange format and its corresponding books and publications?

The format shall be terse, robust, readable and have efficient en/decoding. The dilemma between binary format and textual format etc.


texts:
I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle.

Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow \mathbb{N}$, find an efficient algorithm to determine whether the graph has a min cut of at most $k$ edges (assume $k=100$).

My thinking was computing a min cut, then for every edge on that cut, increase it by 1 and compute the min cut again - if the max flow has risen, that means that that edge exists in every single min cut. And If I found there to be over 100 of these edges, then there is no min cut of at most $k$ edges.

However, I don't think that if I found there to be less 100 of these edges, there's necessarily a min cut of at most 100 edges.


texts: Longest path in directed graph between two specified nodes

texts:
There is plenty of algorithms available online, but they do things exactly opposite of what i need:

Find longest path in a graph between any nodes.
Do not remember the path, just weight.

I need an algorithm that can return both weight and path itself. I have tried two things so far:

Dijkstra's algorithm with negative weights - works fine in most cases, sometimes returns shorter path (especially when source and tap are connected directly).
DFS search from source, applies weights. Seems to work better overall, but results are rarely optimal.

Is there an algorithm that is designed to solve that one specific problem?


texts: Addition of 3 bits using Full Adder when the initial carry bit is 0

texts:
How do I add 3 bits using full adder and basic gates, when the initial carry bit is 0??

I have tried using two full adders where two terminals of the first adder gets the first two inputs then the output of this adder goes to of the inputs of the second adder and the third input is given to the second input terminal of the second adder. The carry out from the first adder goes to the carry input of the second adder.

I've added a picture of the circuit which was created by using Logisim(software for designing digital logic circuit).

But it doesn't give the right answer.

normally in binary system, for addition of three bit sum is 1 and carry output bit is 1.

  1+1+1 = 1 & carry bit = 1

But as you can see in the picture of the circuit I designed below, output of my circuit for adding three binary digit, sum is 0 and carry output bit is 1.
 which is not the right answer

  1+1+1, is sum = 0 & carry = 1

The reason of this is clear to me. But I can't design the exact circuit.
How do I design the circuit that can add 3 bit when initial carry is 0?


texts: Proving a certain superset the halting language is not recursive

texts:
Let $\Sigma =\{ 0, 1\}$. Let $val:\Sigma^* \rightarrow \mathbb{N}$ be a function that given a string returns its decimal value, and $L_{halt} = \{\langle M\rangle \langle w\rangle \mid M $ halts on $w \}$.

I define the following language:

$L=\{ x \mid x\neq x^R \wedge (x\in L_1 \vee x\in L_2 \vee x\in L_3)\}$

where:

$L_1=\{ x \mid x\in L_{halt} \wedge x^R \in L_{halt} \wedge val(x)<val(x^R) \}$
$L_2=\{ x \mid x\notin L_{halt} \wedge x^R \notin L_{halt} \wedge val(x)<val(x^R) \}$
$L_3=\{ x \mid x\in L_{halt} \wedge x^R \notin L_{halt} \}$ (in this language there is no requirement on $val$ function)

That is, a string in $L$ has 3 options how to look like.

Intuitively I can feel that $L\notin R$, but I do not know how to approach a formal proof for this.

I tried using a reduction $L_{halt} \leq L$, and then since $L_{halt}\notin R$ I can deduce that $L\notin R$, but I could not find a reduction that will work.

The closest thing I could come up with is using an intermediate reduction, first defining $L_{halt}^{'} =\{ 1  x 0 \mid x \in L_{halt} \}$ and then easily $L_{halt} \leq L_{halt}^{'}$ and all I have to do is $L_{halt}^{'} \leq L$, so my idea for reduction was given $x=1y0$ then $f(x)=y$ (the reduction returns $y$), but then this reduction has a problem if $y\notin L_{halt}$ and $y^R\notin L_{halt}$ then it might be possible that $val(y) < val(y^R)$ and then $f(x)=y\in L$ but $y\notin L_{halt}^{'}$...

I'm kind of stuck at how my reduction should work?

I'm also assuming that any string from $\Sigma^*$ is a possible encoding of a $<M><w>$, that is I cannot assume something about the encoding itself and also every word is a possible encoding of $\langle M\rangle \langle w\rangle$...


texts:
Suppose I have the following from alphabet $\mathcal{X} = \{0 ,1\}$ to $\mathcal{Y} = \{0 ,1\}$. The channel simply does

\begin{align}
 0 \rightarrow 0&\quad  \text{with probability 1} \\
 1 \rightarrow 0&\quad  \text{with probability 1/2}\\
 1 \rightarrow 1&\quad  \text{with probability 1/2}
\end{align}

The classical capacity of this channel is given by the mutual information between the input register, $X$ and output register $Y$ maximized over input probability distributions, $p(x)$. That is,

$$C = \max_{p(x)} H(Y) - H(Y|X)$$

The appropriate distribution turns out to be $(0.6, 0.4)$ and the capacity is $0.3219$ bits.

How does one actually use this result to practically communicate (in the asymptotic limit) over this channel at this rate? Does it mean that I should use input codewords that obey these statistics over the input alphabet for example?


texts: Number of vertices of a graph in vertex cover of size $m$

texts:
Let $G$ have a vertex cover of size at most $m$ and let the degree of $G$ be bounded by $k$. Then $G$ has at most $m(k+1)$ vertices.
Note: Remove all vertices of degree $0$.

Answer:
The idea is to have $m$ graphs like the below one.

But how can I prove this proposition formally?
Thank you in advance for your answers.


texts: Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem

texts:
We are given a set 2-dimensional points $|P| = n$ and an integer $k$. We must find a collection of $k$ circles that enclose all the $n$ points such that the radius of the largest circle is as small as possible. In other words, we must find a set $C = \{ c_1,c_2,\ldots,c_k\}$ of $k$ center points such that the cost function $\text{cost}(C) = \max_i \min_j D(p_i, c_j)$ is minimized. Here, $D$ denotes the Euclidean distance between an input point $p_i$ and a center point $c_j$. Each point assigns itself to the closest cluster center grouping the vertices into $k$ different clusters.

The problem is known as the (discrete) $k$-clustering problem and it is $\text{NP}$-hard. It can be shown with a reduction from the $\text{NP}$-complete dominating set problem that if there exists a $\rho$-approximation algorithm for the problem with $\rho < 2$ then $\text{P} = \text{NP}$.

The optimal $2$-approximation algorithm is very simple and intuitive. One first picks a point $p \in P$ arbitrarily and puts it in the set $C$ of cluster centers. Then one picks the next cluster center such that is as far away as possible from all the other cluster centers. So while $|C| < k$, we repeatedly find a point $j \in P$ for which the distance $D(j,C)$ is maximized and add it to $C$. Once $|C| = k$ we are done.

It is not hard to see that the optimal greedy algorithm runs in $O(nk)$ time. This raises a question: can we achieve $o(nk)$ time? How much better can we do?


texts: Which of the query approaches are more efficient?

texts:
There are two relations, registered(participant,topic) and fee(participant,amount).
The primary key for registered is (participant, topic) and the primary key for fee is participant.
The premise is that of an academic conference. The relation registered stores the names of the participants and the names of the topics registered by them. On the other hand, the fee relation stores the names of participants and the fees that they have paid for the topics.
Also the participants are segregated into five categories depending on the amount of fees they paid. The fees paid under each category are Rs 1000, 2000, 3000, 4000 and 5000. It may be safely assumed that each category has equal number of participants.
Now the query that we are interested in is :

List all topics registered by participants who have paid more than a given amount, x

The query is presented in the following two approaches:
Approach 1 :
   create table r1 as select * from fee where amount > x ;
   select distinct topic
   from registered as R, r1 as T
   where R.participant = T.participant ;

Approach 2 :
   select distinct topic
   from registered as R, fee as T
   where R.participant=T.participant and amount > x ;

Henceforth, I have two questions that have arisen...
(i) Which if the approaches is faster for x = 3000 , and why ?
(ii) Which approach has less disk access time ?

It would be great if I could have some help on the above problem. I'll share my advances on the same :
Assuming there are m participants in each of the categories,the number of rows in relation fee would be 5m. In Approach 1, there's a query running throw these 5m entries to extract out those which have a fees amount value greater than x ( = 3000, here ). Now in this context, this would mean table r1 that Approach 1 creates would have 2m entries ( due to the fact that there are only two categories above 3000 viz 4000 and 5000 ). So finally when we select distinct topics from the subsequent query we make 2m * 5m ( for R.participant = T.participant ) = 10m + 5m = 15m comparisons to ascertain the fact in approach 1.
Whereas in Approach 2, we don't have any such table as r1 being created, and that makes the single select distinct topic query on registered and fee comparing participant names and a check for amount > x use 5m * 5m = 25m comparisons to retrieve the data we looking for in the query result.
So could this enable me to say that Approach (1) would work faster than Approach (2) for x=3000 in the given query ?


texts:
Given a list of numbers as L, how do you find the minimum value m such that L can be made into a strictly ascending list by adding or subtracting values from [0,m] from each element of L except the last? (Strictly ascending means the new list can't have any duplicates.)

Example #1:

for L = [5, 4, 3, 2, 8] the minimum value for `m` is 3.
5 - 3 = 2 # subtract by 3
4 - 1 = 3 # subtract by 1
3 + 1 = 4 # add by 1
2 + 3 = 5 # add by 3
8 untouched # nothing

result = [2, 3, 4, 5, 8]

Example #2:

for L = [5, 4, 3, 0, 8], minimum value for `m` is 4

NOTE: I'm not looking for a complete solution just give me few thoughts and clue.


texts: Genetic algorithm does not always find the global optima and a higher mutation rate finds a better solution

texts:
I wanted to make a tool which minimizes the interference between antennas.

Currently, the tool is very limited for prototyping reasons. It can only place an antenna every 1 meters. The available space that the antennas can be placed is 1 dimensional and is 15 meters wide.

The user can only decide how many antennas will be used (e.g. 3 antennas).

I decided to encode the setup as follows: a binary array where 1 represents an antenna and 0 is an empty space because it seemed straightforward. The length of the array is thus the available space to place those antennas (= 15 meters).

For example, here are all the antennas on the left: 11100 00000 00000 and here they are on the right: 00000 00000 00111.

My mutate function enforces that the offspring contains only 3 antennas. If it is not the case the mutate function will try again. Same thing for the crossover.

In this case, the total search space consists of 455 solutions since there are only 455 ways to place those antennas.

I benchmarked a little bit the algorithm and I got the following results:

If I use a 5% of the search space, thus a population of 7 with 4  generations (7 * 4 = 28) then I got a solution which is better than 96% of the 455 solutions.
If I use a population of 10% of the search space, thus a population of 9 with 5 generations (9 * 5 = 45) then I got a solution which is better than 98% of the 455 solutions
The higher the mutation rate the better the results. This one is very strange since the algorithm becomes more and more a random search. I thought that it should normally give worst results. The difference of the results is 1-2% better when using a mutation rate of e.g. 0.8 instead of 1 / n = 1 / 15 (where n is the length of the encoding).

Finally, I have two questions:

I got a good solution but never the best one, even by using 10% of the search space. Is this normal?

A higher mutation rate gives me better results? Is it because I am working with a toy problem? Or is my encoding bad?


texts: How can we transform elements of FMEA into spaces and transitions in Colored Petri net?

texts:
To ensure safety for systems, hazard analysis can be performed. FMEA is one of an effective technique to analyze systems. FMEA analyze systems potential hazards.
To see the behavior of system, colored petri net models are used. I am wondered how can we connect these two. One way can be partial transformation of FMEA elements(Failure Mode, Failure Cause, Intermediate Effect, System Effect, Recommended Actions) into places and transitions in colored petri nets. But my question is how can we do that or is it feasible approach ?


texts:
In "Computational Complexity" by Arora and Barak they state that the following is $NP$-complete:

$\{ \langle \alpha, x, 1^n , 1^t \rangle : \exists u \in \{0,1\}^n \text{ s.t. } M_{\alpha} \text{ outputs } 1 \text{ on input } \langle x,u \rangle, \text{ within } t \text{ steps} \}$.

They call this language $TSAT$.

I am trying to check the "complete" part of the claim.

Suppose $L \in NP.$ By definition, there is a polynomial $p$ and poly-time TM $M$ such that $\forall x \in \{0,1\}^*,$ we have $$x \in L \iff \exists u \in \{0,1\}^{p(|x|)} \text{ such that } M(x,u)=1.$$
Let $t()$ be the polynomial in which $M$ runs, and let $\alpha$ be the TM $M$ represented as a binary string. Then I think this mapping reduction $f$ works: $$f(x) = \langle \alpha, x, 1^{p(|x|)}, 1^{t(|x|)} \rangle.$$

My two questions are:

1) Is this correct?

2) If it's correct, how do we know that $f$ is computable? Just because some verifier $M$ exists, how do we guarantee that $f$ can "compute" it? Or is $M$ "hardcoded" in the Turing machine that is used to compute $f(x)$ from $x$?


texts:
Below is a question I was asked in an Interview
What is the best case time complexity to find the height of a Binary Search Tree?
I answered it explaining using the below algorithm

$\mathrm{height}(v)$
if $v$ is a leaf, return 0
otherwise, return $\max(\mathrm{height}(v.\mathit{left}), \mathrm{height}(v.\mathit{right})) + 1$

So, in best case, my recurrence would become
$$T(n)=2T\left(\frac{n}{2}\right) + c.$$
Here $T(\frac{n}{2})$ is for each of the recursive calls, and $c$ for all the rest. So even best case complexity is $O(n)$.
Now, in the worst case, my recurrence would become
$$T(n)=T(n-1)+c,$$
and this would be a case of a skewed BST.
Still, here complexity remains $O(n)$.
So, in all cases, the time complexity to find the height of a BST remains $O(n)$.
Is my claim correct?


texts: A* Search Algorithm Implementation with Priority Queue

texts:
I've got a question regarding the A* search algorithm's implementation.

According to Wikipedia, one has to use a priority queue for retrieving the next node with the lowest f value, is it possible to skip to a node that is not a direct descendant of the current node?

For example:
Say we start with node S (set f=0), then add nodes A (with f=5) and B (with f=3).
B is obviously picked, then we add its descendant C (with f=4). Since the priority queue holds A(5) and C(4), C is now picked.
With C we encounter two additional nodes, D (with f=7) and E (with f=8).
Clearly A has the lowest f value in the queue, which means it should be picked, however, it does not have a direct connection with C.

Is it possible to continue developing A even though it is not a direct descendant of C? or is it that D should be picked to develop.
Using a naive priority queue would choose A, is that fine?


texts: What is the complexity of these tree-based algorithms?

texts:
Suppose we have a balanced binary tree, which represents a recursive partitioning of a set of $N$ points into nested subsets.  Each node of the tree represents a subset, with the following properties: subsets represented by two children nodes of the same parent are disjoint, and their union is equal to the subset represented by the parent.  The root represents the full set of points, and each leaf represents a single distinct point.  So there are $\log N$ levels to the tree, and each level of the tree represents a partitioning of the points into increasingly fine levels of granularity.

Now suppose we have two algorithms, each of which operates on all of the subsets of the tree.  The first does $O(D^2)$ operations at each node, where $D$ is the size of the subset represented by the node.  The second does $O(D \log D)$ operations at each node.  What is the worst case runtime of these two algorithms?

We can easily bound the first algorithm as $O(N^2 \log N)$, because it does $O(N^2)$ work at each of $\log N$ levels of the tree.  Similarly, we can bound the second algorithm as $O(N \log ^2 N)$, by similar reasoning.

The question is, are these bounds tight, or can we do better?  How do we prove it?


texts: Does there exist a problem that is hard to do in parallel?

texts:
I am looking for a workload which is hard to paralellise/distribute between multiple machines.

For example, integer factorization does not go 10 times faster if you have 10 machines to split the load, but is there a better example?


texts: Is the existence of an oracle such that $P^O = NP^O$ nontrivial?

texts:
This famous paper proves the existence of both oracles $A$ and $B$ such that $\textbf{P}^A = \textbf{NP}^A$ and $\textbf{P}^B \neq \textbf{NP}^B$, therefore proving that any resolution to the P versus NP problem must be nontrivial in the sense that it cannot relativize.

I understand the significance of the oracle separation given by the latter oracle $B$: it shows that it certainly isn't trivially true that P = NP (of course, this result is incredibly obvious anyway!). But while I'm sure I'm wrong, the existence of the former oracle seems kind of obvious to me.

I would naively expect that for any complexity classes A and B, there would exist some oracle $O$ such that $\textbf{A}^O = \textbf{B}^O$. Just let $O$ be any oracle for a language that is complete for any complexity class C that is "sufficiently larger" than $\mathbf{A} \cup \mathbf{B}$ (in some sense which I suspect could be made precise). Then the oracle $O$ would be so much more powerful than the abstract machines whose capabilities define A and B that the most efficient solution to any tractable problem would simply be to consult the oracle and call it a day. In this case the oracle would "eat up" the original abstract machines and we would simply have $\mathbf{A}^O = \mathbf{B}^O = \mathbf{C}$. As a rather overpowered example, isn't it trivially true that $\mathbf{P}^\mathbf{R} = \mathbf{NP}^\mathbf{R} = \mathbf{R}$?

(Sorry, this question probably shows that I lack a basic conceptual understanding of how relativization works.)


texts: Gray-like code with maximum value <= maximum value of original symbol

texts:
I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit.  I'm going to be using each number as an index into a matrix, and each index must be in the range $0..n-1$.

Gray codes look useful.  The problem is that standard grey codes only work when $n$ is a power of two.  Or, if we use a $k$-bit gray code (where $k = \lceil \lg n \rceil$), then some of the numbers in the gray code sequence will be larger than $n-1$, which will cause a segmentation fault when I try to access that index in the matrix.

So is there something like a gray code that works when $n$ is not a power of two?  In other words, is there a way to construct a permutation of $0,1,\dots,n-1$ so that each number is at a Hamming distance of one from the previous number in the sequence?


texts: Using a 2nd neural network to predict 1st neural network prediction error

texts:
So for example, we are trying to predict the amount of rainfall in the afternoon base on continuous features such as humidity and temperature in the morning.

1st neural network: Regression neural network on features to give one output label which is a continuous value for predicted rainfall in the afternoon.

2nd neural network: Features will be the same as the 1st neural network. But now, the label will be the absolute difference between the 1st neural network predicted rainfall and the actual rainfall.

From this, we can train the 2nd neural network to recognise what particular set of features will result in the 1st neural network giving a 'bad' prediction and be more wary of that 'bad' prediction. In a way, this is like using another neural network to give the confidence level of the first neural network, solely based on the same features (the humidity and temperature in the morning).

I could not find much literature on this subject and am wondering if this idea makes sense in the first place? Perhaps stacking neural networks over each other is a bad idea because it compounds the error from one network to another?

I tried this with some data except my 2nd neural network is a classifier which classifies if the error is above a certain threshold (bad prediction) or below a certain threshold (good prediction).

However, from a few different model runs, it seems that my 2nd neural network usually gives a matthew's correlation coefficient of about 0. This means my 2nd neural network is as good as guessing whether the 1st neural network prediction is good or bad.

So I am not sure if the problem is the idea itself or that my model hyperparameters are bad.

More details: I used 10 fold cross-validation for the 1st model to get a predicted rainfall for all the data. Then I used another separate 10 fold cross-validation and a siamese neural network for the 2nd model to predict whether the 1st neural network prediction is good or bad.


texts: Does Bellman–Ford algorithm can handle zero-weight cycles?

texts: According to my understanding, the Bellman–Ford algorithm can handle cyclic graphs with negative weights. but it cannot have negative cycles. But can it handle zero weight cycles?


texts: Modelling belonging of a real variable to an interval by a boolean variable

texts:
In the context of a MILP, I have variables $x_{t} \in \mathbb{R}$ which have a lower bound $x^{min}$ and an upper bound $x^{max}$.

Let $I_{1} = [x^{min},a_{1}], I_{2} = ]a_{1}, a_{2}], ..., I_{n} = ]a_{n-1}, x^{max}]$ form a partition of $[x^{min}, x^{max}]$.

The behaviour of the system I want to model depends on which $I_{p}$ the value of each $x_{t}$ belongs to, therefore I want other variables $y_{p,t} \in \{0,1\}$ such that $y_{p,t} = 1 \iff x_{t} \in I_{p}$.

The variables $y_{p,t}$ appear in the objective function in a sum of the type $$\sum_{t} \sum_{(p,q) \in \{1,n\}^2} c_{p,q}*y_{p,t}*y_{q,t-1}$$ where the $c_{p,q}$ are constant, positive factors1. We want to minimize the objective function, so the $y_{p,t}$ will be minimized by the solver.

I came up with the following constraints for the $y_{p,t}$ variables but I am not entirely satisfied and wondering if I could do better.

For each interval $I_{p} = ]a_{p-1}, a_{p}]$ we would have the following constraints on new variables, $z^{ub}_{p,t}$ and $z^{lb}_{p,t} \in \{0,1\}$ :

$$ z^{lb}_{p,t} \geq \frac{x_{t}-a_{p-1}}{M}$$
$$ z^{ub}_{p,t} \geq \frac{a_{p}-x_{t}}{M}  + \epsilon$$
where $M$ and $\epsilon$ are appropriate constants.

The case $p = 0$ is different but obtained by adding epsilon to the first constraint right hand side as well.

Then $y$ would be obtained with a logical "and" between $z^{lb}$ and $z^{ub}$ :
$$ y_{p,t} = z^{lb}_{p,t}*z^{ub}_{p,t} $$ which is easily linearized.

The reasons I am not satisfied with this, although I believe it should work, is both having to use $M$'s and $\epsilon$'s and having to linearize the logical "and" constraint. Is there a smarter way to design these constraints ?

Hopefully I provided enough information. I didn't include the whole model because it's quite long and I don't think it would be useful. But please let me know if that's not the case.

1 : I know this is not linear, but it is easily linearized and I think it is clearer this way.


texts:
I'm reading CLRS Section-4.5: The Master method for solving recurrences. There is a line saying

  $f(n)$ must be polynomially smaller than $n^{\log_b a}$.

What is meant by polynomially smaller? Can anybody explain it to me with an example?


texts: How to know if a problem belongs to NP Class?

texts:
What I know (NOT strictly speaking): I know that there is an open question about the equality of P and NP Classes and as long as there is no known algorithm that solves NP problems in P time then we make a distinction about the space-time solvability of such problems. Also, I know that you can make reductions (of polynomial time) between problems, so if you know that a problem belongs to a certain class, then the other problem will also belong to this class. Also, I know that the Simplex algorithm solves problems for linear programming

What I would like to know: I would like to know how to "guess" if a problem belongs to NP Class. Does it have to do with the constraints of the problem, the number of constraints, the "type" of constraints?

An example In this link https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/ we can see an algortihm that solves "Maximum profit by buying and selling a share at most k times" with dynamic programming.

However, what if we increase the constraints. Let's say that we are limited to a net worth (we don't have unlimited money) or we can buy and sell more than one stock at a time but we are limited to the ammount of stocks we can buy or sell in the given time, or there are multiple stocks of various companies we can choose from but we are limited in the total number of stocks we can have.

How can we know what kind of constraints make the problem harder and harder "moving" it from P to NP Class ? What kind of constraints should a problem have to be sure that this problem certain belongs either to P or NP Class ?


texts: Algorithm for ensuring that each element ends up in its specified range when composing a list

texts:
I am designing a feature recommendation system and I have encountered an algorithmic problem and I am wondering if any of you know if there are known algorithms to solve this type of issue. In our recommendation system the content recommended can have in its metadata information at what range it should be put. To demonstrate:

Items 1-2 can be put in slots 3-5
Items 3-4 can be put in slot 7-9
Item 5 can be put in slot 1
We are composing 9 element list which (based on content performance) may look like this: [5, 6, 2, 8, 1, 7, 3, 4, 9]

Implementation of this problem has a lot of corner cases (like ranges overlapping and content from 1 range takes the position from another range, thus making the whole result invalid). Do any of you know if there are some algorithms to handle this type of issue?

It would be best if the algorithm had time complexity lower than O(n^2)

Thanks a lot!


texts: Checking whether the win-loss standings of a league are possible

texts:
You're hosting a 1 v 1 basketball league with a game schedule. At the end of the league you have each player report their supposed win-loss record (there are no ties), but you want to check whether the proposed standings were actually possible given the schedule.

For example: you have four players (Alice+Bob+Carol+Dave) and your schedule is a simple round robin. The reported standings [A: 3-0 B: 1-2 C: 1-2 D: 1-2] and [A: 2-1 B: 1-2 C: 1-2 D: 2-1] would be possible, but the standing [A: 3-0 B: 0-3 C: 0-3 D: 3-0] would not be.

Now suppose the schedule is instead a 3 game head to head between Alice+Bob and Carol+Dave. The reported standing [A: 3-0 B: 0-3 C: 0-3 D: 3-0] is now possible, but [A: 3-0 B: 1-2 C: 1-2 D: 1-2] would no longer be.

(The schedule does not need to be symmetric in any way. You could have Alice only play against Bob 10 times, then make Bob+Carol+Dave play 58 round robins against each other.)

Problem: Given a schedule with k participants and n total games, efficiently check whether a proposed win-loss standings could actually occur from that schedule.

The O($2^n$) brute force method is obvious, enumerate all possible game outcomes and see if any match the proposed standings. And if k is small increasing n doesn't add much complexity - it's very easy to check a two person league's standings regardless of whether they play ten games or ten billion games. Beyond that I haven't made much headway in finding a better method, and was curious if anyone had seen a similar problem before.


texts: Is this problem NP-Complete (Bin packing with seperable items and penalty)?

texts:
The problem is a bit like bin-packing, so I'll describe it with similar naming:

You have $N$ bins, with the same size, $V$, where $V$ is a positive integer
This problem has items, and also "pieces" of items: each item is considered a piece, and each piece must always have a "valid size": size must be a positive integer
You have a set, $S_1$, of items that must all be placed into bins, but can be seperated into "pieces" of any valid sizes (ie. the sum of the sizes of the pieces of an item must always equal the original size of the item)
You have a second set, $S_2$, with non-seperable items of all the same size, $F$, where the cardinality of this set is sufficiently large / unbounded
If you place any piece from $S_1$ into a bin you must also place exactly one item from $S_2$ into the same bin

Given an instance is it possible to place all elements from $S_1$ into the bins without exceeding the capacity of the bins?

More simply put: Is bin-packing still NP-Complete if you allow for items to be separated into pieces, but there is a "penalty" for having more pieces in each bin, where you're forced to place a "filler" between each piece in a bin?

I've considered trying to reduce from bin-packing, scheduling, 3-partition, 3-col, 3-SAT, TSP, but I can't think of a way to do it. Also, in trying to solve the problem in poly time. I can only think of approximation algorithms such as greedily placing the largest item in the bin with the largest remaining capacity.

Any answers or observations on this would be very appreciated.


texts: Understanding a Computer Architecture Problem

texts:
Below, we have given you four different sequences of addresses generated by a program
  running on a processor with a data cache. Cache hit ratio for each sequence is also shown
  below.

  \begin{array}{|c|c|c|}
\hline
Sequence No. & Address Sequence & Hit Ratio \\ \hline
 1& 0, 2, 4, 8, 16, 32, 64, 128 &0.50\\ \hline
 2&0, 1024, 2048, 3072, 4096, 3072, 2048, 1024, 0  &0.33 \\ \hline
 3&0, 256, 512, 1024, 2048, 1024, 512, 256, 0  &4/9 \\ \hline
4& 0, 512, 2048, 0, 1536, 0, 1024, 512   &0.25 \\ \hline
\end{array}

  Assumptions: all memory accesses are one byte accesses. All addresses are byte addresses. Assuming that the cache is initially empty at the beginning of each sequence, find out the
  following parameters of the processors data cache:

  Associativity (1, 2 or 4 ways) (4 points)
  Block size (1, 2, 4, 8, 16, or 32 bytes) (4 points)
  Total cache size (1024 B or 2048 B) (4 points)
  Replacement policy (LRU or FIFO) (4 points)

  Please justify (explain) your answers.

I can't understand what they are asking. When they say "find out the following parameters of the processors data cache", do they mean that I have to choose one of these parameters that fits the logic in the table? Can you better explain what I have to do in this problem?