texts: How to show that a languge is not regular

texts:
How can I show that this language is not regular?

$$
    L = \{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \}
$$

This is my attempted solution:

Assuming the pumping number to be $p$ and making $m=0$

the language reduces to $a^p b^{p+1}$ so  $s=a^p b^{p+1}$

let $s=xyz$ where $y$ is not $\epsilon \\$

$y=a^k$; $0 \lt k<=p$

$x=a^q$; $0 \lt= q \lt p$

$z=a^{p-k-q}b^{n+1}$

so with this definitions, $xyyz$ cannot be part of the language since this would be written as

$xyyz$=$a^qa^ka^ka^{p-k-q}b^{p+1}$ = $a^{k+p}b^{p+1}$ which means there is always an extra $a$ which is not in the original language.

Is this approach correct ?


texts: Counting different words in text using hashing

texts:
I am still fighting with hashing and I am ask myself: what is the most efficient way to count the number of different words in a text using a hash table?

My intuition says that applying the hashcode function to every word in the text, as result we will have words with different hash values in different buckets and the same words will have the same bucket and therefore we will have a collision problem which we can resolve using the chaining method.

Does it work like that?


texts: Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?

texts:
So in this math exchange question I asked, it was proven that for $n>2$ dimensions, you can always find a curve that separates $k$ points in $n$-dimensional space into $2$ arbitrary sets that you pre-defined. What I wanted to know is if there is a polytime algorithm (polynomial in $k$) for determining this curve.

If so, is there a known way to transform this curve into a function using some form of linear or non-linear transformation?


texts:
I saw this relationship in my exercise.
    max{n,k}= Ө(n+k)
Could somebody prove it?


texts: Name for value which may only be -1, 0 or 1?

texts:
Is there a name for a value which may only be -1, 0 or 1?

Is there a name for a function which creates such a value from arbitrary numbers?

It would be implemented like this:

T Function( T value ) {
  return ( value < 0 ) ? -1 : ( value > 0 ) ? 1 :0;
}


texts: What is the difference between self-rewriting program and program-with-updates-and-restart

texts:
I am reading about Goedel machine http://people.idsia.ch/~juergen/goedelmachine.html and especially the article about possible implementation (in the Scheme language) of this machine http://people.idsia.ch/~juergen/selfreflection.pdf . The idea is that there is Scheme environment, then there is special virtual machine (written in Scheme) and at laste there is program (written in the special language for this virtual machine - L3 in the article) for this virtual machine. The virtual machine is quite unusual - it not only loads the program but it also provides extension point through which the program can modify the value of any variable of the executing program and also modify the instruction tree that sits in the memory of the virtual machine. That is the self-modifying progam.

I have 2 questions regarding self-modifying programs:

Is there virtual machine (e.g. for Java or JavaScript), that exposes such facilities for modifying the values of the variables of the running program or for modifying the loaded program structure?
I can not grasp the difference between run-time modification of the self-modifying program (let us call it the scenario S1) and between the following process (that can implement the self-modifying program scenario alternatively) (let us call it the scenario S2):

Program L3 (continuing the notation to name the upper-most program) computes: 1) the updated program - new code; 2) the new values of all the variables of the old program and the initial values of the additional variables introduced anew by the updated program; 3) the codepoint of the updated program at which the execution should be started
Program L3 exits and instructs the execution environment about the next steps that should be taken;
Execution environment loads the updated program and assigns the values of the variables and the starting point/point of resume/point of load according to the point 1. and execution environment boosts the updated program.
Updated program executes and computes the next version of the update in parallel.

Of course, there is third option (S3) - to rewrite JavaScript function pointers of use Perl/Python eval construction - it keeps the current code running, but it spans the new code. So - is there difference between S1, S2, S3? The drawback of S3 is that the memory used by the previous versions of the code is never recovered and so - the program can not be life-long running.

So - what is the difference between S1 and S2? If we consider the conventional computing architecture where the program is executed deterministically (assuming we can control the time slices between tread execution and so on) then I can not see the difference between S1 and S2? In both cases the currently running program should decide which variables and how should be changed, which instruction should be executed next and so on, so on. Restart with update should be the same as the run-time modification of in-memory running program. Or - maybe there is any difference?

Just curious - are there any other applications, research efforts of self-modifying code (especially for Java and JavaScript) which can guide me in my efforts to understand how to implement the self-modifying programs?

There is http://commons.apache.org/proper/commons-bcel/index.html for Java, but I guess, that it does not allow to modify the values of the variables of the code itself or already loaded (for execution) Java class file. There is also culture of meta-circular interpreters https://en.wikipedia.org/wiki/Meta-circular_evaluator - but they are more the intellectual curiosities and the opening up of the running program (variables and code) is not the feature they offer, so, no use for self-modifying programs.


texts: Is deciding whether the language of a TM contains all strings of length 4 computable?

texts:
I was going through some Halting Problem reduction and I found the following problem:

  Given a semi-decider TM $M$, does the language $L(M)$ contain all strings of exactly length $4$?

The question later asks to prove whether this is recursive or r.e. Going through some practicing, I came to the conclusion that this is must be r.e., since otherwise such problem would solve the Halting Problem.

So, I attempted this question by showing that $$HP < 4LENGTH$$

My approach is to show that $4LENGTH$ is recursive and then showing the contraddiction, that $HP$ is not recursive, so is $4LENGTH$.

However I can't understand how to construct such machine. Moreover, by looking at some similar proof I see that they suggest to build a machine $M'$ that erases the tape, writes $I$ (input) on the tape and simulate $M$. However, I can't follow such proof.

Can someone describe how to solve such problem or give any direction?


texts: Is this algorithm actually a graph-traversal algorithm?

texts:
I was given in a lecture the following algorithm that wwas said to be a graph-traversal algorithm.

The algorithm given during the lecture

The algorithm

EXPLORE (s:sommet, D:list of the following vertices of the vertices ahead,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    Else LIST←LIST-{i}

PARCOURS(D: list of the out-going vertices or ahead vertices)
for all vertex x in X
     {visited [x]<-false}
for all x in X
    if not visited [x]
    EXPLORE(x,D,M or visited)

 the example I tried

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
X1 & X2,X4 \\
X2 & X1,X3\\
X3 & X4,X5 \\
X4 & X6,X7 \\
X5 & X2,X6 \\
X6 & X4,X7 \\
X7 & \emptyset \\
\end{array}

I assume that this is the list (tell me if you think this is not the case).

Select 1 $\in$ LIST

LIST(1)=X2,X4 $\not= \emptyset$

X2 $\in$ LISTE(1) is not visited, so we change visited2 to true
X4 $\in$ LISTE(1) is not visited, so we change visited[4] to true
no more elements are not visited, we do LISTE <-LISTE-(1)

the array-list thus becomes:

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
X2 & \not X1,X3\\
X3 & X4,X5 \\
X4 & X6,X7 \\
X5 & X2,X6 \\
X6 & X4,X7 \\
X7 & \emptyset \\
\end{array}

And I can plot $X1$

Then I do the algorithm again

Select 1 $\in$ LIST

LIST(2)=X3 $\not= \emptyset$

X3 $\in$ LISTE(2) is not visited, so we change visited$[3]$ to true
no more elements are not visited, we do LISTE <-LISTE-(2)

the array-list thus becomes:

\begin{array}{|l|cr|}
x & \Gamma^+(x)\\
\hline
X3 & X4,X5 \\
X4 & X6,X7 \\
X5 & \not X2,X6 \\
X6 & X4,X7 \\
X7 & \emptyset \\
\end{array}

I can plot anew:

Then I'm not sure wether to SELECT X4 or X3. It seems that it is the whole difference between Depth-first search algorithm and Breadth-first search ones.

I think this the way the first part of this algorithm run, yet I'm not sure on how does the second partt works. It seems that it allows to explores every paths in my mere opinion...

The algorithm given by a friend of mine

Yet, a friend of mine just wrote the following one rather shorter to do the same thing:

EXPLORE (s:sommet, D:list of the following vertices of the vertices ahead,
var visited:tab)
var: LIST:list; i,j: vertexes;
visited[s]←_true_;
LIST←{s}
While LISTE ≠ 0
    Select i∈LIST
    if ∃ j ∈ D[i], not visited[j]
    visited[j]←true;
    LIST←LIST+{j};
    Else LIST←LIST-{i}

I don't understand how the first one is a graph traversal algorithm and I wonder if it is the best one as far as it seems that the second one is shorter, (but unclearly to me actually).


texts: Is there a difference between a complete graph and a clique topology? As far as I understand, both refer to graphs in which every possible edge between any two vertices is present. Is there a subtle difference between these two concepts?


texts: Given a graph and an integer $k$ is there an independent set larger than $k$ is INDSET problem and is there a cut larger that $k$ is the MAXCUT problem. Is there standard way to convert to 3SAT from these problems that preserves number of solutions? I have only seen reductions other way in standard texts. Since all these are NPC there should be a way to convert back.


texts: How to Construct a Lattice from Program Statements

texts:
In order to optimize a program, I am trying to figure out how the idea of a lattice applies to data-flow graphs, as introduced by this presentation (first diagram below). The lattice seems to take a program, order its inputs and outputs, and allow for easily determining flow of variables and state, so you can perform verification and optimization. But I am not sure how to construct the lattice from the program statements.

In this question I would like to know how to construct the lattice from the program.

Specifically, given a program such as this:

var x = 10
var y = 20
var z = 0
var i = z
while (i < x) {
  y = y + x * i
  i = i + 1
  z = y + i
}

We can construct a Control-Flow Graph (CFG) where each node is a program statement such as var x = 10. From that we can construct a Data-Flow Graph (DFG) where we are keeping track of how a variable is used. This creates an def-use ordering, along the lines of:

x, y, i at the same time
z comes after i
...

That's where I start getting lost. But once we have a partial ordering, somehow a lattice is created. Finally from the lattice, we can do things such as doing pointer analysis (Figure 2) and computing fix-points (Figure 3). That will help in optimization and verification of the program.

I'm wondering only the first part, how to construct the lattice from the example program above. Wondering what is needed to construct the lattice at a high-level. I understand the upper and lower bounds of a lattice, which seems to correspond to CFG inputs and outputs being joined, but I don't quite see how to actually do the join (meet), what the nodes/vertices are in the lattice (not sure if it's a single program statement, a variable, or what), and what the edges are in the lattice. Once that is defined, then doing the rest of the stuff should be straightforward. Thank you for your help.

^- Figure (1).

^- Figure (2).

^- Figure (3).


texts: Do we want largest or smallest priority in the A* algorithm?

texts:
On this site http://algs4.cs.princeton.edu/25applications/ is described A* algothihm this way

  The A* algorithm is a problem-solving process where we put the start
  configuration on the priority queue, then do the following until
  reaching the goal: remove the highest-priority configuration and add
  to the queue all configurations that can be reached from that with one
  move (excluding the one just removed).

But in the programming assignment specification (http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html) is written next

  delete from the priority queue the search node with the minimum
  priority.

I don't understand why on the booksite is written to remove the highest-priority configuration but in the assignment is written to remove the lowest-priority configuration. Please could you explain me it? Maybe they thinks about "priority" or "configuration" in different meaning?


texts: Is the set of admissible numberings recursively enumerable?

texts:
For each admissible numbering, pick at least one pair of programs (but not necessarily all, which is impossible anyway) where the first translates from a given admissible numbering to that one, and the second work in the opposite way.

Now define a language consisting of all the pairs of programs chosen by one such way, for all admissible numberings. Is there such a language being recursively enumerable?

In other words, is there a way to enumerate all possible, sane programming languages (in the form of compilers), in a Turing-machine?

It is not even recognizable whether the two programs defines an admissible numbering. But it doesn't matter much since we only need to get one pair of translators for each numbering.


texts: In multiobjective optimization, how to calculate the distance to reference point?

texts:
In multiobjective optimization, what does the distance exactly means, is it:

1) The distance from reference point (V) to an individual (Xi) (candidate solution) in the population (decision space).

 Euclidean Distance = d(Xi,V)

OR

2) The distance from reference point (V) to the objective vector f(X) in the objective space, where f(Xi) = f(f1(Xi),...fm(Xi)). m is the number of objectives.

Euclidean Distance = d(f(Xi),V)

In this paper "Harris’s Hawk Multi-Objective Optimizer for Reference
Point Problems", in the pseudo code, Section 4.2:

a-

  Calculate distances to reference point v for each search agent(hawk)
  Xi on all objectives ݂fm(Xi).

and

b-

  Calculate distances to reference point vi for all ݂fm(Xi) on each
  search agent in group

What is the difference between a and b?


texts: Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?

texts: This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?


texts:
I am trying to understand basic concepts such as MIPS rate, frequency, CPI etc.

But I am having some trouble understanding the details.
For example suppose a processor designer builds a processor with frequncy 200 kHz and furthermore let's suppose that the processor has MIPS of 0.2. In what ways can that design be accomplished?

What I am thinking is: 200kHz = 200 * 1000 = 200000Hz so that's 200K pulses per second. Based on this if I calculate the CPI by the formula:

$$MIPS = \frac{f}{CPI \times 10^6}$$

$$CPI = \frac{f}{10^6 \times MIPS}$$

$$CPI = 1$$

Now, this is the number of the overall cycles per instruction.

Here are my questions:

What other consideriations that the designer must consider to design such a processor?
Doesn't a CPI of 1 mean that the CPU literally executes all instructions in a single clock cycle, I am guessing you can't execute an instruction in less than 1 clock cycle so to get that overall result they must all take 1 clock cycle so the overall CPI is 1. How feasible is this?

Thanks.


texts: How can one prove that a shunting-yard algorithm always returns a correct expression in RPN? I cannot find any proof in the internet.


texts: Average Time Complexity of Searching An Array

texts: Why is the average time complexity of searching an array $O(n)$? Is it because if the element does not exist, then $n$ searches must be done. If the element is at the end of the array then $n$ must also be done, so $\frac{2n}{2} = n$?


texts: Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

texts:
Given a point in N-dimensional space, I'd like to be able to determine which face of an N-dimensional hypercube of edge length 1 that the point is closest to.

In the 2-dimensional case it's fairly trivial, you simply split the square along its diagonals:

if (x < y) then
    if (x + y < 0) then
        // Side 1
    else
        // Side 2
else
    if (x + y < 0) then
        // Side 3
    else
        // Side 4

In 3-dimensions, this becomes more complex; each face creates a 'volume' of points that are closest to it in the shape of a square based pyramid.

Visualisation of the 6 planes that form the 6 pyramids

Of course, given a point, it's possible to determine which side of the 6 planes it lands on and using that information you can determine which face of the cube is closest. However this would involve running 6 separate checks.

Moving this into higher dimensions, a similar algorithm can be run on hypercubes, however, as the number of faces on a n-cube is $2^{n-2}{n \choose 2}$, this quickly becomes computationally very expensive.

However, theoretically a perfect algorithm could cut the search space in half with every check, discarding half the faces each time.

This would give this hypothetical algorithm a runtime of $O(\log_2(2^{n-2}{n \choose 2}))$ which can be simplified, if my rate of growth calculations worked out, to $O(n\log(n))$

Is my logic correct here; can/does such an algorithm exist?


texts: Can arc consistency checks be avoided if constraints are formulated properly?

texts:
While solving a few CSPs by hand, I noticed that I don't actually need to check for arc consistency after each assignment.
All I needed to do was to formulate the CSP in such a way that I'm adding extra constraints based on the nature of initial constraints in an attempt to predict arc inconsistency.
After assigning a value to a given variable, I would do forward checking and that's it.
Unassigned variables are guaranteed to remain arc consistent with each other without the need to run a separate algorithm like MAC-3 or whatnot to purge remaining values.
Has anyone heard of such a thing before? I can't seem to find it in the literature.  feel like I should give an example so let's say variable C has to be greater than variable B and B has to be greater than A. You could either leave it at that and run into arc inconsistency down the road or add an extra constraint stating by inference that C necessarily has to be greater than A, then you don't need a separate arc consistency algorithm. All you need is proper forward checking.
Please let me know if I'm completely wrong about this intuition.


texts: Operating System - CPU scheduling Decisions

texts:
I understand that CPU scheduling takes place on 4 circumstances listed below:

When the process changes state from Running to Ready
Changes state from Running to Waiting
Changes state from Waiting to Ready
Process Terminates

However, i notice that the CPU scheduling does not take place when Ready to running. Why is this so?


texts: Give an example of a language whose Myhill-Nerode equivalence relation is such that if $x,y \in \{0,1\}^*$ with $x \neq y$, then $[x] \neq [y]$

texts:
Suppose $\Sigma = \{0,1\}$.  Provide an example of a language $L \subseteq \Sigma^*$ with the property that its associated Myhill-Nerode equivalence relation, $R_L$, is such that every one of its equivalence classes is a singleton set; that is, if $x,y \in \Sigma^*$ with $x \neq y$, then $[x] \neq [y]$, where $[x]$ and $[y]$ are equivalence classes with representative elements $x$ and $y$, respectively.

I suspect that this language cannot be regular, since the index of $R_L$ is infinite.


texts: Clarifying what it means to be Strongly NP-Complete

texts:
Wikipedia defines strongly NP-Complete as:

  A problem is said to be strongly NP-complete, if it remains so even when all of its numerical parameters are bounded by a polynomial in the length of the input.

What I interpret this to mean is this:

Let's consider the 3-partition problem, with our numerical paramater being $\sum_{x \in S} x = B$. Since this problem is strongly NP-Complete, there exists a polynomial $p(N)$, such that if we restrict ourselves to only sets $S$ such that $B < p(|S|)$, this problem is still NP-Complete. (i.e. finding an algorithm with complexity polynomial in $|S|$ for this restriction would prove P=NP)

Is this the correct interpretation? If so, where could I find upper bounds of such polynomials $p$ for famous problems, such as the 3-partition problem? Also, if I'm not mistaken, this implies that the 3-partition problem is NP-complete in terms of $B$, as well as $|S|$, right?


texts:
In push relabel algorithm, at the end excess at any nodes is pushed back to source by raising height of those nodes above the height of source. Why is this done? In CLRS it's mentioned:

  To make the preflow
  a “legal” flow, the algorithm then sends the excess collected in the reservoirs of
  overflowing vertices back to the source by continuing to relabel vertices to above
  the fixed height |V| of the source. As we shall see, once we have emptied all the
  reservoirs, the preflow is not only a “legal” flow, it is also a maximum flow.

What does it mean to say "to make preflow a legal flow". Could someone elaborate on the same.


texts: Why are decision problems commonly used in complexity theory?

texts:
From Wikipedia:

  The type of computational problem: The most commonly used problems are
  decision problems. However, complexity classes can be defined based on
  function problems, counting problems, optimization problems, promise
  problems, etc.

I also saw the definitions of NP-complete, NP-hard, NP, ..., are defined for decision problems only. I wonder why that is the case?

Is it because any other problem can be equivalently converted to a decision problem?


texts: Generate data set using unknown distribution

texts: For my research work, I need to generate dataset by using some standard statistical distribution. I have seen Unknown distribution for dataset generation. I do not have any idea about unknown distribution and how to generate data using this distribution. Could you please clarify what is unknown distribution? My problem belongs to NP class, to test my algorithm, I need to generate dataset using different statistical distribution.


texts: Approximate subset sum with two-dimensional vectors

texts:
Consider the following optimization problem:

  Given $n\leq 10^3$ vectors $v_i\in\mathbb{R}^2$, all of which are small, i.e., $\|v_i\| \leq 1$, find a subset $S$ of them that minimizes
  $ \| w + \sum_{i\in S} v_i \|^2$, where $w$ is a fixed known vector.

I know that this can be reduced to an unconstrained 0-1 quadratic program (with unknowns $x_i\in\{0,1\}$, $x_i=1$ whenever $i\in S$), but that is a hard problem in general.

However, since the constraints are so specific, is there a way to get a reasonably simple efficient approximation algorithm for it? One that doesn't involve integer programming? It's not even clear to me how to efficiently implement a greedy algorithm for it.

Are there special cases of this problem that are easier? For example, would it help if all the vectors were unit length, $\|v_i\|=1$?


texts: If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts

texts:
I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal.
Can you help me to structure the proof?


texts: The use of modal logic in computer science

texts: I have a tentative understanding of modal logic.  Can anyone explain modal logic as it is used in computer science?


texts: NSA Recommended Cryptography Algorithms changes from a single paper

texts:
I know that the NSA has recommended cryptography algorithms, such as their A/B suite algorithms and their Commercial National Security Algorithms Suite. I also know that they change their recommendations for key size, an example being in 2019 when they changed the key size recommended for RSA and Diffie Hellman from 2048 to 3072.
Are there any examples of changes like this that have been directly prompted by the publication of a mathematical paper or the creation of an algorithm? When people ask me about the applications of prime numbers to cryptography I want to be able to cite a specific time where math has changed real word cryptography recommendations.


texts: can a computer be totally made up of SRAM?

texts: can a computer be totally made up of SRAM with no DRAM but with secondary memory and run an opreating system properly?


texts: What kind of model is used by 20 Questions?

texts:
Which kind of machine learning concept / model is used in 20 Questions?
Is this kind of thing best solved by a neural network?
Where I can read something about it?


texts: Determining total of primitive operations and running time for code

texts:
i needed some help with these problem in DSA

For the given pseudo code:

for( i=0; i<n; i++ ) a[i] = 0;
for( i=0; i<n; i++ )
  for( j=0; j<n; j++ )
    a[i] += a[j] + i + j;

Determine:

1. Total number of primitive operations
2. Running Time


texts:
In class, I've heard hexadecimal representation for IEEE754 mentioned and described in 32bit length as a format that consists of one bit for sign, normalized 6-digit fraction (with an implied leading zero) and biased (+64) 7bit exponent, leading me to believe it's not just a made up spec.

However, googling the actual IEEE754-2008 standard, I've found only 5 basic formats for base 2 and base 10 in it (binary32, binary64, binary128, decimal64, decimal128) and some more interchange formats for these two bases, but no mention of representation in base 16. Could that specification be some rejected proposal which is difficult to find now or am I missing something here?


texts: We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n > 1$. We need to show that $T(2^n)=\Theta  (3^n)$.  How should I approach this question? Any suggestion?


texts: Comparing the closed behaviors corresponding to finite state automata

texts:
Let $G$ be a finite state automaton (FSA) with transfer function $\delta(\cdot,\cdot)$ and initial state $q_0$. Suppose also $\Sigma_{G}$ represents its alphabet. Assume that its closed behavior is a set of strings defined as:

$L(G) := \{s \in \Sigma_{G}|\delta(q_0,s) \text{ is defined in }G\}$

Now, consider two particular FSA $G_1$ and $G_2$ such that $\Sigma_{G_{1}} \subseteq \Sigma_{G_{2}}$. Clearly, then we clearly have $\Sigma_{G_{1}}^{*} \subseteq \Sigma_{G_{2}}^{*}$. I'm wondering whether or not we necessarily conclude that $L(G_{1}) \subseteq L(G_{2})$.

To me, it's not always true. Am I right?

Here is a simple example to contradict it:

in which $\Sigma_{G_{1}}^{*} \subseteq \Sigma_{G_{2}}^{*}$, but $L(G_{1}) \supseteq L(G_{2})$.


texts: Why isnt node checked for nil value in start when transplanting binary tree

texts:
Whilst I was reading CLRS I came across this:

When TRANSPLANT replaces the subtree rooted at node u with the subtree rooted at node v, node u’s parent becomes node v’s parent, and u’s parent ends up having v as its appropriate child.

TRANSPLANT(T, u, v)
1  if u.p == NIL
2      T.root = v
3  elseif u == u.p.left
4      u.p.left = v
5  else u.p.right =  v
6  if v != NIL
7      v.p = u.p

Lines 1–2 handle the case in which u is the root of T . Otherwise, u is either a left child or a right child of its parent. Lines 3–4 take care of updating u.p.left if u is a left child, and line 5 updates u.p.right if u is a right child. We allow v to be NIL, and lines 6–7 update v.p if v is non-NIL.

Why wasn't v was checked for nil value in the starting of the procedure and if it was not checked then why was it checked in line 6. If v is nil then its parent will be its original parent and u's parent will reference to v - wouldn't this cause inconsistency in tree ?
Context
Transplant is the sub-procedure used in deletion of a node from a binary search tree. It is used in binary search tree not in RB Trees or B-Trees.
Details about the book
Edition - 3rd
Print - 2nd
PageNo - 296


texts: How to find a good asymptotic approximation of T(n) = T(n/2) + T(n/3) + 1?

texts: I can't figure out how to find a good asymptotic approximation for the following recurrence relation: $$T(n) = T(n/2) + T(n/3) + 1.$$


texts: Polynomial time reductions between two problems

texts:
I have two sets $A$ and $B$, I want to reduce $A$ to $B$ and $B$ to $A$.

Formulas consist of a finite set of variables $\mathcal{V}$. An assignment $\sigma$ assigns truth values to each variable in $F$. When writing $F(\sigma)$ for an assignment $\sigma : \mathcal{V} \rightarrow \{0, 1\}$ I refer to the application of the assignment to formula $F$ (truth values are assigned to variables in $F$ according to $\sigma$).

Set A contains all unsatisfiable propositional formulas $F$:

$A := \{F \in \mathcal{F}\ | \  \forall \sigma: \mathcal{V} \rightarrow \{0,1\}. \sigma(F) = 0 \}$

Set B contains all propositional formulas which evaluate to the same truth value for an assignment $\sigma$ and its opposite $\overline \sigma$ (this condition must hold for all assignments):

$B := \{F \in \mathcal{F}\ | \  \forall \sigma: \mathcal{V} \rightarrow \{0,1\}. \sigma(F) = \overline\sigma(F) \}$

Let $A \subseteq \Sigma ^*$, $B \subseteq \Gamma ^*$ and $f: \Sigma ^* \rightarrow \Gamma ^*$.
By reduction I mean finding a total and computable (in polynomial time) function $f$ such that $\forall w \in \Sigma ^*.w \in A \iff f(w) \in B$ which can be abbreviated by $A \leq B$.

How to do the reductions $A \leq B$ and $B \leq A$? After the reductions are done, does that imply that problems $A$ and $B$ are equally difficult?


texts: Push relabel algorithms in flow networks

texts:
In the CLRS book (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation -

$$
\sum_{u \in U}e(u) \;=\;
\sum_{u \in U}\;\sum_{v \in U}f(v, u) \;+\;
\sum_{u \in U}\;\sum_{v \in \bar{U}}f(v, u) \;-\;
\sum_{u \in U}\;\sum_{v \in U}f(u, v) \;-\;
\sum_{u \in U}\;\sum_{v \in \bar{U}}f(u, v)
$$

where $f(u, v)$ is the flow between vertices $u$ and $v$, $e(u)$ is the excess flow at a particular vertex, $U$ is the set of vertices which are reachable from the source, and $\bar{U}$ is the set of remaining vertices.

In the next line, the first and third terms disappear. I don't understand why that holds. I do realize that those are flow values from vertex $u$ to vertex $v$ where both of them are in the same set $U$, but I don't understand why they cancel out to zero.


texts: Relationship between SPACE(t(n)) and DTIME(t(n))

texts:
I'm new to complexity theory and am analyzing inclusions between complexity classes. Suppose we are given the following seven complexity classes

$DTIME(n)$
$DTIME(n^2)$
$DTIME(2^n)$
$DTIME(2^{2^n})$
$SPACE(\log^2n)$
$SPACE(n/\log n)$
$SPACE(n)$

We have that

$DTIME(n)\subseteq SPACE(n) \subseteq NSPACE(n) \subseteq DTIME(2^n)$

and by the Time Hierarchy Theorem,

$DTIME(n)\subseteq DTIME(n^2) \subseteq DTIME(2^n) \subseteq DTIME(2^{2^n})$

So, my gut feeling is that

$SPACE(\log^2n) \subseteq DTIME(n) \subseteq DTIME(n^2) \subseteq SPACE(n/\log n) \subseteq SPACE(n) \subseteq DTIME(2^n) \subseteq DTIME(2^{2^n})$

However, I'm not sure where $SPACE(\log^2 n)$ and $SPACE(n/\log n)$ fit in. I think that this follows from the Space Hierachy Theorem -

$${SPACE}\left(o(f(n))\right) \subsetneq SPACE(f(n))$$

Is there another theorem or result I could review to justify my proposed order?


texts: Problem related to the Knapsack problem: Is it NP-hard?

texts:
I am trying to know whether the following problem is NP-hard:

Input: A positive number $k$ and $N$ pairs of numbers. Each pair $i$, contains the positive numbers $a_i$ and $b_i$.

The problem is to select a subset of numbers $S$ among the set $\{a_1,b_1,a_2,b_2,..., a_N, b_N\}$ such that it maximizes the sum of the values of the $S$.

The are two constraints:

For each pair $i,\; (i=1,...,N)$ you cannot select $a_i \text{ AND } b_i$ (either $a_i$, or $b_i$, or none, but never both)
The weight of selecting the number $a_i$ is 1, and the weight of selecting the number $b_i$ is 2 (for all $i=1,...,N$). The sum of the weights of all the numbers selected in $S$ cannot exceed $k$.

Is this problem NP-hard?


texts: Is dynamic programming restricted to optimization problems?

texts: The usual criteria used to decide if a problem can be solved using dynamic programming is (1) if it has optimal sub-problems and (2) if it has overlapping sub-problems. Does the word "optimal" mean that DP can only be used to solve optimization problems? Otherwise, it would make more sense to write (1) as "if it can be decomposed in sub-problems" (i.e. it is recursive). Obviously, this definition includes optimization problems with optimal sub-problems.


texts: Given a directed acyclic graph $G=(V,A)$ and a set $A'$ of $A$. It is well known that searching for a minimum number of vertex-disjoint paths that cover all the vertices of $G$ can be solved in polynomial time. Will the problem remain polynomial if we add the constraint that each path should contain at least one edge of $A'$?


texts: Why doesn't 2-opt return an optimal solution?

texts:
To find a solution for the Traveling Salesman Problem (TSP), one way to go is an algorithm called 2-opt, which is explained below.

The 2-opt algorithm basically removes two edges
from the tour, and reconnects the two paths created.
This is often refered to as a 2-opt move. There is only
one way to reconnect the two paths so that we still
have a valid tour (figure 1).  We do this only if the
new tour will be shorter. Continue removing and re-
connecting the tour until no 2-opt improvements can
be found. The tour is now 2-optimal.

For me, this algorithm tries all possibilities for edge combinations, so it should return the best (optimal) solution, right? Wrong, because :

If we look at the tour as a permutation of all the
cities, a 2-opt move will result in reversing a segment
of the permutation.
Running the 2-opt heuristic will often result in a tour
with a length less than 5% above the Held-Karp bound.

My question is ; why does it not return the optimal solution? Does it not try all possible edge combinations? Can you give an example graph for which 2-opt doesn't give an optimal solution?
I'm citing from here : https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf


texts:
I have proven the foldr Fusion Law as follows:

Given f is strict, f a = b and f (g x y) = h x (f y) for all x and y, than

f.foldr g a = foldr h b

Case []:

(f . foldr g a) [] = foldr h b [] -- Remove . notation
f (foldr g a [])   = foldr h b [] -- definition foldr
f (foldr g a [])   = b            -- definition foldr
f a                = b            -- This is a given, so stop

Case (x:xs):

(f . foldr g a) (x:xs) = foldr h b (x:xs)       -- remove . notation
f (foldr g a (x:xs))   = foldr h b (x:xs)       -- definition foldr
f (g x (foldr g a xs)) = h x (foldr h b xs)     -- inductive hypothesis
f (g x (foldr g a xs)) = h x (f (foldr g a xs)) -- introduce y
                 say y = foldr g a xs
f (g x y)              = h x (f y)              -- This is a given, so stop

Now, I would also like to prove the Fusion Law for foldl. This goes like this:

Given f is strict, f a = b and f (g x y) = h (f x) y for all x and y, than

f.foldl g a = foldl h b

However, I don't seem to be able to use the same trick as in the proof for foldr. How can I prove the foldl Fusion Law?


texts: Reducing from Hamiltonian Cycle to Subgraph Isomorphism

texts:
I am reading Subgraph isomorphism problem

I am having trouble understanding how they prove that the subgraph isomorphism problem is NP-Complete using the Hamiltonian cycles problem in the article.

Can someone help me explain what is happening in more laymen terms?


texts: What is the complexity of sum of Logarithm of an arithmetic series

texts:
this is the arithmetic series:

$a/b,2a/b,3a/b,...,ba/b$

The new series:

$log(a/b),log(2a/b),log(3a/b),...,log(ba/b)$

I want the complexity of sum of the latter.

p.s: sorry about formatting.

edit 1: I realized that I need to provide more info:

$a,b \in \mathbb{N} $

$a>b$

a and b are not constants.
and the answer is something similar to :
$O(b*log(a))$


texts:
I'm working on a clustering problem and want to sample partitions (possible clustering solutions) among a set of constrained ones.

Here is the problem: I have a set of objects $O=\{o_1,\ldots,o_n\}$ and would like to sample among reflexive, symmetric and transitive relations $R \in O \times O$ such that samples satisfy a set of must-link/cannot-link constraints. More specifically, I do have for some pairs $o_i,o_j$ either that $(o_i,o_j) \in R$ or $(o_i,o_j) \not\in R$. Alternatively, I could see it as the problem of sampling graphs that are disjoint cliques with pre-specified arcs or absences or arcs.

Reject sampling is likely to not work in practice, as the number of rejection would quickly be prohibitive as n and the set of constraints get high enough (something we can expect).

Do any of you know if this problem has been treated, or any easy way to solve it? Uniformity within the set of samples is desirable, but not absolutely necessary.

Thanks.


texts: Prove there is a polynomial time algorithm for independent set if there exists one to this problem

texts:
Given the following:

"You are organizing a party and you want it to be as much fun as possible.
You have $n$ friends to choose from, but the maximum number of people that you can invite into your flat — its capacity — is $C$. The fun at a party stems from pairwise interactions between guests, and you have the an $n \times n$ “fun table” $F$, such that for every pair $(i,j)$ of your friends, $F[i,j]$ is a number between 0 and 1 that specifies
how much fun their mutual presence at the party would contribute.
The DECENT-PARTY decision problem is—given an $n\times n$ array $F$ representing the fun table, a number $C$ and a number $T$ as inputs—to determine if there is a selection of $C$ guests such that the total fun contributed by all pairwise interactions between them is at least $T$."

How can I prove that if there is a polynomial time algorithm for solving DECENT-PARTY then there is also one for the INDEPENDENT-SET decision problem? In order to do this I want to show a polynomial time reduction from INDEPENDENT-SET to DECENT-PARTY, i.e. that DP is at least as hard as IS and thus it follows.

To do this, I think I need to instantiate IS, a graph and some integer $k$. Then somehow translate that to an instance of DP but I am not sure how as it seems that DP involves non-integer values.


texts: How to express taking the next bit of an infinite string in small-step semantics?

texts:
I have to write a rule as part of a small step operational semantics (https://en.wikipedia.org/wiki/Operational_semantics).

Whenever this rule is applied, the next bit belonging to an infinite
bit string must be taken.
Therefore, in the premise of the rule, I have to express that the next bit of a (previously) fixed bit string is taken.

To represent the set of infinite (bit) strings, it is usually used the notation $\{0,1\}^{\omega}$.

So, the first idea is to write the premise of the rule in the following way:
$ b= nextBit(str) \quad str \in \{0,1\}^{\omega}$.

What do you think about that?
In my opinion, it doesn't make explicit that the infinite string $str$ is chosen once and then fixed.
Is it something like

$ b = nextBit(str  \rvert_{str \in \{0,1\}^{\omega}})$

reasonable or it is too fuzzy/ non standard?

How would you express it explicitly that $str$ is fixed and it doesn't change during the run?


texts: What is the real advantage of Google's new Fuchsia operating system kernel?

texts:
Google's new in-production OS which it desires to replace not only Android but many other devices utilizes a completely new kernel:

  The code differs from Android and Chrome OS due to its being based on the "Zircon" kernel (formerly "Magenta") rather than on the Linux kernel.

https://en.wikipedia.org/wiki/Google_Fuchsia

  Zircon does not support Unix-style signals and provides no way to directly implement them. Instead, it supports waiting on handles, which can be in a number of different signal states, such as ready for writing, running, stopped, etc. Similarly, Zircon does not have Unix-like fork or exec but uses the launchpad library to create processes.

https://www.infoq.com/news/2018/04/google-fuchsia-zircon-early-look

I've seen demos of Fuchsia by reviewers but these are all just demos of a desktop interface and don't actually describe any of the advantages towards moving to a new platform and the motivation for a building a new kernel.

I see a lot of technical jargon and engineering-speak being thrown around but this isn't anything different from what I hear about every new platform and its super-sauce kernel.

In my opinion, it's always been about market penetration and mindshare. Google has a unique advantage in that they have a widespread platform already with Android and may be able to strong arm vendors into switching from Android to Fuchsia. But this may also be a re-run of several failed attempts by previous market leaders to do this very thing.

Software compatibility is, in my opinion, a constant when it comes to enticing existing users to move to a new platform. Apple was able to do this gracefully with Rosetta and Windows with NTVDM. I think that it will be very interesting to see how well Android can handle this with so much fragmentation.

So that was a little history and some of my opinion. But my actual question is on what, from a technical standpoint, does Fuchsia's new kernel "Zircon" bring to the table? Creating an entirely new userspace is one thing but swapping out a kernel is a completely other beast. Especially when there is so much existing experience not only for Android but also Linux kernel expertise.

My personal opinion may be dark but I feel that it comes down to licensing and an attempt at increasing vendor lock-in by moving away from Linux; that Google went window shopping and happened upon what became the basis of Zirkon. But this is speculation. What I would like to know is if there is any real technology that brings tangible benefit to all of this work when we already have the venerable Linux kernel available to us?

I would also like to highlight the following source for your reference:

https://fuchsia.googlesource.com/zircon/+/master/docs/concepts.md

I am an applications programmer and don't understand what the benefit is of Zircon's kernel as a design and welcome being educated on how it compares to existing architectures. If Google thinks that it is worthy as the successor of Android's Linux kernel then I feel that there are probably tangible benefits being brought to the table that I am just too inexperienced to appreciate.


texts: Is there any uncountable Turing decidable language?

texts: There are many(and I mean many) countable languages which are Turing-decidable. Can any uncountable language be Turing decidable?


texts: Difference between symbolic execution and reachability analysis

texts: Now I am confused about symbolic execution (SE) and reachability analysis (RA). As I know, SE uses symbols to execute some code to reach each branch with branch conditions. And RA can be used to find the reachability of each branch, right? When RA is used, we can extract the branch condition for each branch. If so, what's the difference between them? Can they be swift? Are they all static analysis?


texts: Formal Grammar: derivation form posted on Wiki?

texts:
Wiki describes the binary relation $\underset{\mbox{G}}{\implies}$ as "G derives in one step".  I have a question on the condition when there are multiple productions for a single non-terminal.
Wiki defines $G = (N, \Sigma, P, S)$ and $\underset{\mbox{G}}{\implies} \subset (\Sigma \cup N)^* \times (\Sigma \cup N)^*$ where:
$(\underset{\mbox{G}}{x \implies y}) \iff \exists u,v,p,q \in (\Sigma \cup N)^* : (x = upv) \land ((p, q) \in P) \land (y = uqv)$
Then
$(\overset * {\underset{\mbox{G}}{x \implies y}})$ is defined as the refexive transitive closure.  Therefore applying $\underset{\mbox{G}}{\implies}$ multiple times results in the language of the grammar:
$\{w \in \Sigma^* | (\overset * {\underset{\mbox{G}}{S \implies w}})\}$
QUESTION
For the form $(\underset{\mbox{G}}{x \implies y})$ I consider the case of multiple rules $(p,q_0), (p, q_1) \in P$ for a non-terminal $N$.  If solving for $y$, $y$ will result in the string with only a single rule applied.  How should the derivation happen with multiple production rules?
I can see that supplying both arguments $(\Sigma \cup N)^* \times (\Sigma \cup N)^*$ to $\underset{\mbox{G}}{x \implies y}$ will yield all derivations.


texts:
A central processing unit offers to handle various operations like calculating, watching movies, making presentation etc. While a graphics processing unit is majorly used for the purpose of video rendering or playing of high-quality graphical games.
I found the above statement on a website listing the differences between CPU and GPU.
What I am not able to understand is how making PPTs,listening to songs from graphics in terms of mathematical operations that the brain of computer applies!
All these operations handled in terms of bits,so why treat them differently?
Also why cant we have a PC completely based on GPUs if they so good at executing parallel instructions and handling large amount of bits for graphics?Though i have heard about GPGPUs but why cant traditional GPUs be used?


texts: Floating-point oblivious way to compute multiset numbers

texts:
I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be:
$$
R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{1\cdot 2\ \cdots\ k}.$$
The problem is that, if you compute the numerator and denominator separately, you will run very soon into overflow territory, so a better way to calculate this division, since both parts of the fraction have same number of components, is by: $$R = \left(\frac{n+1}{1}\right)\left(\frac{n+2}{2}\right)\cdots\left(\frac{n+k}{k}\right) = \prod_{i=1}^k\frac{n+i}{i} = \prod_{i=1}^k\left(\frac{n}{i} + 1\right)$$
The problem of this approach is that you have to apply floating point arithmetic to do the divisions, which are way more inefficient than using simple integral arithmetic.
But, knowing that the final result would be integral, is there any[1] way to split the big fraction into a sequence of products of fractions so that each fraction has a numerator that is a multiple of its denominator? The idea is to remove any floating point operation to calculate $R$.
Has this formula any property that guarantees that such sequence exists?
[1] Ok, maybe not "any" way would be valid. If the process to avoid the floating point arithmetic would cost more than the floating point arithmetic itself, it won't be worthy.


texts: How to write decoder for compressed stringified objects

texts:
Aim: schema aware transformation.

I've written a code(in js) which can transform data {projectDetails: [ {detail : {}, id : "gwl" }], name: "amit"} into string @gwl|amit. But I'm not able to complete the decoder to transform it back.

Problem: logic to transform string back to object

In detail

Consider that following schema is given to transform data into string and back to object.

var schema = {
    type: "object",
    properties: {
        "projectDetails" : {
            type: "array",
            properties: {
                "detail" : {
                    type: "object",
                    properties: {
                        "first" : { type: "string"},
                        "last" : { type: "string"}
                    }
                },
                "id" : { type: "string"}
            }
        },
        "name" : { type: "string"}
    }
}

Consider following chars to understand the transformation;

| : boundary indicator. To separate consecutive dynamic data fields.
^ : next field(set of fields) is/are repeated array item
$ : empty value
# : missing, null, undefined field
@ : empty object or array
! : missing, null, undefined object or array
Y : True
N : False

Example: Transform

{projectDetails: [ {detail : {}, id : "gwl" }], name: "amit"}
> @gwl|amit

{projectDetails: [ {detail : {} }], name: "amit"}
> @$amit

Problem: transform string back to object

Implementation

I iterated the schema to updated every data field with possible next char may occur in transformed string to identify the boundary of current field. It can help to reduce number of comparisons while decoding.

E.g. for the field id in above schema next possible chars in transformed string can be : [$^|#].

Since this way complicate the solution, following regular expression can be used (.*?)([|^#@!YN]) to read next field always. (it returns 2 matches every time, if first match is empty just ignore it and read further.)

Challenge

> @$

For above string, my decoder fails. Why? Because this is how I transform the string back.

I read the schema.
Since projectDetails is an array type, I loop
Since array's item is of type object, I use recursion
detail is object type and since the first field value in string is @. I mark it empty
I read next field and mark it with $
I come out from the recursion.
Since there is no array separator, I read next field of the root object.
I find nothing in transformed string to read.

Note I don't want to convert transformed string into array of fields. It'll cause issue in case of big objects.(I've faced it with other project)


texts:
Is there a flowcharting application like Raptor for Mac. I am using the OS X (Sierra) version. I use Raptor in Windows and need a similar application
for Mac.


texts: Yao's minimax lemma for Monte Carlo algorithms

texts:
In the query complexity model, we define $R(f)$ as the bounded-error query complexity of $f$.
It is said that

  Claim. we can find two hard distributions over the 0- and 1-inputs of $f$ respectively, such that distinguishing between them with bounded error takes at least $\Omega(R(f))$ time for any randomized algorithm.

I have tried to use Yao's minimax lemma to show this but I failed. More concretely,  the obstacle I met is that an algorithm that distinguishes distributions as described need NOT to be a bounded error algorithm for $f$.

Question. How to prove this claim?


texts: graph has at most 2017 connected components is in NL

texts:
I need to show that deciding whether a graph G has at most 2017 strongly connected components in in NL.

After searching, i found a previous answer:

Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

The answer there by yuval filmus was given for verifying an exact amount of SCCs.

I am not sure how to modify it to make at applicable for checking an "at most" condition.

I though of running the given algorithm for a loop of t:=1 to 2017, where t is the number of SCCs.  the loop continues until an acceptable t is found and the algorithm accepts. if none is found, the algorithm rejects. the result still seems to be in NL becuase i use the same amount of memory and add a loop counter for t.

Is this the correct path?

thank you.


texts: Is this a correct approch of finding expected runtime of an algorithm?

texts:
Consider two algorithms; we analysis their run time only by counting the number of comparisons

TwoMax1(A):
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > L:
             S = L
             L = A[i]
         else
            if A[i] > S
                S = A[i]
    return (L,S)

 TwoMax2(A):
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > S:
            if A[i] > L:
             S = L
             L = A[i]
            else
                S = A[i]
    return (L,S)

Here is my approach for the first algorithm:

(1) define our sample space. Since the returned output is a pair, maximum and second maximum could be anywhere in the array. For each maximum, there are $(n-1)$ possible index for second maximum, and we have $n$ possible index for the maximum value; So sample space: $S = \{(A[0],A[1]),(A[0], A[2]),(A[0],A[3]),\dots\}$ and so on.

Define an indicator $I_i = 1$ iff $A[i] > \max \{A[0], A[1], \dots, A[i-1]\}$.

The total expected comparison of comparing to maximum would be $$\mathbb{E} (\sum_{i=0}^n I_i) = \sum_{i=0}^n \mathbb{E}(I_i) = \mathrm{Prob}(A[i] > \max \{A[0], A[1],\dots, A[i-1]\}) = \frac{n+1}{2}.$$

where $$\mathrm{Prob}(A[i] > \max \{A[0], A[1], \dots, A[i-1]\}) = \frac{i}{n}$$ because under the sorted array, we have $\frac{i}{n}$ chance of choosing a integer that greater than $A[0], A[1],\dots,A[i-1]$.

Now similar, the total expected comparison of comparing to second maximum would be same; and we sum two parts together up is $n+1$.

Is this a good way of approaching? If so, I also want to know some other ways of doing it, for example, define a different random variable to solve the second function.


texts: Turing Machine which will double every 'b' in all inputted string

texts:
I am trying to construct a Turing machine which will double every 'b' in all inputted strings over{c,b}.
How can I double 'b' in inputted string? because I cannot replace b with bb because one cell  of tape can contain only one character.


texts: How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?

texts:
Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such a rule can be modeled as a function that takes as input a 3 by 3 matrix of bits, and outputs a bit.

Such a rule can be represented easily using a string of 512 bits representing the output for each of the $2^{3 \times 3}$ input states. Since this representation is bijective, a rule can also be randomly generated by sampling 512 bits.

However, it is sometimes preferable for reasons of aesthetics and comprehensibility that the output of the rule be the same when the input matrix is rotated or flipped horizontally or vertically. The rule for Conway's Game of Life is an example of a function satisfying this restriction.

Given a function $r : 2^9 \to 2$ which does not necessarily obey this restriction, we can obtain a function that does by mapping the input to the lexicographically smallest matrix obtainable by reflecting or rotating it before passing to $r$. However, this provides little insight into the questions I am interested in:

How many functions obey this restriction?
How can they be compactly representing using a bit string?
How can they be efficiently randomly generated?


texts: Information on Tavori and Dreizin ranged hash function?

texts:
While doing some digging around in the GNU implementation of the C++ standard library I came across a section in bits/hashtabe.h that refers to a hash function "in the terminology of Tavori and Dreizin" (see below). I have tried without success to find information on these people, in the hopes of learning about their hash function -- everything points to online versions of the file that the following extract is from. Can anyone give me some information on this?

*  @tparam _H1  The hash function. A unary function object with
*  argument type _Key and result type size_t. Return values should
*  be distributed over the entire range [0, numeric_limits<size_t>:::max()].
*
*  @tparam _H2  The range-hashing function (in the terminology of
*  Tavori and Dreizin).  A binary function object whose argument
*  types and result type are all size_t.  Given arguments r and N,
*  the return value is in the range [0, N).
*
*  @tparam _Hash  The ranged hash function (Tavori and Dreizin). A
*  binary function whose argument types are _Key and size_t and
*  whose result type is size_t.  Given arguments k and N, the
*  return value is in the range [0, N).  Default: hash(k, N) =
*  h2(h1(k), N).  If _Hash is anything other than the default, _H1
*  and _H2 are ignored.


texts: Closest k points - performance on large lists

texts:
Very similar to this

Problem formulation: Given a list $L$
of n points with GPS coordinates and a second list $Q$ of $m$ points, find the $k$ (let's say 3) closest points on $L$ for each element on $Q$.

Aditional constrains: Assuming that both $L$ and $Q$ are very large, and performance is an issue. We can also assume that $Q$ is much larger thant $L$. Preprocessing can be performed, but has to be robust to updates on lists $L$ and $Q$ (ergo, it can't be be very performance heavy).

Problem extensions: If we can't have preprocessing, because the updates on $L$ and $Q$ are very common, what would be the solution?

If you can also point me out to implemented solutions on R or Python it would be great!


texts: What goes wrong with sums of Landau terms?

texts:
I wrote

$\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

but my friend says this is wrong. From the TCS cheat sheet I know that the sum is also called $H_n$ which has logarithmic growth in $n$. So my bound is not very sharp, but is sufficient for the analysis I needed it for.

What did I do wrong?

Edit:
My friend says that with the same reasoning, we can prove that

$\qquad \displaystyle \sum\limits_{i=1}^n i = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n)$

Now this is obviously wrong! What is going on here?


texts:
In the book introduction to automata theory and languages, $L^*$ is defined as

$$L^* =  \bigcup_{i=0}^\infty L^i $$

The book also says that $\emptyset^* = \{  \epsilon   \}$. But since $\emptyset$ is the empty set

$$L^* =  L^0 \cup L^1 \cup L^2 ... $$

$$=  L^0 \cup \emptyset$$ -- since $ \emptyset\emptyset = \emptyset $ and there are 0 elements of $L$

Now since L is $ \emptyset $, then it does not contain $\epsilon$ either. So thus

$$L^* =  \emptyset $$

But that does not seem to be the case. According to the book, $L^0$ is $\{ \epsilon \}$ and thus $L^* = \{ \epsilon \}$, for L = $\emptyset$. Where am I going wrong?


texts: Using a combination of spatial and non-spatial inputs for convolutional neural networks

texts:
I'm working on training a game AI using deep reinforcement learning to achieve specific examples based on pixel input and some additional state information.

Naturally, I'm using a convolutional neural network to deal with the pixel information, which has been working well so far. However, I still have additional information available, such as numeric values associated with current health and ammo.

I know it must be possible to create a network architecture to take advantage of both the spatial information provided by the screen buffer as well as non-spatial information such as the game states I mentioned earlier. Is there any way to create a neural net architecture that can handle both spatial and non-spatial state?


texts: NFA to recognize bit strings containing 01111110

texts:
Basically, I currently have two ideas but unsure on which is correct for the following question:
"The High level data link control protocol (HDLC), is a popular protocol used for point-to-point data communication. In HDLC, data are organised into frames which begin and end with the sequence 01111110. This sequence never occurs within the main body of the frame, only at the beginning and end (in order to avoid confusion).

a.)Design an NFA which recognises the language of binary strings which contain one or more HDLC frames"

My possible solutions:

The next part is to convert to DFA, but I first need to get this part right.


texts:
Whenever we load a process (which consists of object code, static and global variables, stack and heap space) into main memory it would be of fixed size. But, the program doesn't know in advance how much heap memory is it gonna need? Is there some fixed stack and heap space given to each process of some size in advance? But, then wouldn't it be a waste of space to give same amount of stack and heap space for each process ?

There can  be other possibility that whenever we execute malloc, operating system gives us free space (basically holes) from main memory which is not the part of process. So, process size can increase at runtime. Then, Why is stack and heap space given to a process in the first place?


texts: Optimal order to traverse a grid with caching

texts:
Let's say I want to evaluate a two-argument function using all possible combinations of elements from sets A and B as arguments.
For example, if the function is addition, we get this grid:
       A

     1 2 3
   1 2 3 4
B  2 3 4 5
   3 4 5 6

Let's also say that retrieving an element from a set is has a fixed cost, but we can remember up to N elements at a time.
Is there a known optimal order in which to consider the elements, in terms of cost?
For example, we could start with the first element of A, then consider every element of B. If the size of B is much larger than N then every new element of B will be a "cache miss", making this a not very efficient strategy.


texts: Using induction to prove a big O notation

texts:
I'm trying to prove that the following recurrence relation has a runtime of O(n):

 fac(0)   = 1
 fac(n+1) = (n + 1) * fac(n)

I think that I can use induction in the following manner:

Base case

If n=0 then fac(n) = fac(0) = 1

Inductive case

Assume that fac(n) has a runtime of O(n)

fac(n+1) = (n + 1) * fac(n)

Therefore fac(n+1) has a runtime of O(n+1)

However, I have a suspicion that my inductive case doesn't really prove much. Maybe this is because the my assumption for the inductive case is wrong?

Can you point me in the right direction to prove this runtime?


texts: Why " every non-prime attribute of R is non-transitively dependent on every key of R" in the original def of 3NF?

texts:
I have read the definition in of Third_normal_form here
, which shows

  The third normal form (3NF) is a normal form used in database normalization. 3NF was originally defined by E.F. Codd in 1971.[2] Codd's definition states that a table is in 3NF if and only if both of the following conditions hold:

    The relation R (table) is in second normal form (2NF)
    Every non-prime attribute of R is non-transitively dependent on every key of R.

From the book Database Systems The Complete Book 2nd Edition, key means candidate key.

And I got the definition of transitive dependent here.
So my problem is this:
From the quoted definition, if we denote any non-prime attr as $x$, any key of $R$ as $K$, suppose $x$ is subset of an attributes group $A$, we can easily construct some $A$ satisfied $$K \rightarrow A \wedge A \nrightarrow K \wedge A\rightarrow x  $$ so where am I wrong?


texts: Proving correctness of an exponentiation routine

texts:
I have the following exponentiation routine, which takes $O(\log n)$ steps

function power(a:real, n:positive integer)
begin
  x:=1;
  i:=n;
  while i > 0 do
  begin
    if(i % 2 == 1) then   //i odd
      x:=x*a
    i:=floor(i/2)
    if(i > 0) then
      a:=a*a
  end;
  power:=x
end

I'm trying to prove that it always gives $a^n$.  I think it might be provable via induction on $n$.  in the examples i went through i found that it always ends with $i=1$ before the final division down to $0$.


texts: What's the difference between a calculus and a programming language?

texts:
I think I'm pretty confused about what's called a calculus and what's called a programming language.

I tend to think, and might have been told, that a calculus is a formal system for reasoning about the equivalence of programs. Programs have an operational semantics specified by a machine, that should (I think?) be deterministic. In this way, a (correct) calculus for a language $L$ is a proof method for program equivalence.

This seems like a reasonable split to me, but is this the commonly accepted meaning? Or maybe it's even wrong?

Related, why are some operational semantics nondeterministic (assume it is confluent)? What is gained from leaving the choice of strategy open?

I'd really appreciate some clarification on these; and concrete references even more! Thanks!


texts: Is it possible to prove Turing irreducibility

texts:
Given two languages $L_1$ and $L_2$, is there a known way to show that $L_1\not\leq_T L_2$?

In other words, is it possible proving that there is no Turing reduction from $L_1$ to $L_2$?


texts: Let L be any non-empty language over an alphabet Σ. Show that $L^2$ ⊆ $L^3$ if and only if λ ∈ L

texts:
I have this question in my Theoretical Computer Science class on the topic of Automata and Formal Languages.

$$ λ ∈ L \iff L^2 ⊆ L^3$$

I thought of showing it by proving the contrapositive but I was only able to complete half of the proof (since it is a bidirectional proof) and on top of that I am not even sure it is correctly written in a formal form.

I wanted to prove that if

$$λ ∉ L \implies L^2 \nsubseteq L^3$$

But since it is a bidirectional proof, I must also show that

$$L^2 \nsubseteq L^3 \implies λ ∉ L$$

right?

This is what I have so far:

1) $λ ∉ L \implies L^2 \nsubseteq L^3$

$ \lambda \notin L \implies \forall w \in L, n_o(w) \geq 1$
$ L^2 = L * L \implies \forall w_2 \in L^2, n_o(w_2) \geq 2 $
$ L^3 = L * L * L \implies \forall w_3 \in L^3, n_o(w_3) \geq 3 $
$\forall w_3 \in L^3 \land \forall w_2 \in L^2, n_o(w_3) > n_o(w_2)$
$ \therefore L^2 \nsubseteq L^3$

So first of all, is this correct?

Secondly, how would I go about showing the second part of my proof where
$$L^2 \nsubseteq L^3 \implies λ ∉ L$$

Thank you!


texts: Why does Akra-Bazzi need that toll-function g is bounded?

texts:
Following up on vonbrand's answer I want to write a small document about stronger master theorems for our students, one of which is the Akra-Bazzi theorem. I have copied the theorem from their paper [1] and found -- besides a small notational confusion² -- the following problem.

The authors require (emphasis mine):

  $g(x)$ is defined for real values $x$, and is bounded, positive and nondecreasing function
  $\forall x \geq 0$

Here, $g$ is the toll function, that is the recurrence has the form

$\qquad\displaystyle T(n) = g(n) + \sum_{i=1}^k a_i T\bigl(\lfloor n b_i^{-1} \rfloor\bigr)$.

Now, at the end of their paper (p209) they give multiple examples for applying their result and they use functions in $\Omega(n)$ which are clearly not bounded.

From skimming the proof they mainly seem to require that integrals of the form

$\qquad\displaystyle \int_a^b \frac{g(x)}{x^{p+1}} dx$

have finite values. So, requiring $g$ to be bounded on every compact interval might be sufficient; I did not work through the proof in detail. Is it possible they mean that?

My question is: How should the Akra-Bazzi theorem be stated so that it is consistent with proof and examples?

On the solution of linear recurrence equations by M. Akra and L. Bazzi (1998)
They require $a_i \in R^{*+}$. Is this some notation I don't know, or a typo? I assume the intended meaning is $(0,\infty) \subseteq \mathbb{R}$.


texts: How best to statistically verify random numbers?

texts: Lets say I have 1000 bytes that are supposedly random. I want to verify to a certain certainty that they are indeed random and evenly distributed across all byte values. Aside from calculating the standard deviation and mean value, what are my options for a robust verification process?


texts: Turing Machine-Like Formalism for The Actor Model

texts:
Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.

The Actor Model is sometimes mentioned as a more powerful computational-model than Turing machines (not in what it can compute, but in other aspects).

Is The Actor Model a full fledged Turning machine alternative as a computational model?
Does The Actor Model also have such a symbol-based formal computation description akin to the Turing machine?
Are the actors assumed to be Turing machine equivalent - since each message is processed sequentially (and atomically)?

There are many theoretical results based on Turing machines, e.g. the halting problem, decidability, relation to Gödel's incompleteness theorem etc.

Can these proofs be formally generalize to the Actor Model? Has this been done?


texts: Unconditional arithmetic circuit lower bounds for permanent/determinant

texts:
In this http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.12.1090&rep=rep1&type=pdf an unconditional lower bound (provided constants used are bounded by absolute value smaller than $1$) of $\Omega(n^2\log n)$ for size of arithmetic circuits computing $n\times n$ Matrix Multiplication is given.

What is the best unconditional lower bound for size of arithmetic circuits computing $n\times n$ Matrix Determinant and Permanent along similar lines?


texts:
For any context free grammar, there is a parser that takes atmost n^3 time to parse a string of length n.
Doubt: I marked it false in a national level exam.I think it should be any null-free context free grammar and not any cfg because we first have to convert cfg to cnf but only null free cfg can be converted to cnf.
Is this statement correct?


texts: Prove that Weighted Independent Set is NP Complete using Independent Set?

texts:
$k$-Weight Independent Set
  Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$.
  Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum_{v\in V'} w(v) \geq k$?

Showing that this problem is in NP is trivial, but I'm suck on showing that $X \Longleftrightarrow Y$. The forward direction is simple I think.

$\Longrightarrow$ If you have a $k$-Independent Set, then we know that each node has a weight that is a natural number ( $\ge 1$ ), so the graph has weighted independent set of at least $k$.

But how would you show the reverse direction $\Longleftarrow$?


texts: Use the pumping lemma to prove that {www} is not context-free

texts:
Use the pumping lemma to prove that the following language is not context-free.

$\qquad L = \{ w w w \mid w \in \{a,b\}^*\}$

I am studying for an exam and really trying to understand this question. For some reason the third w is throwing me off.

I first tried using the string $a^p b^p a^p b^p a^p b^p$ but didn't get very far.

The other string I tried to work through it with was $a^p b^p b^p$

Having a hard time figuring out how exactly to split it up.

Any guidance and explanation would be greatly appreciated.


texts: What is the optimal way to find unique combinations of N sets of integers

texts:
This is a simplification of a real world problem and only a small piece at that.

Example sets are

----------------------       ------------------------------------
| Set1 | Set2 | Set3 |  OR   | Set1 | Set2 | Set3 | Set4 | Set5 |
|--------------------|       |--------------------|--------------
| 1    | 10   | 40   |       | 1    | 1    | 1    | 1    | 1    |
| 2    | 12   | 45   |       | 2    | 2    | 2    | 2    | 2    |
| 3    | 13   | 51   |       | 3    | 3    | 3    | 3    | 3    |
| 4    | 20   | 61   |       | 4    | 4    | 4    | 4    | 4    |
| 5    | 25   | 76   |       | 5    | 5    | 5    | 5    | 5    |
|      | 31   | 78   |       ------------------------------------
|      |      | 81   |
----------------------

Real world constraints are

Up to 12 sets
N numbers in each set
Only care about distinct combinations - (112), (211) and (121) are considered the same.

Example with desired result

----------------------
| Set1 | Set2 | Set3 |
|---------------------
| 1    | 1    | 1    |
| 2    | 2    | 2    |
| 3    | 3    | 3    |
----------------------
Results: [1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]

Generally real world examples tend to either be like the first example where there are a variable number in each set and they are different in each set, or like the second where there are the same items in each set. However there are no hard and fast rules.

A real world example of the latter is 10 sets with 40 values in each. To naively iterate that example would be $1x10^{16}$ iterations.

Are there any optimal algorithms I can implement to find distinct combinations? I am hoping that there is something clever that can be done when there are the same items in different sets, somehow excluding them once certain conditions are met, but i have failed to think of or find one.


texts: R-tree insertion procedure when leaf is full

texts:
I am implementing an R-tree with the quadratic splitting method.

However in most articles I have read there a piece of information that is missing or misleading (or the most probably case, I completely misunderstood something).

R-trees are supposed to be balanced, yet you need to find the node that will increase less in area to insert your new object, and split such node if full. However this can clearly lead to having a very unbalanced tree in depth, as that node can always be on a single branch (say, leftmost in a graph-type representation of the tree).

Should the insertion criteria say " find the node that will increase less in area to insert your new object among those that are not full, [...]" ?

OR can the quadratic splitting method create very unbalanced trees if you are unlucky with new entries? Say if after N insertions all the new insertions are are very localized, e.g. in always fit in the leftmost leaf in the following figure

Or is there something else that I did not understand?


texts: Calculus of constructions, type-in-type and recursion

texts: Does adding type-in-type to the calculus of constructions lead to (general) recursion? Such that one can write the Y combinator.


texts: Amortized analysis of binary counter with increment and resetting operations

texts:
I have a question about a specific amortized accounting algorithm and to be specific the variant with Reset operation.

First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$  because for example going from 100 to 101 would set $\max[A]$ to $-1$ which does not make much sense.

Then, "if max[A] increases place 1 dollar as a credit on a new high-order 1." - when the high-order 1 has been set, 2 coins were given for this operation in increment - one for actually setting the bit to 1 and one for for the future, hence eventual reset to 0 would be covered by it. Why do we need to put yet another coin?


texts: What is the optimal algorithm for finding all sets of overlapping ranges?

texts:
I have a set of (integer) ranges and want to compute the (possibly non-disjoint) set of all subsets of overlapping ranges. The data structure used for the output is not of particular importance to me; if a linked list can be used to reduce the run time, for example, then that's alright with me.

Formal problem

Consider a set of integer ranges $R$. Find the largest set $O = \{ R_i \subset R \}$ where each (non-empty, unique) $R_i$ satisfies $\forall r, r' \in R : r \ \text{overlaps}\ r' \iff r, r' \in R_i$.

What is the algorithm with the lowest known time complexity for solving this problem?


texts: Examples of context-free languages with a non-context-free complements

texts:
Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia: For
$$A = \{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ_0\}\quad\text{and}\quad B = \{\mathtt a^m \mathtt b^n \mathtt c^n;~m, n ∈ ℕ_0\},$$
both $A$ and $B$ are context-free, but their intersection $A ∩ B$ is not. Since context-free languages are closed under unions, they can’t be closed under complementation as well.

However, this only shows that one of the three languages $A$, $B$, and $\overline A \cup \overline B$ is a context-free language with a non-context-free complement, but not for which one of these this is true. So what is it?

Also, is there a minimal and elegant example of a context-free language with a non-context-free complement, maybe over a binary alphabet?


texts: How does the computational complexity of problems depend on the model specifics of a register machine?

texts:
On wikipedia page of register machines it says that all register machines defined appropriately are equivalent to Turing machines but that

  Computational speed is very dependent on the model specifics.

Does this mean that when we say a problem has complexity $O(n^2)$ or is a polynomial time problem, or something like that, this is assuming some specific model of computation? If so, how general is the statement that a problem is in $P$ or in $NP$ or anything like that?


texts: Finding growth of "inter-recursive" functions

texts:
consider following code
int f(int x)
{
  if(x<1) return 1;
  else return f(x-1)+g(x);
}
int g(int x)
{
  if(x<2) return 1;
  else return f(x-1)+g(x/2);
}

Questions:

How do I find the growth of f(x), being that it contains a recursion to another function?
Are growth and time complexity of a a function same thing? Are they the same for f(x)?


texts: Push two symbols to stack at once in a push down automata

texts:
I am pretty new to PDAs and I was solving a problem which asked to design a PDA for the following: $a^n b^{2n}$.

The transitions on the PDAs I've encountered so far have pushed only one symbol onto the stack at any time. Can we push two symbols?
Eg: for every $a$ I encounter I push two symbols.  Thus, the transition will be:

$\Delta(q_0, a,0;000) \to \Delta(q_0)$

where "$a,0;000$" indicates pushing two zeroes onto stack for every $a$ that it encounters.


texts:
I'm learning about computable functions. Our definition for computable function is as follows:

Informally, a computable function is a function f : A → B such
that there is a mechanical procedure for computing the result
f(a) ∈ B for every a ∈ A.

they go on to give the following non-example:

A function that takes an input p (which I assume to be a program), and checks if p is a syntactically valid Python program without any user interaction that terminates and returns 1 if this is true, 0 otherwise.

I was just trying to understand why this is not computable. I know when I write a program with incorrect syntax that I get an error when I try to run it, so I am assuming that it is possible to check whether a program is syntactically correct, but I have a hunch that the terminating part has to do with the halting problem. Is this simply just an obscured halting problem?


texts: Number of path with given length within an unrooted Tree

texts:
Given a Tree (without a root) function w : v -> N and a number C - How can we count the number of verticies with distance between them equal to C.

I was thinking about some smart vertice numbering so we could use dynamic programing to do it but after some thinking it is no good.

I would be really thankful for any tips.


texts:
Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to move wins.

  GG = { : G is a directed graph, b is a node in G, and the next player to play has a winning strategy for generalized geography from start node b, i.e., there are moves for the next player to win no matter how opponent plays }

This problem is well-known to be in PSPACE and EXPTIME-hard. My question is: If we allow repetitions in GG, it still belongs to EXPTIME-hard?


texts: Is L = {  | M is a TM and L(M)={w}} turing recognizable? And its complement?

texts: My approach is to prove that the complement is turing recognizable and undecidable, so that we can prove L not recognizable. But what is the complement of such L?


texts: Batch regularization & L2 regularization

texts:
Is performing batch regularization in addition to L2 regularization redundant?

Batch regularization: http://arxiv.org/abs/1502.03167

Notice how when performing batch regularization, you forgo using a bias term (and instead normalize your layer output, followed by scaling with a 'scale' term, and shifting with a 'beta' term.  I was under the impression that L2 regularization punishes large weights & biases... but if I'm not using biases because of batch regularization, then would I just punish the weights with L2 regularization?

Thanks--


texts: MIS complexity in cubic triangle-free graphs

texts:
The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the question Independent set on cubic triangle-free graphs, it is claimed that a more general problem - maximum independent set in triangle-free cubic graphs (not necessarily planar) - is NP-complete. Could you please provide a reference to the paper for that result?
(Note that the answer to the first of the mentioned questions provides a paper where MIS is shown to be NP-hard in triangle-free planar graphs with vertices of degree <= 3, and I am asking for 3-regular graphs.)
Update: There has appeared a new answer in there since, and it addresses this question as well. The note "NP-complete problems on a 3-connected cubic planar graph and their applications" by Ryuhei Uehara contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.


texts: Is there any model of Game of Life compatible with hypercomputation?

texts:
I found a question in Mathematics Stack Exchange which asks a very similar question

(https://math.stackexchange.com/questions/1023812/hypercomputation-higher-dimensional-variants-of-conways-game-of-life)

It asks whether there are Game of Life models with 3 or more dimensions and if there are Game of Life models related to hypercomputation, but the answers seem to refer to the first question and ignore the second.

So, if I am not wrong, and that is the case, then:

Is there any specific model of Game of Life (Or Cellular Automata in general) that can perform hypercomputation (i.e a Hypercomputational model of Game of Life and/or Cellular Automata)?

And also, Is there any specific model of a hypercomputational Game of Life/Cellular automata that has been applied to physics? That has proposed a cosmological/physical model of the universe based on these Cellular Automata? (Like some sort of Zuse's thesis: https://en.wikipedia.org/wiki/Calculating_Space)


texts: How can I mathematically show the largest possible value of a 64-bit double?

texts: I'm a physics student wondering how I can mathematically show the largest possible value of a 64-bit double. I don't want to know just the answer, since that is freely available. The equation I was shown by a professor says a machine number is represented as $s\times m \times 2^{E-e}$ with $m$ the mantissa and $e$ the bias of the exponent, but I'm not sure how to use this to show the largest possible 64-bit double. The mantissa is 52 bits long and the largest exponent is 2047. The bias is 1023. The largest exponent is reserved for infinity. The leading 1 is not stored.


texts:
Is it in in a deadlocked state?

In this graph, there is a deadlock initially I think. Since P1 is holding R1 and waiting for R2; P2 is holding R2 and waiting for R1 and R3; P3 is holding R3 and waiting for R1.
Or P1 and P2 are also in a cycle. So it is in a deadlocked state. Am I correct to claim that?

If one more instance of resource R1 is added, will it be in a deadlocked state? Explain why? Need to show the graph reduction steps to justify your answer

I think it can if P3 takes R1 so that it releases R1 and R3.
But if P2 takes the newly added R1, it is still waiting for an R3.
In this case, should I say it is still in a deadlocked state?
Also, how to do graph reduction? Any help is appreciated.


texts: When do you use amortized time complexity and when to use unamortized?

texts:
This is my guess:
-Use amortized because we want to know the "averaged" complexity over n operations assuming the operation is going to be used frequently
-Use unamortized when you know the operation is going to be used rarely


texts: Intractable properties of Two-factor in connected bridgeless cubic graphs

texts:
Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that cover $V$. I'm interested in the computational properties of 2-factors in connected bridgeless cubic graphs. I conjecture that every non-trivial property of two-factors in connected bridgeless cubic graphs is intractable.

There are two parameters of two-factor: the number of disjoint cycles and the size of each cycle. So, it seems that restricting cycles sizes and/or the number of cycles in the 2-factor would make the decision problem of deciding the existence of restricted 2-factor is $NP$-complete. For instance, I conjecture the following decision problem is NP-complete: Given connected bridgeless cubic graph, decide whether it contains 2-factor such that cycles sizes are between two integers $n$ and $m$.

Non-trivial property in this context means a restriction on the parameters of  2-factor (in connected bridgeless cubic graph ) which partitions the class of connected bridgeless cubic graphs into two infinite sets. Therefore, there is infinite set of connected bridgeless cubic graphs with their 2-factor satisfying the property and infinite set not satisfying the property. I am aware of several $NP$-complete properties of 2-factors in connected bridgeless cubic graphs. For instance, Deciding the existence of connected 2-factor, even 2-factor, and odd 2-factor are all $NP$-complete problems.

  When does such non-trivial property of 2-factor become $NP-complete? When does it become polynomial-time decidable?

This is an improved version of a post originally posted on TCS SE.


texts: Difference Between Small and Big-step Operational Semantics

texts:
What's the fundamental difference(s) between small and big-step operational semantics?

I'm having a hard time grasping what it is and the motivation for having the two.


texts: Big notation of sigma 4i (from i = 1 to n)

texts:
Why is the big O of this function O(n^2)?

Isn't this just a sum of constant terms? Shouldn't the function be O(1)?


texts: What to do when the information gain on decision trees is 0 for all possible splits?

texts:
I just started studying decisions trees and I am trying to construct a tree for a training set which uses Status as the class label. I am using the misclassification error as measure of impurity. After the first iteration, the information gain indicates that Department should be the tree root. The following table represents the sub-table for Department = Secretary.

I got to this point and I don't know how to add the corresponding nodes to the tree. Should the next node be Age or Salary?

Thanks!


texts: How can a machine with fixed output for all inputs be considered a Turing machine?

texts:
From this answer, and the comments that follow:

To clarify, this machine T′ with the fixed output for all inputs is a Turing machine? – Shashank V M

@ShashankVM, Yes, T′ is a Turing machine. – D.W.♦ (When can a deterministic finite-state-automata (DFSA) along with its input sequence be said to be a part of another DFSA?)

From what I understand, a machine with fixed output for all inputs is a Turing machine.
Consider this thought experiment, I have a "machine" which is a wall with a slit through which I can pass a tape in. The "output" of this machine is on the wall, i.e. it is painted on the wall as a fixed string $S$, which for the purpose of this experiment is "Hello". So no matter what is written on the tape, the output of this "machine" is "Hello". From what I understand this "machine" is a Turing machine.
Is my understanding correct or am I missing something?
Because I find it hard to believe that this wall with a slit can be considered a Turing machine, when a supercomputer is considered a Deterministic Finite State Automaton.
Also I cannot see how this "machine" can emulate any another Turing machine or do any useful computation.


texts: In general, how does a DFA know how to successfully process a string the intended way?

texts:
Suppose we have:
$$A\text{ }\colon=\{x, y, z\}$$
$$M\text{ }\colon=\text{some DFA using A}$$
$$S\text{ }\colon=xyzxyzxyz$$
Intuitively, one might say $S$ is fed to $M$ on a per-character basis.
This means that somehow we have an undisclosed mechanism that can tell where a symbol starts and ends.
One might say, simply use the maximum valid substring similar to how Lexers tokenise plaintext. To that I say, suppose instead that we defined $A$ as:
$$A\text{}\colon= \{x, xx, xxx\}$$
Now we have 3 unique symbols, that, as it so happens, using the maximum valid substring will yield in a restriction to what our our $M$ can actually process, because any string longer than 2 characters will always be assumed to start with $xxx$ rather than perhaps, $x$ and $xx$.
One way I see around this is to actually have a character synonymous to a symbol. That is, $x$ and $xxx$ (from $A$) are both a single character each.
Thoughts?
EDIT
In the case my question is unclear:
The extended transition function is defined so as to extend the processable input of a DFA from simply one alphabetic character at a time, to an arbitrary amount. Usually we go about defining it as follows for a string wa:
$$\hat{δ}(q,w) = δ(\hat{δ}(q, x), a)$$
My issue is: What is converting the input from a string to a partition? Whatever this object may be, it has to follow some lexing rules, does it not?
Are there any conventions that go about this?


texts: Can Floyd-Warshall be used to solve an APSP problem without copying the matrix?

texts:
According to CLRS, each iteration of the outermost loop (on $k$) makes a new copy of the adjacency matrix. Is it safe not to copy the matrix on every iteration?

What I mean is, according to CLRS:

$d_{ij}^K = \min(d_{ij}^{K-1}, d_{ik}^{K-1} + d_{kj}^{K-1})$

Is the following possible?

$d_{ij} = \min(d_{ij}, d_{ik} + d_{kj})$

I have tried not copying the matrix, and got the same result before as the one which makes a copy after each iteration, but did I just get lucky?


texts:
We know $$\mathsf{PP=RP},\mathsf{coPP=coRP},\mathsf{PP=coPP=coRP=RP=ZPP=BPP\subseteq P/poly}$$ are equivalent and the polynomial hierarchy collapses to $2$nd level.

What are the other non-trivial collapses and consequences?


texts: Finding the longest path in an undirected node-weighted tree

texts:
I have a tree where each node is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the sum of the weights of the nodes in the path is maximum). There's no restriction on what node the path starts or ends.

I have a possible algorithm, but I am not sure it works and I am looking for a proof. Here it is:

1)Select an arbitrary node u and run DFS(u) to find the maximum weight simple path that starts at u. Let (u, v) be this path.

2)Run DFS(v) to find the maximum weight simple path that starts at v. Let this path be (v, z).

Then (v, z) is a simple path of maximum weight. This algorithm is linear in the size of the graph. Can anyone tell me if it works, and if so, give a proof?

Note: The Longest Path Problem is NP-Hard for a general graph with cycles. However, I only consider trees here.


texts: How to reconstruct the image from a neural network output?

texts:
I am trying to use the genetic algorithm to optimise a multi-layered neural network for image classification (i am using a subset of the MNIST handwritten digit data set as my initial dataset, but eventually would like to make it more general).

my neural network is represented by connection weight matrices with inputs as the rows an outputs as the columns (so element (3, 4) is the weight of the connection between input 3 and output 4, etc) and have an extra column and row for the biases of the inputs/outputs

the system seems to work well, it takes an input vector, multiplies it by the first layer matrix, uses the sigmoid function to determine whether that neuron will fire or not, then uses the output vector of that as the input to multiply by the 2nd layer and so on to the final layer, and i am getting the results that i expect with test data that i know the expected output for.

i have an idea of how i will implement the genetic algorithm to search for the best solutions, but my problem is that im having a little bit of trouble understanding how neural networks can be used to reconstruct images so i can test for the error between the input image and the reconstruction to test each solution for fitness.

i understand that i need to first encode the image into a vector of pixels, and that that input needs to be passed through the network to the end layer, but i am not sure what that end data is supposed to represent..

the dataset i am using are images of 28*28 pixels, so the structure of my network is as follows (inspired by the Hinton paper here):

484 -> 1000 -> 500 -> 250 -> 30

so the output of the whole thing will be a vector 31 (30 neurons +1 for the bias column/row) elements long

how should i use this vector to reconstruct the image?

i read somewhere that to decode information from a neural network you need to multiply the output by the transpose of the transformation matrix, but that doesnt really make sense as (for example):

T = [ 1  2 ;
      3  4 ]

A = [ 5  6 ]

A * T = [ 23  34 ] = B

B * T' = [ 91  205 ] != A

clearly this is not a very good reconstruction of the original data..

can someone give an explanation as to how neural nets can be used to reconstruct data, and if possible, point me to some good resources on the subject?


texts: How do I arrive at the multiplication function in lambda calculus?

texts:
I'm familiar with how Church numerals are defined in the lambda calculus, i.e. as functions that take two arguments and apply the first argument $n$ times to the second.

Then I have the successor and addition functions, both of which I managed to derive and understand:

$$\begin{align}
\mathrm{succ} &:= \lambda nsz.s (n s z) \\
(+) &:= \lambda nm.n\ succ\ m \\
\end{align} $$

But multiplication is where I'm stuck.

I understand that we can define a multiplication function $(*)$ by adding the number $m$ to $0$ exactly $n$ times. After all, $3 \times 2$ is simply $2 + 2 + 2 + 0$.

So that could mean that $(*)$ looks like this:

$$(*) := \lambda nm.n\ ((+)\ m)\ 0$$

This appears to be a somewhat intuitive definition of a lambda calculus multiplication function to me, and if I try it out with $2$ and $3$, after some messy reductions, the result seems correct and $(*)\,2\,3 \rightarrow 6$.

But then elsewhere I found this definition for multiplication:

$$\mathrm{mult} := \lambda xya.x (y a)$$

Now I don't see how you arrive at this function $\mathrm{mult}$. My definition $(*)$, which takes two arguments, seems intuitive enough to me. But his here, which takes two arguments, one for the $x$ and $y$ respectively, which are the numbers to be multiplied, and then a third one $a$, just seems impenetrable to me—and I cannot figure out why it works, or how you would derive it.

Can somebody help me understand the reasoning and derivation of this $\mathrm{mult}$ function?


texts: Different definitions of Exponential Time Hypothesis

texts:
I am reading basics of Exponential Time Hypothesis (ETH). There are two statements for it:
Statement 1
There exists no $2^{o(n)}$ algorithm for $3$-SAT, where $n$ is the number of variables.
Statement 2
If $\delta_q$ ($q \ge 3$) is the infimum of set of constants $c$ for which there exists an algorithm for solving $q$-SAT (each clause has $\le q$ literals) in time $\mathcal{O}^{\text{*}}(2^{cn})$ (here $\mathcal{O}^{\text{*}}(.)$ supresses any non-exponential part of the running time). Then $\delta_q > 0$.
I can see that if $1$ holds, then so does $2$. But why is it so that $2$ may/may not imply $1$ ?
If $2$ holds then would it be wrong to argue that $\delta_3 > 0$. And as $\delta_{i+1} \ge\delta_i$ ($i \ge 3$), because increasing upper bound on number of literals in each clause can only make the problem more difficult to solve, it will imply $1$.


texts: Identifying an object in an image based on color (AI ?)

texts:
First off, I am not sure if this is the correct stackexchange site to ask this question on, so moderators can feel free to move it.

I am working on an application that identifies an object in an image.  For example, let's say that the object is an apple, and the apple can be green, red, or both.

My plan is to create an array the same size as the image, then scan through the image, pixel by pixel, and if the current pixel is within my range of colors (green-ish or red-ish), add a 1 to the corresponding location in the array, else add a 0.

After this scan through the array, I will have an array of 1s and 0s, which will hopefully contain a concentration of 1s, representing the apple.

I am a computer science student, but have yet to take an AI class.  So my question is:  is this a good way to go about doing this?  Or are there more established AI methods (or algorithms) for identifying objects in an image based on color?

EDIT:  I should clarify that the problem isn't identifying if the image contains an apple, the problem is identifying where the apple is in the image.