texts: Does this program have a runtime of O(N) or O(n*m)

texts:
This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure I am properly evaluating the run time of this algorithm.

Imagine we have a list of strings, such as this:

words = ["eat", "tea", "tan", "nat", "bat", "cat", "act"]

We want to visit each character of each word in this list (The above example comes from an anagram grouping prompt). What would the runtime of visiting each character be? Assume that neither the number of words or the length of the words are constants. They are both variables.

in python, that could be done as so

for w in words:
    for c in w:
        print(c)

I have seen the run time of visiting every element in this list as being:

O(n*m): where n is the number of words in the list and m is the number of characters

O(N): where N is the total number of characters in the list

O(N) is clearly linear, but O(n*m) is not (according to the answers in the aforementioned question)

How can the same algorithm be both linear and not linear, simply depending on how you describe the inputs.

In the example case I am considering, all words have the same number of characters, but how might our answer change if this was not the case? Does m then represent the average character length? the length of the longest word?


texts: Do we know any function which has same quantum and classical time complexity (bounded error), or at least same upper bound?  Of course,  let's rule out trivial functions like the constant function, and may be assume the time complexity of the desired function be at least polynomial in input size.


texts: What is a formula for the number of strings with no repeats?

texts:
I want to count the number of strings $s$ over a finite alphabet $A$, that contain no repeats, and by that I mean for any substring $t$ of $s$, $1< |t| < |s|$, there is no disjoint copy of $t$ in $s$.  For exapmle, let $A=\{a,b\}$.  Then $aaa$ is one of the strings I want to count, since for the substring $aa$, there are no disjoint copies.  However, $abab$ contains such a repeat.

If someone's already figured out a useful formula, please link.  Otherwise, I will refer back to this post in any article I write, if I use someone's answer.

Here is another example.  Let's try to construct a long string over $\{a,b\}$, that contains no repeats:

aaa (can't be a)
   aaab (a or b)
     aaabbb (can't be b)
       aaabbba (can't be b or a)
   aaaba (can't be a or b)

If we built a tree, we could count the number of nodes, but I want a formula.

Edit:
Well, it's not as daunting as I first thought if we convert this to a bin-choosing problem.  A set of strings of length k with at least one repeat is equal to the set that is the union of all permutations of the cartesian product:
$A \times A \times \cdots\times A \text{(k-4 times)} \times R \times R$ where $R$ is the required repeat.  I don't know if that's helpful, but it sounded pro :)  Anyway, let their be |A| bins, choose any two (even if the same one) to be the repeat, then choose $k-4$ more and multiply (the first 4 are already chosen, see?).  Now I just need to find that formula from discrete math.


texts: Find all possible configurations of a grid graph

texts:
Say, given a $4\times 4$ grid with black and white dots on vertices. Each dot can form one (and only one) bond with a nearest dot of opposite color. Suppose every dot is guaranteed to find its other part. For one set of dot arrangement there can be many valid bond configurations. Question: an efficient algorithm to find all configurations?

For example, the following are 2 valid configurations of the same chessboard grid. How to find all others efficiently?

config 1

config 2

In such a simple form I guess this may be a classic problem for algorithm or graph theory courses, but I don't even know what's the keyword to search. I was thinking about exhaustive method: loop over all dots, bookkeeping all bonds(T/F) and reject conflicts during the process; it was, of course, exhaustive.

[edit]

Another example using $2\times 2$ chessboard grid. There are only 2 valid solutions.

O--X  or  O  X
          |  |
X--O      X  O


texts: minimum moves for Knight on a infinite chessboard

texts:
You are given an infinite chessboard, a knight, a source and a destination.(Normal chess rules apply) we are required to get move knight from source to destination in minimum moves possible.

I can only think of a bfs solution. Is there a better solution possible?

The question is further extended by adding obstacles to the board. How to solve this question what will be the complexity.(I basically need a answer for this.)

Thank you.


texts: Resources for teaching computer science with R

texts:
I am a professor at a university of applied sciences and will teach computer science next semester.

My question is if you know resources which use the R project as the basis, i.e. not using it primarily for statistics (I do this already in this semester) but for other topics in informatics, mentioned e.g. in this wikipedia article.

Yet I don't want to go through this list one-by-one but was hoping for a more consistent approach (books, slides, scripts...) covering important parts of the field.


texts: How does image reconstruction take place in neural network?

texts: I am reading through and thinking about how neural network works and have been reading about convolutional neural networks (CNN). I am particularly interested in image filtering (or enhancing) using CNN. The thing that confuses me is, how exactly does CNN produce the output, filtered/enhanced image? From what I understand each layer convolves the previous input into more distinctive features, so aren't we essentially losing details? How would the network then know that, for example, this noisy image A, should be cleaned up here and there as such trained to produce a clean image B?


texts: Binary search tree with $n$ internal vertices

texts: How can we prove a binary search tree with $n$ internal vertices has height $h = \lceil \log(n+1) \rceil$?


texts: implementing a 802.15.4 math model based on a paper. How to verify it

texts:
I am implementing a mathematic model for predicting the congestion of 802.15.4 network based on the paper:
Performance analysis of IEEE 802.15.4 non-beacon mode with the unslotted CSMA/CA
Based on the system of nonlinear equations mentioned in that paper, I converted that formula into python code and solved it with "scipy". However, the prediction result is quite different from the one in the paper. I actually spent a few days to debug it, and even rewrited it in OCTAVE(another math program)(since I thought the reason might be on the nonlinear solver itself), but I failed in all manners.
Could someone help me check if my implementation has some flaws. Or it is proper to contact the authors of the paper?
HERE is my code:
# coding: utf-8

# In[58]:

from scipy.optimize import root
import numpy as np
from matplotlib import pyplot as plt
import random
np.seterr(divide='ignore', invalid='ignore')

# In[59]:

#parameters
BEmax=5
BEmin=3
MaxBF=4
UnitBFPeriod=0.32#320us
Tcca=0.25
Ttx=1.12
Tturn=0.192
Tack=0.352
Lamda=0.03
NumDev=0

# In[60]:

def W(j):
    global BEmax,BEmin,MaxBF,UnitBFPeriod,Tcca,Ttx,Tturn,Tack,Lamda,NumDev
    return min(2**(j+BEmin),2**BEmax)

# In[61]:

def meanGamma(ed):
    global BEmax,BEmin,MaxBF,UnitBFPeriod,Tcca,Ttx,Tturn,Tack,Lamda,NumDev
    rho=Lamda*(ed+Ttx+2*Tturn+Tack)
    return 1/(1-rho)

# In[62]:

#var[alpha,EDhol,Ploss]
def model_equ(var):
    global BEmax,BEmin,MaxBF,UnitBFPeriod,Tcca,Ttx,Tturn,Tack,Lamda,NumDev
    Ploss_zero=var[0]**(MaxBF+1)-var[2]
    first_verse=np.arange(MaxBF+1).astype('float')
    first_verse=var[0]**(first_verse)*(1-var[0])
    with np.nditer(first_verse, flags=['f_index'],op_flags=['readwrite']) as it:
        for x in it:
            temp=np.arange(it.index+1).astype('float')
            with np.nditer(temp,flags=['f_index'],op_flags=['readwrite']) as it2:
                for y in it2:
                    y[...]=(W(y)-1)/2*UnitBFPeriod+(x+1)*Tcca
            x[...]=x*np.sum(temp)
    sec_verse=np.arange(MaxBF+1).astype('float')
    with np.nditer(sec_verse, flags=['f_index'],op_flags=['readwrite']) as it:
        for x in it:
            x[...]=(W(x)-1)/2*UnitBFPeriod+(MaxBF+1)*Tcca
    EDhol_zero=np.sum(first_verse)+var[0]**(MaxBF+1)*np.sum(sec_verse)-var[1]
    Alpha_zero=((NumDev-1)*(1-var[2])*meanGamma(var[1])*(Tcca+Ttx+2*Tturn+Tack))/(1/Lamda+meanGamma(var[1])*var[1])-var[0]
    return np.array([Alpha_zero,EDhol_zero,Ploss_zero])

# In[63]:

def TP(var):
    global BEmax,BEmin,MaxBF,UnitBFPeriod,Tcca,Ttx,Tturn,Tack,Lamda,NumDev
    return (NumDev*(1-var[2])*meanGamma(var[1])*Ttx)/(1/Lamda+meanGamma(var[1])*(var[1]+Ttx+2*Tturn+Tack))

# In[64]:

def DELAY(var):
    global BEmax,BEmin,MaxBF,UnitBFPeriod,Tcca,Ttx,Tturn,Tack,Lamda,NumDev
    return (Lamda*2/(var[1]**2))/(2*(1-(Lamda*(var[1]+Ttx+2*Tturn+Tack))))+var[1]

# In[75]:

def plot_func(numd):
    global BEmax,BEmin,MaxBF,UnitBFPeriod,Tcca,Ttx,Tturn,Tack,Lamda,NumDev
    tp=[]
    delay=[]
    for x in range(numd):
        NumDev=x
        random.seed()
        sol = root(model_equ,([random.uniform(0, 1), random.uniform(0, 1), random.uniform(0, 1)]), method='hybr')
        tp.append(TP(sol.x))
        delay.append(DELAY(sol.x))
    nd=np.arange(numd)
    plt.plot(nd,tp,label='Lambda='+str(Lamda))
    #plt.show()

# In[77]:

Lamda=0.01
plot_func(25)
Lamda=0.02
plot_func(25)
Lamda=0.03
plot_func(25)
plt.legend()
plt.show()

# In[71]:

# In[ ]:

This code will plot a graph of throughput vs number of device, which is also showed on the paper. the graph is speciously similar with the one in the paper, but the throughput is slightly different.
this is my graph.
Unfortunately I could not paste the graph in that paper due to copyright. I hope someone have access can help me tackle this problem.
Am I supposed to send a email to the author for help?


texts: k-means clustering with efficient point lookup?

texts:
What's an algorithm for $k$-means clustering, in particular an online algorithm (you can stream new points to it), such that once the size of the set of clusters $k$ becomes large, we can still efficiently lookup a point $p$ and classify it into a cluster ID (an integer)?

Obviously standard $k$-means alone is not sufficient.   Would putting the centroids of each cluster into a BSP or $k'$D-tree do the trick?  I used $k'$ there because that $k'$ has nothing to do with $k$.


texts: Is "imperative computing" just a fancy way of saying "scripting"? Or is there more to it?

texts: Maybe this is a very ignorant question. I don't understand imperative computing very well, would it be correct to think of it as simply scripting (as in, running one or a few commands at a time, typically run through a shell language, as opposed to writing a fully fledged program)?


texts: How to prove that the predecessor of each node in Dijkstra form a tree?

texts:
Prove that the array prev[.] computed by Dijkstra’s algorithm, the edges (v, prev[v])
for all v ∈ V , form a tree

In order to prove this I used induction.

Lemma : "A tree with n vertices has n-1 edges"
R contains vertices with shortest distance from s and rest are in R'

Base case : s is added to R. There are 0 edges.
I-H: Vertex v is added to R such that it has the shortest distance from s in R'.

I don't know how to continue from here since I am new to this.


texts: Grover algorithm when element not present in the array/database

texts:
I've been reading about the Grover algorithm for finding elements in an unstructured database by the means of quantum computing, and even done some exercises.

What I don't understand (and can't find anywhere) is what is supposed to happen if the element is NOT present in the database. The oracle would never flip any qubit, and then I don't know what would happen with the inversion about the mean operator. Would the algorithm keep iterating forever?


texts: Finding a simple cycle that goes through two vertices

texts:
Given a directed graph $G$ and two vertices $u$ and $w$, how can we find a simple cycle that goes through $u$ and $w$?

One can try putting together paths from $u$ to $w$ and $w$ to $u$ — but these might have edges or nodes in common, even if they are chosen to be shortest paths.


texts:
I understand how Kruskal's algorithm works. However, I am not sure how to determine the number of minimum spanning trees that a given graph has. For example say graph $G=(V,E)$ given by

When running Kruskal's you can end up with:

However, as you might note, there are several other minimum spanning trees that are still valid. An example would be getting rid of edge $BD$ and adding edge $AB$ or $CB$. So how can you determine the total number of different minimum spanning trees that exist in the graph, without having to inspect for all the different possibilities?


texts: If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$?

texts:
Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$.

If the statement is true, then can anyone provide a counterexample for when any of the two conditions in bold are relaxed.

If the statement is false, can someone provide a counterexample to show why

I believe that the statement is true and my attempt at the proof is by assuming without loss of generality that $f\notin O(g)$

$f\notin O(g)\implies\neg(\exists N\in\mathbb{N}$ s.t $f(n)\leq Cg(n)$, for some $C>0$ and $\forall n>N)$

$\implies\forall N\in\mathbb{N}\space,\space f(n)>Cg(n)$, for some $C>0$ and $\forall n>N$

Have I negated the expression correctly, because I can't see how I can get $g\in O(f)$ from this expression


texts: Error estimates of piecewise-linear curve approximations

texts:
In order to plot a curve a set of points is usually calculated based on some formula. The function FPLOT in MATLAB also supports plotting with some error tolerance. Its help says the following about this functionality:

The FPLOT function begins with a minimum step of size (XMAX-XMIN)*TOL.
The step size is subsequently doubled whenever the relative error
between the linearly predicted value and the actual function value is
less than TOL.

So, if I plot a curve based on some expression and with some predefined tolerance TOL, is the error of the line segment approximation between any two calculated points always lower than TOL? Unfortunately, this is not obvious for me.

If not, how could one achieve a guaranteed (small) error of a piecewise-linear curve approximation (compared with the "exact" curve).


texts: How to eliminate context-free grammar's ambiguity

texts:
I want to write a CFG that generates the words over {a,b} with the same number of ocurrences of a's and b's.

I have come up with a couple of possibilties so far. I think they're correct but they're all ambiguous, and I want the grammar to be non-ambiguous, this is one option:

S -> aX | bY | ε

X -> bS

Y -> aS

This is another one:

S -> aSb | bSa | SS | ε

And another one:

S -> aSb | bSa | abS | baS | ε

These grammars can generate the word ab in at least two different ways, for example, so they are ambiguous.

Is there any "tip" or "way" to eliminate ambiguity in a context free grammar such as this one?

Thanks for your time and have a nice day! :D


texts:
Is there a program that will tell you the optimal algorithm for ANY problem if the problem is decidable? If not, why not? If yes, how can such a program be realistically constructed?

I would prefer an intuitive explanation over a formal one, thanks.


texts: Consider the set cover problem: given a collection of sets ${\cal U}$ whose elements come from $\{1, \ldots, m\}$ find the smallest number of sets in ${\cal U}$ whose union is all of $\{1, \ldots, m\}$. My question is: what would be a certificate for this problem? That is, if I wanted to convince someone that it is not possible to do this with fewer than $k$ sets, what information could I provide that would allow someone to verify that this is the case in polynomial time?


texts: "Unusual" coupling between a decision problem and a corresponding optimization problem

texts:
There seems to usually be a tight connection between decision problems and (corresponding) optimization problems in general. However, is this always the case?

  Are there examples where the typical "tight coupling" between a decision problem and the correponding optimization problem breaks down or behaves in an unusual way, e.g. have significantly different complexity?

Or, maybe there is a case where there is a cluster of problems that are all closely related, but the "best" or "definitive" version is not obvious or apparent? Also, I am looking for any survey or broad overview or discussion of this apparent basic connection between decision and optimization problems.

A similar question was asked here, but the answers were highly theoretical and it did not seem to yield any specific or tangible examples.


texts: How to remove cycles from a directed graph

texts:
I saw this from SO which led to Feedback Arc Set, which describes the problem nicely:

  In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph (DAG).

I am wondering how this is done. Given a graph such as this:

a -> b
b -> c
c -> d
d -> a

Or a for loop flattened out such as:

somemethod -> forloop start
forloop start -> forloop next
forloop next -> forloop result
forloop next -> forloop next // i+1
forloop next -> forloop end
forloop end -> forloop result
forloop result -> next method

Wondering how you can possibly remove the cycles from a graph like that.


texts:
I have collection $U$ of sets, where each set is of size at most 95 (corresponding to each printable ASCII character). For example, $\{h,r,l,a\}$ is one set, and $U = \{\{h,r,l,a\}, \{l,e,d\}, \ldots\}$. The number of sets in $U$ is nearly a million. Also a set in $U$ will mostly contains 8-20 elements.

I am looking for a datastructure for storing collection of sets that support following operations:

set matching,            e.g. check if set $\{h,r,l,a\}$ is present in $U$
subset matching          e.g. check if set $\{h,r,l\}$ is subset of any set in $U$
superset matching        e.g. check if set $\{h,r,l,a,s\}$ is superset of any set in $U$
union matching           e.g. check if set $\{h,r,l,a,e,d\}$ is union of sets in $U$
approximate set matching e.g. check if set $\{h,r,l,e\}$ is present in $U$, should return true

In particular, we can assume that once the data structure is built, no modifications are made but only queries of the above type (the structure is static).

I was thinking of trie data structure. But, it demands storing data in some order. So I have to store every set as a bit vector, but then the trie becomes binary decision tree. Am I in the right direction? Any pointers will be appreciated.


texts:
I need to prove the following:

reverse(append(zs, z)) = Cons(z, reverse(zs))

Where:

sealed abstract class IntList
case object Nil extends IntList
case class Cons(x: Int, xs: IntList) extends IntList

def append(xs: IntList, x: Int): IntList = xs match {
    case Nil => Cons(x, Nil)
    case Cons(y, ys) => Cons(y, append(ys, x))
}

def reverse(xs: IntList): IntList = xs match {
    case Nil => Nil
    case Cons(x, ys) => append(reverse(ys), x)
}

I've already made the induction basis:

Assume $zs=Nil$.
\begin{align*}
  reverse(append(zs, z)) &=reverse(append(Nil,z)) \\
                       &=reverse(Cons(z,Nil)) \\
                       &=append(reverse(Cons(Nil),z)) \\
                       &=Cons(z,reverse(Nil))
\end{align*}

How do I make the induction step?


texts: Consider a social network. The goal is to find in the in the network a largest group of people who are all friends with each other.

texts: Describe the problem as a graph problem. I've tried to modify the breadth first search algorithm, but haven't gotten anywhere. Any ideas?


texts: Where can I find a proof that Martin-Löf Type Theory isn't Turing Complete, if such proof exists?


texts: Problems that are hard in the best case?

texts: Are there any problems that are hard in the best case? In particular, I was wondering if there are problems that are NP-hard or #P-hard in the best case.


texts: Decision tree: how to decide the next node?

texts:
I have to decide for which value of "Klasse"

How do i do it?

I know that I have to decide on maximum information gain

So first off I've calculated the entropy of "Klasse"

That is E(Klasse)= -(3/11*log(3/11)+3/11*log(3/11)+5/11*log(5/11)) = 1.067

So how do I proceed from that?

I now need to find the first decision node, yes?

And how do I proceed if I've found a decision node ?

Thanks


texts: Can a Red Black tree be constructed of only black nodes using RB insert only?

texts:
I am trying to construct a red black tree out of only black nodes.
I know it is possible getting it after some deletions but I am trying to construct one only via insertion orders.
Is it possible?
I couldn't find a way to do so , so far even after trying to use the simulator.

*** exept of a root node being added to an empty tree.


texts: What is the best algorithm to compute ALL homomorphisms between two rooted labeled trees?

texts:
Lets consider two node-labeled rooted trees Q and D.
According to wikipedia definition ( https://en.wikipedia.org/wiki/Tree_homomorphism ) a mapping m from the nodes of Q to the nodes of D is a tree homomorphism iff :

m maps the root of Q to the root of D
if node c is a child node of p in Q then m(c) is a child of m(p) in D
and for every node n in Q, the label of n is the same as the label of m(n) in D.

What is the best algorithm in terms of time complexity to compute ALL such mappings from Q to D ?

I have heard that there exists one algorithm that computes all these mappings in O(|Q|.|D|) worse case time complexity but the best I could find on my own has worse case time complexity O(|Q|.(log |Q|).|D|).

The only algorithm with O(|Q|.|D|) time complexity related to tree homomorphism that I could find CHECKS if there exists such homomorphism from Q to D and computes all the IMAGES OF THE ROOT of Q ; but do not compute ALL the complete mappings (for all the nodes). You can get the article here (it is called MORPHISM p17-18) :  http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.37.4645&rep=rep1&type=pdf

I have been searching among a lot of other articles :

those dealing with pure theoritical computer science (graph theory for example) usually do not adress this problem specifically and dont give a tight bound (some just stop at the polynomial time complexity claim).
those dealing with XML, XPath and XQuery are too much complicated (I dont understand them) or they go far beyond the strict computation of tree homomorphism (XPath and XQuery are indeed very rich languages).

I would appreciate some help on this topic either in terms of references to articles (not too complicated please) or in terms of a beautiful algorithm that does the job with a nice time complexity proof :-) (I know I'm dreaming...)


texts: Greedy max k-cut approximation algorithm

texts:
I'm trying to formulate a greedy algorithm for the Max k-cut problem:

Let's have an not oriented graph $G(V,E)$, each edge $e \in E$ has its weight $w_e$. The goal of the algorithm is to divide all vertices $v\in V$ to $k$ disjunct sets $V_1,\dots,V_k$ and maximize the weight of the edges that are connecting these sets.

I have come up with the following algorithm:

Take any vertex $v$ from $v\in V$ and add it into a queue $Q$.
while $Q$ is not empty

take the first vertex from the queue. (Let's name it $u$.)
$p_i:=0$ for $i\in\{1, 2, \dots, k\}$
for each neighbour $n\in \text{Neighbours}(u)$ consider the edge $\{u, n\}$.

$p_i := p_i + 1$ if $n\in V_i$

Add the vertex $u$ to the set $V_i$ that has the lowest $p_i$.
Add all neighbours of $u$ that have not been yet assigned to any set to the queue $Q$.

return $V_1, V_2, \dots, V_n$

It is basically a greedy breadth-first search algorithm, that adds each vertex to the best set based on information of the neighbours that have already been added.

Now I am trying to analyze the algorithm, if it is an $\left(1-\frac{1}{k}\right)$-approximation algorithm, but I am having hard time finding where to start.

Could someone please give me some hints on how to analyze this algorithm?


texts: Type theory for imperative programming languages?

texts:
The type theory that I have seen is all developed over lambda calculus, which is an inherently functional language.

Nevertheless, in practice imperative languages have type systems. Are there differences in the type theory for imperative vs functional languages?


texts: How can I analyze the runtime of recursive function that calls another recursive function?

texts:
for example the runtime of this program:

Thanks!


texts: Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

texts:
I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have

$$
NSPACE(S(n)) \subseteq DSPACE(S(n)^2)
$$

Am wondering, what happens if $S(n)$ is fully time-constructible instead, could we have the stronger result $NSPACE(S(n)) \subseteq DSPACE(S(n))$ ? ...

For instance, for fully time-constructible $S(n))$, we have the result :

$$
NSPACE(S(n)) \subseteq \bigcup DTIME(c^{S(n)}) \text{ for } c \geq 1
$$

However, we also have:

$$
\bigcup DTIME(c^{S(n)}) \subseteq NTIME(S(n)) \subseteq DSPACE(S(n))
$$

where the first containment follows given that for a fully time constructible $S(n)$, we have that $c^{S(n)}$ can be 'simulated' by the non-determinisitc branches of an $NTIME$ machine..

Combining the two statements above, we have:

$$
NSPACE(S(n)) \subseteq DSPACE(S(n))
$$

for fully time-constructible $S(n))$... But is this result correct or am I missing something?


texts: Pumping lemma: if you can keep pumping, what does this tell you?

texts: Hypothetically, let's say you are using the pumping lemma for either regular or context free languages. Now using either, you come across a case that remains true despite pumping it. In this situation, do you have to "throw out" the lemma so to speak? I am under the impression that the answer is yes, but I'm just not sure.


texts: Are colored graphs and red-black trees related?

texts:
I've come across the concepts of colored graphs (register allocation) and red-black trees. They both seem to have this notion of "coloring", but I've never seen them being connected conceptually.
Do they have anything to do with each other?


texts: red black tree and 2-3-4 tree isomorphism

texts: Are all cases of addition and removal in 2-3-4 trees isomorphic to cases of addition and removal in red black trees?


texts: How do I reduce subset sum to another problem in NP?

texts:
I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following.

Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it possible to arrange the pens where each row has a maximum length G, where G is the minimum possible.

I have shown that this problem is in NP, but now I'm trying to reduce a subset sum problem to this problem with karp reduction.

I know how the subset sum problem looks like, but I'm having a trouble where to start with the reduction, any tips would be greatly appreciated.


texts: Why do we use big O rather than $\Omega$ when discussing best case runtime?

texts:
When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ of an algorithm, we also attempt to bound $T(n)$ above and use $O$ notation.

Why don't we instead attempt to bound the best case runtime from below? Wouldn't it make more sense to put an upper bound on the worst case runtime and a lower bound on the best case runtime, as this will then give us upper and lower bounds on all cases?

I understand that both $O$ and $\Omega$ notations can be useful for discussing best/worst/average case runtime., and that we can put upper and lower bounds on the worst or best case runtimes, respectively. My question is about the convention in the field to list an upper bound rather than a lower bound for the best case runtime (for example, see here and here).


texts: Why NAT is a disadvantage when TCP source port field is 16 bits?

texts:
Here is an excerpt from Andrew S. Tanenbaum, Computer Networks, 5th edition, Chapter 5 (The Network layer), Page 455:

My question is on the second paragraph. From what I understand, basically this part talks disadvantage of using NAT(Network Address Translation). I don't understand what second paragraph is trying to say about disadvantage of using NAT because it seems to me that the second paragraph is saying about benefit of using NAT because by using NAT, we can solve the problem of depletion of IP address.
Can anyone explain to me what the second paragraph is trying to convey?


texts:
XOR is not the correct name, but I am looking for some kind of exclusive behavior.

I am currently solving a set of different (assignment) problems by modeling flow networks and running a min-cost-max-flow algorithm. Flow networks are quite handy because a lot of problems can be reduced to them in an easy and understandable way. In my case these are matchings with some additional constraints. As these constraints are getting more complex I've been wondering if there are some existing constructions to model specific behaviors.

In this case I want to restrict the outgoing flow of a node to a single edge.

Given a graph $G=(V, E)$, integral capacities $c(u,v)$ and costs $k(u,v)$. An arbitrary node is called $A$. It's direct neighbors are called $B_1, ..B_n$. Can we replace the edges $AB_1,...AB_n$ (red) with some construction so that only one edge can receive flow? Which means that if $AB_1$ gets some flow (e.g. $5/10$) no other (red) edge can receive flow.

We could add intermediate nodes/edges and play with costs and capacities. The total capacity of our new construction has to stay the same and the cost of the different alternatives have to stay somehow proportional.

So my questions are:

Are there constructions like this in general? (Any keywords, links, papers)
Can you suggest a solution to my specific problem?


texts: I have a hard time to understand why the concatenation of two languages over an alphabet (concatenation is in NP), doesn't imply that each of the languages for themselves are in NP. I talked with my Prof about the problem today, but I can't wrap my head around it. Can you help me out?


texts:
Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.

I was thinking that when we augment a path the residual capacity of reverse edge increases and can be used to decrease the flow in that edge (but overall increase the network flow) if needed. So if we disallow the edges into $s$ that means we are not allowing decrease in flow in edges $s\to x$ ($x$ is the adjacent node to $s$). So in the case when we allow edges into $s$ we can have a cycle like

$\qquad \displaystyle s \to x_1 \leadsto y \leadsto x_2 \to s \to x_3 \leadsto t$.

But if we disallow edges into $s$ again we can find the same path with out the cycle. All the above are intuitive ideas but I want a formal proof.

The question is from Introduction to Algorithms by Cormen et al.


texts: examples for: A is mapping reducible to B but B is not mapping reducible to A

texts:
I find it hard to find reductions that only work on one side:
A is mapping reducible to B, but B is not mapping reducible to A.
what could be an easy way to find such two languages A,B ?
I tried Atm,Htm,EQtm,Etm,RegTm, and many others, and whenever I found that A is reducable to B, I also found that B is reducable to A.

thanks.


texts: Is XSL-Transformation a type of compiling?

texts:
I am currently working on a paper based on the topic of creating a source-to-source compiler from an existing application to C#. The existing application is actually just based on XML files, which define certain logic and are interpreted by another program.

From my point of view I tend to say that I am working on a source-to-source compiler, since I have programming language ( even if it's based on XML) on the input and a programming language on the output of my translation.

Now since i have read about the basics of compiler design and knowing techniques like XSLT, i am unsure about the actual differences between transforming and compiling.

I assume that the XSLT processor will also parse the given XML and tries to analyze its content on a semantic basis. As a result the processor outputs another XML file. And that's actually what a theoretical compiler does: Reading a program of a certain input language and output it in another output language.

Now my question is, if XSL-Transformation is a type of compiling or maybe vice versa. Or is there another (theoretically proved) link between both of these processes?

Or even more specific: Is there a term for the "translation" I deal with (XML-Description of a program to a high level language)?


texts: Calculate the minimum absolute difference between the maximum and minimum number from the triplet of 3 arrays

texts:
Question is:

Calculate the minimum absolute difference between the maximum and minimum number from the triplet a, b, c such that a, b, c belongs arrays A, B, C respectively.

There is another question: Find i, j, k such that :
max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i])) is minimized.
Return the minimum max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i])). A, B & C are sorted arrays.

Reading the solution approach here and here, I realize that the solution approach for both these questions is same, to:

minimize abs( max(a,b,c) - min(a,b,c) )

I'm not sure why this follows and how we should go about relating these two questions and their algorithms. Why are these two questions identical?


texts: Prove that there is a path of lenght k+1 in a graph with minimum degree k

texts:
I am faced with this question.

  Let $G$ be a graph in which each vertex has degree at least $k$. Show
  that there is a path of length $k$ in $G$ - that is, a sequence of $k+1$ distinct vertices $v_0, v_1, ..., v_k$ such that for $0 ≤ i < k$, $v_i$ is connected to $v_{i+1}$ in $G$.

I started attacking it this way:

If $G$ has a vertex of degree atleast $k$, it has atleast $k+1$ vertices. That is, $G$ can have $|v| \geq k+1$

In the case where $|v| = k+1$, the graph is a fully connected graph of $k+1$ vertices, which trivially has a path of length $k+1$.

I am not able to prove the cases where $|v| \geq k+2$


texts: When compiled into binary, what signifies the end of a string? How can this be differentiated from user input which compiles to the same binary?

texts:
Apologies for the strange title, this is one of those questions I can't find through a Google search just because I don't even know what I'm supposed to be searching for.

As I understand it, programs are ultimately compiled into binary which is then run by a computer.

So say, for example, you have a simple program which takes a user input and then executes some code -- when compiled into binary, there must be some sort of 'signature' that signifies the end of the user input so the computer knows where it ends. Say just for the sake of this example it's something simple like 0110. So after the user has input his data it might look like ...1100 0101 0110 1010 1001..., where the 0110 signifies the end of the string so the computer knows it's ended and that the rest is code from the program.

But what if the user input contained the same signature? Say the user input, after conversion to binary, came out to be ...0110 0010 0110 1010 1001... What is there to prevent the user from 'tricking' the computer into thinking the user input has ended, and then running malicious code now that the PC believes it's part of the program and not the string?

Hope this question makes any sort of sense, I'd be incredibly grateful if someone could explain this to me. It seems so trivial but it's been bugging me that I can't find an answer for it.


texts: Effective Acces time in Demand Paging system with Associative memory

texts:
Q: Consider a demand-paging system with a paging disk that has an average access and transfer time of 20 milliseconds. Addresses are translated through a page table in main memory, with an access time of 1 microsecond per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we add an associative memory that reduces access time to one memory reference, if the page-table entry is in the associative memory.

Assume that 80 percent of the accesses are in the associative memory, and that, of the remaining, 10 percent (or 2 percent of the total) cause page faults. What is the effective memory access time?

(This question comes in the exercise of the book Operating System concepts by Silberschatz|Galvin|Gagne.)

This is my approach. The associative memory has the page in it (and not just the physical address?), so just one access would do if found. Else, search in the page table. If found, it would take two accesses (one for the page table and other for accessing the page in memory). If not found, need to access it from disk. So,

effective access time EAT = (0.8 x 1μs) + (0.18 x (1μs + 2μs)) + (0.02 x (1μs + 2μs + 20ms)) = 401.4μs

Is this approach correct? This question had been posted in various forums and the answers written there were not matching this. Hence I posted here to check what exactly is the correct way to calculate the effective access time?

I also have some follow up questions. Here there is an associative memory used - is this not the same as TLB(Translation Lookaside Buffer)? Because I'm assuming if there was a TLB, it would still need to access the page from the memory after finding the address in the TLB. Please correct me if I'm wrong.


texts: How to teach random number generator algorithms?

texts:
How can I teach random number generator algorithms? I'd like to show how seeding makes randomization closer to truly random.

Details of the task to be given are as follows:

  Code should read a text file. The file has random words (one word on each line). This is the dataset from which words will be selected randomly.

I am unsure of how to explain the difference between deterministic randomization and non-deterministic randomization using the above example.


texts: Is forward chaining space friendlier compared to backward chaining?

texts:
In the context of rule-based systems, is forward chaining more efficient than backward chaining?

I know that forward chaining is used when we know some facts and from there we want to conclude some new facts. For backward chaining we use it when we want to assert a particular hypothesis. Is forward chaining faster or more efficient in terms of space compared to backward chaining?


texts: What is the best way to avoid using goto statements in the pesudocode for an algorithm?

texts:
What is the best way to avoid using goto statements when writing the pseudocode for an algorithm?

I want to avoid it and use another way to replace it.


texts:
I don't remember seeing any color conventions in Computer Science used to represent some abstract information or to simplify diagrams.

For instance, chemists have the CPK coloring which associates elements to colors.

Electrical technicians have the electronic color code for resistors and wire colors (black for neutral/ground red for phase).

Physicists have conventions for magnets (North pole red, South pole blue), and even quarks have colors!

In CS, one of the only cases I know of are red-black trees, but it's not so much the concepts themselves, but this particular implementation.

I'm asking because I wonder if these colors could be useful in some contexts, for instance: if CFGs were always depicted with a given color for starting node and a different one for ending node; or in programming languages, having something as "immutable data is green, mutable data is blue", or in cryptography ("hash functions are yellow, symmetric encryption is blue, asymmetric is orange"), or computer architecture ("processors are red, memory is blue, buses are green"), etc. I've never seen for instance UML color conventions, or in automata theory, or other areas which frequently use diagrams. Apart from the very universal conventions of "green = good/pass, red = bad/stop", nothing seems to stick.


texts: Why is Boolean satisfiability such a rare case?

texts:
In the space of all K-sat formulas, True and False should have an equal set size. For every un-Satisfiable formula (F), there will an F' (or F-prime) which will be Satisfiable by definition. I cannot get my head around this.

Edit: Let me put it this way: I have constructed a circuit based on a Boolean formula, it is not Satisfiable, now I add one NOT-gate just before the output of the circuit. Does it make sense?


texts:
Wiki in https://en.wikipedia.org/wiki/PP_(complexity) says "a PP algorithm is permitted to do something like the following:

On a YES instance, output YES with probability $1/2 + 1/2^n$, where n is the length of the input.
On a NO instance, output YES with probability $1/2 - 1/2^n$."

Can we replace $2^n$ by something larger like $2^{n^{1+\epsilon}}$ or $2^{2^n}$? It seems that this case should be already known to be distinct from $BPP$.


texts: On "practical" polynomial coefficients if P = NP

texts:
I got riddled by the following problem: Wikipedia states (without citation)

Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution[Note 1] to an NP-complete problem such as 3-SAT would break most existing cryptosystems including:
[...]

Exactly how efficient a solution must be to pose a threat to cryptography depends on the details. A solution of $\mathcal{O}(N ^ 2)$  or better and a reasonable constant term would be disastrous. On the other hand, a solution that is $\Omega (N ^ 4)$ or worse in almost all cases would not pose an immediate practical danger.

(see https://en.wikipedia.org/wiki/P_versus_NP_problem)
How can you make such strong a statement about the whole class of NP-complete problems if by the very definition the reduction function and the growth of the input string caused by the reduction can have arbitrary polynomial constants?
For example, consider I have an algorithm A that solves some subclass C of NP-complete problems in time $\mathcal{O}(n)$. Further consider C is really weird, e.g. Super Mario Bros or something like that and my reduction function needs $\mathcal{O}(n ^ 8)$ time to reduce a problem p $\small{\in}$ 3SAT  to p1 $\small{\in}$ C while it also grows the size of the input string by $\mathcal{O}(n ^ 8)$.
So, to solve a problem p in 3SAT I would need to

reduce it to p1, needing $\mathcal{O}(n ^ 8)$ time
solve p1, needing $\mathcal{O}(n)$ time if n is the size of the input string p1, but $\mathcal{O}(n ^ 8)$ if n is the size of the input string p

In the end I would need to solve two problems in $\mathcal{O}(n ^ 8)$ if n is size of my original problem. And while being linear in the size of p1 (and in consequence be "disastrous" according to Wikipedias definition) it would be more like "impossible to do for big problems" in relation to the size of p.
Am I completely missing something?
Thanks in advance


texts: The Potential function for Fibonacci heaps

texts:
I am trying to get a better understanding of Fibonacci Heaps. I noticed the
following definition for the potential function.
$$ \Phi(F)=|W| +2\cdot \text{# marks}. $$
I do not understand why it is defined that way, or what its significant is. I am hoping somebody can explain it to me.


texts: Can a non-deterministic machine merge its branches?

texts:
Does an NDTM have the power to combine computational branches ie. can a result from branch A be used in the next step in the computation along branch B? Can branches use each others' results, diagrammatically 'merging'?

Example:

Branch i arrives at the number b after n steps, branch j arrives at the number c after 2n steps. After we have waited for both to arrive at their respective values, the computer, on the next step, multiplies those values 3*5 (effectively merging the different branches). Can it do this?


texts: Are all problems approached and solved in fundamentally the same way?

texts:
This question might be a bit to vague, not make sense, or not developed enough yet to ask, but I thought I might give it a shot.

This questions stems from a conversation a friend and I were having about the google interview process. It boiled down to my argument that they are searching for individuals who are fundamentally better problem solvers than others (His argument is that prior job experience proves this, mine is that it doesn't).

This got me thinking. Say we want to solve a simple problem 2 + 2, we could go about this the simply way and just count 1 2, 3 4 to get to the answer or we could chose a much more complex way to arrive there. I argue that both ways fundamentally solve the problem the same way; that the more complex solution is reducible to the simplest.

This linked up in my brain to Big O. It has been shown that all problems in NP are equivalent and can be translated (reduced?) to each other (I might be completely wrong on this); essentially if you solve one (in P time) you solve them all. It kind of shows to me that all problems within their given class are fundamentally the same.

This leads me to question, is the way that problems are solved fundamentally the same? Moreover, is there a way to solve all problems (nothing about running time)?

Again disclaimer, not a full complete thought. I just wanted to get it out there before I forget it and never think of it again. I found it interesting enough to share and just wanted input. Please correct if (where.) I am wrong.


texts: Find the longest repeated pattern in a string

texts:
I'm looking for an efficient algorithm to find the longest repeated pattern in a string.

For example, consider the following string of numbers:

5431428571428571428571428571427623874534.

As you can see, 142857142857 is the longest pattern which is repeated for a couple of times (at least twice) in this string.

The repeated string should not contain any re
any idea rather than brute-force?


texts: Is it possible for a Turing machine to halt without reading the complete input string?

texts: Is it possible for a Turing machine to halt without reading the complete input string. Suppose there is a string "adc" preceded and succeeded by infinite number of blanks. Can a Turing machine halt after reading just "a" and never touching "dc" or any of the blanks. If yes, will this string be accepted or rejected?


texts: Motivation behind the computational way of language translation

texts:
As I am going through learning about compilation , what I see is the approach to the subject through machines , known as automata , which change from one state to another depending on the input provided to them . And there is an accepting state in the automata , which when reached indicates a valid language input .

I wonder how was the process of translation of a language into another language conceived as a problem about machines changing states ? What was the intuition behind this approach to compile/translate languages ?

P.S : I got a reply that the automata part is only for the lexer generator . Even for the lexer generator part , I need to know how was the idea of automata  conceived as a solution to approach this problem .
That may definitely  form an important clue to questions like the following :

How many minimum states in an automata do we need for a language of specific size (no of independent entities maybe ? ) ?
How many accepting states and epsilon transitions are required in an automata ?

What should be the geometry of the automata ? (For the lack of a better word for the set of transitions in an automata , I used the word geometry)


texts: Explanation of recursive structure of Van Emde Boas Tree

texts:
From Van Emde Boas trees lecture:

  We will use the idea of superimposing a tree of degree ${u^{1/2}}$ on top of
  a bit vector, but shrink the universe size recursively by a square
  root at each tree level. The ${u^{1/2}}$ items on the ﬁrst level each hold
  structures of ${u^{1/4}}$ items, which hold structures of ${u^{1/8}}$ items, and
  so on, down to size 2.
  I have a  question regarding van Emde Boas trees :

How is the universe size getting reduced ? Aren't we just spreading the universe keys which is always constant at $u$ to different levels ? I can not understand the idea of "shriniking" the universe size .  I find similar language is used in defining the recursive structure for Van Emde Boas tree in Introduction to Algorithms by CLRS also .


texts: Is defragmentation a kind of minification, a kind of compression or perhaps both?

texts:
As far as I understand defragmentation:

Removes spaces between objects by putting objects nearer one to the other
reorganizes objects for better performance

The first action feels to me as some kind of minification and the second action feels to me as some kind of compression.


texts: Time complexity of finding a node with no incoming edges in a DAG: O(n) or O(m+n)

texts:
I'm reading Algorithm Design by Jon Kleinberg. In section 3.6, in order to compute the topological ordering of a DAG, one first finds a root node in this DAG, then deletes it from the DAG. The author claimed that this can be done in $O(n)$.

How should I understand this time complexity? Just because we traverse all nodes in $O(n)$? But in the iteration for some node $v$, one also needs to traverse all its incident edges. Does that mean the time complexity should be $O(m+n)$ or $O(m)$? Is it related to the data structure which one uses to represent the DAG?


texts: Why the universal Turing machine simulation in O(TlogT) cannot be applied to transform multi-taped Turing machine into single-taped?

texts: Recently, I've read Hennie's Paper. I understood the construction of buffer zones, but why can't it be applied to yield a single-taped Turing machine?


texts: How do I interpret the wording of this passage about abstract binding trees from the book Practical Foundations of Programming Languages

texts:
On page 7/8, section 1.2, of Practical Foundations of Programming Languages, 2nd edition, Robert Harper gives this initial definition of abstract binding trees:
The smallest family of sets closed under the conditions

If $x \in \mathcal{X}_s$, then $x \in \mathcal{B}[\mathcal{X}]_s$
For each operator $o$ of arity $(\vec{s_1}.s_1,\ldots,\vec{s_n}.s_n)s$, if $a_1 \in \mathcal{B}[\mathcal{X},\vec{x_1}]_{s_1},\,\ldots,\, a_n \in \mathcal{B}[\mathcal{X},\vec{x_n}]_{s_n}$, then $o(\vec{x_1}.a_1;\ldots;\vec{x_n}.a_n) \in \mathcal{B}[\mathcal{X}]$

(Here $\mathcal{X}$ denotes a set of variables, $\mathcal{X},x$ the union of $\mathcal{X}$ with $\{x\}$ where $x$ is fresh for $\mathcal{X}$, $\vec{x}$ a sequence of variables,$\mathcal{X}_s$ a set of variables of sort $s$, $\mathcal{B}[X]_s$ the set of abstract binding trees of sort $s$ over the variables in $\mathcal{X}$

This definition is almost correct, but fails to properly account for renaming of bound variables. An abt of the form $\text{let}(a_1;x.\text{let}(a_2;x.a_3))$ is ill-formed according to this defnition, because the first binding adds $x$ to $\mathcal{X}$, which implies that the second cannot also add $x$ to $\mathcal{X},x$, because it is not fresh for $\mathcal{X},x$.

I am confused about his meaning here.
How does this definition result in an ill-formed abt?
By first/second binding does he mean A) outer/inner (read from left to right) or B) inner/outer (read from the inside out)?
What I think he is saying:
Because of the outer("first") binding of $x$, assume that $x$ occurs free in $a_2$. For example $a_2=x,\, a_3=x$. Then because $x$ occurs free in $a_2$, it must be that $a_2 \in \mathcal{B}[\mathcal{X}]$ where $\mathcal{X} = \{x\}$. Since $a_3$ occurs inside an abstractor that binds $x$, $a_3 \in \mathcal{B}[\mathcal{X,x}]$, but then $a_3 \in \mathcal{B}[\{x\},x]$ which is ill-formed since $x$ is not fresh for $\{x\}$
But then I think of the concrete example $\text{let}(y,x.\text{let}(z,x.x))$ in which $a_2 \in \mathcal{B}[\{z\}]$ and $a_3 \in \mathcal{B}[\{z\},x]$, which poses no problems in this interpretation.

Edit to elaborate on the accepted answer...
What I now believe Harper meant is that the outer binding of $x$ indicates that $x$ is considered to be among the free, or "already used" variables in the inner let. This may or may not mean that $x$ must actually appear free in the inner let.
In either case, it means that validation of abts for well-formedness must proceed from the outside-in. In the specific examples Harper gives, the outer binding of $x$ means $x \in X$ in the validation of the inner let:
if $a_2 \in \mathcal{B}[\mathcal{X}]$ and $a_3 \in \mathcal{B}[\mathcal{X},x] \ldots$ (<-- ill formed; $x$ is not fresh for $\mathcal{X}$)
If in particular the wording means that $x$ must specifically appear free in the inner let, then in the given example, it would have to be in $a_2$ as suggested in my question and in the answer below. This amounts to saying that a particular instance of an abt in $\mathcal{X}$ is not automatically an abt in $\mathcal{X}\cup\mathcal{Y}$ for any set of variables $\mathcal{Y}$.


texts: Trivial solution to the Continuous Knapsack problem

texts:
I am a bit puzzled as to why the continuous knapsack problem is a non-trivial problem

https://en.m.wikipedia.org/wiki/Continuous_knapsack_problem

Using the terminology in the Wikipedia link above,

If the Knapsack had a capacity of $W$, couldn't we just pick $W/w_i$ of the material $i$ having the maximum value per unit weight $v_i$?


texts:
I have the definition of an in-situ algorithm from the professor, but I don't understand it.

  In-situ algorithms refer to algorithms that operate with Θ(1) memory.

What does that mean?


texts: The center of a graph is the set of vertices with minimum eccentricity, so a $C_n$ have the minimum eccentricity equals to $n$ and a $K_n$ have the minimum eccentricity equals to $1$? Is valid that a center of a graph be the graph itself?


texts: Help wrapping my head around a combinatorial optimization problem

texts:
Here's the problem I'm trying to solve:

I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight requirement, while maximizing the total number of groups I can form.

Knowing a specific name for this class of problem would be a good start. Help formalizing it would be even better. I did this stuff so long ago in school, I need my memory jogged good and hard. Thanks!


texts: What are the primal and dual planes in the context of the point-line duality?

texts: In computational geometry, we can define a duality between points and lines. The line is the primal (or dual) object of a point, or a point is the primal (or dual) object of a line. However, the exact definition of the primal and dual planes is often not given in the literature. It's a little bit confusing which one is which. What are exactly the primal and dual planes in this context?


texts: Is this possible when it comes to the relations of P, NP, NP-Hard and NP-Complete?

texts:
I saw an image that describes the relations of P, NP, NP-Hard and NP-Complete which look like this  :

https://en.wikipedia.org/wiki/NP-hardness#/media/File:P_np_np-complete_np-hard.svg

I wonder if the following is possible ? Which means, P = NP, but not all of them are in NP-Hard :

Edit : I want to add this : I'm not here to say if the original image is wrong or right, I'm just here to ask a question if my image contains a possible situation. In other words, is it correct to assume that all 3 images are possible ?


texts: Maximizing a convex function with a linear constraint

texts:
$$\text{maximize  } f(\mathbf{x}) \quad\text{subject to  } \mathbf{Ax} = \mathbf{b}$$

where

$$f(\mathbf{x}) = \sum_{i=1}^N\sqrt{1+\frac{x_i^4}{\left(\sum_{i=1}^{N}x_i^2\right)^2}},$$

$\mathbf{x} = [x_1,x_2,...,x_N]^T \in \mathbb{R}^{N\times 1}$ and $\mathbf{A} \in \mathbb{R}^{M\times N}$.

We can see that $f$ is convex and of the form $\sqrt{1+y^2}$. It can be also shown that $f$ is bounded in $[\sqrt{2}, 2]$. I know that a convex maximization problem is NP-hard, in general.

However, using the specific nature of the problem, is it possible to solve it using any standard convex optimization software/package?


texts: GATE CSE 2009, Which of the following is FALSE?

texts:
This is a question from GATE CSE 2009.

Which of the following is FALSE?
A]  There is a unique minimal DFA for every regular language.
B]  Every NFA can be converted to an equivalent PDA.
C]  Complement of every context-free language is recursive.
D]  Every non-deterministic PDA can be converted to an equivalent
deterministic PDA.

The answer provided to me (without any explanation) is B, which I think is wrong.
Here is my approach.

A] Every RL has an equivalent DFA and there is one unique minimal DFA
for a given RL. [so True]
B] Since RL are proper sub-set of CFL and every RL has equivalent FA
and every CFL has equivalent PDA, every FA can be converted to PDA but
not vice versa. [so True]
C] Given a CFL we can create an equivalent Total TM [RECURSIVE],
RECURSIVE languages are closed under complement. [so True]
D] This is only remaining option and by method of elimination answer.

Is my answer correct?


texts: Can most programs (except the IO part) be re-written as a sequence of matrix operations?

texts:
I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to render the 3D world in a game) by processing the data in memory. All of these tasks could be done through a sequence (probably a graph) of matrix and vector operations, such as multiply, add, sum, etc.

For instance, I used to work for a car pool company, there was a piece of code to decide which car should respond to user. That logic was implemented with c++ stl containers and flow controls like if/else/break. Then I realized that it can be re-written as logistic regression (the business logic is stored in the linear predictive model) , with certain precision.

In this sense, matrix operation is a programming language by itself.

Can anyone share any thoughts here? Is there any introductory discussion wiki that I can read ?


texts: Why are the control statements[if-else, while, for] commonly used in programming?

texts:
One simple question I've never been able to answer is, "why use 'for', 'while', and 'if' as control statements?"

Could someone please elucidate the rationale behind using the above mentioned control statements, that have been embraced by most, if not all, high-level languages. I believe this has something to do with automata theory, but I'm generally uncertain.


texts: Complexity of the problem to determine if a spanning tree exists inside a connected graph

texts: Given a connected graph G, what is the complexity of the problem to determine if a spanning tree with a number of leaves less or equal to k exists inside G? I don't really know how to determine it and how to reach a proper solution to this.


texts: Machine has 64 bit architecture and two word long instruction

texts:
A machine has a 64-bit architecture, with 2-word long instructions. It has 128 registers, each of which is 32 bits long. It needs to support 49 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is a signed integer, the maximum value of the immediate operand is that can be stored is?

edit: would 1 word long instruction for this case be of 64 bit and 2 word long instruction be of 128 bits?
Also do we have to add an extra bit while calculating the total bits required for 49 instructions?


texts: Create an algorithm for computing the shortest path in O(m + nlogn)

texts:
So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non negative) graph $G = (V, E)$, a set of vertices $X \subset V$, and two vertices $s, t \in V \setminus X$. The graph is given with adjacency lists and we can assume that it takes $O(1)$ time to determine if a vertex is in $X$. I'm trying to write an algorithm which can compute the shortest path between $s$ and $t$ in $G$ such that the path includes at most one vertex from $X$ if such a path exists in $O(m + n \log n)$ time. I know that this algorithm would require a modified Dijkstra's algorithm but I'm unsure how to proceed from here.
Could anyone please help me out?


texts: Does the Halting Problem prove that true Artificial Intelligence is impossible?

texts:
The Halting Problem demonstrates that there are things that a machine can never be programmed to do.

Is this proof that true Artificial Intelligence - that is, the ability for a machine to think and reason like humans - is not possible?


texts: What is the computational complexity of "real-life" regular expressions?

texts:
Regular expressions in the sense as equivalent to regular (Chomsky type 3) languages know concatenation xy, alternation (x|y), and the Kleenee star x*.
"Real-life" regular expressions as used in programming usually have a lot more operations available; amongst others, quantification x{n}, negation [^x], positive and negative lookahead x(?=y), or back-reference \n.
There is a famous post on SO stating that regular expressions can not be used to parse HTML for the reason that HTML is not a regular language.
My question is: Is this accurate? Do "real-life" regular expressions, say the selection defined in the Java docs, really have the same expressive power as regular expressions as understood in formal language theory; or do the additional constructs, although possibly not strong enough to capture HTML and the like, put common regular expressions further up on the Chomsky scale than just Type 3 languages?
I would imagine the proof of the computational equality of the two would amount to showing that each operation available for the common regexp is just syntactic sugar and can be expressed by means of the 3 basic operations (concatenation, alternation, Kleene start) alone; but I am finding it hard to see how one would e.g. simulate back-reference with classic regexes alone.


texts: Why divide by $b-1$ when computing size of a tree

texts:
In one of the lectures I went to, my professor stated that in order to determine the size of a search tree, we use the following formula:
$$\frac{b^{d+1}-1}{b-1},$$
whee $b$ is the branching factor and $d$ is the depth of the tree in question. I would like to understand why we divide by $b-1$. I would have thought that the correct solution is $b^{d+1}-1$.


texts: What is a regular expression for solutions to the dog/cat/mouse river crossing puzzle?

texts:
This is a question that's been bugging me off and on for years, ever since I took a compiler theory class as an undergraduate.  There, we learned how to convert a regular expression into a non-deterministic finite automaton, then convert that into a deterministic finite state machine, then minimize that state machine.  It was also mentioned in passing that there's a transformation in the opposite direction, but that wasn't covered as not practically useful for our purposes.

In the introduction to finite state machines, on the other hand, one of the examples given was an analysis of the classic children's puzzle to bring a dog, a cat, and a mouse across a river in a small rowboat.  It's not hard to list the valid reachable states in this puzzle and construct a finite state machine like this (where dcm*| is the initial state and |dcm* is the only accepting state):

So, putting these two together, it led me to the question in the title: what's a corresponding regular expression for valid solutions to the puzzle?  All the possible loops mean I quickly get bogged down in any attempt to construct a regular expression which covers all cases.

OK, I'm now led to this answer by the suggested links appearing as I'm typing this question: How to convert finite automata to regular expressions? .  However, if I try any of the algorithms suggested there, I quickly get an exponential explosion of terms.  So, I guess a possible answer would be "this is a pathological case which probably doesn't have any answer shorter than $2^{10}$ or so symbols" if that's indeed correct.


texts:
I was watch this lecture https://youtu.be/moPtwq_cVH8?t=2895, and at this point he says a lot about reductions, take a problem and reduce to another problem. From what I could understand this is a symmetric relation, if I can reduce A to B, then I can reduce B to A. This seems pretty intuitive to me but I don't have a formal proof, is there any (for beginners would be better) material on this proof?
Still on this lecture, from what I could understand we have problems that are known to be NP-hard, if I have a problem that I don't know what is but I can reduce to NP-hard problem then it must be NP-hard.
Another question, supposing that reduction is symmetric if any NP problem can be reduced to P problem that would prove that P = NP. Or in reverse, if I have a known NP problem and I prove it can't be reduced to a P problem then this would prove that P ≠ NP.
Is my reasoning right? I'm not trying to prove anything just want to make sure that I understand the reduction implications because this seem powerful tool for day reasoning on solving problems in general.


texts: How would I prove that the regular expression rejects string?

texts:
Prove that the regular expression $\Sigma\Sigma(ab\cup ba)^∗a$ rejects the string $aabaabba$.
Would this be because the union of $ab$ and $ba$ would not accept the string $aabaabba$? I'm just confused on how to explain it.


texts: What properties does a co-RP problem need to be in P?

texts:
Given an arbitrary language $L$ with an algorithm $A$ that places $L$ in $co-RP$ what other properties does the Algorithm $A$ need to have to so that $L$ is in $P$?

For example:

Considering $L$ is in $co-RP$ we have a guarantee that:

if $x \in L$ then $A$ accepts $x$ guaranteed $(P(A(x)=1) = 1)$

if $x \not\in L$ then $A$ accepts $x$ with a propability $f(n)$ $(P(A(x)=1) = f(n))$ with $n = |x|$ and $f(n) \geq 0$

What property does $f$ need to have so that $L$ is in $P$?

As $P \subseteq ZPP$ and $ZPP = RP \cap co-RP$ there needs to be a property to $f$ that places $L$ also in $RP$. As such there needs to be a way to construct an algorithm $B$ for $L$ that discards $x \not\in L$ guaranteed in polynomial time. Under what conditions for $A$ is this possible? For what $f$ is this the case? Is there any other property $A$ needs to have so that $L$ is in $P$?


texts: Not able to find any pattern for $4T(n/2)+n^2 n^{1/2}$

texts: I have tried my best but I'm not able to find any pattern for the $n^2n^{1/2}$ part. This question must be solved  iteratively and I get totally clueless after two iteration.s I've to find tight bound in big-O.


texts: In a flow network, is it possible to restrict the flow going into a node?

texts: For example, if a node has 2 edges going into it and two edges coming out of it all with capacity 1, is there a way to make it so that only 1 unit of flow can go through this node (without just deleting edges)?


texts: What is the purpose of ϵ-transitions in PDA?

texts:
$A = \{a^i b^j c^k\mid i = j\text{  or } j = k; i, j, k \ge 0\}$.
In its push down automaton should not there be the red colored transition instead of the black colored one?


texts: Inductive proof that $n^2 + bn + d$ is $O(n^2)$ using definition of big O

texts:
Given that $T(n) = n^2 + bn + d$ then it's $O(n^2)$ if I can prove that:
$O(n^2) = \{T(n): \text{there exist positive constants } c, n_0 \text{ such that } \forall n \geq n_0, 0 \leq T(n) \leq cn^2 \}$

So I was going to try and prove this using induction where

$Let:\ c = 2bd, n_0 = 2$

$\text{Base Case} (n = n_0):$
$$n^2 + bn + d \leq cn^2$$
$$4 + 2b + d \leq 8bd$$
$$\frac{1}{2bd} + \frac{1}{4d} + \frac{1}{8b} \leq 1$$

...and I can continue to do the rest, but I was looking at the base case and I wasn't sure how to prove that it is true if I don't know what $b$ and $d$ are.

For example, if they're both $0.01$ then it's clearly not true, and I'm not sure how to proceed. Could someone explain this to me?


texts: Does Halts reduce to all other undecidable languages?

texts:
In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of reductions that started with Halts.
Are there any undecidable languages which Halts does not reduce to?


texts: how to reduce the time complexity of this code?

texts:
I have a graph G=(V,E). A list of nodes NODE subset of V. I want to find out all the neighbor nodes of each node in NODE and add edge if those neighbors have distance greater than 2. Can anyone here please help me to reduce the time complexity of this code to quadratic time or less.

import networkx as nx
import random

G = nx.erdos_renyi_graph(30, 0.05)

node=[]
for j in range(5):
        node.append(random.randint(1,30))

for i in node:
    lst=list(G.neighbors(i))
    if(len(lst)>1):
         for j in range(len(lst)):
             for k in range(j+1,len(lst)):
                 if(len(nx.shortest_path(G,lst[j],lst[k]))>2):
                     G.add_edge(lst[j],lst[k])


texts: Remove features with too little variation

texts:
I have the following messy chart;

As you can see some features are very stable through the time series (post-2011) like Extraversion.
Is there an algorithm to remove features that do not have much variation compared to the other features?


texts: Why does heapsort run in $\Theta(n \log n)$ instead of $\Theta(n^2 \log n)$ time?

texts:
I am reading section 6.4 on Heapsort algorithm in CLRS, page 160.

HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i to A.length downto 2
3   exchange A[i] with A[i]
4   A.heap-size = A.heap-size-1
5   MAX-HEAPIFY(A,1)

Why is the running time, according to the book is $\Theta (n\lg{n})$ rather than $\Theta (n^2\lg{n})$ ? BUILD-MAX-HEAP(A) takes $\Theta(n)$, MAX-HEAPIFY(A,1) takes $\Theta(\lg{n})$ and repeated $n-1$ times (line 3).


texts: minimum number of points a convex hull must have

texts:
Quick question:
Say for example there are 10 colinear points. my question is does a convex hull have to be a convex polygon? or can it be a line as well according to the formal definition of the convex hull?
Thanks in advance.


texts: Minimum bottleneck path between two vertices in an undirected graph

texts:
I have an undirected graph, where the value of the path is the maximum weight among all weights
edges included in it. And I want find the path of minimum value between two  given vertices in time $O(n + m)$, where $n$ - number of vertices, $m$ - number of edges.


texts: Algorithm to select sets of objects while maximizing number of objects covered

texts:
If we have different objects,

[A1, A2, A3, B1, B2, B3, B4, B5]

Some calculations will be performed to find compatible objects. For example, lets assume following 3 sets were formed and every set contains compatible objects:

 1. {A1, B2}
 2. {A3, B2}
 3. {A1, A3, B4, B5}

Now we need to perform filtering. One node can participate only once. For example, if B2 has made a pair with A1, then B2 can not participate in any other set. Which means, if we select set 1, then set 2 will be deleted because B2 has already participated. And set 3 will be deleted because A1 has already participated.

Now we need to do filtering such that we maximize number of objects being utilized. If we select set 1, then we are only utilizing A1 and B2.
Thus, optimal way would be to select set 3 which is utilizing 4 objects. And discard sets 1 and sets 2

Right now, i have a complex function which goes through list of sets recursively and keeps on adjusting until no changes are made to existing sets. This is not only inefficient, but it might not work in cases where changing sets can cause ripple effect.

I am not looking for coded solution, but just a guidance that is there any graph algorithm which I should study?


texts: Accounting method amortized analysis of a sequence of operations (CLRS 17.2-2)

texts:
I'm working through CLRS, Chapter 17 on Amortized Analysis. One of the problems I attempted to solve is 17.2-2 (described below), but my answer differs from the one in the instructor's manual, so I thought I'd solicit your feedback. I appreciate any help with this.

Problem. We have a data structure supporting some number of operations. Given a sequence of n such operations, we're to determine the amortized cost of each operation using the Accounting Method [CLRS, 17.2]. The actual cost of $i^{th}$ operation is defined as follows:

$$
cost(i) =
\begin{cases}
i  & \text{if $i$ is an exact power of 2} \\[2ex]
1 & \text{otherwise}
\end{cases}
$$

Assume that exact powers of 2 form the sequence: $1, 2, 4, 8, \ldots$.

Solution. (My attempt) For the sake of concreteness, consider a sequence of 10 operations:

$$
\begin{array}{c|ccc}
i & cost(i) & notes\\
\hline
1 & 1 & 1 = 2^0\\
2 & 2 & 2 = 2^1\\
3 & 1 &\\
4 & 4 & 4 = 2^2\\
5 & 1 &\\
6 & 1 &\\
7 & 1 &\\
8 & 8 & 8 = 2^3\\
9 & 1 &\\
10 & 1 &\\
\end{array}
$$

The approach is predicated on the observation, based on this data, that between consecutive power of 2 operations (say, 1 and 2 or 2 and 4 or 4 and 8, etc.) there are exactly $i-1$ unit-cost operations. For example, if $i=1$, then between operations 1 and 2 there should be $1-1 = 0$ unit-cost operations and indeed there are none. Another example, consider $i=4$. We again verify that between 4 and 8 there are $4-1 = 3$ unit-time operations.

Based on that hypothesis, we assign the following "charges" ($\widehat{cost}$) to each of the operations:

$$
\widehat{cost}(i) =
\begin{cases}
i + (i - 1)  & \text{if $i$ is an exact power of 2} \\[2ex] \tag{$\alpha$}
0 & \text{otherwise}
\end{cases}
$$

The idea is that each power of 2 operation pays for itself (that's the $i$ summand) and leaves credit just enough to cover the $cost$ of the next $(i-1)$ unit-cost operations. Visually:

$$
\begin{array}{c|ccc}
i & cost(i) & \widehat{cost(i)} & \text{"remaining credit"}\\
\hline
1 & 1 & 1 & 0\\
2 & 2 & 3 & 1\\
3 & 1 & 0 & 0\\
4 & 4 & 7 & 3\\
5 & 1 & 0 & 2\\
6 & 1 & 0 & 1\\
7 & 1 & 0 & 0\\
8 & 8 & 15 & 7\\
9 & 1 & 0 & 6\\
10 & 1 & 0 & 5\\
\end{array}
$$

At the end of the sequence, we're left with 5 units of credit, which will pay the price of the next 5 unit-cost operations ($i = 11, \ldots, 15$).

The amortized cost of a given operation is $i + (i - 1)$, which is bounded by $2n$. The book has a $3n$ in the analysis, so I'm wondering where I'm messing up.


texts:
Say I have a library that looks like that:

   123cm
<-------->

|________|
|________|
|________|
|________|
|________|
|________|
|________|
|________|
|        |

Its width is (here) 123cm, its height is 231.9cm, the number of book shelves (horizontal lines) is 8. I can put books on the floor so there are effectively 8+1=9 compartments where I can store the books vertically. I have a list of books with title, height and thickness. For example, a pandas dataframe df storing the information would look like:

    height_cm   thickness_cm    title
0   33.0000 2.5000  title1
1   27.4066 5.7912  title2
2   26.2890 4.0894  title3
3   26.1874 3.6068  title4

I can "adjust" the distance between one book shelf and the other and I want to find an "optimal" solution, given my list of books (every book is stored vertically and there is minimal waste of space).

So far I have implemented a really dumb python algorithm that is initialized with average book shelf spacing and tries to insert books sequentially. I pick the shelf whose spacing is the closest to the book's height. If the spacing is not enough I modify it to book's height + some minimum clearance. I also redistribute the modification for this particular spacing across other spacings. I insert the book and I do that for the next book. It gave some results...

EDIT:

Following @RcnSc comment, I tried to cast the problem as a linear programming one.

let :

$S_k$  the height of shelf $k \in \{0, ..., 8\}$
$W$ the max capacity of each shelf, $H$ the library's height. In my problem $W=123$, $H=231.9$
$x_{ik} = \left\{
\begin{array}{ll}
    1 & \mbox{if book } i \in \mbox{shelf } k\\
    0 & \mbox{otherwise}
\end{array}
\right.
$
$N$ the number of books, $t_{i}$ thickness of book $i$, $z_{i}$ height of book $i$.

then I want to optimize:

$$
\begin{equation}
\begin{aligned}
\max \min_{k \in \{0, ..., 8\}} \sum_{i=1}^{N} t_i x_{ik} \\
\text{s.t. } \sum_{i=1}^{N} t_i x_{ij}&\leq W,\ j\in \{0, \dots, 8\} \\
        \sum_{k=0}^{8} x_{ik} &= 1, i \in \{1, \dots, N\} \\
       \sum_{k=0}^{8} S_k &\leq H \\
       x_{ik}z_i &\leq S_k, i \in \{1, \dots, N\}, k \in \{0, \dots, 8\}
\end{aligned}
\tag{P}
\end{equation}
$$

basically I want to put a maximum number of books on each shelf.
I want to find $S_k$ and the assignments $x_{ij}$.
Do you think the formulation makes sense? How to solve it in practice?


texts: Do there exist "O(1)-complete" problems?

texts:
Many complexity classes have "complete" problems. Do complete problems exist for the complexity class of problems that can be solved in $O(1)$ time?

A complication is that this class depends on the model of computation; a problem can be solvable in $O(1)$ time in one reasonable model of computation but not another, given that "reasonable" typically means polynomial-time equivalence with a Turing machine. However, it could still be worked out for specific reasonable models.

I think it makes the most sense to look at constant-time many-one reductions. However, I'm also open to looking at other sensible reductions if there is literature on them.

Does anything like this exist, or has it been studied, for any model of computation?


texts: Finding minimum/maximum value in a Binary Indexed Tree

texts:
I know how a BIT works. But I was wondering if a BIT can be used to find the minimum/maximum element in the complete range, or more specifically, to find the minimum (or maximum) value after all the update processes have been completed. Now, I know that this can very well be achieved using Segment Trees, but is it possible to do the same using a BIT?

I know the obvious way of traversing the complete BIT and calculating the value at each index. I am looking for a more efficient/optimized way.


texts:
Is it possible to use the theorem of Rice to prove that the emptiness problem is undecidable?

With the emptiness problem I mean the question if a certain machine doens't accept any input ?

If you can prove it using the theorem of Rice, can you also prove the acceptance problem (if a certain machine will accept a certain string?).


texts: Shortest Path Variant (constrained max hop)

texts:
INPUT: directed non negative weighted graph, s, t, k

OUTPUT: SSSP from s to t where the path has $\leq k$ vertices

MY PROGRESS:

heap.add(s,0) where s is vertex and 0 is weight and heap is minheap
depth[s] = 1;
do
  c = heap.poll();
  SSSP[c] = c.weight
  if(depth[c] >= k) continue loop;
  for v in c's adjacent vertices
    if SSSP[v] is infinite
      heap.add(v, SSSP[c] + weight c to v)
      depth[v] = depth[c] + 1;
    else if getHeapNode(v).weight > SSSP[c] + weight c to v
      getHeapNode(v).weight = SSSP[c] + weight c to v
      heapify/shiftup
      depth[v] = depth[c] + 1;
while(!heap.isEmpty())

ans = SSSP[t];

Here is my approach and it doesn't work because I think there can be a case where a vertex that has been polled from the heap that exceeds $k$ when later is revisted by a longer (greater weight) path BUT at depth $\leq k-2$. This means that the neighbour of the polled vertex is reachable by the slower path but is not computable as the vertex has already been polled. I don't think this is the only criteria for max-k hops constrained shortest path. How should i go about doing this?


texts: How can I simplify the following Product of Sums: ab+ac'+a'b'+a'c+b'c'+bc?

texts:
I started with POS: (a+b+c)(a+b'+c)(a'+b+c)(a'+b+c')

and after a long while, I got: ab+ac'+a'b'+a'c+b'c'+bc

and then I'm not sure how to simplify this. I thought maybe I can cancel the ab with a'b', and b'c' with bc and end with ac'+a'c but it doesn't seem to be right if I look at the truth table...


texts: Sorting in place & stable in linear time

texts:
Given an array with only 0 & 1. Can we have an algorithm which has all the following desirable characteristics-

The algorithm runs in $O(n)$ time.
The algorithm is stable.
The algorithm sorts in place.

I know the algorithms if only 2 characteristics are required but want to know if all the three characteristics possible simultaneously or not? If yes, how?


texts: Unix glob() function and formal language equivalence

texts:
Can we express the matching capabilities of Unix library function glob() using a single-stack push-down automata, i.e. set of context free formal languages? If not, which is the minimal automata that we need?
For those that do not know what glob() does, it is a pattern matcher generator using a few operators:

* matches an unlimited number of consecutive characters. As this can be in any position, not only in the end of the pattern, I eliminated the possibility of expressing glob expressions in terms of regular expressions.
? matches exactly one arbitrary character, which is similar to a skip state in a finite automaton.
[abc] matches an arbitrary-length string consisting of only symbols in the brackets, and [!abc] matches an arbitrary-length string that includes anything but symbols in the brackets. Those character sets can also be listed in a shorthand notation like [a-z] or [!a-z].


texts: Is the program in secondary memory can be a process?

texts:
Let us consider the following scenario,

The cpu started executing a program, which is in secondary memory with n lines of code, so, it brings m ( <  n ) lines of code in to main memory and started executing.

We can call the m lines of code, which are in main memory as process.

But my doubt is that, what about the remaining n-m lines of code that are in secondary memory, which are not yet reached main memory, can we call them process? or just program? The remaining n-m lines may execute by the CPU in future. But what now the n-m lines of code are?


texts:
I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student).

Is it poly time only for base 2, i.e in binary or will it remain poly time algorithm even if i run it in decimal system i.e base 10?
If I'm calculating $(a^b) \bmod p$,  where $1<a<11$, $1 < b \leq (p-1)/2$, and we run this modular exponentiation at most $p/2$ times, all this being done in decimal base 10 system, will it still be poly time?
Even if this is poly time, and this is a big IF, can this process actually be completed in reasonable time in terms of the real worldly time?


texts: Counting the number of tree when the set of the subtrees is given

texts: There are a set $A$ of trees. There is another set $B$ of trees that is the collection of all possible subtrees of the trees in $A$. I don't have $A$ but only have $B$, and I need to figure out the size of $A$. A brute-force way is making a graph of the trees. For each root node in $B$, find a tree that contains the node, if there exists such a tree, then make a link from the root node's tree to the containing tree. Finally I can obtain the number of trees in $A$ by counting the number of connected components in the graph. However, this may not be so efficient. How can I do it efficiently?


texts: With a list of opcodes for a virtual machine, is it possible to assign a number to every possible program of size n that can be run on that machine?

texts:
Say you have some virtual machine with < 100 numbered opcodes that fully specify its behaviour. Is there an easy way to order and enumerate all possible programs of less than n instructions, the result being that a particular number refers to a particular program? Preferably with natural numbers and short programs at the begining.
As this list would be combinatorially large, it would be helpful to assign these numbers without running the programs or loading them into memory.


texts: Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity?

texts:
If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to state the complexity is amortized $O(n\log n)$?

I have a tree building algorithm - when adding elements a rebalancing operation occurs every so often, with those operations getting progressively more expensive as the tree size grows close to a power of two elements (before becoming cheaper again once we pass such a power). At every power of two elements its easy to state the number of steps done so far but in between it's not so easy.

I'm slightly embarrassed by this question as I currently assume it is OK to state an amortized time of $O(n\log n)$ for this situation but my conclusions, from reading a discussion elsewhere (see next part), seemed to contradict this.

Update: I've move the second part of part of this question, relating to Conc-tree lists and my confusion over how such trees could be built in $O(n)$, into a separate question.


texts: Proving a language is not Turing-recognizable by reduction from $D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}$

texts:
I'm having a really hard time understanding some of these concepts. I've read them over from several different sources and still can't reach the a-ha moment.

I need to prove a language $L$ is not Turing-recognizable by giving a reduction from the following language:

$$D = \{\langle M\rangle \mid M \text{ rejects input }\langle M\rangle\}\,,$$

where $M$ is a Turing machine, and $\langle M\rangle$ is a binary encoding of $M$, and it is already assumed $M$ is neither decidable nor recognizable.

Most of the things I've read show how to prove a language is undecidable, but not unrecognizable. How would it be different?

I've encountered the following that I feel I can modify for my problem:

$$\mathrm{A_{TM}} = \{\langle M,w\rangle \mid M \text{ accepts }w\}\,.$$

$D$ reduces to $\mathrm{A_{TM}}$. Consider the computable function that maps $\langle M\rangle$ to $\langle M',w\rangle$, where $w=\langle M\rangle$ and $M'$ is a machine that accepts if and only if $M$ rejects. Therefore, $\mathrm{A_{TM}}$ is undecidable.

But I'm not really sure how to understand it, in plain English. Could someone explain it? Plus, how could I change this to show $\mathrm{A_{TM}}$ is unrecognizable (even if it is recognizable)?


texts: Can a CFG end have a non-terminal symbol in the middle of it?

texts:
What is the correct way to write a CFG?

A -> B C' E
C' -> C
C' -> null

or

A -> B C'
C' -> C E
C' -> E


texts: What is the formal name for this algorithmic problem?

texts:
I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction.

The problem is this, Given a long straight road S is the set of the locations of houses down the road. For example S = [1,2,3] would be that houses are placed at 1km 2km and 3km from the end of the road.

We have radio towers that cover a range of 1km and we want to place radio towers at locations along the road so that all houses are covered using the minimum number of towers.

I already know the algorithm to do it, however I'm finding it difficult to understand the proof so would really like the formal name for this problem so that I can research it further.


texts: Proving building a balanced BST out of sorted array is $\Theta(n)$

texts:
I'm having hard time proving building a balanced BST out of sorted array is $\Theta(n)$

I got the following formula: $$T(n)=2T(\frac{n}{2})+\Theta(1)$$

I tried to prove it by induction but got stuck with the case in which $n$ is an odd number.

Is there a better way to prove it? Substitution wouldn't be considered a valid proof (I reached the closed formula using substitution of-course).


texts:
There are POSIX signals (linux man), and various event-based operating systems (such as TinyOS, most seem to be targeted at embedded systems). But the mechanisms seem very similar.

Are the terms 'signal' and 'event' interchangeable? Or are signals a sub-set of events? Or are they two fundamentally different for some reason that I am completely missing?


texts: Is there a shell between the kernel and hardware

texts:
First and foremost, i know what a shell, kernel is. Now the dilemma.

Today i had my systems viva in college. The examiner asked me is there a shell between the hardware and the kernel. Obviously, i said no, and the gave the usual explanation that the shell is an interpreter, it takes the user input, interprets the command and communicates with the kernel via system calls.

He then says what if i say that there is a shell between the hardware and kernel. I said it can't because there is no point. The job of the kernel itself is to interface with the hardware why will the shell be involved.

Then he started arguing that kernels are itself a set of programs, the how can they run another program. Now i got confused.

So if anyone could clear my query that whether a shell exists or not. And the biggest one, how can a kernel run a program. Is it because the kernel is in memory and its starts the init process and all other programs are run by it


texts: Find a simple cycle in an undirected subgraph of a grid graph that encloses the most faces

texts:
Imagine a finite $n*n$ grid graph $G(V,E)$, much like a chessboard. Imagine further an undirected subgraph $H(V',E')$ of $G$. Let us call the squares of chessboard $G$ "faces". A DFS algorithm can detect a simple cycle in $H$ in linear time. However, such a search cannot efficiently find all simple cycles in $H$ as the number of cycles can grow exponentially (?) with the numer of vertices of $H$.

Remark: Since I'm referring to a square grid graph, we have maximum degree 4 for the vertices of $H$. Furthermore, $H$ does not have to be strongly connected. It does not have to have a "reasonable" data structure.

I wonder: What is the time complexity for finding the simple cycle, should it exist, that encloses (surrounds) the most faces? That simple cycle $C(V'',E'')$ is of course itself a subgraph of $H$.

Edit: I would like to add that the very same problem but with a directed graph is also of interest! :-)


texts: What is the regular expression for language containg no.  of 011 equal to 110 in string ?


texts: Minimum number of comparisons in comparison-based sorting algorithms

texts:
I've seen that every comparison-based sorting algorithm must perform at least $\log_{2}(n!)=\Omega(nlog(n))$ comparisons on some input (n being the size of the input).

Why is the minimum number of comparisons $\log_{2}(n!)$, and how is the omega-notation bound calculated?


texts:
Last week I stood up and gave a talk on the Raft Consensus Algorithm.

The first question I got was:

  Doesn't it need an odd number of nodes?

I answered "During leader election, the first node to become a candidate, all the other nodes have to vote for. (Provided for that node the lack of heartbeat, timeout conditions have been triggered, and for the client nodes the candidate has an update to date term log). If two candidates arise at the same time, and neither gets a majority, each will fall back to a different random timeout, and the first to become a candidate (provided all the other criterion are met) will win. So you don't need an odd number of nodes to reach a majority, you just need to be the first candidate. Split votes are handled."

Immediately after this answer - I got the same question from a different person all over again.

  So how does it reach consensus if it doesn't have an odd number of nodes?

My question is: What is the consensus algorithm that requires an odd number of nodes?

EDIT:

Here is an online publication that claims distributed systems need an odd number of nodes. (Spurious claim).

  Partition tolerant consensus algorithms use an odd number of nodes (e.g. 3, 5 or 7). With just two nodes, it is not possible to have a clear majority after a failure. For example, if the number of nodes is three, then the system is resilient to one node failure; with five nodes the system is resilient to two node failures.


texts: Identifying the Equivalence Classes of a Language with equal number of 10 and 01 strings

texts:
I'm doing a problem where I need to find the equivalence classes of the language below:

Let A = {x ∈ {0, 1}* | #(01, x) = #(10, x)}, where, for a, b ∈ {0, 1}*, #(ab, x) is the number of places in x where an a is immediately followed by a b.

So I can start to see some equivalence classes. 1* and 0* both are in A, because they both have zero 10's and 01's, so the condition holds. I don't really know how I would describe the other equivalence classes?

Any help would be great!


texts: How can an extended linearizable history G be equivalent to sequential history S?

texts:
I am undertaking a module in Concurrent Programming where some of the new content this year covers linearizability, the Java Memory Model, and sequential consistency. Our class slides are companion slides to The Art Of Multiprocessor Programming.

I have been doing OK with linearizability but have become confused at this point below:

I understand that removing pending invocations gives a complete subhistory, however I cannot understand from this example how a subset G can be equivalent to set S which is larger than it - how is G  obtained from S here?

As far as I am aware there is not enough information to determine if there are pending invocations from the diagram on the right and I am not sure why a --> b is removed in the subset that is G - at first I thought it's because they are overlapping but A and B both have linearization points for viewing them 'as sequential objects'.

I may be over looking something simple and have just misunderstood the slides.


texts: Can integer linear programs have non-integer OPT solutions?

texts: Why is it that every integer linear program has optimal solutions that are integers? At least in online text books, they are always integers. Can solutions of ILPs only be integers?


texts: Good pointers to learn foundations of Program induction and Program synthesis

texts:
I was interested in learning more about program induction and program synthesis. I was especially interested in learning about how to form program from data for example. My background is in traditional ML+Neural Nets so I have no idea were to start...I am familiar with Program Sythesis by Sketching but beyond that don't know what would be a good say, introduction textbook to the field. Any pointers to get started would be good! Especially if they are the standard foundations for program synthesis/induction.

Of course I saw there are wikipedia articles but they didn't seem like a great reference to learn the foundations and then move forward...


texts: Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?

texts:
I have implemented in C++ the Needleman-Wunsch algorithm for pairwise sequence alignment using the following scores: +1 for match (regardless of base), -1 gap penalty and -1 for a mismatch. Given two sequences of length $m$ and $n$ the algorithm then generates the $mn$ search space row by row as per the algorithm's specifications and backtracks generating all solutions of maximum score. Given two sequences in which the first two letters overlap ie:

GCATGCU

and

GATTACA

the algorithm succesfully generates all the alignments of maximum score. Howeever, given two sequences of the kind:

ACTGCUGCTA

and

UGCTAATCGU

the algorithm fails to find any of the solutions that begin with a gap in sequence 1 or 2, thus failing to find the optimal solution as well:

ACTGCUGCTA-----
-----UGCTAATCGU

Once I add the letter A to the second sequence the algorithm once again has no problem finding the optimal solution (which in this case begins with a match and not a gap)

ACTGCUGCTA-----
A----UGCTAATCGU

Could someone explain to me why the algorithm doesn't find this subset of solutions and perhaps how I can modify it to find these solutions as well?